全书定理依赖图
全书定理依赖图
这张图不按章节目录重复罗列，而按“读懂后续结果需要先掌握什么”来组织。初学者可以把它当成全书路线图：先看每条链的起点，再回到对应章节补证明。
主干路线
| 路线 | 起点 | 中段工具 | 终点应用 |
|---|---|---|---|
| 集中不等式路线 | 第 1 章概率工具、第 2 章独立和集中 | 次高斯、次指数、Bernstein、Chernoff | 第 3 章随机向量薄壳、第 4 章随机矩阵谱范数、第 6 章二次型 |
| 几何离散化路线 | Appetizer 的近似 Caratheodory、第 4 章 net | covering/packing、epsilon-net、体积法 | 随机矩阵一致控制、随机投影、矩阵偏差 |
| 随机过程路线 | 第 7 章 Gaussian process | Slepian、Sudakov-Fernique、Gordon、Gaussian width | 第 8 章 chaining、经验过程、第 9 章 matrix deviation |
| chaining 路线 | Dudley inequality | empirical process、VC dimension、generic chaining | Chevet inequality、一般范数偏差、Dvoretzky-Milman |
| 几何恢复路线 | matrix deviation inequality | $M^*$ bound、escape theorem、tangent cone | 压缩感知、RIP、低秩/稀疏恢复 |
依赖链 1：从独立和到矩阵偏差
| 读到这里 | 需要先会 | 后面怎么用 |
|---|---|---|
| 第 2 章：独立和集中 | Markov、MGF、Chernoff 优化、Bernstein 二阶段尾界 | 作为所有“固定方向”概率界的来源。 |
| 第 3 章：高维随机向量 | 次高斯一维投影、各向同性、薄壳现象 | 把随机向量投影到固定方向，再用 union bound 或 net 升级。 |
| 第 4 章：随机矩阵 | net argument、operator norm、singular value | 从固定向量控制升级到所有向量控制。 |
| 第 6 章：二次型与对称化 | decoupling、Hanson-Wright、symmetrization、contraction | 为协方差估计和经验过程提供二次型控制。 |
| 第 9 章：矩阵偏差 | Gaussian width、subgaussian increments、chaining 思想 | 一次性控制集合 $T$ 上的 $\|Ax\|_2$ 偏差。 |
依赖链 2：从 net 到 chaining
| 阶段 | 关键问题 | 技术升级 |
|---|---|---|
| 第 4 章 net | 如何把无穷集合变成有限集合？ | 用 epsilon-net 把 operator norm 等问题化成有限并集界。 |
| 第 7 章 Gaussian width | 有限并集界太粗时，如何衡量集合大小？ | 用 $w(T)=\mathbb E\sup_{x\in T}\langle g,x\rangle$ 表示随机方向能看见的大小。 |
| 第 8 章 Dudley | 如果集合有多尺度结构，单尺度 net 不够怎么办？ | 把所有尺度覆盖数积分起来。 |
| 第 8 章 generic chaining | Dudley 仍可能浪费时，如何沿最优树状近似走？ | 用 $\gamma_2(T)$ 表示最佳多尺度路径代价。 |
| 第 9 章 general deviation | 如何把 Gaussian/chaining 工具用于一般范数？ | 用增量控制和 Talagrand comparison 推出统一偏差界。 |
依赖链 3：从几何到数据科学应用
| 应用 | 前置理论 | 关键转化 |
|---|---|---|
| Johnson-Lindenstrauss | 随机投影、矩阵偏差、Gaussian width | 点集差向量集合的复杂度是 $\sqrt{\log N}$。 |
| PCA / covariance estimation | 薄壳、Hanson-Wright、矩阵谱范数 | 样本协方差偏差是随机矩阵二次型问题。 |
| stochastic block model | operator norm perturbation、Davis-Kahan | 先控噪声谱范数，再控特征空间扰动。 |
| sparse recovery | escape theorem、tangent cone、Gaussian width | 恢复成功等价于随机核空间避开坏锥。 |
| Dvoretzky-Milman | Chevet、general deviation、support function | 随机投影后的凸体近似 Euclidean ball。 |
第一遍主线阅读路径
如果只想先抓住全书骨架，建议第一遍按下面路径读；完整四层读法见 全书分层阅读路线：
- 第 2 章：Hoeffding、Chernoff、Bernstein、次高斯/次指数等价刻画。
- 第 4 章：epsilon-net 控制 operator norm，以及固定方向到所有方向的升级。
- 第 7 章：Slepian/Sudakov-Fernique/Gordon 与 Gaussian width。
- 第 8 章：Dudley inequality、VC law、generic chaining。
- 第 9 章：matrix deviation、$M^*$ bound、escape theorem、Dvoretzky-Milman。
与学习笔记的关系
每章学习笔记的“本章主线”解决局部顺序问题；本页解决跨章依赖问题。读证明卡住时，优先回到本页找前置工具，再跳回对应章节。