@article {saab2008ACHAsrb,
title = {Sparse recovery by non-convex optimization - instance optimality},
journal = {Applied and Computational Harmonic Analysis},
volume = {29},
number = {1},
year = {2010},
month = {07},
pages = {30-48},
abstract = {In this note, we address the theoretical properties of $Δ_p$, a class of compressed sensing decoders that rely on $l^p$ minimization with $p {\i}n (0,1)$ to recover estimates of sparse and compressible signals from incomplete and inaccurate measurements. In particular, we extend the results of Cand{\textquoteleft}es, Romberg and Tao [3] and Wojtaszczyk [30] regarding the decoder $Δ_1$, based on $\ell^1$ minimization, to $Δ p$ with $p {\i}n (0,1)$. Our results are two-fold. First, we show that under certain sufficient conditions that are weaker than the analogous sufficient conditions for $Δ_1$ the decoders $Δ_p$ are robust to noise and stable in the sense that they are $(2,p)$ instance optimal. Second, we extend the results of Wojtaszczyk to show that, like $Δ_1$, the decoders $Δ_p$ are (2,2) instance optimal in probability provided the measurement matrix is drawn from an appropriate distribution. While the extension of the results of [3] to the setting where $p {\i}n (0,1)$ is straightforward, the extension of the instance optimality in probability result of [30] is non-trivial. In particular, we need to prove that the $LQ_1$ property, introduced in [30], and shown to hold for Gaussian matrices and matrices whose columns are drawn uniformly from the sphere, generalizes to an $LQ_p$ property for the same classes of matrices. Our proof is based on a result by Gordon and Kalton [18] about the Banach-Mazur distances of p-convex bodies to their convex hulls.},
keywords = {Compressive Sensing, non-convex},
doi = {10.1016/j.acha.2009.08.002},
url = {http://www.sciencedirect.com/science/article/pii/S1063520309000864},
url2 = {https://slim.gatech.edu/Publications/Public/Journals/ACHA/2010/saab2008ACHAsrb/saab2008ACHAsrb.pdf},
author = {Rayan Saab and Ozgur Yilmaz}
}