Image Processing Reference
In-Depth Information
to work; scanning the DFT off integer values requires performing the CS recovery algorithm
over and over again with an unknown sparse transform and becomes prohibitively
expensive when the number of sinusoids in the signal exceeds 1.
Here we present a new approach to recovering sparse signals to arbitrary accuracy when the
parameters of the signal do not lie on a grid and the sparsifying transform is unknown. Our
approach is based on orthogonal matching pursuit (OMP), which has been applied to
recovering CS signals by many authors (Donoho et al., 2006; Tropp and Gilbert, 2007; Liu
and Temlyakov, 2010; Huang and Zhu, 2011). The major difference between our work and
previous work is that we add a nonlinear least squares (NLS) step to each OMP iteration. In
the first iteration of conventional OMP applied to finding sinusoids, one finds the frequency
that maximizes the correlation between the measurement matrix evaluated on an
overcomplete dictionary and the CS measurement, solves a linear least squares problem to
find the best estimate of the amplitude of the sinusoid at this frequency, and subtracts this
sinusoid multiplied by the measurement matrix from the CS measurement. In the second
iteration, one finds the frequency that maximizes the correlation between the measurement
matrix and the residual measurement, solves a least squares problem for both frequencies to
get new estimates of both amplitudes, and subtracts the sum of the two sinusoids multiplied
by the measurement matrix from the previous residual. This process is described in detail in
„Algorithm 3 (OMP for Signal Recovery)“ in the paper by Tropp and Gilbert (2007) and in
our Table 1 in Section 3. Our approach proceeds in the same way as conventional OMP but
we substitute a
Nonlinear Least Squares
step for the linear least squares step. In the NLS
step, we use a minimizer to find better values for the frequencies without reference to a
discrete grid. Because the amplitudes are extremely sensitive to the accuracy of the
frequencies, this leads to a much better value for the amplitudes and thus to a much more
accurate expansion of the input signal. Just as in conventional OMP, we continue our
algorithm until a system level threshold in the residual is reached or until a known number
of sinusoids is extracted. A related procedure for matching pursuit but not yet applied to
compressive sensing or orthogonal matching pursuit is described by Jacques & De
Vleeschouwer (2008). What we refer to as the NLS step appears in their Section V, eq. (P.2).
Our approach to CS recovery differs from most methods presented to date in that we
assume our signal (or image) is sparse in some model as opposed to sparse under some
transform. Of course, for every sparse model there is some sparsifying transform, but it may
be easier in some problems to find the model as opposed to the transform. Models
inevitably involve parameters, and in most cases of practical interest, these parameters do
not lie on a discrete grid or lie on a grid that is too large for efficient discrete processing
techniques (see the discussion in Section 1 of Jacques & De Vleeschouwer, 2008). For
instance, to recover the frequency of a sinusoid between 0 and 1 to precision of 10
-16
would
require 10
16
grid points. While we first developed our method to find the frequency and
amplitude of sinusoids, like OMP it is readily adaptable to signals that are the superposition
of a wide range of other models. In Section 2, we present background material on the OMP,
NLS and CS methods on which our method is based. In Section 3, we develop the model-
based OMP/NLS formulation. Sections 4 and 5 contains the application to signals that
consist of a sum of a small number of sinusoids. Section 6 compares performance of our
algorithm to conventional OMP using a linear least square step and to penalized ell-1 norm
methods.
