New Bounds for Restricted Isometry Constants

DOI10.1109/TIT.2010.2054730MaRDI QIDQ5281299zbMATH OpenFDO

Authors Lie Wang, Guangwu Xu, T. Tony Cai

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Measures of information, entropy (94A17)

Abstract: In this paper we show that if the restricted isometry constant $delt{a}_k$ of the compressed sensing matrix satisfies [ delta_k < 0.307, ] then $k$-sparse signals are guaranteed to be recovered exactly via $el{l}_1$ minimization when no noise is present and $k$-sparse signals can be estimated stably in the noisy case. It is also shown that the bound cannot be substantively improved. An explicitly example is constructed in which $delt{a}_k=frack-12k-1<0.5$, but it is impossible to recover certain $k$-sparse signals.

Cited in

(64)

• Signal recovery under cumulative coherence
• Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework
• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling
• Compressed data separation via dual frames based split-analysis with Weibull matrices
• Asymptotic analysis for extreme eigenvalues of principal minors of random matrices
• Robust sparse recovery via a novel convex model
• Weighted \(\ell_p\) (\(0<p\le 1\)) minimization with non-uniform weights for sparse recovery under partial support information
• Penalized and constrained LAD estimation in fixed and high dimension
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Stable restoration and separation of approximately sparse signals
• Sparse signals recovery from noisy measurements by orthogonal matching pursuit
• Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions
• A note on block-sparse signal recovery with coherent tight frames
• New conditions on stable recovery of weighted sparse signals via weighted l₁ minimization
• Optimal D-RIP bounds in compressed sensing
• Recovery error analysis of noisy measurement in compressed sensing
• A new bound on the block restricted isometry constant in compressed sensing
• Improved RIP conditions for compressed sensing with coherent tight frames
• Concentration of \(S\)-largest mutilated vectors with \(\ell_p\)-quasinorm for \(0<p\leq 1\) and its applications
• Stable recovery of low-rank matrix via nonconvex Schatten p-minimization
• Exact low-rank matrix recovery via nonconvex Schatten \(p\)-minimization
• An error bound for L₁-norm support vector machine coefficients in ultra-high dimension
• Sparse approximation using _1-_2 minimization and its application to stochastic collocation
• Stochastic collocation methods via \(\ell_1\) minimization using randomized quadratures
• A unified framework for linear dimensionality reduction in L1
• The restricted isometry property for signal recovery with coherent tight frames
• A survey of compressed sensing
• Block sparse recovery via mixed l₂/l₁ minimization
• Recovery of high-dimensional sparse signals via \(\ell_1\)-minimization
• The bounds of restricted isometry constants for low rank matrices recovery
• The L₁ penalized LAD estimator for high dimensional linear regression
• Sparse Legendre expansions via _1-minimization
• Sparse concordance-assisted learning for optimal treatment decision
• A tight bound of hard thresholding
• New bounds for RIC in compressed sensing
• Weighted \(\ell_1\)-minimization for sparse recovery under arbitrary prior information
• A null-space-based weightedl₁minimization approach to compressed sensing
• Bounding the restricted isometry constants for a tight frame
• Compressed sensing with preconditioning for sparse recovery with subsampled matrices of Slepian prolate functions
• Compressed sensing with coherent tight frames via \(l_q\)-minimization for \(0 < q \leq 1\)
• Binary sparse signal recovery with binary matching pursuit
• Sparse convex optimization via adaptively regularized hard thresholding
• Sufficient conditions on stable reconstruction of weighted problem
• Stability analysis of a class of sparse optimization problems
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
• Stochastic collocation algorithms using \(l_1\)-minimization for Bayesian solution of inverse problems
• An Improved Estimate in the Restricted Isometry Problem
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• A new result on recovery sparse signals using orthogonal matching pursuit
• Compressed sensing
• Stable recovery of weighted sparse signals from phaseless measurements via weighted l₁ minimization
• New bounds on the restricted isometry constant \(\delta _{2k}\)
• Moving force identification based on group Lasso and compressed sensing
• k block sparse vector recovery via block _1-_2 minimization
• Constrained mix sparse optimization via hard thresholding pursuit
• Noise folding in completely perturbed compressed sensing
• Sufficient condition based on nearly optimal order RIC for IHT algorithm
• From linear system of equations to artificial intelligence -- the evolution journey of computer tomographic image reconstruction algorithms
• Sparse recovery with fusion frames and bounded orthonormal systems
• On support sizes of restricted isometry constants
• Improved bounds for restricted isometry constants
• Subgradient-based tableau pivot method for sparse signal recovery
• Conditional value-at-risk portfolio optimization in high dimensions
• On the _1-norm invariant convex k-sparse decomposition of signals

This page was built for publication: New Bounds for Restricted Isometry Constants

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