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

DOI10.1016/J.LAA.2013.07.025zbMATH Open1332.94044OpenAlexW2963956267WikidataQ57392883 ScholiaQ57392883MaRDI QIDQ2437335FDOQ2437335

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

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) Matrix completion problems (15A83) Approximation by convex sets (52A27) Sampling theory in information and communication theory (94A20)

Abstract: We discuss a general notion of "sparsity structure" and associated recoveries of a sparse signal from its linear image of reduced dimension possibly corrupted with noise. Our approach allows for unified treatment of (a) the "usual sparsity" and "usual $el{l}_1$ recovery," (b) block-sparsity with possibly overlapping blocks and associated block-$el{l}_1$ recovery, and (c) low-rank-oriented recovery by nuclear norm minimization. The proposed recovery routines are natural extensions of the usual $el{l}_1$ minimization used in Compressed Sensing. Specifically we present nullspace-type sufficient conditions for the recovery to be precise on sparse signals in the noiseless case. Then we derive error bounds for imperfect (nearly sparse signal, presence of observation noise, etc.) recovery under these conditions. In all of these cases, we present efficiently verifiable sufficient conditions for the validity of the associated nullspace properties.

Recommendations

• A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations
• Block-sparse recovery of semidefinite systems and generalized null space conditions
• The null space property for sparse recovery from multiple measurement vectors
• Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements
• scientific article; zbMATH DE number 7678028
• A general theory for subspace-sparse recovery
• A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization
• Sparse Recovery Conditions and Performance Bounds for $\ell _p$-Minimization
• Generalized notions of sparsity and restricted isometry property. I: A unified framework
• Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants

Cites work

• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• Accuracy Guarantees for <formula formulatype="inline"> <tex Notation="TeX">$\ell_1$</tex></formula>-Recovery
• Compressed sensing
• Decoding by Linear Programming
• Exact matrix completion via convex optimization
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Null space conditions and thresholds for rank minimization
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• Phase retrieval via matrix completion
• 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
• Simultaneous analysis of Lasso and Dantzig selector
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Uncertainty principles and ideal atomic decomposition
• Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions
• \(s\)-goodness for low-rank matrix recovery

Cited in

(11)

• Sparse recovery on Euclidean Jordan algebras
• A Unified Recovery of Structured Signals Using Atomic Norm
• Null space conditions and thresholds for rank minimization
• Real versus complex null space properties for sparse vector recovery
• A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery
• Recovery under side constraints
• The null space property for sparse recovery from multiple measurement vectors
• Block-sparse recovery of semidefinite systems and generalized null space conditions
• Piecewise sparse recovery in union of bases
• Error bounds for compressed sensing algorithms with group sparsity: A unified approach
• Solving variational inequalities with monotone operators on domains given by linear minimization oracles

Describes a project that uses

Uses Software

• PhaseLift

This page was built for publication: On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437335)