High-Dimensional Probability

Contents......Page 8
Foreword......Page 12
Preface......Page 14
0. Using Probability to Cover Geometric Set......Page 16
0.1 Notes......Page 19
1.1 Basic Quantities Associated with Random Variables......Page 20
1.2 Some Classical Inequalities......Page 21
1.3 Limit Theorems......Page 23
1.4 Notes......Page 25
2.1 Why Concentration Inequalities?......Page 26
2.2 Hoeffding\'s Inequality......Page 28
2.3 Chernoff\'s Inequality......Page 32
2.4 Application: Degrees of Random Graphs......Page 34
2.5 Sub-Gaussian Distributions......Page 36
2.6 General Hoeffding and Khintchine Inequalities......Page 41
2.7 Sub-Exponential Distributions......Page 43
2.8 Bernstein\'s Inequality......Page 48
2.9 Notes......Page 51
3. Random Vectors in High Dimensions......Page 53
3.1 Concentration of the Norm......Page 54
3.2 Covariance Matrices and Principal Component Analysis......Page 56
3.3 Examples of High-Dimensional Distributions......Page 60
3.4 Sub-Gaussian Distributions in Higher Dimensions......Page 66
3.5 Application: Grothendieck\'s Inequality and Semidefinite Programming......Page 70
3.6 Application: Maximum Cut for Graphs......Page 75
3.7 Kernel Trick, and Tightening of Grothendieck’s Inequality......Page 79
3.8 Notes......Page 83
4.1 Preliminaries on Matrices......Page 85
4.2 Nets, Covering Numbers, and Packing Numbers......Page 90
4.3 Application: Error Correcting Codes......Page 94
4.4 Upper Bounds on Random Sub-Gaussian Matrices......Page 98
4.5 Application: Community Detection in Networks......Page 102
4.6 Two-Sided Bounds on Sub-Gaussian Matrices......Page 106
4.7 Application: Covariance Estimation and Clustering......Page 108
4.8 Notes......Page 112
5.1 Concentration of Lipschitz Functions for the Sphere......Page 113
5.2 Concentration for Other Metric Measure Spaces......Page 119
5.3 Application: Johnson-Lindenstrauss Lemma......Page 125
5.4 Matrix Bernstein Inequality......Page 128
5.5 Application: Community Detection in Sparse Networks......Page 136
5.6 Application: Covariance Estimation for General Distributions......Page 137
5.7 Notes......Page 140
6.1 Decoupling......Page 142
6.2 Hanson-Wright Inequality......Page 145
6.3 Concentration for Anisotropic Random Vectors......Page 149
6.4 Symmetrization......Page 151
6.5 Random Matrices With Non-I.I.D. Entries......Page 153
6.6 Application: Matrix Completion......Page 155
6.7 Contraction Principle......Page 158
6.8 Notes......Page 160
7.1 Basic Concepts and Examples......Page 162
7.2 Slepian\'s Inequality......Page 166
7.3 Sharp Bounds on Gaussian Matrices......Page 172
7.4 Sudakov\'s Minoration Inequality......Page 175
7.5 Gaussian Width......Page 177
7.6 Stable Dimension, Stable Rank, and Gaussian Complexity......Page 182
7.7 Random Projections of Sets......Page 185
7.8 Notes......Page 189
8.1 Dudley\'s Inequality......Page 191
8.2 Application: Empirical Processes......Page 198
8.3 VC Dimension......Page 203
8.4 Application: Statistical Learning Theory......Page 215
8.5 Generic Chaining......Page 221
8.6 Talagrand\'s Majorizing Measure and Comparison Theorems......Page 225
8.7 Chevet\'s Inequality......Page 227
8.8 Notes......Page 229
9.1 Matrix Deviation Inequality......Page 231
9.2 Random Matrices, Random Projections, and Covariance Estimation......Page 237
9.3 The Johnson–Lindenstrauss Lemma for Infinite Sets......Page 240
9.4 Random Sections: M* Bound and Escape Theorem......Page 242
9.5 Notes......Page 246
10.1 High-Dimensional Signal Recovery Problems......Page 247
10.2 Signal Recovery Based on M* Bound......Page 249
10.3 Recovery of Sparse Signals......Page 251
10.4 Low-Rank Matrix Recovery......Page 254
10.5 Exact Recovery and the Restricted Isometry Property......Page 256
10.6 Lasso Algorithm for Sparse Regression......Page 262
10.7 Notes......Page 267
11.1 Deviations of Random Matrices with respect to General Norms......Page 269
11.2 Johnson-Lindenstrauss Embeddings and Sharper Chevet Inequality......Page 272
11.3 Dvoretzky-Milman Theorem......Page 274
11.4 Notes......Page 279
Chapter 2......Page 280
Chapter 4......Page 281
Chapter 6......Page 282
Chapter 7......Page 283
Chapter 8......Page 284
Chapter 10......Page 285
Chapter 11......Page 286
References......Page 287
Index......Page 296