Restricted Isometry Property of Random Subdictionaries

We study statistical restricted isometry, a property closely related to sparse signal recovery, of deterministic sensing matrices of size m × N. A matrix is said to have a statistical restricted isometry property (StRIP) of order k if most submatrices with k columns define a near-isometric map of Rk into Rm. As our main result, we establish sufficient conditions for the StRIP property of a matrix in terms of the mutual coherence and mean square coherence. We show that for many existing deterministic families of sampling matrices, m = O(k) rows suffice for k-StRIP, which is an improvement over the known estimates of either m = Θ(k log N) or m = Θ(k log k). We also give examples of matrix families that are shown to have the StRIP property using our sufficient conditions.