翻译状态说明
本页为第 5 章的精校翻译，覆盖正文、Notes、Exercises 5.1-5.32、原书 Figure 5.1-5.2，并为原文明确证明、正文隐藏验证和习题加入学习笔记证明跳转。
第 5 章 无独立性的集中
到目前为止，我们研究集中不等式时严重依赖随机变量之间的独立性。现在，我们转向另外一类方法：它们不依赖独立性。第 5.1 节以 Euclidean 球面为例，引入等周不等式方法；第 5.2 节再介绍其他度量测度空间上的集中现象。
第 5.3 节利用球面上的集中推出经典的 Johnson-Lindenstrauss 引理，这是高维数据降维中的核心结果。
第 5.4 节介绍矩阵集中不等式，重点是矩阵 Bernstein 不等式，它把经典 Bernstein 不等式推广到随机矩阵。第 5.5 与 5.6 节再把这一工具用于稀疏网络中的社群检测，以及更一般分布下的协方差估计。
不要跳过习题。本章习题会研究二值随机投影的降维版本（Exercise 5.14）、矩阵函数演算（Exercises 5.16-5.19）、多个矩阵集中不等式（Exercises 5.20-5.24），以及矩阵 sketching（Exercise 5.32）、社群检测（Exercise 5.25）等应用。
5.1 球面上 Lipschitz 函数的集中
给定随机向量 $X\in\mathbb R^n$ 和函数 $f:\mathbb R^n\to\mathbb R$，什么时候随机变量 $f(X)$ 会集中，即
$$ f(X)\approx \mathbb Ef(X) \qquad \text{with high probability}? $$
如果 $X$ 是正态向量且 $f$ 是线性函数，这很容易：$f(X)$ 仍是正态随机变量（Corollary 3.3.2），并且有很好的集中（Proposition 2.1.2）。
非线性函数 $f$ 呢？不能指望任意函数都有好集中；例如函数可以在极小区域内剧烈振荡。
不过，如果 $f$ 的振荡不太剧烈，我们就可以期待集中。为精确表达这一点，我们引入 Lipschitz 函数。它们正是用来排除极端振荡的。
5.1.1 Lipschitz 函数
设 $(X,d_X)$ 和 $(Y,d_Y)$ 是度量空间。如果存在 $L\in\mathbb R$，使得对所有 $u,v\in X$ 都有
$$ d_Y(f(u),f(v))\le L\,d_X(u,v), $$则称函数 $f:X\to Y$ 是 Lipschitz 的。所有这类 $L$ 的下确界称为 $f$ 的 Lipschitz 范数，记为 $\|f\|_{\mathrm{Lip}}$。
换句话说，Lipschitz 函数不会把距离拉得太大。当 $\|f\|_{\mathrm{Lip}}\le1$ 时，它们是 contraction，因为它们只会缩短距离。Lipschitz 函数位于可微函数和一致连续函数之间：
$$ f\text{ 可微} \Longrightarrow f\text{ Lipschitz} \Longrightarrow f\text{ 一致连续}. $$
在 Exercise 5.1 中，你还会对 $f:\mathbb R^n\to\mathbb R$ 定量化第一个蕴含：
$$ \|f\|_{\mathrm{Lip}} \le \sup_{x\in\mathbb R^n}\|\nabla f(x)\|_2. $$
(a) 固定 $\theta\in\mathbb R^n$。线性泛函
$$ f(x)=\langle x,\theta\rangle $$的 Lipschitz 范数为 $\|f\|_{\mathrm{Lip}}=\|\theta\|_2$。
(b) 更一般地，对任意 $m\times n$ 矩阵 $A$，线性算子 $f(x)=Ax$ 的 Lipschitz 范数为 $\|A\|$。
(c) 对 $\mathbb R^n$ 上任意范数 $\|\cdot\|$，函数 $f(x)=\|x\|$ 的 Lipschitz 范数等于最小的 $L$，使得
$$ \|x\|\le L\|x\|_2 \qquad \text{for all }x\in\mathbb R^n. $$ 查看学习笔记：Example 5.1.2 验证5.1.2 通过等周不等式得到集中
我们现在证明 Euclidean 球面
$$ S^{n-1}=\{x\in\mathbb R^n:\|x\|_2=1\} $$
上的任意 Lipschitz 函数都会集中。
设 $X$ 均匀分布在半径为 $\sqrt n$ 的 Euclidean 球面上，即 $X\sim\operatorname{Unif}(\sqrt n S^{n-1})$。那么，对任意 Lipschitz 函数 $f:\sqrt n S^{n-1}\to\mathbb R$，都有
$$ \|f(X)-\mathbb Ef(X)\|_{\psi_2} \le C\|f\|_{\mathrm{Lip}}. $$等价地，对所有 $t\ge0$，
$$ \mathbb P\{|f(X)-\mathbb Ef(X)|\ge t\} \le 2\exp\left(-\frac{ct^2}{\|f\|_{\mathrm{Lip}}^2}\right). $$我们已经在线性函数情形证明过 Theorem 5.1.3。Theorem 3.4.5 告诉我们，$X$ 是次高斯随机向量；按定义，$X$ 的任意线性函数都是次高斯随机变量。
为了完全证明 Theorem 5.1.3，需要说明任意 Lipschitz 函数至少像线性函数一样集中。我们不直接比较函数值，而是比较它们的 sublevel sets，即给定水平 $a$ 时球面上满足 $f(x)\le a$ 的区域。对线性函数而言，这些区域就是 spherical caps。比较一般集合和 spherical caps 的面积，需要一个重要几何原则：等周不等式。
在 $\mathbb R^n$ 中，在所有给定体积的集合 $A$ 里，Euclidean 球具有最小表面积。更强地，对任意 $\varepsilon>0$，Euclidean 球也使 $A$ 的 $\varepsilon$-邻域体积最小，其中
$$ A_\varepsilon = \{x\in\mathbb R^n:\exists y\in A,\ \|x-y\|_2\le\varepsilon\} = A+\varepsilon B_2^n. $$Theorem 5.1.4 的“更强”部分推出第一部分；令 $\varepsilon\to0$ 即可看出。Figure 5.1 给出了等周不等式的示意。
球面 $S^{n-1}$ 上也有类似等周不等式，此时最小化者是 spherical caps，也就是某个点的邻域。用 $\sigma_{n-1}$ 表示球面 $S^{n-1}$ 上的归一化面积测度。
设 $\varepsilon>0$。在所有具有给定面积 $\sigma_{n-1}(A)$ 的集合 $A\subset S^{n-1}$ 中，spherical caps 使邻域面积 $\sigma_{n-1}(A_\varepsilon)$ 最小，其中
$$ A_\varepsilon = \{x\in S^{n-1}:\exists y\in A,\ \|x-y\|_2\le\varepsilon\}. $$本书不证明等周不等式（Theorem 5.1.4 与 5.1.5）；本章 bibliographic notes 会给出若干已知证明的参考。
5.1.3 球面上集合的 blow-up
等周不等式推出一个非常反直觉的现象：如果集合 $A$ 至少覆盖球面一半面积，那么它的 $\varepsilon$-邻域 $A_\varepsilon$ 会覆盖球面的大部分。我们先陈述并证明这个 blow-up 现象，然后解释直觉。为了适配 Theorem 5.1.3，我们在半径为 $\sqrt n$ 的球面上工作。
设 $A\subset\sqrt n S^{n-1}$，$\sigma$ 是该球面上的归一化面积测度。若 $\sigma(A)\ge1/2$，则对所有 $t\ge0$，
$$ \sigma(A_t)\ge1-2\exp(-ct^2). $$ 查看学习笔记完整证明考虑第一坐标定义的半球
$$ H=\{x\in\sqrt n S^{n-1}:x_1\le0\}. $$由假设 $\sigma(A)\ge1/2=\sigma(H)$，球面等周不等式给出
$$ \sigma(A_t)\ge\sigma(H_t). \tag{5.1} $$$H_t$ 是半球 $H$ 的邻域。直接计算 spherical cap 面积可以完成证明，但更方便的是用 Theorem 3.4.5：若 $X\sim\operatorname{Unif}(\sqrt n S^{n-1})$，则 $X$ 是次高斯随机向量，且 $\|X\|_{\psi_2}\le C$。
由于 $\sigma$ 是球面均匀概率测度，
$$ \sigma(H_t)=\mathbb P\{X\in H_t\}. $$邻域定义推出
$$ H_t\supset \{x\in\sqrt n S^{n-1}:x_1\le t/\sqrt2\}. \tag{5.2} $$ 查看学习笔记：为什么 (5.2) 成立于是
$$ \sigma(H_t) \ge \mathbb P\{X_1\le t/\sqrt2\} \ge 1-2\exp(-ct^2). $$最后一个不等式来自 $\|X_1\|_{\psi_2}\le\|X\|_{\psi_2}\le C$。结合 (5.1)，引理得证。
Lemma 5.1.6 中面积为 $1/2$ 的数值不是本质的。它可以替换为任意常数，甚至可以替换为指数级小的量。Exercise 5.3 会让你验证这一点。
刚才看到的 blow-up 现象一开始可能很反直觉。一个指数级小的集合 $A$，为什么只在 $2t$ 的小扰动下就变成指数级大的集合 $A_{2t}$？这里 $t$ 可以远小于球面半径 $\sqrt n$。这正是高维空间的典型现象，类似概率论中的零一律：由许多随机变量共同影响的事件，概率往往接近 $0$ 或 $1$。
5.1.4 Theorem 5.1.3 的证明
不失一般性，假设 $\|f\|_{\mathrm{Lip}}=1$。
令 $M$ 是 $f(X)$ 的一个中位数，即
$$ \mathbb P\{f(X)\le M\}\ge\frac12, \qquad \mathbb P\{f(X)\ge M\}\ge\frac12. $$
考虑 sublevel set
$$ A=\{x\in\sqrt n S^{n-1}:f(x)\le M\}. $$
因为 $\mathbb P\{X\in A\}\ge1/2$，Lemma 5.1.6 给出
$$ \mathbb P\{X\in A_t\} \ge 1-2\exp(-ct^2). \tag{5.3} $$
另一方面，我们声称
$$ \mathbb P\{X\in A_t\} \le \mathbb P\{f(X)\le M+t\}. \tag{5.4} $$
确实，若 $X\in A_t$，则存在 $y\in A$ 使得 $\|X-y\|_2\le t$。由 $A$ 的定义，$f(y)\le M$。又因为 $\|f\|_{\mathrm{Lip}}=1$，
$$ f(X)\le f(y)+\|X-y\|_2\le M+t. $$
这就证明了 (5.4)。结合 (5.3) 和 (5.4)，得到
$$ \mathbb P\{f(X)\le M+t\} \ge 1-2\exp(-ct^2). $$
对 $-f$ 重复同样论证，可得到 $f(X)\ge M-t$ 的概率下界。
合并两侧尾界，得到 $|f(X)-M|\le t$ 的类似概率界，从而
$$ \|f(X)-M\|_{\psi_2}\le C. $$
最后把中位数 $M$ 替换为均值 $\mathbb Ef(X)$，这可由中心化和 Lemma 2.7.8 得到。
Theorem 5.1.3 得证。Exercise 5.7 会让你反向证明：集中现象与 blow-up 现象本质上等价。
5.2 其他度量测度空间上的集中
我们现在把球面上的集中推广到其他空间。Theorem 5.1.3 的证明依赖两个成分：
- 一个等周不等式。
- 最小化集合的 blow-up。
这两个成分并非球面独有；许多空间都有类似结构，因此也有类似集中结论。下面介绍两个关键例子：$\mathbb R^n$ 中的 Gaussian concentration，以及 Hamming cube 上的集中；之后再简要提到其他情形。
集中意味着均值、中位数和 $L^p$ 范数彼此接近。因此，可以把 $\mathbb Ef(X)$ 替换为中位数（Exercise 5.6）；若均值非负，也可以替换为任意 $p\ge1$ 的 $L^p$ 范数，不过常数可能依赖 $p$（Exercise 5.10）。
5.2.1 Gaussian concentration
Theorem 5.1.4 中 $\mathbb R^n$ 上的经典等周不等式不仅对体积成立，也对 $\mathbb R^n$ 上的 Gaussian measure 成立。对 Borel 集 $A\subset\mathbb R^n$，Gaussian measure 定义为
$$ \gamma_n(A) = \mathbb P\{X\in A\} = \frac1{(2\pi)^{n/2}}\int_A e^{-\|x\|_2^2/2}\,dx, $$
其中 $X\sim N(0,I_n)$。
设 $\varepsilon>0$。在所有具有给定 Gaussian measure $\gamma_n(A)$ 的集合 $A\subset\mathbb R^n$ 中，half-spaces 使邻域 Gaussian measure $\gamma_n(A_\varepsilon)$ 最小。
用与球面相同的方法，可以推出下面的 Gaussian concentration inequality（见 Exercise 5.8）。
设 $X\sim N(0,I_n)$，并设 $f:\mathbb R^n\to\mathbb R$ 是关于 Euclidean 距离的 Lipschitz 函数。则
$$ \|f(X)-\mathbb Ef(X)\|_{\psi_2} \le C\|f\|_{\mathrm{Lip}}. \tag{5.5} $$ 查看学习笔记：由 Gaussian 等周推出集中(a) 对线性函数 $f$，结论来自 $X\sim N(0,I_n)$ 是次高斯随机向量。
(b) 对 Euclidean 范数 $f(x)=\|x\|_2$，结论来自 norm concentration（Theorem 3.1.1）。
Exercise 5.9 会让你用 Gaussian concentration 证明 $n$ 个 Gaussian 最大值的集中。
5.2.2 Hamming cube
基于等周的集中方法也适用于 Hamming cube
$$ (\{0,1\}^n,d,\mathbb P), $$
其中 $d(x,y)$ 是归一化 Hamming 距离：
$$ d(x,y)=\frac1n|\{i:x_i\ne y_i\}|. $$
测度 $\mathbb P$ 是 cube 上的均匀概率测度：
$$ \mathbb P(A)=\frac{|A|}{2^n}, \qquad A\subset\{0,1\}^n. $$
设 $X\sim\operatorname{Unif}\{0,1\}^n$。因此，$X$ 的坐标是独立的 $\operatorname{Ber}(1/2)$ 随机变量。则对任意 $f:\{0,1\}^n\to\mathbb R$，有
$$ \|f(X)-\mathbb Ef(X)\|_{\psi_2} \le \frac{C\|f\|_{\mathrm{Lip}}}{\sqrt n}. \tag{5.6} $$这一结论来自 Hamming cube 上的等周不等式，其最小化者是 Hamming balls，即关于 Hamming 距离的单点邻域。
5.2.3 对称群
类似结论也适用于对称群 $S_n$，即 $n$ 个符号 $\{1,\ldots,n\}$ 的全部 $n!$ 个排列。把它看成度量测度空间
$$ (S_n,d,\mathbb P), $$
其中 $d(\pi,\rho)$ 是归一化 Hamming 距离：
$$ d(\pi,\rho)=\frac1n|\{i:\pi(i)\ne\rho(i)\}|, $$
而 $\mathbb P$ 是 $S_n$ 上的均匀概率测度：
$$ \mathbb P(A)=\frac{|A|}{n!}. $$
设 $X\sim\operatorname{Unif}(S_n)$，并设 $f:S_n\to\mathbb R$。则集中不等式 (5.6) 成立。
5.2.4 正 Ricci 曲率 Riemannian 流形
Riemannian 流形提供了许多集中空间的例子。如果你不关注微分几何，可以跳过这一节剩余内容。
紧连通 Riemannian 流形 $(M,g)$ 带有 geodesic distance $d(x,y)$，即连接两点的最短曲线长度。它可看成度量测度空间
$$ (M,d,\mathbb P), $$
其中 $\mathbb P$ 是归一化 Riemannian 体积给出的均匀概率测度。令 $c(M)$ 表示 Ricci curvature tensor 在所有切向量上的下确界。若 $c(M)>0$，则可证明对任意 Lipschitz 函数 $f:M\to\mathbb R$，
$$ \|f(X)-\mathbb Ef(X)\|_{\psi_2} \le \frac{C\|f\|_{\mathrm{Lip}}}{\sqrt{c(M)}}. \tag{5.7} $$
例如 $c(S^{n-1})=n-1$，因此 (5.7) 给出单位球面集中不等式 (5.29) 的另一种证明。
5.2.5 特殊正交群
特殊正交群 $\operatorname{SO}(n)$ 由 $\mathbb R^n$ 中所有旋转组成，等价地说，是所有行列式为 $1$ 的 $n\times n$ 正交矩阵。把它看成度量测度空间
$$ (\operatorname{SO}(n),\|\cdot\|_F,\mathbb P), $$
距离由 Frobenius 范数给出，$\mathbb P$ 是均匀测度。
设随机正交矩阵 $X\sim\operatorname{Unif}(\operatorname{SO}(n))$，并设 $f:\operatorname{SO}(n)\to\mathbb R$。则集中不等式 (5.6) 成立。
生成 $X\sim\operatorname{Unif}(\operatorname{SO}(n))$ 的一种方法是：先取 $n\times n$ Gaussian 随机矩阵 $G$，其 entries 独立同分布为 $N(0,1)$；再计算 SVD $G=U\Sigma V^{\mathsf T}$，令 $X=UV^{\mathsf T}$。这样得到的 $X$ 均匀分布在 $\operatorname{SO}(n)$ 上。
$\operatorname{SO}(n)$ 上的均匀概率分布为
$$ \mu(A)=\mathbb P\{X\in A\}. $$它是唯一的 rotation-invariant probability measure，称为 Haar measure。
查看学习笔记：旋转不变性检查5.2.6 Grassmannian
Grassmann 流形 $G_{n,m}$ 由 $\mathbb R^n$ 中所有 $m$ 维子空间组成。当 $m=1$ 时，它可与球面 $S^{n-1}$ 识别起来，因此 Grassmannian 上的集中包含球面集中。把 $G_{n,m}$ 看成度量测度空间
$$ (G_{n,m},d,\mathbb P), $$
其中子空间 $E$ 与 $F$ 的距离定义为
$$ d(E,F)=\|P_E-P_F\|, $$
$P_E$ 和 $P_F$ 是对应正交投影。概率测度 $\mathbb P$ 仍是均匀的 Haar probability measure。随机子空间 $E\sim\operatorname{Unif}(G_{n,m})$ 可通过 $n\times m$ Gaussian 随机矩阵 $G$ 的像空间构造。
设随机子空间 $X\sim\operatorname{Unif}(G_{n,m})$，并设 $f:G_{n,m}\to\mathbb R$。则集中不等式 (5.6) 成立。
5.2.7 连续 cube 与 Euclidean ball
对单位 Euclidean cube $[0,1]^n$ 和 Euclidean ball $\sqrt n B_2^n$，也有类似的集中不等式。这可通过把 Gaussian measure push forward 到 cube 或 ball 上的均匀测度来证明。证明留给 Exercises 5.12、5.13。
设 $T$ 是 cube $[0,1]^n$ 或 ball $\sqrt n B_2^n$。若 $X\sim\operatorname{Unif}(T)$，且 $f:T\to\mathbb R$ 是关于 Euclidean 距离的 Lipschitz 函数，则集中不等式 (5.5) 成立。
5.2.8 形如 $e^{-U(x)}$ 的密度
前一节的 push-forward 方法可用于 $\mathbb R^n$ 上许多其他分布。设随机向量 $X$ 有密度
$$ p(x)=e^{-U(x)} $$
其中 $U:\mathbb R^n\to\mathbb R$。例如，若 $X\sim N(0,I_n)$，则正态密度对应 $U(x)=\|x\|_2^2/2+c$，Gaussian concentration 成立。
如果一般函数 $U$ 的曲率至少像 $\|x\|_2^2$ 一样强，就应期待至少有 Gaussian concentration。$U$ 的曲率由 Hessian $\operatorname{Hess}U(x)$ 度量。
设随机向量 $X$ 在 $\mathbb R^n$ 中的密度为 $p(x)=e^{-U(x)}$。若存在 $\kappa>0$，使得对所有 $x\in\mathbb R^n$ 都有
$$ \operatorname{Hess}U(x)\succeq \kappa I_n, $$则任意 Lipschitz 函数 $f:\mathbb R^n\to\mathbb R$ 满足
$$ \|f(X)-\mathbb Ef(X)\|_{\psi_2} \le \frac{C\|f\|_{\mathrm{Lip}}}{\sqrt\kappa}. $$5.2.9 独立有界坐标的随机向量
还有一个重要的部分推广：设 $X=(X_1,\ldots,X_n)$ 的坐标独立，且坐标分布任意但有界。通过缩放，可假设 $|X_i|\le1$。
设 $X=(X_1,\ldots,X_n)$ 的坐标独立并满足 $|X_i|\le1$ a.s.。那么，对任意凸 Lipschitz 函数 $f:[-1,1]^n\to\mathbb R$，集中不等式 (5.5) 成立。
特别地，Talagrand concentration inequality 适用于 $\mathbb R^n$ 上任意范数。本书不证明该结果。
5.3 应用：Johnson-Lindenstrauss 引理
假设有 $N$ 个数据点位于 $\mathbb R^n$，而维度 $n$ 很大。能否在不严重损失数据几何结构的前提下降维？最简单的方法是把数据点投影到低维子空间
$$ E\subset\mathbb R^n, \qquad \dim(E)=m\ll n. $$
Figure 5.2 展示了这一想法。关键问题是：怎样选择子空间 $E$？维度 $m$ 可以多小？
Johnson-Lindenstrauss 引理说明，只要把 $E$ 选为维度
$$ m\asymp \log N $$
的随机子空间，就能很好地保留数据几何。
设 $\mathcal X$ 是 $\mathbb R^n$ 中含有 $N$ 个点的集合，$\varepsilon>0$，并假设
$$ m\ge C\varepsilon^{-2}\log N. $$令 $P$ 为 $\mathbb R^n$ 到随机 $m$ 维子空间 $E\sim\operatorname{Unif}(G_{n,m})$ 上的正交投影。则以至少
$$ 1-2\exp(-c\varepsilon^2m) $$的概率，缩放投影 $Q=\sqrt{n/m}\,P$ 在 $\mathcal X$ 上是近似等距：
$$ (1-\varepsilon)\|x-y\|_2 \le \|Qx-Qy\|_2 \le (1+\varepsilon)\|x-y\|_2 \quad \text{for all }x,y\in\mathcal X. \tag{5.8} $$ 查看学习笔记完整证明证明基于球面上 Lipschitz 函数的集中。先研究随机投影 $P$ 对固定向量 $x-y$ 的作用，再对所有 $N^2$ 个差向量做 union bound。
令 $P$ 是 $\mathbb R^n$ 到随机 $m$ 维子空间 $E\sim\operatorname{Unif}(G_{n,m})$ 上的投影。固定任意 $z\in\mathbb R^n$ 和 $\varepsilon>0$。则：
(a)
$$ \bigl(\mathbb E\|Pz\|_2^2\bigr)^{1/2} = \sqrt{\frac mn}\|z\|_2. $$(b) 以至少 $1-2\exp(-c\varepsilon^2m)$ 的概率，
$$ (1-\varepsilon)\sqrt{\frac mn}\|z\|_2 \le \|Pz\|_2 \le (1+\varepsilon)\sqrt{\frac mn}\|z\|_2. $$ 查看学习笔记完整证明不失一般性设 $\|z\|_2=1$。换一个视角：随机 $m$ 维子空间 $E$ 可由固定坐标子空间 $\mathbb R^m$ 随机旋转得到。等价地，可以固定 $E=\mathbb R^m$，随机旋转向量 $z$；此时 $z$ 均匀分布在 $S^{n-1}$ 上。由旋转不变性，$\|Pz\|_2$ 的分布不变。
查看学习笔记：随机子空间和随机向量视角等价(a) 此时 $P$ 投影到前 $m$ 个坐标，因此
$$ \mathbb E\|Pz\|_2^2 = \mathbb E\sum_{i=1}^m z_i^2 = m\mathbb Ez_1^2 = \frac mn. $$最后一步来自 $\sum_{i=1}^n z_i^2=1$ 且各坐标同分布。
(b) 函数 $x\mapsto\|Px\|_2$ 在 $S^{n-1}$ 上 Lipschitz 范数至多为 $1$。
查看学习笔记：投影范数函数是 1-Lipschitz由单位球面集中不等式 (5.30)，
$$ \mathbb P\left\{ \left|\|Px\|_2-\sqrt{m/n}\right|\ge t \right\} \le 2\exp(-cnt^2). $$这里用 Remark 5.2.1 把 $\mathbb E\|Px\|_2$ 换成 $(\mathbb E\|Px\|_2^2)^{1/2}$。取 $t=\varepsilon\sqrt{m/n}$，结论得证。
考虑差集
$$ \mathcal X-\mathcal X=\{x-y:x,y\in\mathcal X\}. $$我们希望以所需概率证明对所有 $z\in\mathcal X-\mathcal X$，
$$ (1-\varepsilon)\|z\|_2 \le \|Qz\|_2 \le (1+\varepsilon)\|z\|_2. $$由于 $Q=\sqrt{n/m}\,P$，这等价于
$$ (1-\varepsilon)\sqrt{\frac mn}\|z\|_2 \le \|Pz\|_2 \le (1+\varepsilon)\sqrt{\frac mn}\|z\|_2. \tag{5.10} $$对固定 $z$，Lemma 5.3.2 说明 (5.10) 失败的概率至多 $2\exp(-c\varepsilon^2m)$。对 $|\mathcal X-\mathcal X|\le N^2$ 个差向量做 union bound，可知 (5.10) 对所有差向量同时成立的概率至少为
$$ 1-N^2\cdot2\exp(-c\varepsilon^2m). $$若 $m\ge C\varepsilon^{-2}\log N$，上式至少为 $1-2\exp(-c\varepsilon^2m/2)$。调整常数即得定理。
Johnson-Lindenstrauss 引理的一个突出特征是：降维映射是非自适应的，不依赖数据本身。注意，数据的 ambient dimension $n$ 在维度条件里没有出现。后续 Sections 9.2.4 和 9.7 会发展更高级的 Johnson-Lindenstrauss 版本。
Johnson-Lindenstrauss 引理把维度降到 $O(\log N)$。还能不能更低，例如 $o(\log N)$？Exercise 5.15 会说明不能：即使允许非线性映射，$\log N$ 量级也是最优的。
Exercise 5.14 会让你证明 Johnson-Lindenstrauss 引理的次高斯矩阵版本。
5.4 矩阵 Bernstein 不等式
这里，我们把独立随机变量和 $\sum X_i$ 的集中不等式推广到独立随机矩阵和。矩阵 Bernstein 不等式是 Theorem 2.9.5 的矩阵版本：把随机变量 $X_i$ 换成随机矩阵，把绝对值 $|\cdot|$ 换成算子范数 $\|\cdot\|$。注意，每个随机矩阵 $X_i$ 内部的 entries、rows 或 columns 不需要独立，这是非常一般的假设。
设 $X_1,\ldots,X_N$ 是独立、均值为零的 $n\times n$ 对称随机矩阵，并且对所有 $i$，
$$ \|X_i\|\le K \quad\text{a.s.} $$则对所有 $t\ge0$，
$$ \mathbb P\left\{ \left\|\sum_{i=1}^N X_i\right\|\ge t \right\} \le 2n\exp\left( -\frac{t^2/2}{\sigma^2+Kt/3} \right), $$其中
$$ \sigma^2 = \left\|\sum_{i=1}^N \mathbb E X_i^2\right\| $$是矩阵和的 variance matrix 的算子范数。
等价地，右侧可写成次高斯与次指数混合尾：
$$ \mathbb P\left\{ \left\|\sum_{i=1}^N X_i\right\|\ge t \right\} \le 2n\exp\left[ -c\min\left(\frac{t^2}{\sigma^2},\frac tK\right) \right]. $$ 查看学习笔记完整证明证明思路很简单：重复第 2.9 节的 MGF 论证，只是把标量替换为矩阵。大部分步骤都可工作，唯一的主要挑战是矩阵乘法不可交换。因此先准备矩阵函数演算。
5.4.1 矩阵函数演算
对 $n\times n$ 对称矩阵 $X$，取逆、平方等运算只作用在特征值上，特征向量保持不变。若谱分解为
$$ X=\sum_{i=1}^n \lambda_i u_i u_i^{\mathsf T}, $$
则
$$ X^{-1}=\sum_i\lambda_i^{-1}u_iu_i^{\mathsf T}, \qquad X^2=\sum_i\lambda_i^2u_iu_i^{\mathsf T}, \qquad 2I_n-5X^3=\sum_i(2-5\lambda_i^3)u_iu_i^{\mathsf T}. \tag{5.11} $$
设 $f:\mathbb R\to\mathbb R$，且 $X$ 是 $n\times n$ 对称矩阵，谱分解为
$$ X=\sum_{i=1}^n\lambda_i u_i u_i^{\mathsf T}. $$定义
$$ f(X)=\sum_{i=1}^n f(\lambda_i)u_i u_i^{\mathsf T}. $$若 $X$ 是对称半正定矩阵，记 $X\succeq0$。进一步，若 $X-Y\succeq0$，则记 $X\succeq Y$ 或 $Y\preceq X$。
这是偏序而不是全序，因为有些矩阵之间既没有 $X\succeq Y$，也没有 $Y\succeq X$。
(a) 特征值单调性：$X\preceq Y$ 推出 $\lambda_i(X)\le\lambda_i(Y)$。
(b) Trace 单调性：若 $f:\mathbb R\to\mathbb R$ 弱增，则
$$ X\preceq Y \quad\Longrightarrow\quad \operatorname{tr}f(X)\le\operatorname{tr}f(Y). $$(c) 算子范数：
$$ \|X\|\le a \quad\Longleftrightarrow\quad -aI_n\preceq X\preceq aI_n, \qquad a\ge0. \tag{5.12} $$(d) 标量不等式升级为矩阵不等式：若对所有 $|x|\le a$ 都有 $f(x)\le g(x)$，则对所有 $\|X\|\le a$ 都有 $f(X)\preceq g(X)$。
查看学习笔记完整证明(5.12) 是标量事实 $|x|\le a\iff -a\le x\le a$ 的矩阵版本。这解释了为什么矩阵 Bernstein 不等式中自然出现算子范数。
能否把 Proposition 5.4.4(b) 的 trace monotonicity 升级为 matrix monotonicity，即
$$ X\preceq Y \quad\Longrightarrow\quad f(X)\preceq f(Y) \tag{5.13} $$对所有弱增函数 $f$ 成立？若 $X$ 与 $Y$ 交换，答案是肯定的；一般情形是否定的（Exercise 5.17）。不过某些函数确实是矩阵单调的，例如 $1/x$ 和 $\log x$：
$$ 0\preceq X\preceq Y \quad\Longrightarrow\quad X^{-1}\succeq Y^{-1}\succeq0, \qquad \log X\preceq\log Y. $$ 查看学习笔记：$1/x$ 和 $\log x$ 的矩阵单调性5.4.2 Trace inequalities
到目前为止，把标量概念推广到矩阵还比较顺利。但这并不总是成立。矩阵不可交换会使许多标量恒等式失效。例如标量恒等式 $e^{x+y}=e^xe^y$ 对矩阵一般不成立；Exercise 5.19 会让你找出 $n\times n$ 对称矩阵 $X,Y$，使得
$$ e^{X+Y}\ne e^Xe^Y. $$
这很麻烦，因为 $e^{x+y}=e^xe^y$ 正是标量 MGF 方法中分解和的关键。幸运的是，有一些 trace inequalities 可以替代缺失的恒等式。
对任意 $n\times n$ 对称矩阵 $A,B$，
$$ \operatorname{tr}(e^{A+B}) \le \operatorname{tr}(e^Ae^B). $$不过，Golden-Thompson 不等式不能直接推广到三个或更多矩阵。
设 $H$ 是 $n\times n$ 对称矩阵。定义正定矩阵上的函数
$$ f(X)=\operatorname{tr}\exp(H+\log X). $$则 $f$ 在正定 $n\times n$ 对称矩阵空间上是凹函数。
如果 $X$ 是随机矩阵，Lieb 与 Jensen 不等式推出
$$ \mathbb Ef(X)\le f(\mathbb EX). $$
令 $X=e^Z$，得到下面的形式。
设 $H$ 是固定的 $n\times n$ 对称矩阵，$Z$ 是随机 $n\times n$ 对称矩阵。则
$$ \mathbb E\operatorname{tr}\exp(H+Z) \le \operatorname{tr}\exp(H+\log\mathbb Ee^Z). $$5.4.3 矩阵 Bernstein 不等式的证明
设
$$ S=\sum_{i=1}^N X_i. $$
为了控制 $\|S\|$，需要分别控制 $S$ 的最大特征值和最小特征值。记
$$ \lambda_{\max}(S)=\max_i\lambda_i(S). $$
则
$$ \|S\| = \max_i|\lambda_i(S)| = \max(\lambda_{\max}(S),\lambda_{\max}(-S)). \tag{5.14} $$
固定 $\lambda\ge0$。由 Markov 不等式，
$$ \mathbb P\{\lambda_{\max}(S)\ge t\} \le e^{-\lambda t}\mathbb E e^{\lambda\lambda_{\max}(S)}. \tag{5.15} $$
而 $e^{\lambda S}$ 的特征值是 $e^{\lambda\lambda_i(S)}$，所以
$$ \mathbb E e^{\lambda\lambda_{\max}(S)} \le \mathbb E\operatorname{tr}e^{\lambda S}. $$
用 Lemma 5.4.9 逐个分离 $\lambda X_N,\lambda X_{N-1},\ldots,\lambda X_1$，得到
$$ \mathbb E e^{\lambda\lambda_{\max}(S)} \le \operatorname{tr}\exp\left[ \sum_{i=1}^N\log\mathbb Ee^{\lambda X_i} \right]. \tag{5.16} $$
接下来需要控制单个矩阵的 MGF。
设 $X$ 是均值为零的 $n\times n$ 对称随机矩阵，并满足 $\|X\|\le K$ a.s.。则当 $|\lambda|<3/K$ 时，
$$ \mathbb E\exp(\lambda X) \preceq \exp(g(\lambda)\mathbb EX^2), \qquad g(\lambda)=\frac{\lambda^2/2}{1-|\lambda|K/3}. $$ 查看学习笔记完整证明把 Lemma 5.4.10 代入 (5.16)，并使用 $\log x$ 的矩阵单调性与 trace monotonicity，得到
$$ \mathbb E e^{\lambda\lambda_{\max}(S)} \le \operatorname{tr}\exp(g(\lambda)Z), \qquad Z=\sum_{i=1}^N\mathbb EX_i^2. $$
由于 $Z\succeq0$，
$$ \operatorname{tr}\exp(g(\lambda)Z) \le n\exp(g(\lambda)\|Z\|) = n\exp(g(\lambda)\sigma^2). $$
代回 (5.15)，得到
$$ \mathbb P\{\lambda_{\max}(S)\ge t\} \le n\exp[-\lambda t+g(\lambda)\sigma^2]. $$
取
$$ \lambda=\frac{t}{\sigma^2+Kt/3}, $$
可化简为
$$ \mathbb P\{\lambda_{\max}(S)\ge t\} \le n\exp\left(-\frac{t^2/2}{\sigma^2+Kt/3}\right). $$
对 $-S$ 重复论证，并用 (5.14) 合并，即得 Theorem 5.4.1。
矩阵 Bernstein 不等式给出高概率界。用尾积分公式可推出更简单但信息更少的期望界：
$$ \mathbb E\left\|\sum_{i=1}^N X_i\right\| \lesssim \left\|\sum_{i=1}^N\mathbb EX_i^2\right\|^{1/2} \sqrt{\log(2n)} + K\log(2n). \tag{5.17} $$ 查看学习笔记：由尾界推出期望界和标量情形相比，高维矩阵升级只多出一个对数因子。这是高维中的小代价，并且在一般情形下基本不可去掉；Exercise 5.28 给出例子。
5.4.4 矩阵 Hoeffding 与 Khintchine 不等式
设 $\varepsilon_1,\ldots,\varepsilon_N$ 是独立 Rademacher 随机变量，$A_1,\ldots,A_N$ 是固定的对称 $n\times n$ 矩阵。则对任意 $t\ge0$，
$$ \mathbb P\left\{ \left\|\sum_{i=1}^N\varepsilon_iA_i\right\|\ge t \right\} \le 2n\exp\left(-\frac{t^2}{2\sigma^2}\right), $$其中
$$ \sigma^2=\left\|\sum_{i=1}^N A_i^2\right\|. $$ 查看学习笔记完整证明在 Theorem 5.4.13 的设定下，对每个 $p\in[1,\infty)$，
$$ \left( \mathbb E\left\|\sum_{i=1}^N\varepsilon_iA_i\right\|^p \right)^{1/p} \le C\sqrt{p+\log n} \left\|\sum_{i=1}^N A_i^2\right\|^{1/2}. $$ 查看学习笔记完整证明矩阵集中不等式可用 Hermitian dilation 扩展到矩形矩阵。把每个 $m\times n$ 矩阵 $X_i$ 替换为对称块矩阵
$$ \mathcal D(X_i)= \begin{bmatrix} 0 & X_i\\ X_i^{\mathsf T} & 0 \end{bmatrix}, $$再应用对称矩阵的集中不等式。Exercises 5.23、5.24 会给出矩形矩阵 Bernstein 与 Khintchine 版本。
5.5 应用：稀疏网络中的社群检测
第 4.5 节分析了 stochastic block model $G(n,p,q)$ 上的谱聚类，并说明当期望平均度 $\gtrsim\sqrt n$ 时算法有效。现在借助矩阵 Bernstein 不等式，我们将证明谱聚类可用于更稀疏的网络，期望平均度低至 $O(\log n)$。
设 $G\sim G(n,p,q)$，其中 $p=a/n$、$q=b/n$，且 $b<a<3b$。若
$$ (a-b)^2\ge Ca\log n, $$则以至少 $0.99$ 的概率，谱聚类算法（Section 4.5.5）能以 $99\%$ 的准确率识别 $G$ 的两个社群，也就是误分类顶点数至多为 $0.01n$。
查看学习笔记完整证明证明沿用 Section 4.5 的论证，只是把误差上界换成更锐利的矩阵 Bernstein 界。设邻接矩阵为 $A$，分解为
$$ A=D+R, \qquad D=\mathbb EA, \qquad R=A-\mathbb EA. $$
随机部分 $R$ 可写成独立、均值为零的对称矩阵和：
$$ R=\sum_{i\le j}Z_{ij}, $$
其中 $Z_{ij}$ 只保留 $(i,j)$ 与 $(j,i)$ 两个位置的随机噪声。因为 $A_{ij}\in\{0,1\}$，有 $|R_{ij}|\le1$，从而 $\|Z_{ij}\|\le1$。
用矩阵 Bernstein 的期望形式和 Markov 不等式，可以以至少 $0.99$ 的概率得到
$$ \|R\| \lesssim \sigma\sqrt{\log n}+\log n, \qquad \sigma^2= \left\|\mathbb E\sum_{i\le j}Z_{ij}^2\right\|. \tag{5.18} $$
计算可得 $\sigma^2\le np=a$，因此
$$ \|R\| \lesssim \sqrt{a\log n}+\log n \lesssim \sqrt{a\log n}. \tag{5.19} $$
最后一步使用假设推出 $a\gtrsim\log n$。
查看学习笔记：为什么假设推出 $a\gtrsim\log n$
再对 $D$ 和 $A$ 应用 Davis-Kahan。第 4.5 节已经算出 $D$ 的第二特征值与其余谱的分离为
$$ \delta = \min(\lambda_2(D),\lambda_1(D)-\lambda_2(D)) = \min\left(\frac{p-q}{2},q\right)n = \frac{a-b}{2}, $$
这里用到了 $a\le3b$。由 Davis-Kahan，
$$ \|\bar u_2(D)-\theta\bar u_2(A)\|_2 \le \frac{2\|R\|}{\delta} \le \frac{C_1\sqrt{a\log n}}{a-b} < \frac1{10}, $$
其中 $\theta\in\{-1,1\}$。若定理假设中的常数 $C$ 取得足够大，最后不等式成立。把单位向量还原为 $\pm1$ 系数向量，可得至少 $99\%$ 的顶点符号正确。
Theorem 5.5.1 非平凡时，最稀疏图的期望平均度满足
$$ \frac{n(p+q)}2=\frac{a+b}{2}\asymp\log n. $$这比第 4 章得到的 $O(\sqrt n)$ 稀疏度大幅改进。Exercise 5.25 会让你处理没有 loops 的 stochastic block model。
5.6 应用：一般分布的协方差估计
第 4.7 节中，我们学习了如何用 $O(n)$ 个样本估计 $\mathbb R^n$ 中次高斯分布的协方差矩阵。现在去掉次高斯假设，使方法适用于更广泛的分布，甚至离散分布；代价只是一个对数 oversampling 因子。
与第 4.7 节一样，我们用样本版本估计 second moment matrix
$$ \Sigma=\mathbb EXX^{\mathsf T}, \qquad \Sigma_m=\frac1m\sum_{i=1}^m X_iX_i^{\mathsf T}. $$
如果 $X$ 均值为零，则 $\Sigma$ 是 $X$ 的协方差矩阵，$\Sigma_m$ 是样本协方差矩阵。
设 $X$ 是 $\mathbb R^n$ 中的随机向量，$n\ge2$。假设存在 $K\ge1$，使得
$$ \|X\|_2 \le K(\mathbb E\|X\|_2^2)^{1/2} \quad \text{a.s.} \tag{5.20} $$那么对任意正整数 $m$，
$$ \mathbb E\|\Sigma_m-\Sigma\| \le C\left( \sqrt{\frac{K^2 n\log n}{m}} + \frac{K^2 n\log n}{m} \right)\|\Sigma\|. $$ 查看学习笔记完整证明证明中用 Proposition 3.2.1(b) 得到 $\mathbb E\|X\|_2^2=\operatorname{tr}(\Sigma)$，所以 (5.20) 等价于
$$ \|X\|_2^2\le K^2\operatorname{tr}(\Sigma) \quad \text{a.s.} \tag{5.21} $$
对 i.i.d. 矩阵和 $\sum_i(X_iX_i^{\mathsf T}-\Sigma)$ 应用矩阵 Bernstein 的期望形式 (5.17)，得到
$$ \mathbb E\|\Sigma_m-\Sigma\| \lesssim \frac1m(\sigma\sqrt{\log n}+M\log n), \tag{5.22} $$
其中
$$ \sigma^2 = m\left\|\mathbb E(XX^{\mathsf T}-\Sigma)^2\right\|, \qquad \|XX^{\mathsf T}-\Sigma\|\le M. $$
先估计 $\sigma^2$。展开平方：
$$ \mathbb E(XX^{\mathsf T}-\Sigma)^2 = \mathbb E(XX^{\mathsf T})^2-\Sigma^2 \preceq \mathbb E(XX^{\mathsf T})^2. \tag{5.23} $$
又由 (5.21)，
$$ (XX^{\mathsf T})^2 = \|X\|_2^2XX^{\mathsf T} \preceq K^2\operatorname{tr}(\Sigma)\,XX^{\mathsf T}. $$
取期望得
$$ \mathbb E(XX^{\mathsf T})^2 \preceq K^2\operatorname{tr}(\Sigma)\Sigma, $$
所以
$$ \sigma^2 \le K^2m\operatorname{tr}(\Sigma)\|\Sigma\|. $$
再估计 $M$：
$$ \|XX^{\mathsf T}-\Sigma\| \le \|X\|_2^2+\|\Sigma\| \le K^2\operatorname{tr}(\Sigma)+\|\Sigma\| \le 2K^2\operatorname{tr}(\Sigma) =M. $$
把这些代入 (5.22)，再用 $\operatorname{tr}(\Sigma)\le n\|\Sigma\|$ 即得 Theorem 5.6.1。
Theorem 5.6.1 说明，对任意 $\varepsilon\in(0,1)$，只要
$$ m\asymp \varepsilon^{-2}n\log n, \tag{5.25} $$就能得到
$$ \mathbb E\|\Sigma_m-\Sigma\|\le\varepsilon\|\Sigma\|. \tag{5.24} $$相比次高斯分布的 $m\asymp\varepsilon^{-2}n$，去掉次高斯假设只付出了一个小的对数 oversampling 因子。
证明末尾用了粗糙界 $\operatorname{tr}(\Sigma)\le n\|\Sigma\|$。若改用有效秩
$$ r(\Sigma)=\frac{\operatorname{tr}(\Sigma)}{\|\Sigma\|}, \tag{5.26} $$则可得到更精细的界
$$ \mathbb E\|\Sigma_m-\Sigma\| \le C\left( \sqrt{\frac{K^2 r\log n}{m}} + \frac{K^2 r\log n}{m} \right)\|\Sigma\|. \tag{5.27} $$因此，$m\asymp\varepsilon^{-2}r\log n$ 个样本足以估计协方差。由于 $r\le n$，它不会比 (5.25) 更差。
查看学习笔记：为什么 $r(\Sigma)\le n$若 $\Sigma\succeq0$，则
$$ r(\Sigma) = \frac{\sum_{i=1}^n\lambda_i(\Sigma)} {\max_i\lambda_i(\Sigma)}. $$它总是被实际 rank 控制，并且对近似低秩矩阵可以远小于实际 rank。相关概念是任意矩阵 $A$ 的 stable rank：
$$ s(A) = \frac{\|A\|_F^2}{\|A\|^2} = \frac{\sum_i s_i(A)^2}{\max_i s_i(A)^2} = r(A^{\mathsf T}A) = r(AA^{\mathsf T}). $$ 查看学习笔记：有效秩练习上面给出的是期望界，但同一论证也给出高概率版本：对所有 $u\ge0$，以至少 $1-2e^{-u}$ 的概率，
$$ \|\Sigma_m-\Sigma\| \le C\left( \sqrt{\frac{K^2 r(\log n+u)}{m}} + \frac{K^2 r(\log n+u)}{m} \right)\|\Sigma\|, \tag{5.28} $$其中 $r=\operatorname{tr}(\Sigma)/\|\Sigma\|\le n$。Exercise 5.26 会让你证明它。
查看学习笔记完整证明(5.20) 的有界性假设看似强，但一般不能去掉：若 $X$ 各向同性但以很高概率为零，则样本很可能全是零，使协方差估计不可能。Exercise 5.27 会让你形式化这个论证。实践中通常用截断来保证这一条件，即丢弃少量范数最大的样本。
查看学习笔记完整证明5.7 Notes
关于集中不等式，可参见本章 bibliographic notes 中列出的专著、教程和参考文献。第 5.1 节的等周方法源于 P. Levy。V. Milman 意识到 Levy 方法的威力后，推动了 concentration of measure principle 的广泛发展。
本章为了简洁省略了许多重要方法，包括 bounded differences、martingales、semigroups、transport、Poincare 与 log-Sobolev inequalities、hypercontractivity、Stein 方法和 Talagrand inequalities。Gaussian 等周不等式、Hamming cube 与对称群上的集中、正曲率 Riemannian 流形上的集中、连续 cube/ball 上的集中、强凸密度下的集中，以及 Talagrand concentration inequality，都有成熟文献证明。
Johnson-Lindenstrauss 引理的原始版本来自 Johnson 与 Lindenstrauss；条件 $m\gtrsim\varepsilon^{-2}\log N$ 是最优的。矩阵集中不等式部分沿用 Ahlswede-Winter 与 Tropp 发展出的思路；Golden-Thompson、Lieb inequality 和矩阵 Bernstein 的大量变体可在相关矩阵分析和随机矩阵文献中找到。矩阵 Bernstein 中出现的维度因子 $n$ 在某些版本中可被 intrinsic dimension 或 effective rank 替代。
本章还省略了 bounded differences inequality（McDiarmid inequality），它不仅适用于和，也适用于独立随机变量的一般函数，是 Hoeffding 不等式的推广。
设 $X=(X_1,\ldots,X_N)$ 的坐标独立，$f$ 是可测函数。假设改变第 $i$ 个坐标最多使 $f$ 的值改变 $c_i>0$，即对所有 $i$ 和所有可能输入都有
$$ |f(x_1,\ldots,x_i,\ldots,x_N) - f(x_1,\ldots,x_i',\ldots,x_N)| \le c_i. $$则对任意 $t>0$，
$$ \mathbb P\{f(X)-\mathbb Ef(X)\ge t\} \le \exp\left( -\frac{2t^2}{\sum_{i=1}^N c_i^2} \right). $$ 查看学习笔记完整证明Exercises
下面保留原书习题内容，并为每题加入学习笔记证明入口。
(a) 证明每个 Lipschitz 函数都是一致连续的。(b) 证明每个可微函数 $f:\mathbb R^n\to\mathbb R$ 若满足 $\sup_x\|\nabla f(x)\|_2<\infty$，则是 Lipschitz，并且 $\|f\|_{\mathrm{Lip}}\le\sup_x\|\nabla f(x)\|_2$。(c) 找一个非 Lipschitz 但一致连续的 $f:[-1,1]\to\mathbb R$。(d) 找一个不可微但 Lipschitz 的 $f:[-1,1]\to\mathbb R$。
查看学习笔记完整证明检查 Example 5.1.2 中所有关于线性泛函、线性算子和范数函数的 Lipschitz 范数断言。
查看学习笔记完整证明设 $A\subset\sqrt n S^{n-1}$ 且 $\sigma(A)>2\exp(-cs^2)$。(a) 证明 $\sigma(A_s)>1/2$。(b) 推出对任意 $t\ge s$，$\sigma(A_{2t})\ge1-2\exp(-ct^2)$。
查看学习笔记完整证明Theorem 5.1.3 是对球面上的 Euclidean 距离表述的。证明它对 geodesic metric 也成立，其中 geodesic metric 是两点之间最短球面弧长。
查看学习笔记完整证明由 Theorem 5.1.3 推出：若 $X\sim\operatorname{Unif}(S^{n-1})$，则单位球面上的 Lipschitz 函数满足
$$\|f(X)-\mathbb Ef(X)\|_{\psi_2}\le\frac{C\|f\|_{\mathrm{Lip}}}{\sqrt n}.\tag{5.29}$$等价地，对任意 $t\ge0$，
$$\mathbb P\{|f(X)-\mathbb Ef(X)|\ge t\}\le2\exp\left(-\frac{cnt^2}{\|f\|_{\mathrm{Lip}}^2}\right).\tag{5.30}$$查看学习笔记完整证明设 $Z$ 的中位数为 $M$。证明
$$c\|Z-\mathbb EZ\|_{\psi_2}\le\|Z-M\|_{\psi_2}\le C\|Z-\mathbb EZ\|_{\psi_2}.$$查看学习笔记完整证明设随机向量 $X$ 取值于度量空间 $(T,d)$，且对所有 Lipschitz 函数 $f:T\to\mathbb R$ 都有 $\|f(X)-\mathbb Ef(X)\|_{\psi_2}\le K\|f\|_{\mathrm{Lip}}$。定义 $\sigma(A)=\mathbb P\{X\in A\}$。证明若 $\sigma(A)\ge1/2$，则对所有 $t\ge0$，
$$\sigma(A_t)\ge1-2\exp(-ct^2/K^2).$$查看学习笔记完整证明由 Gaussian 等周不等式 Theorem 5.2.2 推出 Gaussian concentration inequality Theorem 5.2.3。
查看学习笔记完整证明(a) 若 $X_1,\ldots,X_n$ 独立同分布为 $N(0,1)$，证明 $\|\max_iX_i-\mathbb E\max_iX_i\|_{\psi_2}\le C$。(b) 更一般地，若 $X_1,\ldots,X_n$ 联合正态，不必独立，证明
$$\|\max_iX_i-\mathbb E\max_iX_i\|_{\psi_2}\le C\max_i\sqrt{\operatorname{Var}(X_i)}.$$查看学习笔记完整证明设 $\mathbb EZ\ge0$ 且 $p\ge1$。证明
$$\|Z-\|Z\|_{L^p}\|_{\psi_2}\le C\sqrt p\,\|Z-\mathbb EZ\|_{\psi_2}.$$查看学习笔记完整证明令 $\Phi$ 为标准正态分布函数，$Z\sim N(0,I_n)$。检查
$$\phi(Z)=(\Phi(Z_1),\ldots,\Phi(Z_n))\sim\operatorname{Unif}([0,1]^n).$$查看学习笔记完整证明按如下方法证明 Theorem 5.2.10 中 $T=[0,1]^n$ 的情形：(a) 用 Exercise 5.11 表示 $X=\phi(Z)$，并用 Gaussian concentration 控制 $f(\phi(Z))$。(b) 证明 $\|\phi\|_{\mathrm{Lip}}$ 被绝对常数控制。
查看学习笔记完整证明按类似 Exercise 5.12 的策略证明 Theorem 5.2.10 中 $T=\sqrt n B_2^n$ 的情形：构造把 Gaussian measure 推送到 $\sqrt n B_2^n$ 均匀测度的映射 $\phi$，并检查其 Lipschitz 范数有界。
查看学习笔记完整证明设 $A$ 是 $m\times n$ 随机矩阵，rows 独立、均值为零、次高斯、各向同性。证明 $Q=(1/\sqrt m)A$ 满足 Johnson-Lindenstrauss 引理。说明 $\pm1$ entries 的二值 Johnson-Lindenstrauss 是特例。
查看学习笔记完整证明(a) 设 $z_1,\ldots,z_N\in\mathbb R^n$ 满足 $1<\|z_i-z_j\|_2\le2$，证明 $N\le5^n$。(b) 若 $n<\frac12\log N$，构造 $x_1,\ldots,x_N\in\mathbb R^N$，使不存在任何映射 $T:\mathbb R^N\to\mathbb R^n$ 对所有点对保持 $0.99$ 到 $1.01$ 的距离失真。
查看学习笔记完整证明验证矩阵函数定义与多项式、幂级数和矩阵指数 Taylor 展开一致。
查看学习笔记完整证明(a) 若 $X,Y$ 交换，检查 $X\preceq Y$ 推出 $f(X)\preceq f(Y)$ 对任意弱增函数 $f$ 成立。(b) 给出非交换矩阵的反例。
查看学习笔记完整证明设 $0\preceq X\preceq Y$ 且 $X$ 可逆。证明 $Y$ 可逆且 $X^{-1}\succeq Y^{-1}\succeq0$；检查积分恒等式
$$\log x=\int_0^\infty\left(\frac1{1+t}-\frac1{x+t}\right)\,dt,$$并推出 $\log X\preceq\log Y$。
查看学习笔记完整证明(a) 若对称矩阵 $X,Y$ 交换，证明 $e^{X+Y}=e^Xe^Y$。(b) 找出 $e^{X+Y}\ne e^Xe^Y$ 的例子。
查看学习笔记完整证明从 Theorem 5.4.1 推出
$$\mathbb E\left\|\sum_{i=1}^N X_i\right\|\lesssim\left\|\sum_{i=1}^N\mathbb EX_i^2\right\|^{1/2}\sqrt{1+\log n}+K(1+\log n).$$查看学习笔记完整证明仿照矩阵 Bernstein 的证明，证明 Theorem 5.4.13。
查看学习笔记完整证明从 Theorem 5.4.13 推出 Theorem 5.4.14。
查看学习笔记完整证明设 $X_i$ 是独立、均值为零的 $m\times n$ 随机矩阵，且 $\|X_i\|\le K$ a.s.。证明矩形矩阵 Bernstein 不等式，维度因子为 $2(m+n)$，variance 参数由 $\sum\mathbb EX_i^{\mathsf T}X_i$ 与 $\sum\mathbb EX_iX_i^{\mathsf T}$ 控制。
查看学习笔记完整证明对固定 $m\times n$ 矩阵 $A_i$ 和独立 Rademacher 变量 $\varepsilon_i$，证明
$$\left(\mathbb E\left\|\sum_i\varepsilon_iA_i\right\|^p\right)^{1/p}\le C\sigma\sqrt{p+\log(m+n)},$$其中 $\sigma^2=\left\|\sum_iA_i^{\mathsf T}A_i\right\|+\left\|\sum_iA_iA_i^{\mathsf T}\right\|$。
查看学习笔记完整证明修改 Definition 4.5.1，使 stochastic block model 不允许 loops，并证明 Theorem 5.5.1 的相应版本。
查看学习笔记完整证明证明 Remark 5.6.5 中的高概率协方差估计结论。
查看学习笔记完整证明证明 Theorem 5.6.1 中的有界性假设 (5.20) 一般不能去掉。
查看学习笔记完整证明(a) 构造一个分布，使得若 $m\not\gtrsim n\log n$，则 $\|\Sigma_m-\Sigma\|<\|\Sigma\|$ 以高概率失败。(b) 推出矩阵 Bernstein 期望界中的对数因子一般不能去掉。
查看学习笔记完整证明对 $\Sigma\succeq0$，$r(\Sigma)=\operatorname{tr}(\Sigma)/\|\Sigma\|$。(a) 证明 $1\le r(\Sigma)\le\operatorname{rank}(\Sigma)\le n$。(b) 说明这些不等式最优。(c) 说明有效秩是连续的。(d) 若 $X$ 取值于 $k$ 维子空间，证明 $\operatorname{rank}(\Sigma)\le k$，从而 $r(\Sigma)\le k$。
查看学习笔记完整证明设 $(u_1,\ldots,u_M)$ 是 $\mathbb R^n$ 中等范数 Parseval frame。证明随机抽取 $m\gtrsim n\log n$ 个 frame elements 后，高概率仍形成近似 frame，并形式化“近似”的含义。
查看学习笔记完整证明设 $A$ 是 $m\times n$ 随机矩阵，rows 独立各向同性，且 $\|A_i\|_2\le K\sqrt n$ a.s.。证明对 $t\ge1$，以至少 $1-2n^{-ct^2}$ 的概率，
$$\sqrt m-Kt\sqrt{n\log n}\le s_n(A)\le s_1(A)\le\sqrt m+Kt\sqrt{n\log n}.$$查看学习笔记完整证明设 $A$ 是 tall $N\times n$ 矩阵，所有 rows 等范数。令 $B$ 为从 $A$ 中有放回均匀抽取 $m=O(n\log n)$ 行形成的矩阵。证明若 $m\ge Cn\log n$，则以至少 $0.9$ 的概率，
$$\max_{i=1,\ldots,n}\left|s_i(A)^2-\frac Nm s_i(B)^2\right|\le0.1s_1(A)^2.$$查看学习笔记完整证明校对说明
concentration without independence译为“无独立性的集中”，强调本章从独立和转向几何与矩阵工具。isoperimetric inequality译为“等周不等式”，blow-up保留英文并解释为“邻域快速膨胀”。matrix Bernstein、Loewner order、Haar measure、Johnson-Lindenstrauss保留英文术语，方便与原书和后续章节对照。- OCR 中若干箭头、矩阵块和英文断字已按数学语义修正。