Loading...
Please wait, while we are loading the content...
Similar Documents
The Johnson-Lindenstrauss Lemma Meets Compressed Sensing
| Content Provider | Semantic Scholar |
|---|---|
| Author | Baraniuk, Richard G. Davenport, Mark A. DeVore, Ronald A. Wakin, Michael B. |
| Copyright Year | 2006 |
| Abstract | We show how two fundamental results in analysis related to n-widths and Compressed Sensing are intimately related to the Johnson-Lindenstrauss lemma. Our elementary approach is based on the same concentration inequalities for random inner products that have recently provided simple proofs of the Johnson-Lindenstrauss lemma. We show how these ideas lead to simple proofs of Kashin's theorems on widths of finite balls in Euclidean space (and their improvements due to Gluskin) as well as the existence of optimal Compressed Sensing measurement matrices. In the process we also prove that these measurement matrices are universal with respect to the sparsity-inducing basis. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.math.tamu.edu/~alperen/wsdm/jlmeetscs.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
