# So, $$\ell_1$$ minimization works fine, but greedy methods perform much better for certain sparse signals?

I have spent the past week studying the performance of various greedy algorithms in recovering sparse signals from compressive measurements, with most interest in that of cyclic matching pursuit, and cyclic orthogonal least squares. Then I looked at the performance of relaxing the strict sparsity criterion with the $$\ell_1$$ norm, the principle known as Basis Pursuit (BP). It appeared that BP performs much worse than all the others — which was strange to me because with a sensing matrix of size 50 x 250, its coherence seems to me to preclude greedy methods from performing any good at all. Thinking it was some result of using CVX for solving the convex problem, I used MATLAB’s linear program function, and found that BP is still underperforming the greedy methods.

Then, a commenter (thank you Alejandro!) took my code and substituted Elad’s sparse signal construction for mine and found the expected result: BP outperforms greedy approaches. We can see below that only when the sparsity of the sensed signal is over 8/50, then reconstruction by BP begins to fail, while all the greedy approaches begin to fail after 5/50. But actually, comparing the BP performance seen below to that of my previous study, we see its performance hasn’t changed, but rather the performances of the greedy approaches became worse.

So what is the difference between the sparse signals that has caused these differences?
Apparently, it is a magnitude thing. Before, I generated the signals like so:

activelements = randperm(N);
x(activelements(1:K)) = randn(K,1);
x = x./sqrt(x’*x);
y = Phi*x;

where N is 250, K is the sparsity, and Phi is the $$50 \times 250$$ sensing matrix.
These sparse signals apparently make greedy recovery methods way out-shine the more complex and sophisticated approach using convex relaxation.

activelements = randperm(N);
x(activelements(1:K)) = sign(randn(K,1)).*(1+rand(K,1));
x = x./sqrt(x’*x);
y = Phi*x;

The difference is embiggened and emboldened.
All the non-zero elements in Elad’s sparse signals have a magnitude uniformly distributed in $$[1,2]$$ (before normalization),
whereas in my original approach I created sparse signals with non-zero elements having amplitudes distributed standard normal (before normalization).
This is entirely confusing to me.
Why should greedy methods work better than $$\ell_1$$ minimization when entries are distributed normally?