Alternative to Orthogonal Matching Pursuit (OMP) Algorithm

Question

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.

Answer 1

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.

Answer 2

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.