Image Processing Reference
In-Depth Information
There are two methods to handle the case where the actual number of sinusoids present is
unknown, yet still smaller than K . The simpler method, applicable for high SNR ( small
compared to the smallest signal amplitude), is to perform K iterations of the OMP/NLS
algorithm, which will incur an additional noise folding penalty, by projecting the additional
noise dimensions onto the solution. The second method is to stop when the residual can be
explained by noise alone though hypothesis testing. At the solution, the weighted squared
residual r H k W r k will display a -squared statistic with 2 k degrees of freedom, where k is the
actual number of sinusoids present in the signal. The hypothesis that the residual is caused by
noise alone, is accepted when r k H Wr k < 2 T for some threshold T and rejected otherwise. The
value for T is dependent on a user selectable significance level, the probability of incorrectly
rejecting the given hypothesis. For a significance level of , T = CDF -1 (1-), where CDF is the
cumulative distribution function of the chi-squared distribution with 2 k degrees of freedom.
We used  = 0.05 in our simulations, but  is an application-specific parameter.
4. Results for sparse sinusoids without noise
4.1 Signal composed of a single sinusoid
Consider first a signal of the form given by eq. (4) with K = 1, f 1 = 0.44681715350529533 and
a 1 = 0.8018794857541801. Fig. 1 shows a plot of G ( f , y ) for N = 1024, M = 4. Finding the
argmax of G ( f , y ) evaluated for 32,768 frequencies between f min and f max ( N f = 32) yields an
initial value for the frequency and amplitude of f 1 = 0.446808 and a 1 = 0.801070+0.026421i.
Minimization of R [{ x(f 1 )}] starting at f 1 = 0.446808 yields a final value f 1 equal to the input
frequency f 1 with error less than 1x10 -16 (machine precision) and the amplitude a 1 through
A [{ x( f 1 )}] equal to the input amplitude with error less than 4x10 -16 .
Fig. 1. G ( f , y ) as a function of frequency for a signal composed of a single sinusoid mixed
with N = 1024x4. Note the appearance of a single strong peak in the estimator that serves as
an excellent starting value for minimizing the functional R ( f ) given in eq. (13).
4.2 Signal composed of a 20 sinusoids
The algorithm also works for multiple frequencies. More than 20 independent tests were
performed for an input signal composed of 20 independent frequencies randomly chosen
between 0 and 1; all frequency components have amplitude of 1. In all tests our algorithm
recovered the 20 frequencies to machine precision with a 128x1024 mixing matrix. For test 1,
Search WWH ::




Custom Search