We give a simple technique for verifying the Restricted Isometry Property (as introduced by
Cand`es and Tao) for random matrices that underlies Compressed Sensing. Our approach has
two main ingredients: (i) concentration inequalities for random inner products that have recently
provided algorithmically simple proofs of the Johnson-Lindenstrauss lemma, (ii) covering
numbers for finite dimensional balls in Euclidean space. This leads to an elementary proof of the
Restricted Isometry Property and brings out connections between Compressed Sensing and the
Johnson-Lindenstrauss lemma. As a result, we obtain simple and direct proofs of Kashin’s theorems
on widths of finite balls in Euclidean space (and their improvements due to Gluskin) and
proofs of the existence of optimal Compressed Sensing measurement matrices. In the process
we also prove that these measurements have a certain universality with respect to the sparsity
inducing basis.
1