Restricted isometry properties and nonconvex compressive sensing

The recently emerged field known as compressive sensing has produced powerful results showing the ability to recover sparse signals from surprisingly few linear measurements, using ℓ 1 minimization. In previous work, numerical experiments showed that ℓ p minimization with 0 < p < 1 recovers sparse signals from fewer linear measurements than does ℓ 1 minimization. It was also shown that a weaker restricted isometry property is sufficient to guarantee perfect recovery in the ℓ p case. In this work, we generalize this result to an ℓ p variant of the restricted isometry property, and then determine how many random, Gaussian measurements are sufficient for the condition to hold with high probability. The resulting sufficient condition is met by fewer measurements for smaller p . This adds to the theoretical justification for the methods already being applied to replacing high-dose CT scans with a small number of x-rays and reducing MRI scanning time. The potential benefits extend to any application of compressive sensing.