Greedy Decomposition of Stationary Signals

Consider decomposing a real sinusoid using matching pursuit (MP), cyclic MP (CMP), or orthogonal MP (OMP) and a dictionary of smooth time-frequency atoms built from, e.g., Hann windows of various scales \(s \in \{ 4, 8, 16, 32, 64, 128, 256 \}\) samples, each skipped by one quarter their scale.
To create an atom we modulate a window of scale \(s\) by complex phasor with a normalized frequency \(\omega \in \{ k/s : k = 0, 1, \ldots, \lfloor s/2 \rfloor + 1\}\).
To be sure we have a complete dictionary we include the Dirac basis.
Real atoms are built from complex atoms by adding their conjugate; and optimal phases are phound by phrojection on the dual atom and its conjugate (if not real).
Now, with that out of the way, it is at first surprising to see the behavior of these three greedy methods. Depending on its frequency and phase, a stationary sinusoid can be decomposed into a mess of atoms, producing a model that lacks sense.

Below we see a little movie (click for better resolution) of the amplitude and modulation frequencies of the first 30 atoms found by MP, CMP, and OMP in the decomposition of a unit amplitude sinusoid. We show the results of five different frequencies, from one that matches exactly one of the modulation frequencies of the largest scale atom, to nearly the next highest modulation frequency in the dictionary at the same scale. In this image, the frequency of the sinusoid is designated by the vertical dashed gray line, and its amplitude is shown by the horizontal dashed gray line. We have a mess of information here, including several atoms having maximum amplitudes that exceed the amplitude of the signal by nearly 60%! That is disturbing! And it is upsetting.

Thumbnail image for []_660a5cad-c40e-a384-1dac-3c8716c27630.gif

Even when we are lucky to have a match between the sinusoid frequency and a modulation frequency in the dictionary we are not so lucky as to have found with any of these methods the “ideal” decomposition into uniformly spaced modulated Hann windows of unit amplitude. (I say this is ideal because for this sinusoid of length 1024 samples, seven Hann windows of scale 256 samples, properly spaced and modulated, will give a signal to residual energy ratio (SRR) of about Inf dB in the support [257,1024-256], whereas any other spacing and modulation will give a smaller value — which I am arguing without any concrete proof other than the constant overlap add property of the Hann window. This should be the same for a triangle window. And a square window without overlap. But here we are talking about smooth windows, like Hann and Gaussian.)
The closest we get to this ideal model (seen below) is by OMP when the sinusoid frequency is a smidgen below one of the modulation frequencies in the dictionary. In this case the SRR (in the support [257,1024-256]) is largest for all methods and frequencies tested, even when the frequencies match. The SNR is smallest for MP (~ 21.6 dB) when the sinusoid frequency is about half way between the two modulation frequencies in the dictionary.

Because it does not correct previous poor choices, MP will never recover the “ideal” model of uniformly spaced modulated Hann windows of unit amplitude. But CMP and OMP review and revise their choices, and I should think they can find a model closer to the “ideal” one than MP. When the sinusoid frequency is about half way in-between the two modulation frequencies in the dictionary CMP gets close (see below);
but the seven large scale atoms have nearly the same large overshoot of the unit amplitude of the sinusoid, which is corrected by the seven smaller-amplitude atoms positioned at the same times. Because it is reviewing and revising one atom at a time, CMP will not be able to overcome its error. We would have to remove one atom and its corrective companion before considering a new atom to replace them.

This brings me to some of my current research: when using dictionaries of smooth atoms can I make an adjustment to the update rules of MP, CMP, and OMP such that overshoots and their subsequent corrections are rare? And can this be done in a way that is not ad hoc, and makes sense for decomposing mixtures of sinusoids, and glockenspiel sounds?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s