CS: The Restricted Isometry Property and l_q-Regularization: Phase transition for Sparse Approximation, Decay Properties of RIC

Here are two much expected analyses,I am sure I'll come back to these later:

The Restricted Isometry Property and l_q-Regularization: Phase transition for Sparse Approximation by Jeffery Blanchard, Coralia Cartis, and Jared Tanner. The abstract reads:

Consider a measurement matrix A of size n×N, with n less than N, y a signal in R^N, 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 less than 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/sqrt(n)), 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 l_q-regularization will typically recover all k-sparse signals. Letting n/N go to \delta and k/n go to \rho as n go to \infinity, the aforementioned recoverability region is characterized by all \rho lss than < (1 − \epsilon)rho^RIP_S (\delta; q) for any epsilon above 0, where rho^RIP_S (\delta; 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 (Candes, 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.

and Decay Properties of Restricted Isometry Constants by Jeffery Blanchard, Coralia Cartis, and Jared Tanner. The abstact reads:

The restricted isometry property (RIP) is an important technique of analysis in sparse approximation. Many sparse approximation algorithms accurately capture the sparsest solution provided the restricted isometry constants satisfy certain bounds. There are no known sufficiently large deterministic matrices that satisfy the desired RIP bounds; however, many random matrix ensembles satisfy RIP bounds with high probability on the draw of the matrix. Here we construct matrices whose RIP constants behave in a markedly different fashion from those of classical random matrix ensembles. In particular, the RIP constants can satisfy desirable bounds and also take on values in a narrow range.

Image Credit: NASA/JPL/Space Science Institute, image of Saturn taken on January 23, 2009