A simple proof of the restricted isometry property for random matrices

Richard Baraniuk, Mark Davenport, Ronald DeVore, Michael Wakin

Research output: Contribution to journalArticle

1523 Scopus citations

Abstract

We give a simple technique for verifying the Restricted Isometry Property (as introduced by Candès 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.

Original languageEnglish (US)
Pages (from-to)253-263
Number of pages11
JournalConstructive Approximation
Volume28
Issue number3
DOIs
StatePublished - Dec 2008

Keywords

  • Compressed sensing
  • Concentration inequalities
  • Random matrices
  • Sampling

ASJC Scopus subject areas

  • Mathematics(all)
  • Analysis
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A simple proof of the restricted isometry property for random matrices'. Together they form a unique fingerprint.

Cite this