A Simple Proof of the Restricted Isometry Property for Random Matrices Academic Article uri icon

abstract

  • We give a simple technique for verifying the Restricted Isometry Property (as introduced by Cands 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; and (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. 2008 Springer Science+Business Media, LLC.

published proceedings

  • Constructive Approximation

altmetric score

  • 6

author list (cited authors)

  • Baraniuk, R., Davenport, M., DeVore, R., & Wakin, M.

citation count

  • 1614

complete list of authors

  • Baraniuk, Richard||Davenport, Mark||DeVore, Ronald||Wakin, Michael

publication date

  • December 2008