Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices

DOI10.1016/J.LAA.2012.11.024zbMATH Open1282.15030arXiv1207.4883OpenAlexW2073664962MaRDI QIDQ2437333FDOQ2437333

Authors: Bubacarr Bah, Jared Tanner 

Publication date: 3 March 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Restricted Isometry Constants (RICs) provide a measure of how far from an isometry a matrix can be when acting on sparse vectors. This, and related quantities, provide a mechanism by which standard eigen-analysis can be applied to topics relying on sparsity. RIC bounds have been presented for a variety of random matrices and matrix dimension and sparsity ranges. We provide explicitly formulae for RIC bounds, of n by N Gaussian matrices with sparsity k, in three settings: a) n/N fixed and k/n approaching zero, b) k/n fixed and n/N approaching zero, and c) n/N approaching zero with k/n decaying inverse logrithmically in N/n; in these three settings the RICs a) decay to zero, b) become unbounded (or approach inherent bounds), and c) approach a non-zero constant. Implications of these results for RIC based analysis of compressed sensing algorithms are presented.

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

Recommendations

• Improved bounds on restricted isometry constants for Gaussian matrices
• A simple proof of the restricted isometry property for random matrices
• New bounds for RIC in compressed sensing
• Compressed sensing: how sharp is the restricted isometry property?
• Bounding the restricted isometry constants for a tight frame

zbMATH Keywords

sparse approximationcompressed sensingrestricted isometry constantGaussian matricessingular values of random matrices

Mathematics Subject Classification ID

Large deviations (60F10) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52) Sampling theory in information and communication theory (94A20)

Cites Work

• Decoding by Linear Programming
• A simple proof of the restricted isometry property for random matrices
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Phase transitions for greedy sparse approximation algorithms
• The restricted isometry property and its implications for compressed sensing
• Bayesian Compressive Sensing Using Laplace Priors
• Testing the nullspace property using semidefinite programming
• A limit theorem for the norm of random matrices
• Compressive sensing and structured random matrices
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Compressed sensing: how sharp is the restricted isometry property?
• Theoretical foundations and numerical methods for sparse recovery. Papers based on the presentations of the summer school ``Theoretical foundations and numerical methods for sparse recovery, Vienna, Austria, August 31 -- September 4, 2009.
• The smallest eigenvalue of a large dimensional Wishart matrix
• Improved bounds on restricted isometry constants for Gaussian matrices
• A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
• Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices

Cited In (10)

• Bounding the restricted isometry constants for a tight frame
• On the prediction loss of the Lasso in the partially labeled setting
• Improved bounds for restricted isometry constants
• On higher order isotropy conditions and lower bounds for sparse quadratic forms
• Recovery error analysis of noisy measurement in compressed sensing
• A tight bound of hard thresholding
• Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
• Sparse recovery from extreme eigenvalues deviation inequalities
• On the sparsity of Lasso minimizers in sparse data recovery
• Improved bounds on restricted isometry constants for Gaussian matrices

Uses Software

• CoSaMP

This page was built for publication: Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices

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