### Technical Report ERGO 09-005

#### Compressed sensing: how sharp is the restricted isometry property?

*Jeffrey D. Blanchard, Coralia Cartis and Jared Tanner*

##### Abstract:

Consider a measurement matrix A of size n x N, with n < 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 < 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 with A with entries drawn i.i.d. from the
Gaussian distribution N(0, 1 /√ 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 → ∞, the aforementioned recoverability region is
characterized by all ρ < (1 - ε)ρ^{RIP}(δ ; q)
for any ε > 0, where ρ^{RIP}(δ ; 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ès, 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.

##### Keywords:

Compressed sensing, sparsity, sparse approximation, sparse solutions to underdetermined systems, restricted isometry property, restricted isometry constants, phase transitions, convex relaxation, random matrices, Gaussian matrices, Wishart matrices, singular values of random matrices, eigenvalues of random matrices

##### Download:

ERGO-09-005.pdf

##### Status:

Published in *SIAM Review*.