Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions

DOI10.1007/s40305-013-0010-2zbMath1288.65091MaRDI QIDQ384215

Yin Zhang

Publication date: 27 November 2013

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40305-013-0010-2

zbMATH Keywords

stability; prior information; compressive sensing; recoverability; \(\ell_1\)-minimization; non-restricted isometry property; uniform recoverability

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C30: Nonlinear programming

94A08: Image processing (compression, reconstruction, etc.) in information and communication theory

94A20: Sampling theory in information and communication theory

Related Items

A null-space-based weightedl₁minimization approach to compressed sensing, Spherical Designs and Nonconvex Minimization for Recovery of Sparse Signals on the Sphere, Analysis and Algorithms for Some Compressed Sensing Models Based on L1/L2 Minimization, A Scale-Invariant Approach for Sparse Signal Recovery, Weak Stability of ℓ₁-Minimization Methods in Sparse Data Reconstruction, Minimization of $\ell_{1-2}$ for Compressed Sensing, Moment Tensor Potentials: A Class of Systematically Improvable Interatomic Potentials, A hybrid splitting method for smoothing Tikhonov regularization problem, Sparse Solutions of a Class of Constrained Optimization Problems, An analysis of noise folding for low-rank matrix recovery, A survey on compressive sensing: classical results and recent advancements, Heuristics for Finding Sparse Solutions of Linear Inequalities, Sorted \(L_1/L_2\) minimization for sparse signal recovery, 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory, \(s\)-goodness for low-rank matrix recovery, Equivalence and strong equivalence between the sparsest and least \(\ell _1\)-norm nonnegative solutions of linear systems and their applications, The sparsest solutions to \(Z\)-tensor complementarity problems, Sharp non-asymptotic performance bounds for \(\ell_1\) and Huber robust regression estimators, Computation of sparse and dense equilibrium strategies of evolutionary games, Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing, Necessary and sufficient conditions of solution uniqueness in 1-norm minimization, The sparsest solution to the system of absolute value equations, One condition for solution uniqueness and robustness of both \(\ell_1\)-synthesis and \(\ell_1\)-analysis minimizations, Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets

Uses Software

• PDCO
• CoSaMP

Cites Work

• The restricted isometry property and its implications for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Breakdown of equivalence between the minimal \(\ell^1\)-norm solution and the sparsest solution
• A simple proof of the restricted isometry property for random matrices
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Compressed sensing and best 𝑘-term approximation
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Decoding by Linear Programming
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Linear Inversion of Band-Limited Reflection Seismograms
• Atomic Decomposition by Basis Pursuit
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item