# Alternative to Orthogonal Matching Pursuit (OMP) Algorithm

In the Compressed Sensing context, assume there is a signal $x \in {\mathbb{R}}^{n}$ which is $k$ sparse. Namely its Pseudo ${\ell}_{0}$ Norm is ${\left\| x \right\|}_{0} = k$ (The signal has only $k$ non vanishing elements) where $k << n$.

Given a Model Matrix $A \in {\mathbb{R}}^{m \times n}$ the measurements are given by (This is the Model):

$$y = A x$$

The recovery problem is given by:

$$\arg \min_{x} {\left\| A x - y \right\|}_{2}^{2} \; \text{s. t.} \; {\left\| x \right\|}_{0} = k$$

Since the exact solution to the problem above is hard to find the recovery (Estimation) of the signal $x$ from the measurements $y$ is usually done using Orthogonal Matching Pursuit (OMP) Algorithm.

Basically the OMP finds iteratively the elements with highest correlation to the model.

The question is, since the measure of the quality to select indices is based on Correlation, why can't one just find the support using the following:

[vCorrVal vCorrIdx] = sort(A' * Y);
vSignalSupport = vCorrIdx(1:k);


The result is almost the same as that of normal OMP.

• I can't fully follow you; I'm not sure which definition of "iterative decoding" you're using. "select sequence with highest correlation" does sound like "decoding by finding the symbol with highest correlation", which would make iterative decoding the same as matching pursuit if what is symbols in decoding is atoms in MP. Feb 7, 2017 at 12:28
• Thanks for your reply. I am asking about the OMP algorithm. In which we find the support by selecting the column of the sensing matrix (A) which has maximum correlation with the received signal (Y). E.g Res=Y; [val ind]= max(<A' * Res>). We select the support as ind. Support=[support ind]; Then we update the residual(Res) and run the algorithm until K (sparsity) times or some other stopping criteria. My question is why we don't select the maximum K indices. Like [val ind]= sort(<A' * Y>,2); and then find the Support=ind(1:K); ... Feb 7, 2017 at 13:10
• Edit your question to include that info. Use proper Latex/Mathjax to express your formulas! Feb 7, 2017 at 16:31
• So, what do you think "use the $K$ maximum correlation columns" is, rather than multiple iterations of the "find the maximum correlation" algorithms?! Feb 7, 2017 at 17:06
• I see no update in the last 16h; no, in OMP you don't have to update the residual. That's the point about O in OMP. Feb 8, 2017 at 9:20

The main advantage of OMP is that the residual is orthogonal to the current solution.

Let's say you select all $k$ columns from $A$ (also called atoms) at once and let us also presume that $A$ is an overcomplete basis (this is more or less the standard in OMP literature).

Now, with your method, if the atom that correlates the most with your measurements $y$ is linear-dependent with $p < k$ other atoms in $A$ you will end-up with an $k-p$-sparse signal, because $p$ entries will be more or less redundant. The same argument can of course be extended to less correlated atoms. You might also be lucky and never see the phenomenon.

Let's take the same example but with OMP this time. During the first iteration you would select the atom that correlates the most with measurements $y$. After that you compute the coefficient in $x$ such that the new residual is orthogonal to the current measurements approximation. In other words you got the most of the information provided by the currently selected atom so during the next iteration you are very likely to pick an atom that contains fresh information (ask yourself what would happen with linear dependent atoms in this case).

Here is a list of atom selection look-ahead strategies based on OMP and OLS that you might find interesting to read: POMP, LAOLS and POLS.

What you propose is actually being used in other algorithms. Your proposal corresponds to the first step of iterative hard thresholding. After the first step, the residual is updated, correlation repeated, and the correlation result added to the signal estimate before thresholding again. This is repeated until convergence is reached in some sense (Iterative Hard Thresholding for Compressed Sensing). One can also update the estimate in a way more similar to OMP; then it corresponds to hard thresholding pursuit (Hard Thresholding Pursuit: An Algorithm For Compressive Sensing).

The principle (of identifying many support index candidates in each iteration) is also seen in the two-step thresholding algorithms such as CoSaMP (CoSaMP: Iterative Signal Recovery From Incomplete and Inaccurate Samples) and subspace pursuit (Subspace Pursuit for Compressive Sensing Signal Reconstruction).

All of these algorithms have in common that they all run several iterations of "correlating" the signal with the "model" and updating the residual accordingly, because it improves the estimate.