On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
From MaRDI portal
Publication:633105
DOI10.1007/s10107-010-0417-zzbMath1211.90333arXiv0809.2650WikidataQ57392898 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
65K05: Numerical mathematical programming methods
90C90: Applications of mathematical programming
90C05: Linear programming
94A12: Signal theory (characterization, reconstruction, filtering, etc.)
Related Items
The smoothing objective penalty function method for two-cardinality sparse constrained optimization problems, Heuristics for Finding Sparse Solutions of Linear Inequalities, Nonnegative partial \(s\)-goodness for the equivalence of a 0-1 linear program to weighted linear programming, Locally sparse reconstruction using the \(\ell^{1,\infty}\)-norm, A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions, \(s\)-goodness for low-rank matrix recovery, 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, Randomization of data acquisition and \(\ell_{1}\)-optimization (recognition with compression), Testing the nullspace property using semidefinite programming, Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions, Accuracy guaranties for \(\ell_{1}\) recovery of block-sparse signals, Self-concordant analysis for logistic regression, Computing the spark: mixed-integer programming for the (vector) matroid girth problem, Sparse recovery with integrality constraints, Finite-sample analysis of \(M\)-estimators using self-concordance, An evaluation of the sparsity degree for sparse recovery with deterministic measurement matrices, A numerical exploration of compressed sampling recovery, The sparsest solution to the system of absolute value equations, On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization, 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, Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors, Constructing New Weighted ℓ1-Algorithms for the Sparsest Points of Polyhedral Sets, Necessary and Sufficient Conditions for Noiseless Sparse Recovery via Convex Quadratic Splines
Uses Software
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