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 lscr 1 norm among those having the given measurements. We show that by replacing the lscr 1 norm with the lscr 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.