Image Processing Reference
In-Depth Information
2. Background
Our method and results rely heavily on work in three well-known areas: orthogonal
matching pursuit, nonlinear least squares and compressive sensing.
2.1 Compressive sensing
In compressive sensing (Donoho, 2006; Candes & Tao, 2006; Baraniuk, 2007), a sparse vector
s of dimension N can be recovered from a measured vector y of dimension M ( M << N ) after
transformation by a sensing matrix  as shown in eq. (1)
y =  s + n (1)
where n is a noise vector. Often,  is factored into two matrices,  =  where  is a
„random” mixing matrix and  is a Hermitian matrix with columns that form a basis in
which the input vector is sparse. A canonical example is the case in which the input is a time
series with samples taken from a single sinusoid with an integer number of periods in the
time window. These data are not sparse but are transformed into a sparse vector by the
discrete Fourier transform (DFT). Note that although  is not square and hence not
invertible,  is both square and invertible. Work in compressive sensing has shown
(Donoho, 2006; Candes & Tao, 2006; Baraniuk, 2007) that under quite general conditions, all
N components of s may be recovered from the much smaller number of measurements of y .
With no noise ( n = 0) recovery proceeds by minimizing the ell-1 norm of a test vector s ' (the
ell-1 norm of s' is given by the sum of the absolute values of the elements of s ' ) subject to the
constraint y =  s '. In the presence of noise, recovery proceeds by minimizing a linear
combination of the ell-1 norm of the target vector and the ell-2 norm of the residual vector
given by y -  s
s '() = argmin s (|| s || 1 + || y -  s || 2 )
(2)
where the parameter  is chosen such that the signal is optimally recovered (Baraniuk, 2007;
Loris, 2008).
2.2 Orthogonal Matching Pursuit method
Orthogonal matching pursuit (OMP) is an alternative method that can be used to find the
target vector s from the measurement vector y . Matching pursuit has a rich history in signal
processing long before CS and has appeared under many names (Mallat & Zhang, 1993; Pati
et al., 1993; Davis et al., 1997). With the advent of CS, many variants of OMP have been
applied to recovery including methods called MOMP, ROMP, CoSaMP, etc. (Needell and
Tropp, 2008; Needell and Vershynin, 2009; Huang and Zhu, 2011) but with one exception
(Jacques and De Vleeschouwer, 2008) discussed below, all of these methods recover
frequencies (or other parameters) from discrete grids.
The basic idea of all matching pursuit algorithms is to minimize a cost function to obtain
frequencies of sinusoids present in the signal. First, take the frequency corresponding to the
smallest value of the cost function and calculate the linear least squares estimate for the
complex amplitude at this frequency. Second, mix this sinusoid with the known CS mixing
matrix  and remove this mixed approximation to the first sinusoid from the CS
measurement vector [ y in eq. (1)]. This process is repeated until a known number of
sinusoids is found or a system-defined threshold is reached. For frequencies not on the DFT
Search WWH ::




Custom Search