On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization

DOI10.1007/s10107-010-0417-zzbMath1211.90333arXiv0809.2650OpenAlexW2026653661WikidataQ57392898 ScholiaQ57392898MaRDI QIDQ633105

Arkadi Nemirovski, Anatoli B. Juditsky

Publication date: 31 March 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

sparse recoverycompressed sensing\(\ell_{1}\)-recovery

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Linear programming (90C05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items

On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization, A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions, The smoothing objective penalty function method for two-cardinality sparse constrained optimization problems, \(s\)-goodness for low-rank matrix recovery, Heuristics for Finding Sparse Solutions of Linear Inequalities, Sparse recovery with integrality constraints, Nonnegative partial \(s\)-goodness for the equivalence of a 0-1 linear program to weighted linear programming, Testing the nullspace property using semidefinite programming, Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions, Self-concordant analysis for logistic regression, Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices, RIPless compressed sensing from anisotropic measurements, On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures, Partial \(S\)-goodness for partially sparse signal recovery, Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets, Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors, Finite-sample analysis of \(M\)-estimators using self-concordance, Sparse recovery on Euclidean Jordan algebras, Equivalence and strong equivalence between the sparsest and least \(\ell _1\)-norm nonnegative solutions of linear systems and their applications, On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery, The sparsest solutions to \(Z\)-tensor complementarity problems, An evaluation of the sparsity degree for sparse recovery with deterministic measurement matrices, Computing the spark: mixed-integer programming for the (vector) matroid girth problem, Randomization of data acquisition and \(\ell_{1}\)-optimization (recognition with compression), A numerical exploration of compressed sampling recovery, Accuracy guaranties for \(\ell_{1}\) recovery of block-sparse signals, Necessary and Sufficient Conditions for Noiseless Sparse Recovery via Convex Quadratic Splines, Locally sparse reconstruction using the \(\ell^{1,\infty}\)-norm, The sparsest solution to the system of absolute value equations

Uses Software

• Mosek

Cites Work

• Unnamed Item
• Unnamed Item
• The restricted isometry property and its implications for compressed sensing
• Simultaneous analysis of Lasso and Dantzig selector
• Deterministic constructions of compressed sensing matrices
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
• Lectures on Modern Convex Optimization
• Compressed sensing and best 𝑘-term approximation
• On Sparse Representations in Arbitrary Redundant Bases
• Decoding by Linear Programming
• Stable recovery of sparse overcomplete representations in the presence of noise
• Recovery of Exact Sparse Representations in the Presence of Bounded Noise
• Just relax: convex programming methods for identifying sparse signals in noise
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Uncertainty principles and ideal atomic decomposition
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Stable signal recovery from incomplete and inaccurate measurements