# New version of “Sparse Vector Distributions and Recovery from Compressed Sensing”

You can read all about it here: http://arxiv.org/abs/1103.6246. Here is the abstract:

It is well known that the performance of sparse vector recovery algorithms from
compressive measurements can depend on the distribution
underlying the non-zero elements of a sparse vector.
However, the magnitudes of these effects has yet to be explored,
and formally presented.
In this paper, I empirically investigate this dependence
for seven distributions and fifteen recovery algorithms.
The two morals of this work are:
1) any judgment of the recovery performance of one algorithm
over that of another must be prefaced by the conditions
for which this is observed to be true,
including sparse vector distributions,
and the criterion for exact recovery;
and 2) a recovery algorithm must be selected carefully based on
what distribution one expects to underlie the sensed sparse signal.

In the paper I have an interesting analysis of the criterion for exact recovery. Maleki and Donoho use the following criterion:
$$\frac{|| \vx – \hat \vx||_2}{||\vx||_2} \le 0.01.$$
This is fine for sparse vectors with components distributed Bernoulli in $$\{-1,1\}$$, but not for vectors distributed in ways with a high concentration of probability density centered on zero. It turns out this gives unfair advantages to some algorithms (e.g., GPSR) over others (e.g., SL0). Below is a graphic of the most egregious differences I find.

At each indeterminacy, I am taking the difference between the phase transition of the most strict recovery condition, i.e., the exact support is recovered, to the less strict one above. So I am subtracting the $$\rho$$ of one from the $$\rho$$ of the other. Since recovering the support includes meeting the condition above, this difference will be at maximum 0.
I find non-zero differences for only these four distributions (not for Bernoulli, bimodal uniform, or bimodal Gaussian), and only these five algorithms (out of the fifteen I test).
We see that the phase transition of GPSR is extremely high under the less strict condition than when looking at support recovery, especially for Laplacian and Normally distributed sparse vectors. ALPS and StOMP are also similarly overrated. I haven’t had time to completely see why this is a the case, but I have a feeling that it is because GPSR and ALPS are really good at estimating the large non-zero elements at the expense of forgetting the smaller components.

This shows that one must be careful when comparing algorithms recovering sparse vectors from different distributions with a single condition for exact recovery.
In my previous version of this paper, I made that very mistake,
which inflated the recovery results for some algorithms for sparse vectors distributed Normal, Laplacian, and Uniform.
That version did not include GPSR, ALPS, or StOMP; but I am glad that I thought about it.
In the current version, I use only the hardest of all criteria: exact recovery of the support, which in the noiseless case is the whole kit and kaboodle.

Of course, it is plainly obvious that the performance of a recovery algorithm depends upon the condition for exact recovery; but what I have yet to see in the literature is such a formal treatment of how that condition itself can depend on the distribution of the sparse vector, and thereby influence one’s judgment of algorithm performance.