MIT CSAIL

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 x 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. Before, only the cases p ∈ {1, 1 + 1log k, 2} were studied. Interestingly, our results show that the case p = 2 is a ‘singularity ’ in terms of the optimum value of m. We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss implications of our results for the Stable Sparse Recovery problem. ar X i