Nonconvex Compressed Sensing and Error Correction

The theory of compressed sensing has shown that sparse signals can be reconstructed exactly from remarkably few measurements. In this paper we consider a nonconvex extension, where the lscr 1 1 norm of the basis pursuit algorithm is replaced with the lscr p norm, for p < 1. In the context of sparse error correction, we perform numerical experiments that show that for a fixed number of measurements, errors of larger support can be corrected in the nonconvex case. We also provide a theoretical justification for why this should be so.