The Usefulness of a Modified Restricted Isometry Property

The restricted isometry property is arguably the most prominent tool in the theory of compressive sensing. In its classical version, it features l_2 norms as inner and outer norms. The modified version considered in this talk features the l_1 norm as the inner norm, while the outer norm depends a priori on the distribution of the random entries populating the measurement matrix.  The modified version holds for a wider class of random matrices and still accounts for the success of sparse recovery via basis pursuit and via iterative hard thresholding. In the special case of Gaussian matrices, the outer norm actually reduces to an l_2 norm. This fact allows one to retrieve results from the theory of one-bit compressive sensing in a very simple way. Extensions to one-bit matrix recovery are then straightforward.