CS: Remarks on Bob's exploration of the failings of OMP and l_1 Minimization

Bob continues his open investigation with today a specific emphasis on Exploring the Failings of OMP and l_1 Minimization.On the Donoho-Tanner phase transition diagram, his investigation lies at \delta =0.2 (=50/250). From the good folks in Edinburgh, running this number to find the transition point that correspond to this \delta, we find:

1. (strong crosspolytope, i.e all k-sparse vector can be recovered with l_1:)  \rho_c = 0.0603
2. (weak crosspolytope i.e most k-sparse vectors can be recovered with l_1:) \rho_c = 0.24

Bob uses a rho = 0.22 (11/50), clearly very close to the point where most k-sparse vectors will not be recovered by l_1.

Here are some remarks that may or may not be relevant to what he is investigating:

• All l_1 recovery algorithms are not behaving the same way. Few authors uses the proprietary code Mosek to get to these phase transitions.
• My best and cheap alternatives to Mosek has been SL0, it might be interesting to try it out. 
• Does feeding the solution of the l_1 failure to the greedy algo change the outcome of this study (i.e. less failures)
• What about trying Threshold ISD, a reweighted algorithm that throws out the wrong measurements
• None of these remarks help in giving a sense of the failure of the other algorithms
• Others ? tell Bob about them.