On the Use of OMP Algorithm to Estimate Sparse Vector
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 &lt; {\rm spark}(\Phi) \leq M+1$, when $\Phi$ is $M \times N$ (so that $x$ is $N\times 1$), i.e., $K&lt;M/2$ 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&lt;M-1$).

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&lt;N$. 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 &lt; N = 16$.