On Verifiable Sufficient Conditions for Sparse Signal Recovery via ${\ell }_1$ Minimization

Abstract

We propose novel necessary and sufficient conditions for a sensing matrix to be "$s$-good" - to allow for exact ${\ell }_1$-recovery of sparse signals with $s$ nonzero entries when no measurement noise is present. Then we express the error bounds for imperfect ${\ell }_1$-recovery (nonzero measurement noise, nearly $s$-sparse signal, near-optimal solution of the optimization problem yielding the ${\ell }_1$-recovery) in terms of the characteristics underlying these conditions. Further, we demonstrate (and this is the principal result of the paper) that these characteristics, although difficult to evaluate, lead to verifiable sufficient conditions for exact sparse ${\ell }_1$-recovery and to efficiently computable upper bounds on those $s$ for which a given sensing matrix is $s$-good. We establish also instructive links between our approach and the basic concepts of the Compressed Sensing theory, like Restricted Isometry or Restricted Eigenvalue properties.

References in corpus (2)

• Simultaneous analysis of Lasso and Dantzig selector
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$

Cited by in corpus (26)

• Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors
• A weighted L1-minimization approach for sparse polynomial chaos expansions
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• RIPless compressed sensing from anisotropic measurements
• On Polynomial Chaos Expansion via Gradient-enhanced ${\ell }_1$-minimization
• Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values
• RSP-Based Analysis for Sparsest and Least ${\ell }_1$-Norm Solutions to Underdetermined Linear Systems
• Unknown sparsity in compressed sensing: Denoising and inference
• Block-length dependent thresholds in block-sparse compressed sensing
• Accuracy guarantees for L1-recovery
• Low-Cost and High-Throughput Testing of COVID-19 Viruses and Antibodies via Compressed Sensing: System Concepts and Computational Experiments
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Estimating Unknown Sparsity in Compressed Sensing
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• On a class of optimization-based robust estimators
• On the Certification of the Restricted Isometry Property
• A Class of Novel STAP Algorithms Using Sparse Recovery Technique
• Sparse Recovery, Kashin Decomposition and Conic Programming
• From variable density sampling to continuous sampling using Markov chains
• Hidden cliques and the certification of the restricted isometry property
• Locally Sparse Reconstruction Using the ${\ell }^{1,\infty }$-Norm
• Testing the Nullspace Property using Semidefinite Programming
• Efficient Representations of Signals in Nonlinear Signal Processing with Applications to Inverse Problems
• Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
• Optimality of ${\ell }_2/{\ell }_1$-optimization block-length dependent thresholds
• Faster $p$-Norm Regression Using Sparsity