Interactions between compressed sensing, random matrices, and high dimensional geometry

Contents......Page 1
Introduction......Page 7
1.1. Orlicz spaces......Page 17
1.2. Linear combination of Psi-alpha random variables......Page 22
1.3. A geometric application: the Johnson-Lindenstrauss lemma......Page 30
1.4. Complexity and covering numbers......Page 32
1.5. Notes and comments......Page 40
2.1. A short introduction to compressed sensing......Page 43
2.2. The exact reconstruction problem......Page 44
2.3. The restricted isometry property......Page 51
2.4. The geometry of the null space......Page 52
2.5. Gelfand widths......Page 55
2.6. Gaussian random matrices satisfy a RIP......Page 57
2.7. RIP for other ``simple" subsets: almost sparse vectors......Page 60
2.8. An other complexity measure......Page 68
2.9. Notes and comments......Page 71
3.1. The chaining method......Page 73
3.2. An example of a more sophisticated chaining argument......Page 78
3.3. Application to Compressed Sensing......Page 85
3.4. Notes and comments......Page 87
4.1. The notion of singular values......Page 89
4.2. Basic properties......Page 92
4.3. Relationships between eigenvalues and singular values......Page 96
4.4. Relation with rows distances......Page 98
4.5. Gaussian random matrices......Page 99
4.6. The Marchenko–Pastur theorem......Page 104
4.7. Proof of the Marchenko–Pastur theorem......Page 108
4.8. The Bai–Yin theorem......Page 117
4.9. Notes and comments......Page 118
Chapter 5. Empirical methods and selection of characters......Page 121
5.1. Selection of characters and the reconstruction property.......Page 122
5.2. A way to construct a random data compression matrix......Page 126
5.3. Empirical processes......Page 128
5.4. Reconstruction property......Page 138
5.5. Random selection of characters within a coordinate subspace......Page 141
5.6. Notes and comments......Page 147
Notations......Page 149
Bibliography......Page 151
Index......Page 161