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.