Optimization Online


Compressed Sensing: How sharp is the RIP?

Jeffrey Blanchard(jeff***at***math.grinnell.edu)
Coralia Cartis(coralia.cartis***at***ed.ac.uk)
Jared Tanner(jared.tanner***at***ed.ac.uk)

Abstract: Consider a measurement matrix A of size nN, 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 (q 2 (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, 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 -->\delta and k/n --> \rho as n grows to infinity, the aforementioned recoverability region is characterized by all  \rho< (1-\epsilon)\rho_S for any  \epsilon > 0, where \rho_S 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.

Keywords: Compressed sensing, sparse approximation, restricted isometry property, phase transitions

Category 1: Applications -- Science and Engineering

Citation: Technical Report, School of Mathematics, University of Edinburgh, 2009

Download: [PDF]

Entry Submitted: 08/28/2009
Entry Accepted: 08/28/2009
Entry Last Modified: 08/28/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society