# On the Use of OMP Algorithm to Estimate Sparse Vector

As known, Orthogonal Matching Pursuit (OMP) Algorithm is to recover the sparse channel after convolution with another vector. But when I implement that in MATLAB, I don't get the sparse vector correctly. I provided below a simple example of multiplication of sparse vector with a matrix and then I tried to get back the sparse vector, but I don't get the correct results. Could you please guide me how to correct that. Below is my example code:

   clear all; clc; clear;

h = [1 0 0 1 0 1 1 0];    %Sparse channel
V = randn(8,8);           %Matrix
Yy = V*h.';

h_esti=OMP(Yy,V,4);             %Perform OMP algorithm


Regarding the OMP function, it's related to the algorithm of OMP as here OMP

NP: The above code gives sometimes the exact results of the sparse vector but it's not always. !! I don't know why that, maybe matrix V must have special conditions or something wrong in my code.

## 1 Answer

Well, in your example, the channel isn't exactly sparse.

It has been shown that $$\ell_0$$ minimization can recover any $$K$$-sparse vector $$x$$ from observations $$\Phi x$$ as long as $$2K < {\rm spark}(\Phi) \leq M+1$$, when $$\Phi$$ is $$M \times N$$ (so that $$x$$ is $$N\times 1$$), i.e., $$K more or less. This is a necessary condition which means that if $$K$$ exceeds $$M/2$$ it can be shown that there is no unique solution anymore (sidenote: for an MMV problem, i.e., if you have multiple snapshots, this condition can be relaxed to $$K).

The example you picked has $$M=N=8$$ and $$K=4$$. This means that you are operating right at the limit of $$K=M/2$$. To have an $$\ell_0$$ algorithm perform well, you would want to have $$K$$ a bit below this limit, even more so if you choose a heuristic one like OMP. Try $$K=2$$ or $$3$$ or increase $$M$$ and $$N$$ a bit, it should work better.

Further notes:

• Results like these are typically asymptotic in $$M$$ and $$N$$ and tend to become tight only as $$M$$ and $$N$$ are somewhat larger. Performance for small-scale systems is much harder to analyze.
• OMP is a sub-optimal technique. It is quite sensitive to correlations in the measurement matrix $$\Phi$$. For $$M=N$$, your could use orth(randn(n,n)) to make $$\Phi$$ orthonormal. OMP would appreciate that.
• As you asked whether there are conditions on the matrix $$\Phi$$. Yes, there are. It should satisfy the restricted isometry condition (RIC). If you draw it randomly, chances are high that it does, even more so the bigger it is (see first point).

*edit: Regarding your comment: yes, OMP is just not such a great algorithm. And your randn design is also not the greatest. Success rates for M=8, N=8 with your design (empirical): K=1: 100%, K=2: ~88%, K=3: ~65%, K=4: ~45%. If you use orth(randn(n,n)) instead, you should see 100% (though in this case you wouldn't need OMP). Going from 8 to 16 also improves things. The truly interesting case for sparse signal recovery is $$M. Here you can make $$\Phi$$ at least row-orthogonal to help OMP a little. Normalizing columns would be another good idea.

*edit2: To emphasize more clearly what I said above, here is a numerical example varying $$K$$ and showing the empirical success rate. Comparing pure random Gaussian design (red line) to one where the rows are made orthogonal to each other (blue line). It helps. Note that here $$M=8 < N = 16$$. • Thank you for your feedback, but even when I make $K=3$ or $K=2$, I don't get the exact solution – Gze Mar 3 '20 at 15:11
• You're welcome, glad it helped. I made a short edit regarding the empirical success rates for $K=2,3$. – Florian Mar 3 '20 at 15:48
• that's really appreciated ! By the way I used also $l_{1}$ minimization, it gives 100% for all $K = 1,2,3,4$. That's really interesting. – Gze Mar 4 '20 at 6:55
• Nice answer! +1. Could you say what's MMV in your answer? I am not familiar with that acronym. – Royi Mar 4 '20 at 7:01
• Oh sorry, what I meant with MMV is the multiple measurement vector case, i.e. the setting $Y=\Psi X$ where $X$ has $T$ linearly independent columns and is row-sparse so that all but $K$ of its rows are entirely zero. – Florian Mar 4 '20 at 7:32