In order to prove that a weaker restricted isometry property is sufficient to guarantee perfect recovery in the lp case, they used an improvement of a proof of Dvoretzky's theorem presented in Gilles Pisier 's book. The algorithm exploiting this weaker RIP was featured in Iteratively Reweighted Algorithms for Compressive Sensing and was implemented in the Monday Morning Algorithm Part deux: Reweighted Lp for Non-convex Compressed Sensing Reconstruction. The paper is available from the authors and will be on the LANL website in about a week. [ Update: it is now available here ]
In previous work, numerical experiments showed that lp minimization with p above 0 and p less than 1 recovers sparse signals from fewer linear measurements than does l1 minimization. It was also shown that a weaker restricted isometry property is sufficient to guarantee perfect recovery in the lp case. In this work, we generalize this result to an lp 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.
Besides the impressive result on the weaker RIP, one of the experimentally noticeable item featured in the article is that below p=0.8, using the reweighted Lp algorithm, perfect recovery below a certain number of measurements is not possible. That number 0.8 is also the coefficient used for efficient recovery of natural images, in Deconvolution using natural image priors by Anat Levin, Rob Fergus, Fredo Durand, and Bill Freeman on the reconstruction from coded aperture measurements. Naaaaah... it's just a coincidence....
 Pisier Gilles, The volume of convex bodies and Banach space geometry.