Restricted Isometry Property for General p-Norms

The restricted isometry property (RIP) is a fundamental property of a matrix, which enables sparse recovery. Informally, an m × n matrix satisfies RIP of order k for the ℓ
_p
norm, if ||Ax||
_p
≈ ||x||
_p
for every vector × with at most k non-zero coordinates. For every 1 ≤ p <; ∞, we obtain almost tight bounds on the minimum number of rows m necessary for the RIP property to hold. Prior to this paper, only the cases p = 1, 1+ 1/ log n, and 2 were studied. Interestingly, our results show that the case p = 2 is a singularity point: the optimal number of rows m is Θ̃(k
^p
) for all p ∈ [1, ∞) \ {2}, as opposed to Θ̃(k) for p = 2. We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss the implications of our results for the stable sparse recovery problem as defined by Candès et al.