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:
- (strong crosspolytope, i.e all k-sparse vector can be recovered with l_1:) \rho_c = 0.0603
- (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.