Image Processing Reference
In-Depth Information
grid of the time series, OMP can be improved by evaluating the cost function on an
overcomplete dictionary (Candes et al. 2011), but as in the ell-1 estimates discussed above,
this step becomes computationally intractable long before machine precision can be
obtained for arbitrary frequencies.
2.3 Nonlinear Least Squares method
Here we follow the development of nonlinear least squares (NLS) given by Stoica and
Moses (1997). Their eq. (4.3.1) defines a cost function to be minimized as a function of the
vectors
f
() =
t
|
y
(
t
) -
k
k
exp[i(
k
t
+
k
)]
|
2
(3)
where the sums are over the number of sinusoids present in the signal,
k
= 1 to
K
and the
time points run from
t
= 0 to
N
-1. Stoica and Moses also show (see their eqs. 4.3.2-4.3.8), that
the frequency vector is the critical unknown and the amplitude and phase (or complex
amplitude) are simply „nuisance“ parameters that are obtained from . While eq. (3)
appears to require simultaneous solution for three real vectors, each of length K, Stoica and
Moses (eqs. 4.3.2-4.3.8) show that the problem can be reduced to solving for just the
frequency vector and that the complex amplitude vector can be calculated directly from
the frequency vector. We use a version of these equations below in eqs. (8) and (13).
In principle, solution of the CS analog of eq. (3) could be performed to directly obtain the
parameters of a sparse signal, but in practice, direct solution of eq. (3) is not computationally
practical (Stoica and Moses, 1997). The difficulty is that even for a small
K
, eq. (3) is highly
multimodal (see for example, Fig. 1 in Li et al., 2000) and the solution requires extremely
good first guesses for the vector . Even with good initial values for , performance
guarantees are difficult to find and continue to be the subject of intense investigation (Salzo
and Villa, 2011 and references therein).
Similar two-step model-based approaches to estimating the frequency and amplitude of real
and complex sinusoids have been discussed previously in the literature (Stoica et al., 2000:
Li et al., 2000; Chan and So, 2004; Christensen and Jensen, 2006). Stoica et al. discuss the use
of NLS to obtain the amplitude for complex sinusoidal signals given the frequency; Li et al.
and Chan and So discuss a combined matching pursuit NLS approach similar to ours for
obtaining the frequencies of complex and real harmonic sinusoidal signals, respectively; and
Christensen and Jensen use matching pursuit plus NLS to estimate frequencies in a signal
that is the sum of arbitrary frequency real sinusoids. To the best of our knowledge, our
paper is the first application of an OMP/NLS algorithm to estimate the frequency and
amplitude from CS measurements.
3. Formulation of OMP with an NLS step for CS
3.1 Mathematical development
Consider a continuous time signal
X
(
t
) consisting of
K
complex sinusoids of the form
(4)
where
a
k
is the complex valued amplitude and
f
k
is the real valued frequency of the
k
th
sinusoid. This signal model is broadly applicable [see Duarte and Baraniuk (2010) and
