Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
From MaRDI portal
Publication:2437333
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.
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
Cites work
- A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
- A limit theorem for the norm of random matrices
- A simple proof of the restricted isometry property for random matrices
- Bayesian Compressive Sensing Using Laplace Priors
- Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Compressed sensing: how sharp is the restricted isometry property?
- Compressive sensing and structured random matrices
- Decoding by Linear Programming
- Improved bounds on restricted isometry constants for Gaussian matrices
- Iterative hard thresholding for compressed sensing
- On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
- Phase transitions for greedy sparse approximation algorithms
- Sparse Recovery With Orthogonal Matching Pursuit Under RIP
- Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
- Subspace Pursuit for Compressive Sensing Signal Reconstruction
- Testing the nullspace property using semidefinite programming
- The restricted isometry property and its implications for compressed sensing
- The smallest eigenvalue of a large dimensional Wishart matrix
- 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.
Cited in
(10)- Bounding the restricted isometry constants for a tight frame
- On the prediction loss of the Lasso in the partially labeled setting
- A tight bound of hard thresholding
- Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
- On the sparsity of Lasso minimizers in sparse data recovery
- Sparse recovery from extreme eigenvalues deviation inequalities
- Improved bounds on restricted isometry constants for Gaussian matrices
- Recovery error analysis of noisy measurement in compressed sensing
- Improved bounds for restricted isometry constants
- On higher order isotropy conditions and lower bounds for sparse quadratic forms
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)
