On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures

DOI10.1016/j.laa.2013.07.025zbMath1332.94044arXiv1207.1119OpenAlexW2963956267WikidataQ57392883 ScholiaQ57392883MaRDI QIDQ2437335

Fatma Kılınç-Karzan, Arkadi Nemirovski, Anatoli B. Juditsky

Publication date: 3 March 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

sparse recoverylow-rank matrix recoverynuclear norm minimizationnullspace propertyblock-sparse recovery

Mathematics Subject Classification ID

Convex programming (90C25) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Approximation by convex sets (52A27) Sampling theory in information and communication theory (94A20) Matrix completion problems (15A83)

Related Items

Block-sparse recovery of semidefinite systems and generalized null space conditions, A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery, Recovery under side constraints, Solving variational inequalities with monotone operators on domains given by linear minimization oracles

Uses Software

• PhaseLift

Cites Work

• Unnamed Item
• \(s\)-goodness for low-rank matrix recovery
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions
• Null space conditions and thresholds for rank minimization
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Simultaneous analysis of Lasso and Dantzig selector
• Exact matrix completion via convex optimization
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Decoding by Linear Programming
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Uncertainty principles and ideal atomic decomposition
• Accuracy Guarantees for <formula formulatype="inline"> <tex Notation="TeX">$\ell_1$</tex></formula>-Recovery
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• Phase Retrieval via Matrix Completion
• Compressed sensing