第 10 部分：全书主题索引
第 10 部分：全书主题索引
本页由 10_2.pdf 的 Index OCR 整理，保留原书主题词和页码信息，并为当前 glossary 已覆盖的高频术语加入口。
| 原书索引条目 | 当前入口 |
|---|---|
| Adjacency matrix, 82 | |
| Admissible sequence, 246 | |
| Anisotropic random vectors, 189, 298 | 术语表 |
| Approximate Caratheodory theorem, see Caratheodory theorem isometry, 108, 109, 124, 152 projection, 133 | |
| Bennett inequality, 58 | |
| Bernoulli distribution, 18, 26, 39, 53 | |
| Bernstein inequality, 47, 48, 58 for matrices, 153, 159, 170, 193 | |
| Bias-variance tradeoff, 245 | |
| Binomial coefficients, 6 distribution, 18, 25, 39, 55 | |
| Blow-up, 144, 167 | |
| Bounded differences inequality, 166 | |
| Brownian motion, 198 | |
| Canonical Gaussian process, 198 metric, 197, 207 | 术语表 |
| Caratheodory theorem, 1 approximate, 2, 192 | |
| Carl-Pajor theorem, 7 | |
| Cauchy-Schwarz inequality, 10, 15 | |
| Centering, 43 | |
| Central limit theorem Berry-Esseen, 27 de Moivre-Laplace, 18 Lindeberg-Lévy, 18 projective, 70, 74 | |
| Chaining, 223 | |
| Chebyshev inequality, 16 | |
| Chernoff inequality, 30, 31, 51, 52 | |
| Chevet inequality, 250, 252, 260, 288 | 术语表 |
| Classification, 242-245 | |
| Clustering, 127 | |
| Coding, 114 | |
| Community detection, 120, 139, 160 | |
| Concave function, 8 | |
| Concentration around the LP norm, 168 for exponential densities, 150 Gaussian, 146, 198 of maximum, 168 of the norm, 60, 189, 192 on SO(n), 148 on a Riemannian manifold, 148 on the ball, 150 on the cube, 147, 150 on the Grassmannian, 149 on the sphere, 142, 143, 167 on the symmetric group, 148 Talagrand inequality, 150 Condition number, 108 Conditional expectation, 13 Conjugate exponents, 10, 15 Contraction principle, 185, 193, 217, 218 Convex body, 71, 75 combination, 1 dominance, 54 function, 8, 15 hull, 1, 21, 93, 137, 209 position, 93, 137 program, 79 relaxation, 277 set, 8 Coordinate distribution, 72, 76, 97 Covariance, 11, 12, 125, 217 estimation, 126, 139, 162, 193, 268, 269 matrix, 61 of a random process, 197 Covering number, 3, 110–113, 207–209 external, 134 monotonicity, 134 of low-rank matrices, 139 of the Euclidean ball, 113 of the Hamming cube, 113 via VC dimension, 238 Cramér-Wold device, 67 Cross-polytope, 9, 21 Gaussian width, 211 is poorly subgaussian, 97 slicing, 272, 297 Cube Gaussian width, 211 random projections, 290 Cumulative distribution function, 15 | 术语表 |
| Curse of dimensionality, 59 | |
| Cut norm, 134 | |
| Davis-Kahan inequality, 107, 132 | |
| Decoding map, 115 | |
| Decoupling, 173, 175, 187, 188 | |
| Degree of a vertex, 35 | |
| Delocalization, 94 | |
| Diameter, 114, 209 | |
| Dimension reduction, 64, 151, 238 | |
| Discrepancy, 241 | |
| Distance to a subspace, 190 | |
| Duality, 10 | |
| Dudley inequality, 223, 227, 246, 253, 254 local, 254 | 术语表 |
| Dvoretzky-Milman theorem, 288, 289 | 术语表 |
| Eckart-Young-Mirsky theorem, 106 | |
| Effective dimension, 213, 220, 271, 272, 276, 290 rank, 164, 171, 193, 220 | 术语表 |
| Eigenvalues min-max theorem, 103 of the covariance matrix, 64 optimization-based characterization, 63 | |
| Ellipsoid, 220 | |
| Embedding, 298 | |
| Empirical CDF, 241 measure, 231 method, 1, 2 process, 228, 230, 239, 259, 293 risk minimization, 244 | |
| Encoding map, 115 | |
| Entropy, 97 metric, 114 ε-net, 109, 111, 117, 134, 136, 137 | 术语表 |
| Erdős-Rényi model, 20–22, 34, 52, 53, 120 | |
| Error correcting code, 114, 115, 136 | |
| Escape theorem, 273, 280 | 术语表 |
| Euclidean norm, 9 | |
| Exact recovery, 280 | |
| Expander, 53 | |
| Expectation, 10 | |
| Exponential moment method, 28, 30, 38, 49 | |
| Extrapolation, 56 | |
| Feature map, 88 | |
| Frame, 72, 76, 94 | |
| Frobenius norm, 63, 104, 105, 130 | |
| Functions of matrices, see Matrix calculus | |
| Gamma function, 20, 53 γ2-functional, 246, 259 | 术语表 |
| Garnaev-Gluskin theorem, 297 | |
| Gaussian cloud, 299 complexity, 212, 213, 263, 285, 288 concentration, see Concentration, Gaussian distribution, 17 integration by parts, 200 interpolation, 199, 201 measure, 146 mixture model, 128, 129, 140 orthogonal ensemble, 92, 218 process, 197 canonical, 198, 208, 209 concentration, 198 replacement, 175, 177 tail, see Tails width, 209, 211, 213, 219, 220, 227, 250, 254 of sparse vectors, 297 Generalization error, 244 Generic chaining, 245, 247–249 Gilbert-Varshamov bound, 129 Ginibre distribution, 92 Glivenko-Cantelli class, 241 theorem, 241 GOE, see Gaussian orthogonal ensemble Goemans-Williamson algorithm, 82, 99 Golden-Thompson inequality, 156 Gordon inequality, 204, 218, 219 Gram matrix, 80, 98 Graph, 81 simple, 81 Grassmannian, 149, 151 Grothendieck identity, 83, 99 inequality, 76, 79, 87, 98 for PSD matrices, 99 quadratic, 98 SDP relaxation, 100 Growth function, 236, 256 Haar measure, 149 Hadamard matrix, 129 Hamming ball, 256 bound, 129 cube, 113, 116, 147 distance, 113, 147, 257 Hanson-Wright inequality, 176, 189 Hermitian dilation, 132, 305 Hessian, 150 Hilbert-Schmidt norm, see Frobenius norm Hoeffding inequality, 28–30, 54, 55 for matrices, 159 subgaussian, 40 lemma, 51 Hölder inequality, 10, 15 Hyperbolic sketch, 212, 272 Hypothesis class, 243 Increments of a random process, 197, 217, 223, 263, 286 Independent copy, 6, 173 Indicator, 11, 26 Integer optimization problem, 80 | 术语表 |
| Integrated tail formula, 16, 23 | |
| Interpolation, 22, 55 | |
| Isometric embedding, 108 | |
| Isometry, 108 | |
| Isoperimetric inequality, 143, 144, 146 | |
| Isotropic distribution, 65 distance, 91 marginals, 91 | 术语表 |
| Jensen inequality, 15, 20, 156 | |
| Johnson-Lindenstrauss lemma, 151, 214, 270 298 optimality, 168 subgaussian, 168 | 术语表 |
| Kernel, 85, 88, 99 | |
| Khintchine inequality, 41, 56, 58 for matrices, 159, 166, 170 l2 space, 99 | |
| Laplace distribution, 52, 190 | |
| Lasso, 279, 291, 295 | |
| Law of large numbers, 2, 17, 126, 228 Lipschitz, 229, 255 total expectation, 13 total probability, 14 | |
| Le Cam's two-point method, 52 | |
| Lieb inequality, 156 | |
| Linear regression, see Regression separability, 93 | |
| Linearity of expectation, 10 | |
| Lipschitz function, 142, 254 law of large numbers, 229, 255 norm, 142 | |
| Littlewood-Offord problem, 20 | |
| Loewner order, 154 | |
| Low-rank approximation, 106 matrices, 139 matrix recovery, 279, 280, 297 | |
| M* bound, 271, 294 | 术语表 |
| Majorizing measure theorem, 249 | |
| Marcinkiewicz-Zygmund inequality, 192 | |
| Markov inequality, 16 | |
| Matrix Bernstein inequality, see Bernstein inequality for matrices calculus, 154 completion, 183 deviation inequality, 263, 266, 267, 285, 292, 293, 298 exponentiation, 169 Hoeffding inequality, see Hoeffding inequality for matrices Khintchine inequality, see Khintchine inequality for matrices monotonicity, 155, 169 sketching, 171, 221 Taylor series, 169 Maximum cut, 81, 99 of Gaussians, 56 of subgaussians, 41, 56 principle, 21 McDiarmid inequality, see Bounded differences inequality Mean, 10 estimation, 32, 49, 189 Mean squared error, 294 Median, 33, 145 of means, 32, 33, 49, 52 Median-of-means, 52 Mercedes-Benz frame, 72, 94 Metric entropy, 114, 207 Mills ratio, 49, 50 Min-max theorem, 103, 104 Minkowski inequality, 9, 15 Minskowski sum, 112 Moment, 11 absolute, 11, 53 generating function, 11, 28, 36, 39, 44 Monte Carlo method, 228 Net, see ε-net Network, 34, 120, 160 Non-commutative Bernstein inequality, see Bernstein inequality for matrices Non-commutative Khintchine inequalities, see matrix Khintchine inequalities Normal distribution, 17, 26, 53 density, 66, 67 general, 67 joint, 68, 92 marginals, 66, 92 moments, 53 multivariate, 66, 67, 96 rotation invariance, 66 sums, 66 uniqueness, 67 Nuclear norm, 219, 279 Nullspace property, 298 One-bit quantization, 257 Operator norm, 105, 117, 130, 131, 137, 155 p → q, 133, 138, 260 for symmetric matrices, 106 Orlicz norm, 46, 57 Orthogonal invariance, 105 projection, 103, 132 p → q norm, 133, 138, 260 Packing number, 110–112, 134 of the Euclidean ball, 113 of the Hamming cube, 113 Pajor Lemma, 234, 256 Paley-Zygmund inequality, 23 | 术语表 |
| Perturbation theory, 106 | |
| Poisson distribution, 18, 31 limit theorem, 19 | |
| Polar decomposition, 93 | |
| Polarization identity, 98 | |
| Polytope, 3, 4, 7, 209 | |
| Positive-homogeneous function, 285 | |
| Power method, 131 | |
| Principal component analysis, 63, 64, 90, 125, 128 | |
| Projective central limit theorem, see Central limit theorem, projective ψ1 norm, 45 ψ2 norm, 38 ψα norm, 46, 57 | |
| Push forward measure, 168 | |
| Quadratic form, 173 | |
| Rademacher complexity, 240 distribution, 14, 28, 39, 53, 73, 74, 82, 179 | |
| Radius, 250 | |
| Random graph, 21, 22, 34, 49, 52, 53 matrix decoupling, 188 Gaussian, 93 Ginibre, 92, 93 GOE, 92 norm, 118, 120, 138, 181, 192, 193, 205, 206, 218, 251, 260 restricted isometry, 284 singular values, 124, 171, 219, 257, 267 process, 196 projection, 151, 152, 214, 221, 267, 268, 288, 290, 293, 298, 299 section, 271 subspace, 151 vector, 11 norm, 7, 60, 90, 91, 175, 188–190, 219, 260 | 术语表 |
| Randomized rounding, 83, 88 | |
| Real analytic function, 86 | |
| Regression, 274 | |
| Regular graph, 35 | |
| Reproducing kernel Hilbert space, 88 | |
| Restricted isometry, 283, 284, 298 | 术语表 |
| Riemannian manifold, 148 | |
| RIP, see Restricted isometry | 术语表 |
| Risk, 243 | |
| Rotation invariance, 66, 69, 95, 151 | |
| Sample covariance, 126 mean, 17, 32, 189 | |
| Sauer-Shelah Lemma, 235 | |
| Schur bound, 131 | |
| Second moment matrix, 62, 126, 162 method, 20, 22 Selectors, 174, 183 Self-normalized sum, 191 Semidefinite program, 79 relaxation, 80, 82, 98, 100 Separate convexity, 98 Shatter, 232 Simplex, 135 Singular value decomposition, 102 values, 102 min-max theorem, 104 of random matrices, 124, 139, 267 vectors, 102 Slepian inequality, 199, 202 Small ball method, 253 probability, 51, 91 Soft thresholding, 94 Sparse recovery, 278, 296, 297 exact, 281, 283, 296, 297 Special orthogonal group, 148 Spectral clustering, 123, 128, 140, 160 decomposition, 63, 154 projection, 107, 132 Spherical distribution, 68, 70, 74, 93, 94, 210, 220 marginals, 94 width, 210, 211, 214 Stable rank, 164, 220 Standard deviation, 11 score, 65, 91 Stirling approximation, 19, 20 Stochastic block model, 120, 123, 160, 170 dominance, 54, 199 Subexponential distribution, 43–45, 57 norm, 45 Subgaussian distribution, 36, 38, 39, 53, 54, 56, 95 entropy, 97 marginals, 95 rotation invariance, 95 increments, 223, 263, 286 norm, 38, 55 exact, 56 projection, 268, 293 random vector, 73 variance, 57 Submatrix, 130, 188 Sudakov inequality, 207, 208, 254 Sudakov-Fernique inequality, 204, 206, 208 Support function, 285, 299 | 术语表 |
| Symmetric group, 148 distributions, 179 | |
| Symmetrization, 180, 185, 190, 191, 217 for empirical processes, 255 | |
| Tails, 15 Gaussian, 26, 50 Poisson, 31, 51, 58 | |
| Talagrand comparison inequality, 249, 250, 260 concentration inequality, 150 | |
| Tensor, 85 | |
| Thin shell phenomenon, 6, 7, 61, 89, 90 | |
| Trace, 63 inequalities, 155, 156 | |
| Truncation, 50, 78 | |
| Type, 191 | |
| Unconstrained optimization, 277, 295 | |
| Union bound, 12, 35 | |
| Variance, 10 | |
| VC dichotomy, 256 dimension, 232, 238, 239 circles, 255 half-planes, 233 half-spaces, 234 of the union, 256 polygons, 256 squares, 256 stability, 236 strips, 237 generalization bound, 244 law of large numbers, 239 stability, 256 | 术语表 |
| Volume of the lP ball, 136 of the Euclidean ball, 134, 135 of the simplex, 134 | |
| Walsh matrix, 131 | |
| Wasserstein distance, 231 | |
| Wedin theorem, 132 | |
| Weyl inequality, 107 |