A short note on non-convex compressed sensing

In this note, we summarize the results we recently proved in\citeSY08 on the theoretical performance guarantees of the decoders $\Delta_p$. These decoders rely on $\ell^p$ minimization with $p ın (0,1)$ to recover estimates of sparse and compressible signals from incomplete and inaccurate measurements. Our guarantees generalize the results of \citeCRT05 and \citeWojtaszczyk08 about decoding by $\ell_p$ minimization with $p = 1$, to the setting where $p ın (0,1)$ and are obtained under weaker sufficient conditions. We also present novel extensions of our results in \citeSY08 that follow from the recent work of DeVore et al. in \citeDPW08. Finally, we show some insightful numerical experiments displaying the trade-off in the choice of $p \in (0,1]$ depending on certain properties of the input signal.