Another Surprise in the Donoho-Tanner Phase Transition ?

[Update 2: Don't read this entry. It is wrong. Like Google Instant, I get to screw up real time, very publicly and with no net. Oh well :-)]

[Update: I think part of the answer stems from the use of sparsity fraction in the y-axis where sparsity is divided by the number of measurements not the number of samples. Increasing the number of measurements, decreases the sparsity fraction] 

The Donoho-Tanner phase transition for space recovery is an important milestone. There are still some details that need to be cleared up in my mind. For instance, I have seen a paper a while back (that for reasons I cannot find again) that showed a slightly different line for the phase transition. As I was completing the phase transition page, I came across a presentation by Victoria Stodden [1] (Model Selection with Many More Variables than Observations) that connected back to this other result I had seen somewhere else. We all know by now the following figure (and it's connection to P vs NP)

But here is the graph that was a little surprising to me:

What's surprising you say ? well the fact that with very few measurements, high noise, a sparse signal can be found with an l_1 approach.

My intuition would have been that with a sizable amount of measurements, high noise, a  sparse solution could be found but no, this is not the case. So to summarize:

Below a certain (very small) number of measurements, the recovery of a sparse signal is possible provided enough noise but there is a limit in the number of measurements above which an l_1 recovery of that sparse solution will be precluded (because it is combinatorial).

One can always hope that the combinatorial solution near the phase transition has very low constants in the exponent.

Any comments are welcome.

Reference:

[1] Breakdown Point of Model Selection when the Number of Variables Exceeds the Number of Observations, Victoria Stodden,  David L. Donoho