作者
Richard Baraniuk, Mark Davenport, Ronald DeVore, Michael Wakin
发表日期
2008/12
期刊
Constructive approximation
卷号
28
页码范围
253-263
出版商
Springer-Verlag
简介
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 …
引用总数
学术搜索中的文章
R Baraniuk, M Davenport, R DeVore, M Wakin - Constructive approximation, 2008