While I am on vacation in Hawaii :), I have the time to finish my revision and considerable expansion of my empirical studies of recovery algorithm performance for sparse vectors distributed in various ways. I have updated my arXiv paper, but the paper will not be available until Monday — which I will announce then. Here is an intriguing picture of how the empirical phase transition can change depending on the distribution underlying the sensed sparse signal. Below are the best empirical phase transitions for sparse vectors distributed: Normal (N), Laplacian (L), Uniform (U), Bernoulli (B), Bimodal Gaussian (BG), Bimodal Uniform (BU), Bimodal Rayleigh (BR). My perfect recovery condition is a tough one: find the true support of the signal. (I find the exact recovery condition of Maleki and Donoho to be too forgiving for vectors distributed with densities having large tails and significant density around zero.) My sensing matrix is sampled from the uniform spherical ensemble. The ambient dimension of my signals is 400.
BP and AMP (approximate message passing) perform the same for Bernoulli and bimodal uniform distributions; but AMP takes much less time.
For the other five distributions,
SL0 performs the best at larger indeterminacies (\(\delta > 0.2\)),
and PrOMP performs better for these at smaller indeterminacies.
Like AMP, SL0 is incredibly fast.
From this graph we see the large difference in recoverability from compressive measurements of signals distributed Laplacian and Bernoulli.