Phase transitions on Hawaii time

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.



One thought on “Phase transitions on Hawaii time

  1. One of the advantages of AMP over SL0 is that it is incredibly fast for very large vectors.
    So what’s the deal about inhabiting islands ?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s