Several authors have shown recently that 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 ℓ^1 norm among those having the given measurements. We show that by replacing the ℓ^1 norm with the ℓ^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.

To appear.