Exact reconstruction of sparse signals via nonconvex minimization

Several authors have shown recently that it is possible to reconstruct exactly a sparse signal from fewer linear measurements than would be expected from traditional sampling theory. The methods used involve computing the signal of minimum l(1) norm among those having the given measurements. We show that by replacing the l(1) norm with the l(p) norm with p < 1, exact reconstruction is possible with substantially fewer measurements. We give a theorem in this direction, and many numerical examples, both in one complex dimension, and larger-scale examples in two real dimensions.