Stable sparse expansions via non-convex optimization

We present theoretical results pertaining to the ability of p-(quasi)norm minimization to recover sparse and compressible signals from incomplete and noisy measurements. In particular, we extend the results of Candes, Romberg and Tao for 1-norm to the p $\ll$ 1 case. Our results indicate that depending on the restricted isometry constants and the noise level, p-norm minimization with certain values of p $\ll$ 1 provides better theoretical guarantees in terms of stability and robustness compared to 1-norm minimization. This is especially true when the restricted isometry constants are relatively large, or equivalently, when the data is significantly undersampled.