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

DOI10.1016/J.LAA.2013.07.025zbMATH Open1332.94044arXiv1207.1119OpenAlexW2963956267WikidataQ57392883 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)

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.

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

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

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)

Cites Work

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

Cited In (8)

• Solving variational inequalities with monotone operators on domains given by linear minimization oracles
• Block-sparse recovery of semidefinite systems and generalized null space conditions
• Recovery under side constraints
• Real versus complex null space properties for sparse vector recovery
• Sparse recovery on Euclidean Jordan algebras
• A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery
• Null space conditions and thresholds for rank minimization
• The null space property for sparse recovery from multiple measurement vectors

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)