第 5 章精校翻译：无独立性的集中
第 5 章无独立性的集中
到目前为止，我们研究集中不等式时严重依赖随机变量之间的独立性。现在，我们转向另外一类方法：它们不依赖独立性。第 5.1 节以 欧几里得 球面为例，引入等周不等式方法；第 5.2 节再介绍其他度量测度空间上的集中现象。
第 5.3 节利用球面上的集中推出经典的 Johnson-Lindenstrauss 引理，这是高维数据降维中的核心结果。
第 5.4 节介绍矩阵集中不等式，重点是矩阵 Bernstein 不等式，它把经典 Bernstein 不等式推广到随机矩阵。第 5.5 与 5.6 节再把这一工具用于稀疏网络中的社群检测，以及更一般分布下的协方差估计。
不要跳过习题。本章习题会研究二值随机投影的降维版本（习题 5.14）、矩阵函数演算（习题 5.16-5.19）、多个矩阵集中不等式（习题 5.20-5.24），以及矩阵草图化（习题 5.32）、社群检测（习题 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) $$
如果 $X$ 是正态向量且 $f$ 是线性函数，这很容易：$f(X)$ 仍是正态随机变量（推论 3.3.2），并且有很好的集中（命题 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$ 时，它们是收缩，因为它们只会缩短距离。Lipschitz 函数位于可微函数和一致连续函数之间：
$$ f\text{ 可微} \Longrightarrow f\text{ Lipschitz} \Longrightarrow f\text{ 一致连续}. $$
在 习题 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{对所有 }x\in\mathbb R^n. $$ 查看学习笔记：例 5.1.2 验证5.1.2 通过等周不等式得到集中
我们现在证明 欧几里得 球面
$$ S^{n-1}=\{x\in\mathbb R^n:\|x\|_2=1\} $$
上的任意 Lipschitz 函数都会集中。
设 $X$ 均匀分布在半径为 $\sqrt n$ 的 欧几里得 球面上，即 $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). $$ 查看学习笔记完整证明我们已经在线性函数情形证明过 定理 5.1.3。定理 3.4.5 告诉我们，$X$ 是次高斯随机向量；按定义，$X$ 的任意线性函数都是次高斯随机变量。
为了完全证明 定理 5.1.3，需要说明任意 Lipschitz 函数至少像线性函数一样集中。我们不直接比较函数值，而是比较它们的下水平集，即给定水平 $a$ 时球面上满足 $f(x)\le a$ 的区域。对线性函数而言，这些区域就是球冠。比较一般集合和球冠的面积，需要一个重要几何原则：等周不等式。
在 $\mathbb R^n$ 中，在所有给定体积的集合 $A$ 里，欧几里得 球具有最小表面积。更强地，对任意 $\varepsilon\gt 0$，欧几里得 球也使 $A$ 的 $\varepsilon$-邻域体积最小，其中
$$ A_\varepsilon = \{x\in\mathbb R^n:\exists y\in A,\ \|x-y\|_2\le\varepsilon\} = A+\varepsilon B_2^n. $$定理 5.1.4 的“更强”部分推出第一部分；令 $\varepsilon\to0$ 即可看出。图 5.1 给出了等周不等式的示意。
球面 $S^{n-1}$ 上也有类似等周不等式，此时最小化者是球冠，也就是某个点的邻域。用 $\sigma_{n-1}$ 表示球面 $S^{n-1}$ 上的归一化面积测度。
设 $\varepsilon\gt 0$。在所有具有给定面积 $\sigma_{n-1}(A)$ 的集合 $A\subset S^{n-1}$ 中，球冠使邻域面积 $\sigma_{n-1}(A_\varepsilon)$ 最小，其中
$$ A_\varepsilon = \{x\in S^{n-1}:\exists y\in A,\ \|x-y\|_2\le\varepsilon\}. $$本书不证明等周不等式（定理 5.1.4 与 5.1.5）；本章文献注记会给出若干已知证明的参考。
5.1.3 球面上集合的膨胀
等周不等式推出一个非常反直觉的现象：如果集合 $A$ 至少覆盖球面一半面积，那么它的 $\varepsilon$-邻域 $A_\varepsilon$ 会覆盖球面的大部分。我们先陈述并证明这个膨胀（blow-up）现象，然后解释直觉。为了适配 定理 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$ 的邻域。直接计算球冠面积可以完成证明，但更方便的是用 定理 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)，引理得证。
引理 5.1.6 中面积为 $1/2$ 的数值不是本质的。它可以替换为任意常数，甚至可以替换为指数级小的量。习题 5.3 会让你验证这一点。
查看学习笔记：指数小集合的膨胀刚才看到的膨胀现象一开始可能很反直觉。一个指数级小的集合 $A$，为什么只在 $2t$ 的小扰动下就变成指数级大的集合 $A_{2t}$？这里 $t$ 可以远小于球面半径 $\sqrt n$。这正是高维空间的典型现象，类似概率论中的零一律：由许多随机变量共同影响的事件，概率往往接近 $0$ 或 $1$。
5.1.4 定理 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 集合
$$ A=\{x\in\sqrt n S^{n-1}:f(x)\le M\}. $$
因为 $\mathbb P\{X\in A\}\ge1/2$，引理 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)$，这可由中心化和 引理 2.7.8 得到。
定理 5.1.3 得证。习题 5.7 会让你反向证明：集中现象与膨胀现象本质上等价。
5.2 其他度量测度空间上的集中
我们现在把球面上的集中推广到其他空间。定理 5.1.3 的证明依赖两个成分：
- 一个等周不等式。
- 最小化集合的膨胀。
这两个成分并非球面独有；许多空间都有类似结构，因此也有类似集中结论。下面介绍两个关键例子：$\mathbb R^n$ 中的高斯集中，以及 Hamming 立方体 上的集中；之后再简要提到其他情形。
集中意味着均值、中位数和 $L^p$ 范数彼此接近。因此，可以把 $\mathbb Ef(X)$ 替换为中位数（习题 5.6）；若均值非负，也可以替换为任意 $p\ge1$ 的 $L^p$ 范数，不过常数可能依赖 $p$（习题 5.10）。
5.2.1 高斯集中
定理 5.1.4 中 $\mathbb R^n$ 上的经典等周不等式不仅对体积成立，也对 $\mathbb R^n$ 上的高斯测度成立。对 Borel 集 $A\subset\mathbb R^n$，高斯测度定义为
$$ \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\gt 0$。在所有具有给定高斯测度 $\gamma_n(A)$ 的集合 $A\subset\mathbb R^n$ 中，半空间使邻域高斯测度 $\gamma_n(A_\varepsilon)$ 最小。
用与球面相同的方法，可以推出下面的高斯集中不等式（见 习题 5.8）。
设 $X\sim N(0,I_n)$，并设 $f:\mathbb R^n\to\mathbb R$ 是关于 欧几里得 距离的 Lipschitz 函数。则
$$ \|f(X)-\mathbb Ef(X)\|_{\psi_2} \le C\|f\|_{\mathrm{Lip}}. \tag{5.5} $$ 查看学习笔记：由高斯等周推出集中(a) 对线性函数 $f$，结论来自 $X\sim N(0,I_n)$ 是次高斯随机向量。
(b) 对 欧几里得 范数 $f(x)=\|x\|_2$，结论来自范数集中（定理 3.1.1）。
习题 5.9 会让你用高斯集中证明 $n$ 个高斯最大值的集中。
5.2.2 Hamming 立方体
基于等周的集中方法也适用于 Hamming 立方体
$$ (\{0,1\}^n,d,\mathbb P), $$
其中 $d(x,y)$ 是归一化 Hamming 距离：
$$ d(x,y)=\frac1n|\{i:x_i\ne y_i\}|. $$
测度 $\mathbb P$ 是 立方体 上的均匀概率测度：
$$ \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 立方体 上的等周不等式，其最小化者是 Hamming 球，即关于 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)\gt 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) 成立。
这一结果可由 5.2.4 中一般黎曼流形上的集中不等式推出。
生成 $X\sim\operatorname{Unif}(\operatorname{SO}(n))$ 的一种方法是：先取 $n\times n$ 高斯随机矩阵 $G$，其元素独立同分布为 $N(0,1)$；再计算 SVD $G=U\Sigma V^{\mathsf T}$。令
$$ D=\operatorname{diag}(\det(UV^{\mathsf T}),1,\ldots,1), \qquad X=UV^{\mathsf T}D. $$这样得到的 $X$ 均匀分布在 $\operatorname{SO}(n)$ 上。
校勘：原文/OCR 中这一处为 $X:=UV^{\mathsf T}$。这只能保证 $X\in\operatorname{O}(n)$，不能保证 $\det X=1$。这里加入行列式修正矩阵 $D$，使 $X\in\operatorname{SO}(n)$。
$\operatorname{SO}(n)$ 上的均匀概率分布为
$$ \mu(A)=\mathbb P\{X\in A\}. $$它是唯一的 旋转不变 概率测度，称为 Haar 测度。
查看学习笔记：旋转不变性检查5.2.6 Grassmannian
Grassmann 流形 $G_{n,m}$ 由 $\mathbb R^n$ 中所有 $m$ 维子空间组成。当 $m=1$ 时，它可看作把球面 $S^{n-1}$ 上的对径点 $x$ 与 $-x$ 识别后的空间，因此 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 概率测度。随机子空间 $E\sim\operatorname{Unif}(G_{n,m})$ 可通过 $n\times m$ 高斯随机矩阵 $G$ 的像空间构造。
这个距离由算子范数给出：$d(E,F)=\|P_E-P_F\|$；可以通过习题 4.12 练习这个距离的几何含义。
设随机子空间 $X\sim\operatorname{Unif}(G_{n,m})$，并设 $f:G_{n,m}\to\mathbb R$。则集中不等式 (5.6) 成立。
该结果可由特殊正交群上的集中推出，因为 $G_{n,m}$ 可表示为商空间 $\operatorname{SO}(n)/(\operatorname{SO}(m)\times\operatorname{SO}(n-m))$，而集中性质可传递到这种商空间上。
5.2.7 连续 立方体 与 欧几里得 球
对单位 欧几里得 立方体 $[0,1]^n$ 和 欧几里得 球 $\sqrt n B_2^n$，也有类似的集中不等式。这可通过把高斯测度推送到 立方体 或球上的均匀测度来证明。证明留给 习题 5.12、5.13。
设 $T$ 是 立方体 $[0,1]^n$ 或球 $\sqrt n B_2^n$。若 $X\sim\operatorname{Unif}(T)$，且 $f:T\to\mathbb R$ 是关于 欧几里得 距离的 Lipschitz 函数，则集中不等式 (5.5) 成立。
5.2.8 形如 $e^{-U(x)}$ 的密度
前一节的 推送 方法可用于 $\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$，高斯集中成立。
如果一般函数 $U$ 的曲率至少像 $\|x\|_2^2$ 一样强，就应期待至少有高斯集中。$U$ 的曲率由 Hessian $\operatorname{Hess}U(x)$ 度量；这是一个 $n\times n$ 对称矩阵，其 $(i,j)$ 元为 $\partial^2 U(x)/\partial x_i\partial x_j$。
设随机向量 $X$ 在 $\mathbb R^n$ 中的密度为 $p(x)=e^{-U(x)}$。若存在 $\kappa\gt 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.7) 的相似性；二者都可用半群方法证明，但本书不展开。
5.2.9 独立有界坐标的随机向量
还有一个重要的部分推广：设 $X=(X_1,\ldots,X_n)$ 的坐标独立，且坐标分布任意但有界。通过缩放，可假设 $|X_i|\le1$。
设 $X=(X_1,\ldots,X_n)$ 的坐标独立并满足 $|X_i|\le1$ 几乎必然。那么，对任意凸 Lipschitz 函数 $f:[-1,1]^n\to\mathbb R$，集中不等式 (5.5) 成立。
特别地，Talagrand 集中不等式适用于 $\mathbb R^n$ 上任意范数。本书不证明该结果。
5.3 应用：Johnson-Lindenstrauss 引理
假设有 $N$ 个数据点位于 $\mathbb R^n$，而维度 $n$ 很大。能否在不严重损失数据几何结构的前提下降维？最简单的方法是把数据点投影到低维子空间
$$ E\subset\mathbb R^n, \qquad \dim(E)=m\ll n. $$
图 5.2 展示了这一想法。关键问题是：怎样选择子空间 $E$？维度 $m$ 可以多小？
Johnson-Lindenstrauss 引理说明，只要把 $E$ 选为维度
$$ m\asymp \log N $$
的随机子空间，就能很好地保留数据几何。
我们前面已经遇到随机子空间：若 $E\sim\operatorname{Unif}(G_{n,m})$，则它的分布是旋转不变的，也就是说对任意固定旋转 $U$，$UE$ 与 $E$ 同分布。
设 $\mathcal X$ 是 $\mathbb R^n$ 中含有 $N$ 个点的集合，$\varepsilon\gt 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{对所有 }x,y\in\mathcal X. \tag{5.8} $$ 查看学习笔记完整证明证明基于球面上 Lipschitz 函数的集中。先研究随机投影 $P$ 对固定向量 $x-y$ 的作用，再对所有 $N^2$ 个差向量做并集界。
令 $P$ 是 $\mathbb R^n$ 到随机 $m$ 维子空间 $E\sim\operatorname{Unif}(G_{n,m})$ 上的投影。固定任意 $z\in\mathbb R^n$ 和 $\varepsilon\gt 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). $$这里用 评注 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$，引理 5.3.2 说明 (5.10) 失败的概率至多 $2\exp(-c\varepsilon^2m)$。对 $|\mathcal X-\mathcal X|\le N^2$ 个差向量做并集界，可知 (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 引理的一个突出特征是：降维映射是非自适应的，不依赖数据本身。注意，数据的环境维度 $n$ 在维度条件里没有出现。后续第 9.2.4 节和第 9.7 节会发展更高级的 Johnson-Lindenstrauss 版本。
Johnson-Lindenstrauss 引理把维度降到 $O(\log N)$。还能不能更低，例如 $o(\log N)$？习题 5.15 会说明不能：即使允许非线性映射，$\log N$ 量级也是最优的。
习题 5.14 会让你证明 Johnson-Lindenstrauss 引理的次高斯矩阵版本。
5.4 矩阵 Bernstein 不等式
这里，我们把独立随机变量和 $\sum X_i$ 的集中不等式推广到独立随机矩阵和。矩阵 Bernstein 不等式是 定理 2.9.5 的矩阵版本：把随机变量 $X_i$ 换成随机矩阵，把绝对值 $|\cdot|$ 换成算子范数 $\|\cdot\|$。注意，每个随机矩阵 $X_i$ 内部的元素、行或列不需要独立，这是非常一般的假设。
设 $X_1,\ldots,X_N$ 是独立、均值为零的 $n\times n$ 对称随机矩阵，并且对所有 $i$，
$$ \|X_i\|\le K \quad\text{几乎必然} $$则对所有 $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\| $$是矩阵和的方差矩阵的算子范数。
等价地，右侧可写成次高斯与次指数混合尾：
$$ \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$。
查看学习笔记：为什么 Loewner 阶不是全序(a) 特征值单调性：$X\preceq Y$ 推出 $\lambda_i(X)\le\lambda_i(Y)$。
(b) 迹单调性：若 $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)$。
(a) 若 $X\preceq Y$，则 $Y-X\succeq0$，所以对所有 $u$ 都有 $u^{\mathsf T}(Y-X)u\ge0$，也就是 $u^{\mathsf T}Xu\le u^{\mathsf T}Yu$。现在使用 min-max theorem（定理 4.1.6）即可得到 $\lambda_i(X)\le\lambda_i(Y)$。
(b) $f(X)$ 的特征值为 $f(\lambda_i(X))$，$f(Y)$ 同理。由 (a) 和 $f$ 弱增，
$$ f(\lambda_i(X))\le f(\lambda_i(Y)). $$对 $i$ 求和即可得到迹单调性，因为 trace 等于特征值之和。
(c) 回忆 (4.10)。若 $\|X\|\le a$，则对所有单位向量 $u$，有 $u^{\mathsf T}Xu\le a$，所以
$$ u^{\mathsf T}(aI_n-X)u\ge0. $$这说明 $aI_n-X\succeq0$，即 $X\preceq aI_n$。类似论证给出 $X\succeq-aI_n$。反方向也同样由二次型判别和 (4.10) 得到。
(d) 考虑 $g-f$，可不失一般性假设 $f=0$。若 $\|X\|\le a$，则由 (4.10)，$X$ 的所有特征值满足 $|\lambda_i|\le a$。由假设，$g(\lambda_i)\ge0$。因此按照矩阵函数的定义，$g(X)$ 的特征值 $g(\lambda_i)$ 全部非负，从而 $g(X)\succeq0$。
(5.12) 是标量事实 $|x|\le a\iff -a\le x\le a$ 的矩阵版本。这解释了为什么矩阵 Bernstein 不等式中自然出现算子范数。
能否把 命题 5.4.4(b) 的迹单调性升级为矩阵单调性，即
$$ X\preceq Y \quad\Longrightarrow\quad f(X)\preceq f(Y) \tag{5.13} $$对所有弱增函数 $f$ 成立？若 $X$ 与 $Y$ 交换，答案是肯定的；一般情形是否定的（习题 5.17）。不过某些函数确实是矩阵单调的，例如 $1/x$ 和 $\log x$：
$$ 0\preceq X\preceq Y \quad\Longrightarrow\quad X^{-1}\succeq Y^{-1}\succeq0 \quad\text{（当 }X\text{ 可逆时）}, \qquad \log X\preceq\log Y. $$ 查看学习笔记：$1/x$ 和 $\log x$ 的矩阵单调性5.4.2 迹不等式
到目前为止，把标量概念推广到矩阵还比较顺利。但这并不总是成立。矩阵不可交换会使许多标量恒等式失效。例如标量恒等式 $e^{x+y}=e^xe^y$ 对矩阵一般不成立；习题 5.19 会让你找出 $n\times n$ 对称矩阵 $X,Y$，使得
$$ e^{X+Y}\ne e^Xe^Y. $$
这很麻烦，因为 $e^{x+y}=e^xe^y$ 正是标量 MGF 方法中分解和的关键。幸运的是，有一些迹不等式可以替代缺失的恒等式。下面陈述两个这样的结果而不证明；它们属于丰富的迹不等式家族。
对任意 $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$ 对称矩阵空间上是凹函数。
在标量情形，定理 5.4.8 只是线性函数的凹性：$\exp(h+\log x)=e^h x$。矩阵情形的内容则深得多，因为 $\exp(H+\log X)$ 不能化简为 $e^H X$。
如果 $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}. $$
用引理 5.4.9 逐个分离 $\lambda X_N,\lambda X_{N-1},\ldots,\lambda X_1$。具体地，先在给定 $X_1,\ldots,X_{N-1}$ 的条件下对最后一项应用引理 5.4.9，再用全期望公式去掉条件；随后对 $X_{N-1},\ldots,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$ 几乎必然。则当 $|\lambda|\lt 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}. $$ 查看学习笔记完整证明先注意 scalar exponential 函数可以由 Taylor expansion 的前几项控制：
$$ e^z \le 1+z+\frac1{1-|z|/3}\cdot\frac{z^2}{2}, \qquad |z|\lt 3. $$为了得到这个不等式，写成
$$ e^z=1+z+z^2\sum_{p=2}^{\infty}\frac{z^{p-2}}{p!}, $$并使用 $p!\ge2\cdot3^{p-2}$。接下来把该不等式用于 $z=\lambda x$。如果 $|x|\le K$ 且 $|\lambda|\lt 3/K$，则
$$ e^{\lambda x} \le 1+\lambda x+g(\lambda)x^2, $$其中 $g(\lambda)$ 正是引理中的函数。
最后用 命题 5.4.4(d) 把这个标量不等式升级为矩阵不等式。若 $\|X\|\le K$ 且 $|\lambda|\lt 3/K$，则
$$ e^{\lambda X} \preceq I+\lambda X+g(\lambda)X^2. $$对两边取期望，并使用 $\mathbb EX=0$，得到
$$ \mathbb E e^{\lambda X} \preceq I+g(\lambda)\mathbb EX^2. $$为了完成证明，使用标量不等式 $1+z\le e^z$。再次由 命题 5.4.4(d)，对所有对称矩阵 $Z$ 都有 $I+Z\preceq e^Z$。取 $Z=g(\lambda)\mathbb EX^2$，便得到
$$ \mathbb E e^{\lambda X} \preceq \exp(g(\lambda)\mathbb EX^2). $$把 引理 5.4.10 代入 (5.16)，并使用 $\log x$ 的矩阵单调性与迹单调性，得到
$$ \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) 合并，即得 定理 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} $$ 查看学习笔记：由尾界推出期望界注意在标量情形 $n=1$ 中，类似的期望界是平凡的：若 $\mathbb EX_i=0$ 且独立，则
$$ \mathbb E\left|\sum_i X_i\right| \le \left(\mathbb E\left(\sum_i X_i\right)^2\right)^{1/2} = \left(\sum_i\mathbb EX_i^2\right)^{1/2}. $$和标量情形相比，高维矩阵升级只多出一个对数因子。这是高维中的小代价，并且在一般情形下基本不可去掉；习题 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\|. $$ 查看学习笔记完整证明在 定理 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}, $$再应用对称矩阵的集中不等式。习题 5.23、5.24 会给出矩形矩阵 Bernstein 与 Khintchine 版本。
5.5 应用：稀疏网络中的社群检测
第 4.5 节分析了随机块模型 $G(n,p,q)$ 上的谱聚类，并说明当期望平均度 $\gtrsim\sqrt n$ 时算法有效。现在借助矩阵 Bernstein 不等式，我们将证明谱聚类可用于更稀疏的网络，期望平均度低至 $O(\log n)$。
设 $G\sim G(n,p,q)$，其中 $p=a/n$、$q=b/n$，且 $b\lt a\lt 3b$。若
$$ (a-b)^2\ge Ca\log n, $$则以至少 $0.99$ 的概率，谱聚类算法（第 4.5.5 节）能以 $99\%$ 的准确率识别 $G$ 的两个社群，也就是误分类顶点数至多为 $0.01n$。
查看学习笔记完整证明证明沿用第 4.5 节的论证，只是把误差上界换成更锐利的矩阵 Bernstein 界。
第一步：分解。 与第 4.5.2 节一样，设 $A$ 是随机图 $G\sim G(n,p,q)$ 的邻接矩阵，并把它分成确定性部分和随机部分：
$$ A=D+R, \qquad D=\mathbb EA, \qquad R=A-\mathbb EA. $$第 4.5.2 节已经分析过期望邻接矩阵 $D$：它的第二大特征向量 $u_2(D)$ 的系数为 $\pm1$，并表示社群成员关系。现在的主要差别是要分析随机部分 $R=A-\mathbb EA$。
逐项分解 $R$，并保留矩阵的对称性。记 $\mathbb R^n$ 的标准基为 $e_1,\ldots,e_n$，则 $R$ 可以写成独立、均值为零的随机矩阵 $Z_{ij}$ 之和：
$$ R=\sum_{i\le j}Z_{ij}, $$ 其中 $$ Z_{ij} = \begin{cases} R_{ij}(e_ie_j^{\mathsf T}+e_je_i^{\mathsf T}), & i\lt j,\\ R_{ii}e_ie_i^{\mathsf T}, & i=j. \end{cases} $$Step 2: 控制误差。 因为 $A_{ij}\in\{0,1\}$，所以 $|R_{ij}|\le1$。对 $i\lt j$，矩阵 $e_ie_j^{\mathsf T}+e_je_i^{\mathsf T}$ 只在 $\operatorname{span}(e_i,e_j)$ 上有非零作用，并且在这个二维子空间中的矩阵为 $\begin{pmatrix}0&1\\1&0\end{pmatrix}$，范数为 $1$；对 $i=j$ 也显然有 $\|e_ie_i^{\mathsf T}\|=1$。因此 $\|Z_{ij}\|\le1$。
查看学习笔记：为什么 $\|Z_{ij}\|\le1$用矩阵 Bernstein 不等式的期望形式 (5.17)，再结合 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$。直接检查可知，$Z_{ij}^2$ 是对角矩阵：
查看学习笔记：为什么 $Z_{ij}^2$ 是对角矩阵 $$ Z_{ij}^2 = \begin{cases} R_{ij}^2(e_ie_i^{\mathsf T}+e_je_j^{\mathsf T}), & i\lt j,\\ R_{ii}^2e_ie_i^{\mathsf T}, & i=j. \end{cases} $$因此，由对称性可得
$$ \sum_{i\le j}Z_{ij}^2 = \sum_{i\lt j}R_{ij}^2(e_ie_i^{\mathsf T}+e_je_j^{\mathsf T}) + \sum_i R_{ii}^2e_ie_i^{\mathsf T} = \sum_{i=1}^n \left(\sum_{j=1}^n R_{ij}^2\right)e_ie_i^{\mathsf T}. $$这是一个对角矩阵，它的期望仍然是对角矩阵。所以
$$ \sigma^2 = \left\|\mathbb E\sum_{i\le j}Z_{ij}^2\right\| = \max_{i=1,\ldots,n} \sum_{j=1}^n\mathbb ER_{ij}^2, $$这里用到了对角矩阵的算子范数等于其对角元绝对值的最大值（习题 4.3(b)）。又因为 $R_{ij}=A_{ij}-\mathbb EA_{ij}$，而在随机块模型中 $A_{ij}$ 服从 $\operatorname{Ber}(p)$ 或 $\operatorname{Ber}(q)$，所以
$$ \mathbb ER_{ij}^2 = \operatorname{Var}(A_{ij}) \le p, $$其中最后一步使用 $p\gt q$。于是
$$ \sigma^2\le np=a. $$代回 (5.18)，得到
$$ \|R\| \lesssim \sqrt{a\log n}+\log n \lesssim \sqrt{a\log n}. \tag{5.19} $$最后一步使用了定理假设推出的 $a\gtrsim\log n$。
查看学习笔记：为什么假设推出 $a\gtrsim\log n$Step 3: 应用 Davis-Kahan。 对 $D$ 和 $A$ 应用 定理 4.1.15（也见 习题 4.16），并关注第二大特征值。第 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$。结合 (5.19) 中 $R=A-D$ 的上界，Davis-Kahan 不等式保证存在 $\theta\in\{-1,1\}$，使得 $D$ 与 $A$ 的单位特征向量（用横线标记）满足
$$ \|\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} \lt \frac1{10}, $$只要定理假设中的常数 $C$ 取得足够大，最后一个不等式就成立。两边乘以 $\sqrt n$，得到
$$ \|u_2(D)-\theta u_2(A)\|_2 \lesssim \frac{\sqrt n}{10}. $$由于 $u_2(D)$ 的所有系数都是 $\pm1$，并且这些符号正确表示社群成员关系，所以至少 $99\%$ 的 $\theta u_2(A)_j$ 与 $u_2(D)_j$ 同号，从而至少 $99\%$ 的顶点被正确分类。
查看学习笔记：特征向量误差如何推出 99% 符号正确定理 5.5.1 非平凡时，最稀疏图的期望平均度满足
$$ \frac{n(p+q)}2=\frac{a+b}{2}\asymp\log n. $$这比第 4 章得到的 $O(\sqrt n)$ 稀疏度大幅改进。习题 5.25 会让你处理没有自环的随机块模型。
5.6 应用：一般分布的协方差估计
第 4.7 节中，我们学习了如何用 $O(n)$ 个样本估计 $\mathbb R^n$ 中次高斯分布的协方差矩阵。现在去掉次高斯假设，使方法适用于更广泛的分布，甚至离散分布；代价只是一个对数过采样因子。
与第 4.7 节一样，我们用样本版本估计二阶矩矩阵
$$ \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{几乎必然} \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\|. $$ 查看学习笔记完整证明由 命题 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{几乎必然} \tag{5.21} $$对 i.i.d. 均值为零的随机矩阵和 $\sum_{i=1}^m(X_iX_i^{\mathsf T}-\Sigma)$ 应用矩阵 Bernstein 不等式的期望形式 (5.17)，得到
$$ \mathbb E\|\Sigma_m-\Sigma\| = \frac1m \mathbb E \left\| \sum_{i=1}^m(X_iX_i^{\mathsf T}-\Sigma) \right\| \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$ 和 $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}=\Sigma$，可得
$$ \mathbb E(XX^{\mathsf T})^2 \preceq K^2\operatorname{tr}(\Sigma)\Sigma, $$把这个上界代入 (5.23)，得到
$$ \sigma^2 \le K^2m\operatorname{tr}(\Sigma)\|\Sigma\|. $$再估计 $M$。由三角不等式、假设 (5.21)、$\|\Sigma\|\le\operatorname{tr}(\Sigma)$ 以及 $K\ge1$，有
$$ \|XX^{\mathsf T}-\Sigma\| \le \|X\|_2^2+\|\Sigma\| \le K^2\operatorname{tr}(\Sigma)+\|\Sigma\| \le 2K^2\operatorname{tr}(\Sigma) =M. $$把 $\sigma$ 和 $M$ 的上界代入 (5.22)，得到
$$ \mathbb E\|\Sigma_m-\Sigma\| \le \frac1m \left( \sqrt{K^2m\operatorname{tr}(\Sigma)\|\Sigma\|}\sqrt{\log n} + 2K^2\operatorname{tr}(\Sigma)\log n \right). $$最后用 $\operatorname{tr}(\Sigma)\le n\|\Sigma\|$ 化简：
$$ \mathbb E\|\Sigma_m-\Sigma\| \le K\sqrt{\frac{n\log n}{m}}\|\Sigma\| + \frac{2K^2n\log n}{m}\|\Sigma\| \le C\left( \sqrt{\frac{K^2n\log n}{m}} + \frac{K^2n\log n}{m} \right)\|\Sigma\|. $$这就是 定理 5.6.1。
定理 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$，去掉次高斯假设只付出了一个小的对数过采样因子。这个对数因子一般不能去掉；见习题 5.28。
证明末尾用了粗糙界 $\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)}. $$它总是被实际秩控制，并且对近似低秩矩阵可以远小于实际秩。相关概念是任意矩阵 $A$ 的稳定秩：
$$ 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}). $$ 查看学习笔记：有效秩练习其中 $s_i(A)$ 表示 $A$ 的奇异值。有效秩与稳定秩都是秩的“软”版本，对小扰动更稳定。
上面给出的是期望界，但同一论证也给出高概率版本：对所有 $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$。习题 5.26 会让你证明它。
查看学习笔记完整证明(5.20) 的有界性假设看似强，但一般不能去掉：若 $X$ 各向同性但以很高概率为零，则样本很可能全是零，使协方差估计不可能。习题 5.27 会让你形式化这个论证。不过，该假设可以放宽；见习题 6.34。实践中通常用截断来保证这一条件，即丢弃少量范数最大的样本。
查看学习笔记完整证明5.7 注记
关于集中不等式的更多内容，可参见专著 [52, 209]，也可参见 [21, 第 3 章]、[246, 136] 的部分章节，以及教程 [23]。
第 5.1 节中的等周方法最早由 P. Levy 发现，他证明了 定理 5.1.4 和 定理 5.1.3；参见 [147]。球面等周不等式的完整证明可见 [136, 第 2.2.1 节]。
当 V. Milman 在 1970 年代意识到 Levy 方法的力量和一般性时，这推动了测度集中原理的深远扩展；其中一部分我们已经在第 5.2 节中概览。为了保持本书简洁，我们略过了许多关键方法，包括有界差分、鞅、半群、输运、Poincare 不等式和对数 Sobolev 不等式、超收缩性、Stein 方法和 Talagrand 不等式；参见 [330, 209, 52]。第 5.1 节和第 5.2 节中的大多数内容可见 [21, 第 3 章]、[246, 209]。
高斯等周不等式（定理 5.2.2）最早由 B. Tsirelson、I. Ibragimov 和 V. Sudakov [87] 以及 C. Borell [50] 证明。高斯等周不等式还有其他若干证明，参见 [45, 22, 30]。也可以不通过等周方法，而用高斯插值初等推出高斯集中（定理 5.2.3），参见 [272]。
Hamming 立方体上的集中（定理 5.2.5）是 Harper 定理的推论；Harper 定理是 Hamming 立方体的等周不等式 [155]，另见 [46]。对称群上的集中（定理 5.2.6）归功于 B. Maurey [227]。定理 5.2.5 和 定理 5.2.6 也都可以用鞅证明，参见 [246, 第 7 章]。
正曲率黎曼流形上的集中（第 5.2.4 节）的证明可见例如 [209, 命题 2.17]。这个一般结果推出许多有趣特例，包括特殊正交群上的 定理 5.2.7 [246, 第 6.5.1 节]，以及随之而来的 Grassmannian 上的 定理 5.2.9 [246, 第 6.7.2 节]。评注 5.2.8 中提到的 Haar 测度构造可见例如 [246, 第 1 章] 和 [125, 第 2 章]；综述 [240] 讨论了生成随机酉矩阵的数值稳定方法。
连续立方体和球上的集中（定理 5.2.10）可见 [209, 命题 2.8、2.9]。定理 5.2.11 关于指数型密度的集中取自 [209, 命题 2.18]。Talagrand 集中不等式（定理 5.2.12）的证明可见 [314, 定理 6.6]、[209, 推论 4.10]、[52, 第 6.6 节]；无界分布情形的扩展可见 [167]。
Johnson-Lindenstrauss 引理（定理 5.3.1）的原始版本由 [178] 证明。关于该引理的各种版本、相关结果、应用和文献注记，可参见 [225, 第 15.2 节]。条件 $m\gtrsim\varepsilon^{-2}\log N$ 是最优的 [197]。
第 5.4 节中我们采用的矩阵集中不等式方法源于 R. Ahlswede 和 A. Winter [12] 的工作。Golden-Thompson 不等式（定理 5.4.7）是 Ahlswede-Winter 方法所依赖的结果；它的短证明可见例如 [41, 定理 9.3.7] 和 [338]。虽然 R. Ahlswede 和 A. Winter 的工作最初受到量子信息论的启发，但该方法后来被用于其他领域，早期工作包括 [349, 339, 148, 260]。
R. Ahlswede 和 A. Winter [12] 的原始论证给出的是一个稍弱于 定理 5.4.1 的矩阵 Bernstein 不等式版本，其中用 $\sum_{i=1}^N\|\mathbb EX_i^2\|$ 代替 $\sigma$。R. Oliveira [259] 后来通过修改 Ahlswede-Winter 方法改进了这个量；J. Tropp [324] 独立地用 Lieb 不等式（定理 5.4.8）而不是 Golden-Thompson 完成了同样改进。本书主要沿用 J. Tropp 对 定理 5.4.1 的证明。J. Tropp 的书 [327] 给出了 Lieb 不等式（定理 5.4.8）、习题 5.21 中的矩阵 Hoeffding 不等式、矩阵 Chernoff 不等式以及许多经典标量集中不等式的矩阵类比的自洽证明。矩阵 Bernstein 不等式（定理 5.4.1）以及一般协方差估计 (5.28) 中的维度因子 $n$ 可以替换为有效秩 [248]，从而得到无维度依赖版本。更多矩阵集中结果可见 [248, 188, 25, 26, 59]。
综述 [270] 讨论了若干有用的迹不等式，并在第 3 节概述 Golden-Thompson 不等式的证明，在命题 7 的证明中嵌入 Lieb 不等式的证明。书籍 [127] 也详细讲解了矩阵 Bernstein 不等式及其若干变体（第 8.5 节），并给出 Lieb 不等式的证明（附录 B.6）。
我们在评注 5.4.6 中陈述，并在习题 5.18 中证明，$1/x$ 和 $\ln x$ 是矩阵单调函数。矩阵单调函数的一般理论由 K. Loewner [218] 发展。
矩阵 Khintchine 不等式（定理 5.4.14）也可以从 F. Lust-Piquard [220] 的非交换 Khintchine 不等式推出；另见 [221, 65, 66, 281]。M. Rudelson [287] 最早观察并使用了这种推出方式。
关于网络中的社群检测（第 5.5 节），参见第 4 章末尾的注记。第 5.5 节中用矩阵 Bernstein 不等式分析随机图集中的方法最早由 R. Oliveira [259] 提出。
第 5.6 节关于一般高维分布的协方差估计讨论遵循 [340]。协方差估计还有一种更早且能给出类似结果的方法，依赖非交换 Khintchine 不等式；该方法由 M. Rudelson [287] 更早发展。关于协方差估计问题的更多参考文献，见第 4 章末尾的注记。
评注 5.6.3 引入并在习题 5.29 中考察的有效秩，也称为内在维度 [327, 第 7 章]。
习题 5.31 的结果来自 [340, 第 5.4.2 节]。习题 5.32 给出了草图化的一个例子。草图化是数值线性代数中常用的技巧；参见例如 [113, 98, 289, 5, 57, 214, 326, 325] 以及综述 [223, 255]。
本章省略了很多集中不等式；其中一个特别有用的是有界差分不等式（也称 McDiarmid 不等式）。它不仅适用于和，也适用于独立随机变量的一般函数，是 Hoeffding 不等式（定理 2.2.6）的推广。
设 $X=(X_1,\ldots,X_N)$ 的坐标独立，$f$ 是可测函数。假设改变第 $i$ 个坐标最多使 $f$ 的值改变 $c_i\gt 0$，即对所有 $i$ 和所有可能输入都有
$$ |f(x_1,\ldots,x_i,\ldots,x_N) - f(x_1,\ldots,x_i',\ldots,x_N)| \le c_i. $$这个定理在 $X_i$ 取值于抽象集合 $\mathcal X$ 且 $f:\mathcal X^N\to\mathbb R$ 时同样成立。
则对任意 $t\gt 0$，
$$ \mathbb P\{f(X)-\mathbb Ef(X)\ge t\} \le \exp\left( -\frac{2t^2}{\sum_{i=1}^N c_i^2} \right). $$ 查看学习笔记完整证明习题
下面保留原书习题内容，并为每题加入学习笔记证明入口。
(a) 证明每个 Lipschitz 函数都是一致连续的。
(b) 证明每个可微函数 $f:\mathbb R^n\to\mathbb R$ 若满足 $\sup_x\|\nabla f(x)\|_2\lt \infty$，则是 Lipschitz，并且
校勘：原题若按字面只写“每个可微函数”，结论不成立；这里补入有界梯度条件。也可把结论理解为扩展意义下允许右侧为 $+\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$。
查看学习笔记完整证明检查例 5.1.2 中所有关于线性泛函、线性算子和范数函数的 Lipschitz 范数断言。
查看学习笔记完整证明设 $A\subset\sqrt n S^{n-1}$，且 $\sigma(A)\gt 2\exp(-cs^2)$。
(a) 证明 $\sigma(A_s)\gt 1/2$。
(b) 推出对任意 $t\ge s$，
$$ \sigma(A_{2t})\ge1-2\exp(-ct^2). $$ 查看学习笔记完整证明定理 5.1.3 是对球面上的 欧几里得 距离表述的。证明它对 geodesic metric 也成立，其中 geodesic metric 是两点之间最短球面弧长。
查看学习笔记完整证明由 定理 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\} \le 2\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}. $$ 查看学习笔记完整证明在第 5.1.4 节中，我们由膨胀现象推出了球面上的 Lipschitz 集中。现在反向证明二者本质等价。
设随机向量 $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). $$这里 $A_t=\{x\in T:\exists y\in A,\ d(x,y)\le t\}$。
查看学习笔记完整证明由高斯等周不等式 定理 5.2.2 推出高斯集中不等式 定理 5.2.3。
查看学习笔记完整证明(a) 若 $X_1,\ldots,X_n$ 独立同分布为 $N(0,1)$，证明
$$ \left\| \max_iX_i-\mathbb E\max_iX_i \right\|_{\psi_2} \le C. $$(b) 更一般地，若 $X_1,\ldots,X_n$ 联合正态，不必独立，证明
$$ \left\| \max_iX_i-\mathbb E\max_iX_i \right\|_{\psi_2} \le C\max_i\sqrt{\operatorname{Var}(X_i)}. $$ 查看学习笔记完整证明在 习题 5.6 中，我们看到集中不等式的中心可以在均值和中位数之间替换。现在对 $L^p$ 范数证明类似结论。设 $\mathbb EZ\ge0$ 且 $p\ge1$。证明
$$ \left\| Z-\|Z\|_{L^p} \right\|_{\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). $$ 查看学习笔记完整证明按如下方法证明 定理 5.2.10 中 $T=[0,1]^n$ 的情形。
(a) 用 习题 5.11 表示 $X=\phi(Z)$，并用高斯集中控制 $f(\phi(Z))$。这里需要用到
$$ \|f\circ\phi\|_{\mathrm{Lip}} \le \|f\|_{\mathrm{Lip}}\|\phi\|_{\mathrm{Lip}}. $$(b) 证明 $\|\phi\|_{\mathrm{Lip}}$ 被绝对常数控制。
查看学习笔记完整证明按类似 习题 5.12 的策略证明 定理 5.2.10 中 $T=\sqrt n B_2^n$ 的情形：构造把高斯测度推送到 $\sqrt n B_2^n$ 均匀测度的映射 $\phi$，并检查其 Lipschitz 范数有界。
查看学习笔记完整证明设 $A$ 是 $m\times n$ 随机矩阵，其行独立、均值为零、次高斯且各向同性。证明 $Q=(1/\sqrt m)A$ 满足 Johnson-Lindenstrauss 引理。说明 $\pm1$ 元素的二值 Johnson-Lindenstrauss 变换是这一结论的特例。
查看学习笔记完整证明证明 Johnson-Lindenstrauss 引理中的目标维度 $n=O(\log N)$ 是最优的，即使允许非线性降维映射也一样。
(a) 设 $z_1,\ldots,z_N\in\mathbb R^n$ 满足
$$ 1\lt \|z_i-z_j\|_2\le2 \qquad (i\ne j). $$证明 $N\le5^n$。
(b) 若 $n\lt \frac12\log N$，构造 $x_1,\ldots,x_N\in\mathbb R^N$，使不存在任何映射 $T:\mathbb R^N\to\mathbb R^n$ 对所有点对保持 $0.99$ 到 $1.01$ 的距离失真。
查看学习笔记完整证明练习定义 5.4.2 中的矩阵函数。令 $X$ 是一个对称矩阵。
(a) 对任意多项式 $f(x)=a_0+a_1x+\cdots+a_px^p$，检查
$$ f(X)=a_0I_n+a_1X+\cdots+a_pX^p. $$右侧使用矩阵加法和矩阵乘法，因此 $X^p$ 表示 $X$ 与自身矩阵相乘 $p$ 次。
(b) 更一般地，若
$$ f(x)=\sum_{k=1}^{\infty}a_k(x-x_0)^k $$是在 $x_0$ 附近收敛的幂级数，检查
$$ f(X)=\sum_{k=1}^{\infty}a_k(X-x_0I_n)^k, $$其中矩阵级数在 Frobenius 范数中收敛，因此也在算子范数中收敛。
(c) 说明
$$ e^X=I_n+X+\frac{X^2}{2!}+\frac{X^3}{3!}+\cdots. $$ 查看学习笔记完整证明(a) 检查：若矩阵 $X,Y$ 交换，则
$$ X\preceq Y \quad\Longrightarrow\quad f(X)\preceq f(Y) \quad\text{for any 弱增 }f:\mathbb R\to\mathbb R. $$(b) 给出例子说明 (a) 对非交换矩阵可能失败。
查看学习笔记完整证明令 $X,Y$ 为对称 $n\times n$ 矩阵，且 $X$ 可逆并满足
$$ 0\preceq X\preceq Y. $$(a) 证明 $Y$ 也可逆，并且
$$ X^{-1}\succeq Y^{-1}\succeq0. $$(b) 检查恒等式
$$ \ln x=\int_0^\infty \left( \frac1{1+t}-\frac1{x+t} \right)\,dt. $$(c) 用 (b) 中的公式，从 (a) 推出
$$ \ln X\preceq\ln Y. $$ 查看学习笔记完整证明令 $X,Y$ 为 $n\times n$ 对称矩阵。
(a) 若 $X,Y$ 交换，即 $XY=YX$，证明
$$ e^{X+Y}=e^Xe^Y. $$(b) 找出对称矩阵 $X,Y$ 的例子，使得
$$ e^{X+Y}\ne e^Xe^Y. $$ 查看学习笔记完整证明从矩阵 Bernstein 不等式（定理 5.4.1）推出如下期望界：
$$ \mathbb E \left\| \sum_{i=1}^NX_i \right\| \lesssim \left\| \sum_{i=1}^N\mathbb EX_i^2 \right\|^{1/2} \sqrt{1+\log n} + K(1+\log n). $$ 查看学习笔记完整证明仿照矩阵 Bernstein 不等式（定理 5.4.1）的证明，证明矩阵 Hoeffding 不等式（定理 5.4.13）。
查看学习笔记完整证明由矩阵 Hoeffding 不等式（定理 5.4.13）推出矩阵 Khintchine 不等式（定理 5.4.14）。
查看学习笔记完整证明令 $X_1,\ldots,X_N$ 为独立、均值为零的 $m\times n$ 随机矩阵，并且对所有 $i$ 都有 $\|X_i\|\le K$ 几乎处处成立。证明：对任意 $t\ge0$，
$$ \mathbb P\left\{ \left\| \sum_{i=1}^NX_i \right\|\ge t \right\} \le 2(m+n) \exp\left( -\frac{t^2/2}{\sigma^2+Kt/3} \right), $$其中
$$ \sigma^2= \left\| \sum_{i=1}^N\mathbb EX_i^{\mathsf T}X_i \right\| + \left\| \sum_{i=1}^N\mathbb EX_iX_i^{\mathsf T} \right\|. $$ 查看学习笔记完整证明证明矩形矩阵版矩阵 Khintchine 不等式。令 $\varepsilon_1,\ldots,\varepsilon_N$ 为独立 Rademacher 随机变量，令 $A_1,\ldots,A_N$ 为任意固定的 $m\times n$ 矩阵。证明：对每个 $p\in[1,\infty)$，
$$ \left( \mathbb E \left\| \sum_{i=1}^N\varepsilon_iA_i \right\|^p \right)^{1/p} \le C\sigma\sqrt{p+\log(m+n)}, $$其中
$$ \sigma^2= \left\| \sum_{i=1}^NA_i^{\mathsf T}A_i \right\| + \left\| \sum_{i=1}^NA_iA_i^{\mathsf T} \right\|. $$ 查看学习笔记完整证明定义 4.5.1 中的随机块模型 $G(n,p,q)$ 允许自环，也就是说每个顶点以概率 $p$ 与自身相连。修改该定义，使模型不允许自环；然后在这个调整后的模型下证明 定理 5.5.1 的对应版本。
查看学习笔记完整证明证明 评注 5.6.5 中陈述的协方差估计高概率版本。
查看学习笔记完整证明证明 定理 5.6.1 中的有界性假设 (5.20) 一般不能去掉。参见 评注 5.6.6。
查看学习笔记完整证明证明一般协方差估计 (5.24) 和矩阵 Bernstein 不等式 (5.17) 中的对数因子一般不可避免。
(a) 构造一个概率分布，使得若 $m\not\gtrsim n\log n$，则协方差估计界
$$ \|\Sigma_m-\Sigma\|\lt \|\Sigma\| $$以高概率失败。
(b) 推出矩阵 Bernstein 不等式 (5.17) 中的对数因子不能去掉。
查看学习笔记完整证明对 $n\times n$ 对称 半正定 矩阵 $\Sigma$，其有效秩在 (5.26) 中定义为
$$ r(\Sigma)=\frac{\operatorname{tr}(\Sigma)}{\|\Sigma\|}. $$不同于精确 rank 只数非零特征值，有效秩更稳健地刻画有多少特征值真正影响矩阵结构。
(a) 证明
$$ 1\le r(\Sigma)\le\operatorname{rank}(\Sigma)\le n. $$(b) 说明这个不等式是最优的：存在 满秩 矩阵，其有效秩可以任意接近 $1$。
(c) 稳定性：说明有效秩不同于 代数秩，它是矩阵的连续函数，例如关于算子范数连续。
(d) 若随机向量 $X$ 取值于 $\mathbb R^n$ 的某个 $k$ 维子空间，证明 $\Sigma=\mathbb EXX^{\mathsf T}$ 满足 $\operatorname{rank}(\Sigma)\le k$，从而 $r(\Sigma)\le k$。
查看学习笔记完整证明考虑 $\mathbb R^n$ 中一个等范数 Parseval frame $(u_1,\ldots,u_M)$。证明：随机抽取
$$ m\gtrsim n\log n $$个 框架元素 后，以高概率仍形成一个“近似”frame；请形式化这里的“近似”含义。
查看学习笔记完整证明证明 定理 4.6.1 的一个版本，其中随机矩阵的行可有任意分布，不必次高斯。令 $A$ 为 $m\times n$ 随机矩阵，其行 $A_i$ 独立且各向同性。假设存在 $K\ge0$，使得对每个 $i$ 都有
$$ \|A_i\|_2\le K\sqrt n \quad\text{几乎必然}. $$证明：对每个 $t\ge1$，有
$$ \sqrt m-Kt\sqrt{n\log n} \le s_n(A) \le s_1(A) \le \sqrt m+Kt\sqrt{n\log n} $$的概率至少为 $1-2n^{-ct^2}$。
查看学习笔记完整证明有些矩阵太大，无法直接计算特征值和特征向量。一个处理技巧是子采样：随机抽取一些行或列，形成较小矩阵。这里证明：可以用由随机抽取行形成的小矩阵 $B$ 来近似高瘦 $N\times n$ 矩阵 $A$ 的奇异值。
设 $A$ 的所有行范数相同。令 $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| \le 0.1s_1(A)^2. $$ 查看学习笔记完整证明