A short note on non-convex compressed sensing

TitleA short note on non-convex compressed sensing
Publication TypeConference
Year of Publication2009
AuthorsRayan Saab, Ozgur Yilmaz
Conference NameSAMPTA technical program

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.

Citation Keysaab2009SAMPTAnccs