Image Processing Reference
In-Depth Information
9
Applications of the Orthogonal Matching
Pursuit/ Nonlinear Least Squares Algorithm
to Compressive Sensing Recovery
George C. Valley and T. Justin Shaw
The Aerospace Corporation
United States
1. Introduction
Compressive sensing (CS) has been widely investigated as a method to reduce the sampling
rate needed to obtain accurate measurements of sparse signals (Donoho, 2006; Candes &
Tao, 2006; Baraniuk, 2007; Candes & Wakin, 2008; Loris, 2008; Candes et al., 2011; Duarte &
Baraniuk, 2011). CS depends on mixing a sparse input signal (or image) down in dimension,
digitizing the reduced dimension signal, and recovering the input signal through
optimization algorithms. Two classes of recovery algorithms have been extensively used.
One class is based on finding the sparse target vector with the minimum ell-1 norm that
satisfies the measurement constraint: that is, when the vector is transformed back to the
input signal domain and multiplied by the mixing matrix, it satisfies the reduced dimension
measurement. In the presence of noise, recovery proceeds by minimizing the ell-1 norm plus
a term proportional to ell-2 norm of the measurement constraint (Candes and Wakin, 2008;
Loris, 2008). The second class is based on „greedy“ algorithms such as orthogonal matching
pursuit (Tropp and Gilbert, 2007) and iteratively, finds and removes elements of a discrete
dictionary that are maximally correlated with the measurement.
There is, however, a difficulty in applying these algorithms to CS recovery for a signal that
consists of a few sinusoids of arbitrary frequency (Duarte & Baraniuk, 2010). The standard
discrete Fourier transform (DFT), which one expects to sparsify a time series for the input
signal, yields a sparse result only if the duration of the time series is an integer number of
periods of each of the sinusoids. If there are N time steps in the time window, there are just
N frequencies that are sparse under the DFT; we will refer to these frequencies as being on
the frequency grid for the DFT just as the time samples are on the time grid. To recover
signals that consist of frequencies off the grid, there are several alternative approaches: 1)
decreasing the grid spacing so that more signal frequencies are on the grid by using an
overcomplete dictionary, 2) windowing or apodization to improve sparsity by reducing the
size of the sidelobes in the DFT of a time series for a frequency off the grid, and 3) scanning
the DFT off integer values to find the frequency (Shaw & Valley, 2010). However, none of
these approaches is really practical for obtaining high precision values of the frequency and
amplitude of arbitrary sinusoids. As shown below in Section 6, calculations with time
windows of more than 10,000 time samples become prohibatively slow; windowing distorts
the signal and in many cases, does not improve sparsity enough for CS recovery algorithms
Search WWH ::




Custom Search