CS: Compressed Sensing: How Sharp is the RIP ?, Blogroll redux.

Following the slides for "Testing the Nullspace Property using Semidefinite Programming" by Alexandre d'Aspremont, Francis Bach, Laurent El Ghaoui featured yesterday which highlight that the Null Space Property is weaker than RIP , Jeffrey D. Blanchard, Coralia Cartis, and Jared Tanner asked themselves and answered the question: Compressed Sensing: How Sharp is the RIP ? . The abstract reads:

Consider a measurement matrix A of size n×N, with n \lt N, y a signal in RN, and b = Ay the observed measurement of the vector y. From knowledge of (b,A), compressed sensing seeks to recover the k-sparse x, k \lt n, which minimizes ||b − Ax||. Using various methods of analysis — convex polytopes, geometric functional analysis, and the restricted isometry property (RIP) — it has been proven that x can be reconstructed via l_q-regularization (q element of (0, 1]) provided A satisfies conditions dictated by the method of analysis. This article focuses on the RIP approach and A with entries drawn i.i.d. from the Gaussian distribution N(0, 1/pn), developing more precise bounds on the restricted isometry constants, and using these bounds in an asymmetric RIP formulation to quantify the region of ( n N , k n ) in which RIP implies that `q-regularization will typically recover all k-sparse signals. Letting n N !  and k n !  as n ! 1, the aforementioned recoverability region is characterized by all  \lt (1 − )RIP S (; q) for any \gt 0, where RIP S (; q) is a lower bound of the true phase transition below which l_q-regularization will typically recover all k-sparse signals. This phase transition framework, proposed in this context by Donoho (2005), is applied to compressed sensing results obtained by the analysis techniques of centro-symmetric polytope theory (Donoho), geometric functional analysis (Rudelson and Vershynin), and the RIP (Cand`es, Romberg and Tao; Foucart and Lai; Chartrand). Recasting the results from different methods of analysis into a common phase transition framework allows for the direct comparison of the efficacy of the respective results.

I need to understand how the null space property being a necessary and sufficient condition for sparse recovery can be weaker than a sufficient condition based on the RIP. Maybe this is the case for RIP-2 ?

Laurent Jacques mentioned a possible collision of notations in the comment section of this entry:

I noticed also that Rick Chartrand and Valentina Staneva, in

"Restricted isometry properties and nonconvex compressive sensing", Inverse Problems, vol. 24, no. 035020, pp. 1--14, 2008

introduced also a RIP_p definition, with an existence proof for Gaussian matrices, but .... for 0 \lt p \le 1

In conclusion, the RIP_p makes sense for p in R^* now ;-)

Following the latest entry on the subject, here are two blogs I will be adding to my blogroll:

• The polylog blog of Andrew McGregor
• The Natural Language Processing Blog of Hal Daume III

Image Credit: NASA/JPL/Space Science Institute, Saturn's rings as seen by Cassini the day before yesterday.