翻译状态说明
本页为第 9 章的结构化精校翻译，覆盖正文、Notes、Exercises 9.1-9.43、原书 Figure 9.1-9.10，并为正式证明、正文隐藏验证和习题加入学习笔记证明跳转。
第 9 章 Deviations of Random Matrices on Sets
固定一个向量 $x\in\mathbb R^n$ 时，若 $A$ 是 $m\times n$ 随机矩阵，行独立、isotropic 且 subgaussian，则 norm concentration 告诉我们
$$ \|Ax\|_2\approx \sqrt m\|x\|_2. \tag{9.1} $$
本章问一个更强的问题：这个近似能否同时对集合 $T\subset\mathbb R^n$ 中所有 $x$ 成立？答案由 $T$ 的 Gaussian complexity 控制。第 9.1 节给出 matrix deviation inequality；后续章节把它依次应用到 random projections、covariance estimation、Johnson-Lindenstrauss、random sections、linear inverse problems、sparse recovery、general norm deviations、two-sided Chevet 和 Dvoretzky-Milman theorem。
9.1 Matrix deviation inequality
令 $A$ 为 $m\times n$ 随机矩阵，行 $A_i$ 独立、isotropic 且 subgaussian。则对任意 $T\subset\mathbb R^n$，
$$\mathbb E\sup_{x\in T}\left|\|Ax\|_2-\sqrt m\|x\|_2\right|\le CK^2\gamma(T),$$其中 $\gamma(T)$ 是 Gaussian complexity，$K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Theorem 9.1.1 完整证明证明计划是把
$$ Z_x=\|Ax\|_2-\sqrt m\|x\|_2 \tag{9.2} $$
看成由 $x$ 索引的随机过程，并用第 8 章 Talagrand comparison 的几何形式。关键是验证该过程具有 subgaussian increments。
在 Theorem 9.1.1 的假设下，过程 (9.2) 满足
$$\|Z_x-Z_y\|_{\psi_2}\le CK^2\|x-y\|_2,\qquad x,y\in\mathbb R^n.$$ 查看学习笔记：Theorem 9.1.2 完整证明Theorem 9.1.2 的证明分四步：先处理 $x$ 为单位向量、$y=0$；再对单位向量比较 squared norms；接着回到原始 norm；最后用齐次性和投影到球面处理一般 $x,y$。
Theorem 9.1.1 可通过 centering 得到围绕 $\mathbb E\|Ax\|_2$ 的版本；通过高概率 Talagrand comparison 得到 tail bound；也可推出 quadratic process $\|Ax\|_2^2-m\|x\|_2^2$ 的偏差界。
查看 Exercise 9.2 查看 Exercise 9.39.2 Random matrices, covariance estimation, and Johnson-Lindenstrauss
9.2.1 Singular values of random matrices
取 $T=S^{n-1}$，matrix deviation inequality 给出
$$ \sup_{x\in S^{n-1}}\left|\|Ax\|_2-\sqrt m\right| \lesssim K^2\sqrt n, $$
这等价于随机矩阵奇异值集中在 $\sqrt m$ 附近。
9.2.2 Random projections of sets
令 $P=A/\sqrt n$ 为 subgaussian projection。对有界集合 $T\subset\mathbb R^n$，投影后直径由 $\sqrt{m/n}\operatorname{diam}(T)$ 与 spherical width $w_s(T)$ 共同控制。
查看学习笔记：Proposition 9.2.1 完整证明该命题把第 7.6 节的 random projection phase transition 推广到 subgaussian matrices。
9.2.3 Covariance estimation for low-dimensional distributions
若 $X$ 是 subgaussian random vector，$\Sigma=\mathbb EXX^{\mathsf T}$，$\Sigma_m=m^{-1}\sum_{i=1}^mX_iX_i^{\mathsf T}$，且 $r=\operatorname{tr}(\Sigma)/\|\Sigma\|$，则
$$\mathbb E\|\Sigma_m-\Sigma\|\le CK^4\left(\sqrt{\frac rm}+\frac rm\right)\|\Sigma\|.$$ 查看学习笔记：Theorem 9.2.2 完整证明证明把分布写成 $X=\Sigma^{1/2}Z$，其中 $Z$ isotropic。然后把 sample covariance operator norm 写成 ellipsoid $T=\Sigma^{1/2}S^{n-1}$ 上的 quadratic matrix deviation。
9.2.4 Johnson-Lindenstrauss lemma for infinite sets
若 $\mathcal X\subset\mathbb R^n$ 有界，$Q=A/\sqrt m$，则以高概率
$$\left|\|Qx-Qy\|_2-\|x-y\|_2\right|\le \delta,\qquad x,y\in\mathcal X,$$其中 $\delta=CK^2w(\mathcal X)/\sqrt m$。
查看学习笔记：Lemma 9.2.4 完整证明有限集的经典 JL lemma 是该结果的相对误差版本；无限集只能期待 additive error，尺度由 Gaussian width 控制。
9.3 Random sections: the $M^*$ bound and escape theorem
9.3.1 The $M^*$ bound
令 $E=\ker A$，其中 $A$ 的行独立、isotropic 且 subgaussian。则任意有界 $T\subset\mathbb R^n$ 满足
$$\mathbb E\operatorname{diam}(T\cap E)\le \frac{CK^2w(T)}{\sqrt m}.$$ 查看学习笔记：Theorem 9.3.1 完整证明证明直接对 $T-T$ 应用 matrix deviation inequality；当 $x,y\in T\cap\ker A$ 时，$\|Ax-Ay\|_2=0$，于是可反推出 $\|x-y\|_2$ 的上界。
9.3.2 The escape theorem
若 $T\subset S^{n-1}$ 且
$$m\ge CK^4w(T)^2,$$则 $E=\ker A$ 以概率至少 $1-2e^{-cm/K^4}$ 满足 $T\cap E=\varnothing$。
查看学习笔记：Theorem 9.3.4 完整证明
9.4 Application: high-dimensional linear models
线性观测模型写成
$$ y=Ax+w, $$
其中 $A$ 已知，$w$ 是噪声，目标是恢复高维向量 $x$。
9.4.1 Constrained recovery
若 $x\in T$ 且 $y=Ax$，用约束程序在 $T$ 中寻找满足 $Ax'=y$ 的解 $\hat x$，则
$$\mathbb E\|\hat x-x\|_2\lesssim \frac{K^2w(T)}{\sqrt m}.$$ 查看学习笔记：Theorem 9.4.4 完整证明
9.4.2 Example: sparse recovery
若未知向量 $x$ 是 $s$-sparse，$\|x\|_2\le1$，则 $\ell^1$ 约束恢复满足
$$\mathbb E\|\hat x-x\|_2\lesssim K^2\sqrt{\frac{s\log n}{m}}.$$ 查看学习笔记：Corollary 9.4.8 完整证明更紧的 convexification 可把 $\log n$ 改进为 $\log(en/s)$；对应练习见 Exercises 9.25-9.27。
9.4.3 Example: low-rank recovery
若 $d\times d$ 矩阵 $X$ 的 rank 至多 $r$ 且 $\|X\|_F\le1$，Gaussian linear measurements 下 nuclear-norm constrained recovery 满足
$$\mathbb E\|\hat X-X\|_F\lesssim \sqrt{\frac{rd}{m}}.$$ 查看学习笔记：Corollary 9.4.11 完整证明9.5 Application: exact sparse recovery
9.5.1 Exact recovery based on the escape theorem
若 $m\gtrsim K^4s\log(en/s)$，则随机矩阵 $A$ 以高概率能通过 basis pursuit 精确恢复所有 $s$-sparse 向量。
查看学习笔记：Theorem 9.5.1 完整证明几何上，exact recovery 等价于随机 null space 与 $\ell^1$ ball 在 $x$ 处的 tangent cone 只在原点相交。
若 $\hat x$ 是 $\ell^1$ 最小化解，误差 $h=\hat x-x$ 在 $x$ 的 support 上不会太小；进一步，$h$ 可被控制在 approximate sparse set 中。
Lemma 9.5.2 Lemma 9.5.39.5.2 Restricted isometries
矩阵 $A$ 对 $s$-sparse vectors 满足 restricted isometry property，若它在所有 $s$-sparse 向量上近似保持 Euclidean norm。
若 $A$ 满足足够阶数和常数的 RIP，则每个 $s$-sparse vector 都可由 $\ell^1$ minimization 精确恢复。
查看学习笔记：Theorem 9.5.6 完整证明若 $m\gtrsim K^4s\log(en/s)$，则 isotropic subgaussian random matrices 以高概率满足 $s$-sparse 集合上的 RIP。
查看学习笔记：Theorem 9.5.7 完整证明9.6 Deviations of random matrices for general norms
这里允许 $f$ 不是非负 norm，但要求 positive homogeneous 与 subadditive，并满足 $f(x)\le b\|x\|_2$。
若 $A$ 是 i.i.d. Gaussian matrix，$f$ positive homogeneous、subadditive 且 $f(x)\le b\|x\|_2$，则
$$\mathbb E\sup_{x\in T}|f(Ax)-\mathbb Ef(Ax)|\le Cb\gamma(T).$$ 查看学习笔记：Theorem 9.6.3 完整证明过程 $Z_x=f(Ax)-\mathbb Ef(Ax)$ 满足
$$\|Z_x-Z_y\|_{\psi_2}\le Cb\|x-y\|_2.$$ 查看学习笔记：Theorem 9.6.4 完整证明
9.7 Two-sided Chevet inequality and Dvoretzky-Milman theorem
9.7.1 Two-sided Chevet inequality
若 $A$ 为 i.i.d. Gaussian matrix，$T\subset\mathbb R^n$、$S\subset\mathbb R^m$ 有界，则
$$\mathbb E\sup_{x\in T}\left|\sup_{y\in S}\langle Ax,y\rangle-w(S)\|x\|_2\right| \le C\gamma(T)\operatorname{rad}(S).$$ 查看学习笔记：Theorem 9.7.1 完整证明9.7.2 Dvoretzky-Milman Theorem
若 $A$ 为 $m\times n$ i.i.d. Gaussian matrix，$T\subset\mathbb R^n$ 有界，则以概率至少 $0.99$，
$$r_-B_2^m\subset \operatorname{conv}(AT)\subset r_+B_2^m,$$其中 $r_\pm=w(T)\pm C\sqrt m\,\operatorname{rad}(T)$。
查看学习笔记：Theorem 9.7.2 完整证明
若 $m\lesssim d(T)\asymp w(T)^2/\operatorname{rad}(T)^2$，随机投影后的凸包接近 Euclidean ball。与第 7.6 和第 9.2.2 节结合，可看到随机投影在 effective dimension 附近发生相变。
9.8 Notes
Matrix deviation inequality 是本章的主引擎，它把第 8 章的 Talagrand comparison 与随机矩阵问题结合起来。$M^*$ bound、escape theorem、compressed sensing、RIP、general norm deviations、two-sided Chevet 和 Dvoretzky-Milman theorem 都可看作同一原则的不同投影。
Exercises
这些题补 exact recovery 几何、noisy exact recovery、nullspace property、random projection RIP、subadditivity、anisotropic/general high-probability deviation、general norm JL、$\ell^1/\ell^\infty$ embeddings、duality、high-probability Dvoretzky、Gaussian cloud 与 true projection version。
9.30 9.31 9.32 9.33 9.34 9.35 9.36 9.37 9.38 9.39 9.40 9.41 9.42 9.43