Sparse Recovery by Non-convex Optimization -- Instance Optimality
Preprint
Abstract
In this note, we address the theoretical properties of $\Delta_p$, a class of compressed sensing decoders that rely on $\ell^p$ minimization with 0<p<1 to recover estimates of sparse and compressible signals from incomplete and inaccurate measurements. In particular, we extend the results of Candes, Romberg and Tao, and Wojtaszczyk regarding the decoder $\Delta_1$, based on $\ell^1$ minimization, to $\Delta_p$ with 0<p<1. Our results are two-fold. First, we show that under certain sufficient conditions that are weaker than the analogous sufficient conditions for $\Delta_1$ the decoders $\Delta_p$ are robust to noise and stable in the sense that they are (2,p) instance optimal for a large class of encoders. Second, we extend the results of Wojtaszczyk to show that, like $\Delta_1$, the decoders $\Delta_p$ are (2,2) instance optimal in probability provided the measurement matrix is drawn from an appropriate distribution.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Stability and Instance Optimality for Gaussian Measurements in Compressed SensingFoundations of Computational Mathematics, 2009
- Compressed sensing and best 𝑘-term approximationJournal of the American Mathematical Society, 2008
- The restricted isometry property and its implications for compressed sensingComptes Rendus Mathématique, 2008
- A Simple Proof of the Restricted Isometry Property for Random MatricesConstructive Approximation, 2008
- Highly sparse representations from dictionaries are unique and independent of the sparseness measureApplied and Computational Harmonic Analysis, 2007
- A simple test to check the optimality of a sparse signal approximationSignal Processing, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimizationProceedings of the National Academy of Sciences, 2003
- Uncertainty principles and ideal atomic decompositionIEEE Transactions on Information Theory, 2001
- Euclidean projections of a p-convex body2000