deposit_your_work

A simple proof of the restricted isometry property for random matrices

Files in this item

Files Size Format View
JL_RIP.pdf 331.6Kb application/pdf Thumbnail

Show full item record

Item Metadata

Title: A simple proof of the restricted isometry property for random matrices
Alternative title: The Johnson-Lindenstrauss lemma meets compressed sensing
Author: Baraniuk, Richard G.; Davenport, Mark A.; DeVore, Ronald A.; Wakin, Michael B.
Type: articles
Citation: R. G. Baraniuk, M. A. Davenport, R. A. DeVore and M. B. Wakin, "A simple proof of the restricted isometry property for random matrices," Constructive Approximation, 2007.
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.
Date Published: 2007-01-18

This item appears in the following Collection(s)

  • DSP Publications [508 items]
    Publications by Rice Faculty and graduate students in digital signal processing.