Compressed sensing: how sharp is the restricted isometry property?

DOI10.1137/090748160MaRDI QIDQ3084491zbMATH OpenOpenAlexFDO

Authors Jeffrey D. Blanchard, Coralia Cartis, Jared Tanner

Publication date 25 March 2011

Published in SIAM Review (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.5026

zbMATH Keywords

compressed sensingconvex relationdata compressioneigenvalues of random matricesGaussian matricesphase transitionrestricted isometrysparse approximation

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Large deviations (60F10) Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Abstract: Compressed Sensing (CS) seeks to recover an unknown vector with $N$ entries by making far fewer than $N$ measurements; it posits that the number of compressed sensing measurements should be comparable to the information content of the vector, not simply $N$. CS combines the important task of compression directly with the measurement task. Since its introduction in 2004 there have been hundreds of manuscripts on CS, a large fraction of which develop algorithms to recover a signal from its compressed measurements. Because of the paradoxical nature of CS -- exact reconstruction from seemingly undersampled measurements -- it is crucial for acceptance of an algorithm that rigorous analyses verify the degree of undersampling the algorithm permits. The Restricted Isometry Property (RIP) has become the dominant tool used for the analysis in such cases. We present here an asymmetric form of RIP which gives tighter bounds than the usual symmetric one. We give the best known bounds on the RIP constants for matrices from the Gaussian ensemble. Our derivations illustrate the way in which the combinatorial nature of CS is controlled. Our quantitative bounds on the RIP allow precise statements as to how aggressively a signal can be undersampled, the essential question for practitioners. We also document the extent to which RIP gives precise information about the true performance limits of CS, by comparing with approaches from high-dimensional geometry.

Recommendations

• The restricted isometry property and its implications for compressed sensing
• A generalization of the restricted isometry property and applications to compressed sensing
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Restricted isometry properties and nonconvex compressive sensing
• Restricted isometries for partial random circulant matrices

Cited in

(50)

• A simple proof of the restricted isometry property for random matrices
• Statistical properties of SNR for compressed measurements
• Sparse total least squares: analysis and greedy algorithms
• LASSO risk and phase transition under dependence
• Hierarchical isometry properties of hierarchical measurements
• Bias versus non-convexity in compressed sensing
• A numerical exploration of compressed sampling recovery
• Uniform recovery from subgaussian multi-sensor measurements
• Packing bounds for outer products with applications to compressive sensing
• Optimal D-RIP bounds in compressed sensing
• On edge connectivity and parity factor
• Compressive sensing and algebraic coding: connections and challenges
• Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
• RIPless compressed sensing from anisotropic measurements
• A provably convergent scheme for compressive sensing under random generative priors
• The geometry of off-the-grid compressed sensing
• On the sparsity of Lasso minimizers in sparse data recovery
• A generalization of the restricted isometry property and applications to compressed sensing
• Performance comparisons of greedy algorithms in compressed sensing.
• Deterministic bounds for restricted isometry in compressed sensing matrices
• Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized X-ray CT
• Reweighted \(\ell_1\) minimization method for stochastic elliptic differential equations
• Restricted isometry properties and nonconvex compressive sensing
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• A null-space-based weightedl₁minimization approach to compressed sensing
• Sparse regression and support recovery with \(\mathbb{L}_2\)-boosting algorithms
• The restricted isometry property for random block diagonal matrices
• Robust width: a characterization of uniformly stable and robust compressed sensing
• An Unbiased Approach to Low Rank Recovery
• Bayesian signal detection with compressed measurements
• On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery
• An unbiased approach to compressed sensing
• The trimmed Lasso: sparse recovery guarantees and practical optimization by the generalized soft-min penalty
• Sparse recovery from extreme eigenvalues deviation inequalities
• Compressed sensing with restricted isometry property
• Debiasing convex regularized estimators and interval estimation in linear models
• Phase transitions for greedy sparse approximation algorithms
• Sparse learning model with embedded RIP conditions for turbulence super-resolution reconstruction
• Joint sparse optimization: lower-order regularization method and application in cell fate conversion
• Discrete uncertainty principles and sparse signal processing
• On convergence of iterative thresholding algorithms to approximate sparse solution for composite nonconvex optimization
• Iterative mix thresholding algorithm with continuation technique for mix sparse optimization and application
• On the conjugate gradient subspace pursuit algorithm
• On support sizes of restricted isometry constants
• Optimal group thresholding algorithms for group sparse optimization with convergence guarantee
• A fast recovery method of 2D geometric compressed sensing signal
• Matrix-free interior point method for compressed sensing problems
• Theoretical guarantees for graph sparse coding
• A strong restricted isometry property, with an application to phaseless compressed sensing
• The restricted isometry property and its implications for compressed sensing

Describes a project that uses

Uses Software

• CoSaMP

This page was built for publication: Compressed sensing: how sharp is the restricted isometry property?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3084491)