Monday, December 13, 2010

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.

4 comments:

Alejandro Weinstein said...

"All l_1 recovery algorithms are not behaving the same way. Few authors uses the proprietary code Mosek to get to these phase transitions."

Why using Mosek may change the results? I thought that Mosek is just one (very fast) solver, but other than the execution time, it should produce the same results as CVX or any other solver.

Igor said...

Alejandro,

I would love to have somebody show me that they are indeed giving the same results. I am not being sarcastic here.

Cheers,

Igor

Alejandro Weinstein said...

But, as far as the solution to the optimization problem is unique, shouldn't all the solver gives you the same solution up to the numerical tolerance?

I've tried solving a BP problem with CVX and l1_magic, and they produce essentially the same results. And if you look at Bob's experiments, the first thing he tried was to replace CVX by the linprog solver, getting the same results.

Am I missing something here?

Igor said...

Alejandro,

No. You are probably not missing anything. Thanks for the information.

Cheers,

Igor.

Printfriendly