# Some Experiments with Low-complexity Orthogonal Matching Pursuit

After writing about low-complexity orthogonal matching pursuit (LoCOMP) a few days ago, I decided to implement and test it starting from my old dissertation code, and furthermore to incorporate some interference adaptation. This task was not as trivial as I first thought, but the end results are interesting. The MATLAB code I used to generate the plots below is here, for those interested in reproducing my research.

Above are four signals of small dimension. These signals have structures that are difficult to efficiently and meaningful decompose over dictionaries with symmetric atoms by greedy pursuits. Today I decomposed these using matching pursuit (MP), OMP, LoCOMP, and OMP with interference adaptation (OMPIA), and LoCOMP with interference adaptation (LoCOMPIA). I used a dictionary of Dirac functions and complex Gabor atoms with the following scales (samples) $$\{1, 4, 8, 16, 32, 64, 128, 256, 512\}$$, with hops (samples) $$\{1, 2, 2, 4, 8, 16, 32, 64, 128\}$$. Thus, this dictionary is ovecomplete, but it is not shift-invariant, unlike that used by Mailhé et al. Another difference is that I am not using MDCT atoms, but complex Gabor to find the best real atoms, à la Gribonval’s subspace method. (See my dissertation for complete details in English; and Gribonval’s in French.)

Seen above are the residual energy decays for the five different decomposition algorithms. In the cases of interference adaptation, $$\gamma \in \{0.5, 0.3, 0.6, 0.1\}$$ for Attack, Bimodal, Sine, and WGN, respectively. These values are hand selected to give the best results. (I am still working on how to select this coefficient automatically.) To calculate the residual energies in the case of LoCOMP, I perform a full orthogonal projection onto the current basis as if it is the final iteration; however, I locally update the residual for selecting the next atom.

In all these signal decompositions, we see that the residual energy decays of OMP and LoCOMP are very similar; and for Bimodal LoCOMP performs better than OMP. When it comes to adding interference adaptation, however, there appears to be a large performance difference for Bimodal and Sine, but not Attack and WGN. (The strange behavior in Sine is due to bad conditioning of the Gramian of the basis matrix… which should not happen, and which I haven’t sorted out yet.) For Attack, we see that the two approaches using inference adaptation have superior efficiency (with respect to differences in residual energy decay) to OMP, and LoCOMP. For Bimodal however, OMPIA performs much better than LoCOMPIA, where the latter has a performance at times worse than MP. This tells me that though the decays of the models built by OMP and LoCOMP are similar, the underlying models are not; and this difference is causing problems when interference comes into play.

Tomorrow I will look at the time and time-frequency atom distribution of each signal model. This way we can see how the models are modeling each signal, and whether these models make sense with respect to the structures in each signal.