翻译状态说明
本页为第 4 章的精校翻译，已覆盖正文、Notes、Exercises 4.1-4.51、明确 Proof 卡片和原书 Figure 4.1-4.7。
第 4 章 随机矩阵
本章开始研究随机矩阵的非渐近理论。第 4.1 节快速回顾线性代数，重点不是重复 SVD 等基础事实，而是为后续随机矩阵分析准备奇异值、算子范数、低秩逼近和扰动理论。
第 4.2 节引入 $\varepsilon$-net、covering number 与 packing number。第 4.3 节把这些几何概念连接到纠错码。第 4.4 与第 4.6 节发展 $\varepsilon$-net argument，用于证明次高斯随机矩阵算子范数上界以及奇异值双侧界。随后应用到社区检测、协方差估计和聚类。
4.1 线性代数快速回顾
先回顾一些关于矩阵的基本材料。你很可能已经在线性代数课程中学过其中不少内容；熟悉的部分可以跳过，但后面的一些内容可能是新的。
4.1.1 奇异值分解
谱分解 (3.7) 是强大的工具，但它只适用于对称矩阵。奇异值分解（singular value decomposition, SVD）把这一思想推广到所有矩阵。
任意实 $m\times n$ 矩阵 $A$ 都可以写成
$$ A = \sum_{i=1}^r s_i u_i v_i^{\mathsf T}, \qquad r=\min(m,n). \tag{4.1} $$这里 $s_i$ 是非负数，称为 $A$ 的奇异值；$u_i\in\mathbb R^m$ 是正交归一向量，称为 $A$ 的左奇异向量；$v_i\in\mathbb R^n$ 是正交归一向量，称为 $A$ 的右奇异向量。
查看学习笔记完整证明不失一般性，可假设 $m\ge n$。由于 $A^{\mathsf T}A$ 是 $n\times n$ 对称正半定矩阵，谱定理告诉我们它有实非负特征值 $s_1^2,\ldots,s_n^2$ 和正交归一特征向量 $v_1,\ldots,v_n\in\mathbb R^n$，满足
$$ A^{\mathsf T}Av_i=s_i^2v_i. $$向量 $Av_i$ 两两正交，因为
$$ \langle Av_i,Av_j\rangle = \langle A^{\mathsf T}Av_i,v_j\rangle = s_i^2\langle v_i,v_j\rangle = s_i^2\delta_{ij}, \qquad i,j=1,\ldots,n. \tag{4.2} $$因此存在正交归一向量 $u_1,\ldots,u_n\in\mathbb R^m$，使得
$$ Av_i=s_iu_i, \qquad i=1,\ldots,n. \tag{4.3} $$当 $s_i\ne0$ 时，(4.3) 唯一定义 $u_i$，而 (4.2) 保证它们正交归一。当 $s_i=0$ 时，由 (4.2)（取 $j=i$）得 $Av_i=0$，所以 (4.3) 平凡成立；此时可任选 $u_i$，只要保持正交归一性。
由于 $v_1,\ldots,v_n$ 构成 $\mathbb R^n$ 的正交归一基，
$$ I_n=\sum_{i=1}^n v_iv_i^{\mathsf T}. $$左乘 $A$ 并使用 (4.3)，得到所需 SVD：
$$ A = \sum_{i=1}^n (Av_i)v_i^{\mathsf T} = \sum_{i=1}^n s_i u_i v_i^{\mathsf T}. $$可以思考一下：这个论证在哪一步用到了 $m\ge n$？
查看学习笔记：$m\ge n$ 用在哪里从 (4.3) 可见，SVD 给出了矩阵的几何图像：$A$ 先把每个正交方向 $v_i$ 按 $s_i$ 拉伸，然后把空间“旋转”，把正交归一基 $(v_i)$ 映到 $(u_i)$。
为方便起见，通常对 $i>r$ 令 $s_i=0$，并把 $s_i$ 按非增顺序排列。也可把 $(u_i)$ 和 $(v_i)$ 分别扩展为 $\mathbb R^m$ 和 $\mathbb R^n$ 的正交归一基。这样 SVD (4.1) 可写成矩阵形式
$$ A=U\Sigma V^{\mathsf T}, \tag{4.4} $$其中 $U$ 是以左奇异向量 $u_i$ 为列的 $m\times m$ 正交矩阵，$V$ 是以右奇异向量 $v_i$ 为列的 $n\times n$ 正交矩阵，$\Sigma$ 是以奇异值 $s_i$ 为对角元素的 $m\times n$ 对角矩阵。
类似地，对称 $n\times n$ 矩阵 $A$ 的谱分解也可写成
$$ A = \sum_{i=1}^n \lambda_i u_i u_i^{\mathsf T} = U\Lambda U^{\mathsf T}, $$其中 $U$ 是以特征向量 $u_i$ 为列的 $n\times n$ 正交矩阵，$\Lambda$ 是以特征值 $\lambda_i$ 为对角元素的 $n\times n$ 对角矩阵。
谱分解与奇异值分解紧密相关。由于
$$ AA^{\mathsf T} = \sum_{i=1}^r s_i^2 u_i u_i^{\mathsf T}, \qquad A^{\mathsf T}A = \sum_{i=1}^r s_i^2 v_i v_i^{\mathsf T}, $$左奇异向量 $u_i$ 是 $AA^{\mathsf T}$ 的特征向量，右奇异向量 $v_i$ 是 $A^{\mathsf T}A$ 的特征向量，而 $A$ 的奇异值 $s_i$ 是 $AA^{\mathsf T}$ 和 $A^{\mathsf T}A$ 的特征值平方根：
$$ s_i(A) = \sqrt{\lambda_i(AA^{\mathsf T})} = \sqrt{\lambda_i(A^{\mathsf T}A)}. \tag{4.5} $$考虑 $\mathbb R^n$ 中到 $k$ 维子空间 $E$ 上的正交投影 $P$。若 $u_1,\ldots,u_k$ 是 $E$ 的正交归一基，则向量 $x$ 到 $E$ 上的投影为
$$ Px = \sum_{i=1}^k \langle u_i,x\rangle u_i. $$因此可把 $P$ 写成谱分解
$$ P = \sum_{i=1}^k u_i u_i^{\mathsf T} = UU^{\mathsf T}, $$其中 $U$ 是以 $u_i$ 为正交归一列的 $n\times k$ 矩阵。特别地，$P$ 是对称矩阵，特征值为 $k$ 个 $1$ 和 $n-k$ 个 $0$。
4.1.2 Min-max 定理
我们在 Proposition 3.2.2 中见过一种基于优化的特征值描述。下面是另一种非常有用的描述。
$n\times n$ 对称矩阵 $A$ 的第 $k$ 大特征值可写成
$$ \lambda_k(A) = \max_{\dim E=k} \min_{x\in S(E)} x^{\mathsf T}Ax = \min_{\dim E=n-k+1} \max_{x\in S(E)} x^{\mathsf T}Ax, \tag{4.6} $$其中最大值和最小值分别取遍所有维数为 $k$ 和 $n-k+1$ 的子空间 $E$，而 $S(E)$ 表示 $E$ 中的 Euclidean 单位球面，即 $E$ 中所有单位向量的集合。
只证明第一个等式。为证明 $\lambda_k=\lambda_k(A)$ 的一个方向，需要找到一个 $k$ 维子空间 $E$，使得
$$ x^{\mathsf T}Ax\ge \lambda_k \qquad \text{for all }x\in S(E). $$如何找到这样的 $E$？取谱分解
$$ A=\sum_{i=1}^n \lambda_i u_i u_i^{\mathsf T}, $$并选择 $A$ “最大”的子空间 $E=\operatorname{span}(u_1,\ldots,u_k)$。任意 $x\in S(E)$ 可写成 $x=\sum_{i=1}^k a_i u_i$。由 $u_i$ 的正交归一性和 $\lambda_i$ 的单调性，
$$ x^{\mathsf T}Ax = \sum_{i=1}^k \lambda_i a_i^2 \ge \lambda_k\sum_{i=1}^k a_i^2 = \lambda_k. $$反过来，要在任意 $k$ 维子空间 $E$ 中找到一个 $x\in S(E)$，使得 $x^{\mathsf T}Ax\le\lambda_k$。看 $A$ “最小”的方向所在的子空间
$$ F=\operatorname{span}(u_k,\ldots,u_n). $$由于 $\dim(E)+\dim(F)=n+1$，交集 $E\cap F$ 非平凡，因此存在单位向量 $x\in E\cap F$。写成 $x=\sum_{i=k}^n a_i u_i$，得到
$$ x^{\mathsf T}Ax = \sum_{i=k}^n \lambda_i a_i^2 \le \lambda_k\sum_{i=k}^n a_i^2 = \lambda_k. $$这就得到 (4.6) 中第一个等式。第二个等式可通过把第一个等式应用于 $-A$ 并按相反顺序排列特征值得到。
把 Theorem 4.1.6 应用于 $A^{\mathsf T}A$，并使用 (4.5)，立刻得到下面的奇异值版本。
设 $A$ 是 $m\times n$ 矩阵，奇异值满足 $s_1\ge s_2\ge\cdots\ge s_n\ge0$。那么
$$ s_k(A) = \max_{\dim E=k} \min_{x\in S(E)} \|Ax\|_2 = \min_{\dim E=n-k+1} \max_{x\in S(E)} \|Ax\|_2, $$其中最大值和最小值分别取遍所有维数为 $k$ 和 $n-k+1$ 的子空间 $E$，$S(E)$ 表示 $E$ 中的 Euclidean 单位球面。
4.1.3 Frobenius 范数与算子范数
所有 $m\times n$ 矩阵构成的线性空间有几种经典范数。最简单的是 Frobenius 范数，也称 Hilbert-Schmidt 范数；它就是 $\mathbb R^{m\times n}$ 上的 $\ell^2$ 范数：
$$ \|A\|_F := \left( \sum_{i=1}^m\sum_{j=1}^n A_{ij}^2 \right)^{1/2}. $$
简言之，Frobenius 范数就是把矩阵向量化之后的 Euclidean 范数。类似地，矩阵内积就是 $\mathbb R^{m\times n}$ 上通常的点积：
$$ \langle A,B\rangle = \sum_{i=1}^m\sum_{j=1}^n A_{ij}B_{ij} = \operatorname{tr}(A^{\mathsf T}B). \tag{4.7} $$
矩阵与自身的内积给出范数平方：
$$ \|A\|_F^2 = \langle A,A\rangle = \operatorname{tr}(A^{\mathsf T}A). \tag{4.8} $$
另一个关键矩阵范数是算子范数，也称 spectral norm。它度量线性变换 $A$ 最多能把向量拉伸多少。
$m\times n$ 矩阵 $A$ 的算子范数，是使得
$$ \|Ax\|_2 \le K\|x\|_2 \qquad \text{for all }x\in\mathbb R^n $$成立的最小数 $K$。等价地，
$$ \|A\| = \max_{x\ne0}\frac{\|Ax\|_2}{\|x\|_2} = \max_{\|x\|_2\le1}\|Ax\|_2 = \max_{\|x\|_2=1}\|Ax\|_2 = \max_{\|x\|_2=\|y\|_2=1} |y^{\mathsf T}Ax|. \tag{4.9} $$前三个等式由缩放得到。最后一个等式来自 Euclidean 范数的对偶公式 (1.6)：
$$ \|Ax\|_2 = \max_{\|y\|_2=1}\langle Ax,y\rangle. $$
在 (4.9) 中保留或去掉绝对值都得到同一个数；原因是如果 $y$ 可取，$-y$ 也可取。你将在 Exercise 4.2 中验证 $\|A\|$ 确实是一个范数。
可以把 Definition 4.1.8 中的 $\ell^2$ 范数替换为其他范数，从而得到更一般的算子范数概念。你将在 Exercises 4.18-4.22 中探索这一点。
4.1.4 矩阵范数与谱
Frobenius 范数和 spectral norm 都是正交不变的。也就是说，对任意矩阵 $A$ 以及维度匹配的正交矩阵 $Q$ 和 $R$，有
$$ \|QAR\|_F=\|A\|_F \qquad\text{and}\qquad \|QAR\|=\|A\|. $$第一部分由 (4.8) 和 trace 的循环性质得到：
$$ \begin{aligned} \|QAR\|_F^2 &= \operatorname{tr} (R^{\mathsf T}A^{\mathsf T}Q^{\mathsf T}QAR)\\ &= \operatorname{tr} (R^{\mathsf T}A^{\mathsf T}AR)\\ &= \operatorname{tr} (RR^{\mathsf T}A^{\mathsf T}A)\\ &= \operatorname{tr}(A^{\mathsf T}A) = \|A\|_F^2. \end{aligned} $$第二部分中，(4.9) 表明 $\|QAR\|$ 可通过在单位向量 $x,y$ 上最大化双线性型
$$ y^{\mathsf T}QARx = (Q^{\mathsf T}y)^{\mathsf T}A(Rx) $$得到。由于 $Q$ 和 $R$ 是正交矩阵，$Q^{\mathsf T}y$ 与 $Rx$ 仍遍历所有单位向量，因此最大值正是 $\|A\|$。
对任意 $m\times n$ 矩阵 $A$，若奇异值满足 $s_1(A)\ge\cdots\ge s_n(A)$，则
$$ \|A\|_F = \left( \sum_{i=1}^n s_i(A)^2 \right)^{1/2}, \qquad \|A\|=s_1(A). $$对 Frobenius 范数部分，使用 SVD (4.4) 与正交不变性（Lemma 4.1.10）：
$$ \|A\|_F = \|U\Sigma V^{\mathsf T}\|_F = \|\Sigma\|_F. $$而 $\Sigma$ 唯一可能非零的元素正是 $s_1,\ldots,s_n$。算子范数部分直接由奇异值 min-max 定理（Corollary 4.1.7）取 $k=1$ 得到。
如果 $A$ 是对称矩阵，特征值为 $\lambda_k(A)$，那么
$$ \|A\| = \max_k|\lambda_k(A)| = \max_{\|x\|_2=1}|x^{\mathsf T}Ax|. \tag{4.10} $$因此在算子范数定义 (4.9) 中可以取 $x=y$。第一个等式来自 Lemma 4.1.11，因为对称矩阵的奇异值就是 $|\lambda_k(A)|$。Min-max 定理（Theorem 4.1.6）给出
$$ |\lambda_k(A)| \le \max_{\|x\|_2=1}|x^{\mathsf T}Ax|, $$这证明了 (4.10) 中的一个方向；另一个方向由在 (4.9) 中取 $x=y$ 立即得到。
可以通过 Exercises 4.2-4.10 进一步熟悉 Frobenius 范数和算子范数。
4.1.5 低秩逼近
假设我们想用一个给定秩 $k$ 的矩阵 $B$ 逼近矩阵 $A$。应该如何构造最佳的 $B$？以算子范数度量时，最小逼近误差是多少？答案是：截断 $A$ 的 SVD，逼近误差正是 $A$ 的第 $k+1$ 个奇异值。
设 $A$ 是 $m\times n$ 矩阵，其 SVD 为
$$ A = \sum_{i=1}^n s_i u_i v_i^{\mathsf T}. $$那么对任意 $1\le k\le n$，有
$$ \min_{\operatorname{rank}(B)=k} \|A-B\| = s_{k+1}, $$其中需要时约定 $s_{n+1}=0$。最小值在
$$ B = \sum_{i=1}^k s_i u_i v_i^{\mathsf T} $$处达到。
设 $B$ 是任意秩为 $k$ 的 $m\times n$ 矩阵，其核 $E=\ker(B)$ 的维数为 $n-k$。由奇异值 min-max 定理（Corollary 4.1.7）对 $k+1$ 使用，可得
$$ \begin{aligned} \|A-B\| &\ge \max_{x\in S(E)} \|(A-B)x\|_2\\ &= \max_{x\in S(E)} \|Ax\|_2\\ &\ge s_{k+1}(A). \end{aligned} $$反方向，取
$$ B = \sum_{i=1}^k s_i u_i v_i^{\mathsf T}, $$则
$$ A-B = \sum_{i=k+1}^n s_i u_i v_i^{\mathsf T}. $$这个矩阵的最大奇异值是 $s_{k+1}$，由 Lemma 4.1.11，它也就是算子范数。
4.1.6 扰动理论
扰动理论研究矩阵扰动时特征值和特征向量如何变化。对特征值而言，min-max 定理（Theorem 4.1.6 和 Corollary 4.1.7）的一个应用给出如下结果。
同维对称矩阵 $A$ 和 $B$ 的第 $k$ 大特征值满足
$$ |\lambda_k(A)-\lambda_k(B)| \le \|A-B\|. $$类似地，一般矩形矩阵的第 $k$ 大奇异值满足
$$ |s_k(A)-s_k(B)| \le \|A-B\|. $$特征向量也有类似结果，但必须小心追踪扰动前后的同一个特征向量。如果特征值太接近，一个小扰动可能交换它们的位置，导致特征向量误差很大，因为对应特征向量正交、相距很远。为避免这种情形，我们假设 $A$ 的特征值彼此分离得足够开。
考虑两个对称矩阵 $A$ 和 $B$，其谱分解分别为
$$ A=\sum_{i=1}^n\lambda_i u_i u_i^{\mathsf T}, \qquad B=\sum_{i=1}^n\mu_i v_i v_i^{\mathsf T}, $$其中特征值按非增顺序排列。假设 $A$ 的第 $k$ 大特征值与其余特征值 $\delta$-分离：
$$ \min_{i:\,i\ne k}|\lambda_k-\lambda_i| = \delta>0. $$那么特征向量 $u_k$ 和 $v_k$ 之间的夹角（取 $0$ 到 $\pi/2$ 之间的数）满足
$$ \sin\angle(u_k,v_k) \le \frac{2\|A-B\|}{\delta}. $$ 查看学习笔记完整证明下面从一个更强的结果推出它。这个更强结果可同时处理多个特征向量。我们会用到 spectral projection，也就是投影到某些特征向量张成空间上的正交投影。
考虑两个对称矩阵 $A$ 和 $B$，谱分解分别为
$$ A=\sum_{i=1}^n\lambda_i u_i u_i^{\mathsf T}, \qquad B=\sum_{j=1}^n\mu_j v_j v_j^{\mathsf T}. $$设 $I,J$ 是 $\mathbb R$ 中两个 $\delta$-分离的子集，且 $I$ 是区间。则谱投影
$$ P=\sum_{i:\lambda_i\in I}u_i u_i^{\mathsf T}, \qquad Q=\sum_{j:\mu_j\in J}v_j v_j^{\mathsf T} $$满足
$$ \|QP\| \le \frac{\|A-B\|}{\delta}. $$不失一般性，假设区间 $I$ 有界且闭。给 $A$ 和 $B$ 加上相同的单位矩阵倍数，可把 $I$ 居中为 $I=[-r,r]$，使得当 $\lambda_i\in I$ 时 $|\lambda_i|\le r$，而当 $\mu_j\in J$ 时 $|\mu_j|\ge r+\delta$。令 $H:=B-A$。核心是研究 $P$ 和 $Q$ 如何通过 $H$ 相互作用：
$$ \|H\| \ge \|QHP\| = \|QBP-QAP\| \ge \|QBP\|-\|QAP\|. \tag{4.11} $$谱投影 $Q$ 与 $B$ 交换，因此
$$ \|QBP\| = \|BQP\| \ge (r+\delta)\|QP\|. \tag{4.12} $$最后一个不等式的原因是：$Q$ 的像空间由满足 $|\mu_j|\ge r+\delta$ 的正交向量 $v_j$ 张成，而 $B$ 把每个这样的 $v_j$ 映为 $\mu_jv_j$，至少按 $r+\delta$ 倍拉伸。因此对任意 $x$，有 $\|B QP x\|_2\ge (r+\delta)\|QP x\|_2$；再对单位向量 $x$ 取上确界即得 (4.12)。
另一方面，
$$ AP=PAP = \sum_{i:\lambda_i\in I} \lambda_i u_i u_i^{\mathsf T}, $$所以
$$ \|QAP\| = \|QPAP\| \le \|QP\|\cdot\|AP\| \le r\|QP\|, \tag{4.13} $$因为 $\|AP\|=\max_{\lambda_i\in I}|\lambda_i|\le r$。把 (4.12) 与 (4.13) 代入 (4.11)，得到 $\|H\|\ge\delta\|QP\|$，证明完成。
令 $\varepsilon:=\|A-B\|$。可假设 $\varepsilon\le\delta/2$，否则结论平凡。由 Weyl 不等式（Lemma 4.1.14），对每个 $j$ 有 $|\lambda_j-\mu_j|\le\varepsilon$，因此
$$ \min_{j:\,j\ne k}|\lambda_k-\mu_j| \ge \min_{j:\,j\ne k}|\lambda_k-\lambda_j|-\varepsilon = \delta-\varepsilon \ge \delta/2. $$把 Lemma 4.1.16 应用于 $\delta/2$-分离的集合 $I=\{\lambda_k\}$ 和 $J=\{\mu_j:j\ne k\}$，得到
$$ \|QP\|\le \frac{2\varepsilon}{\delta}. $$最后，$P$ 和 $I_n-Q$ 分别是到 $u_k$ 与 $v_k$ 方向上的正交投影，直接计算得到
$$ \|QP\| = \|Qu_k\|_2 = \sin\angle(u_k,v_k). $$定理得证。
Exercises 4.11-4.16 会继续探索 Davis-Kahan 不等式的其他版本。
4.1.7 Isometries
矩阵 $A$ 的极端奇异值 $s_1$ 和 $s_n$ 有重要几何意义。由 min-max 定理（Corollary 4.1.7），它们可表示为
$$ s_1(A) = \max_{\|x\|_2=1}\|Ax\|_2, \qquad s_n(A) = \min_{\|x\|_2=1}\|Ax\|_2. \tag{4.14} $$
把这个不等式应用到 $x-y$ 而不是 $x$，得到对所有 $x,y\in\mathbb R^n$，
$$ s_n(A)\|x-y\|_2 \le \|Ax-Ay\|_2 \le s_1(A)\|x-y\|_2. $$
所以，极端奇异值给出了线性映射 $A$ 扭曲空间的上下限。条件数
$$ \kappa(A)=\frac{s_1(A)}{s_n(A)} $$
度量最坏情形下的扭曲因子，是数值算法中的关键量。
如果矩阵精确保距离，也就是
$$ \|Ax\|_2=\|x\|_2 \qquad \text{for all }x\in\mathbb R^n, $$
则称它为 isometry。基本例子是 $m\times m$ 正交矩阵 $U$。更一般地，任取 $U$ 的 $n$ 列构成 $m\times n$ 矩阵，它也是 isometry，给出从 $\mathbb R^n$ 到 $\mathbb R^m$ 的 isometric embedding。事实上，所有 isometry 都是这种形式：对 $m\times n$ 矩阵 $A$ 且 $m\ge n$，下面性质等价：
(a) $A$ 的列正交归一，即 $A^{\mathsf T}A=I_n$；
(b) $A$ 是 isometry；
(c) $A$ 的所有奇异值都等于 $1$。
下面证明一个更强的近似版本；它在处理随机矩阵时会很有用。
设 $A$ 是 $m\times n$ 矩阵，$m\ge n$，并设 $\varepsilon\ge0$。下面性质等价：
(a) $\|A^{\mathsf T}A-I_n\|\le\varepsilon$。
(b) 对任意 $x\in\mathbb R^n$，
$$ (1-\varepsilon)\|x\|_2^2 \le \|Ax\|_2^2 \le (1+\varepsilon)\|x\|_2^2. $$(c)
$$ 1-\varepsilon \le s_n(A)^2 \le s_1(A)^2 \le 1+\varepsilon. $$先证明 (a) $\Leftrightarrow$ (b)。由缩放，可在 (b) 中假设 $\|x\|_2=1$。由 (4.10)，
$$ \begin{aligned} \|A^{\mathsf T}A-I_n\| &= \max_{\|x\|_2=1} \left| x^{\mathsf T}(A^{\mathsf T}A-I_n)x \right|\\ &= \max_{\|x\|_2=1} \left| \|Ax\|_2^2-1 \right|. \end{aligned} $$这个量由 $\varepsilon$ 控制，正等价于 (b) 对所有单位向量成立。
(b) $\Leftrightarrow$ (c) 直接来自 (4.14)。
下面是 Lemma 4.1.17 中关键蕴含 (a) $\Rightarrow$ (c) 的一个更方便版本。对任意 $z,\delta\ge0$，有
$$ |z^2-1| \le \max(\delta,\delta^2) \quad\Longrightarrow\quad |z-1|\le\delta. $$因此，令 $\varepsilon=\max(\delta,\delta^2)$，可得
$$ \|A^{\mathsf T}A-I_n\| \le \max(\delta,\delta^2) \quad\Longrightarrow\quad 1-\delta \le s_n(A) \le s_1(A) \le 1+\delta. \tag{4.15} $$Exercise 4.17 会为 Lemma 4.1.17 增加另一个方便的等价性质。
4.2 Nets, covering and packing
我们将发展一个简单但强大的方法：$\varepsilon$-net argument，并展示它在随机矩阵分析中的作用。本节先回顾 $\varepsilon$-net 的概念；你可能在实分析中见过它。随后把它与 covering、packing、entropy、volume 和 coding 等基本概念联系起来。
设 $(T,d)$ 是度量空间，$K\subset T$，$\varepsilon>0$。子集 $\mathcal N\subset K$ 称为 $K$ 的 $\varepsilon$-net，如果 $K$ 中每个点都在 $\mathcal N$ 中某点的 $\varepsilon$ 距离内，也就是
$$ \forall x\in K\ \exists x_0\in\mathcal N: d(x,x_0)\le\varepsilon. $$等价地，如果以 $\mathcal N$ 中点为中心、半径为 $\varepsilon$ 的球覆盖了 $K$，那么 $\mathcal N$ 就是 $K$ 的 $\varepsilon$-net；见图 4.1(a)。
如果这个一般性让人感到抽象，请记住一个关键例子：令 $T=\mathbb R^n$，并取 Euclidean 距离
$$ d(x,y)=\|x-y\|_2, \qquad x,y\in\mathbb R^n. \tag{4.16} $$
在这个情形中，我们用圆球覆盖子集 $K\subset\mathbb R^n$，如图 4.1(a)。在 Corollary 0.0.3 中我们已经见过这种覆盖的一个例子，当时 $K$ 是一个 polytope。
$K$ 的 $\varepsilon$-net 的最小基数称为 $K$ 的覆盖数，记为 $\mathcal N(K,d,\varepsilon)$。等价地，$\mathcal N(K,d,\varepsilon)$ 是用中心在 $K$ 中、半径为 $\varepsilon$ 的闭球覆盖 $K$ 所需的最少球数。
实分析中的一个重要结果说：完备度量空间 $(T,d)$ 的子集 $K$ 是 precompact 的，也就是其闭包紧，当且仅当
$$ \mathcal N(K,d,\varepsilon)<\infty \qquad \text{for every }\varepsilon>0. $$因此，可以把覆盖数 $\mathcal N(K,d,\varepsilon)$ 看作 $K$ 的紧性的定量度量。
与 covering 密切相关的是 packing。
度量空间 $(T,d)$ 的子集 $\mathcal N$ 称为 $\varepsilon$-separated，如果
$$ d(x,y)>\varepsilon \qquad \text{for any distinct points }x,y\in\mathcal N. $$给定集合 $K\subset T$ 中 $\varepsilon$-separated 子集的最大可能基数，称为 $K$ 的装填数，记为 $\mathcal P(K,d,\varepsilon)$。
如果 $\mathcal N$ 是 $\varepsilon$-separated 的，则由三角不等式，以 $\mathcal N$ 中点为中心的闭 $\varepsilon/2$-球两两不交。因此，总可以像图 4.1(b) 那样，向 $K$ 中“装入”至少 $\mathcal P(K,d,\varepsilon)$ 个两两不交的 $\varepsilon/2$-球。
设 $\mathcal N$ 是 $K$ 的一个极大 $\varepsilon$-separated 子集。那么 $\mathcal N$ 是 $K$ 的一个 $\varepsilon$-net。
任取 $x\in K$。我们要证明存在 $x_0\in\mathcal N$，使得 $d(x,x_0)\le\varepsilon$。如果 $x\in\mathcal N$，取 $x_0=x$ 即可。若 $x\notin\mathcal N$，由极大性，$\mathcal N\cup\{x\}$ 不是 $\varepsilon$-separated 的。这正意味着存在 $x_0\in\mathcal N$，使得 $d(x,x_0)\le\varepsilon$。
Lemma 4.2.6 给出了构造给定集合 $K$ 的 $\varepsilon$-net 的迭代算法。先任取一点 $x_1\in K$，再取与 $x_1$ 距离大于 $\varepsilon$ 的 $x_2\in K$，再取与 $x_1,x_2$ 距离都大于 $\varepsilon$ 的 $x_3$，依此类推。如果 $K$ 紧，这个过程会在有限步后停止，并给出 $K$ 的一个 $\varepsilon$-net。
覆盖数和装填数本质上等价。
对任意集合 $K\subset T$ 和任意 $\varepsilon>0$，有
$$ \mathcal P(K,d,2\varepsilon) \le \mathcal N(K,d,\varepsilon) \le \mathcal P(K,d,\varepsilon). $$上界来自 Lemma 4.2.6：取 $K$ 的一个极大 $\varepsilon$-separated 子集，它既是 $\varepsilon$-net，其基数也不超过 $\mathcal P(K,d,\varepsilon)$。
为证明下界，取 $K$ 中任意 $2\varepsilon$-separated 子集 $\mathcal P=\{x_i\}$，以及任意 $\varepsilon$-net $\mathcal N=\{y_j\}$。按定义，每个 $x_i$ 都落在某个以 $y_j$ 为中心的 $\varepsilon$-球中。任意一个闭 $\varepsilon$-球不可能包含两个 $2\varepsilon$-separated 点，所以每个以 $y_j$ 为中心的球至多包含一个 $x_i$。抽屉原理给出 $|\mathcal P|\le|\mathcal N|$。由于 $\mathcal P$ 和 $\mathcal N$ 任意，下界成立。
Exercises 4.23-4.26 会帮助你练习 covering 和 packing。
4.2.1 覆盖数与体积
现在研究最重要例子中的覆盖数：$T=\mathbb R^n$，度量为 Euclidean 距离
$$ d(x,y)=\|x-y\|_2, $$
如 (4.16) 所示。为简化记号，当度量已明确时，我们常省略它，写作
$$ \mathcal N(K,\varepsilon) = \mathcal N(K,d,\varepsilon). $$
如果覆盖数度量 $K$ 的大小，那么它与最经典的大小度量，也就是 $\mathbb R^n$ 中 $K$ 的体积，有什么关系？两者不可能完全等价，因为“扁平”集合体积为零但覆盖数非零。尽管如此，有一个有用的部分等价，而且常常相当尖锐。它基于 $\mathbb R^n$ 中集合的 Minkowski 和。
设 $A$ 和 $B$ 是 $\mathbb R^n$ 的子集。Minkowski 和 $A+B$ 定义为
$$ A+B := \{a+b:\ a\in A,\ b\in B\}. $$图 4.2 展示了平面上两个集合的 Minkowski 和。
设 $K\subset\mathbb R^n$ 且 $\varepsilon>0$。那么
$$ \frac{\operatorname{Vol}(K)} {\operatorname{Vol}(\varepsilon B_2^n)} \le \mathcal N(K,\varepsilon) \le \mathcal P(K,\varepsilon) \le \frac{ \operatorname{Vol}\bigl(K+(\varepsilon/2)B_2^n\bigr) } { \operatorname{Vol}\bigl((\varepsilon/2)B_2^n\bigr) }. $$这里 $B_2^n$ 表示 $\mathbb R^n$ 中的 Euclidean 单位球，因此 $\varepsilon B_2^n$ 是半径为 $\varepsilon$ 的 Euclidean 球。
中间不等式来自 Lemma 4.2.8，所以只需证明左右两端。
下界。 令 $N:=\mathcal N(K,\varepsilon)$。那么 $K$ 可由 $N$ 个半径为 $\varepsilon$ 的球覆盖。比较体积得到
$$ \operatorname{Vol}(K) \le N\cdot\operatorname{Vol}(\varepsilon B_2^n), $$这证明了下界。
上界。 令 $N:=\mathcal P(K,\varepsilon)$。可以找到 $N$ 个两两不交的闭 $\varepsilon/2$-球，其中心 $x_i$ 属于 $K$（Remark 4.2.5）。这些球未必完全包含在 $K$ 中，但它们都包含在膨胀集合 $K+(\varepsilon/2)B_2^n$ 中。比较体积得到
$$ N\cdot \operatorname{Vol}\bigl((\varepsilon/2)B_2^n\bigr) \le \operatorname{Vol}\bigl(K+(\varepsilon/2)B_2^n\bigr), $$从而得到命题中的上界。
体积界的一个重要结论是：覆盖数以及装填数通常随维数 $n$ 指数增长。
对任意 $\varepsilon>0$，Euclidean 单位球 $B_2^n$ 的覆盖数满足
$$ \left(\frac{1}{\varepsilon}\right)^n \le \mathcal N(B_2^n,\varepsilon) \le \left(\frac{2}{\varepsilon}+1\right)^n. \tag{4.17} $$同样的上界也适用于 Euclidean 单位球面 $S^{n-1}$。
下界直接来自 Proposition 4.2.10，因为 $\mathbb R^n$ 中体积按如下方式缩放：
$$ \operatorname{Vol}(\varepsilon B_2^n) = \varepsilon^n\operatorname{Vol}(B_2^n). $$上界同样来自 Proposition 4.2.10：
$$ \mathcal N(B_2^n,\varepsilon) \le \frac{ \operatorname{Vol}\bigl((1+\varepsilon/2)B_2^n\bigr) } { \operatorname{Vol}\bigl((\varepsilon/2)B_2^n\bigr) } = \frac{(1+\varepsilon/2)^n}{(\varepsilon/2)^n} = \left(\frac{2}{\varepsilon}+1\right)^n. $$球面的上界也可用同样方式证明。
为简化 (4.17)，注意在非平凡范围 $\varepsilon\in(0,1]$ 中，有
$$ \left(\frac{1}{\varepsilon}\right)^n \le \mathcal N(B_2^n,\varepsilon) \le \left(\frac{3}{\varepsilon}\right)^n. \tag{4.18} $$
在平凡范围 $\varepsilon>1$ 中，一个 $\varepsilon$-球就可以覆盖单位球，所以 $\mathcal N(B_2^n,\varepsilon)=1$。
Corollary 4.2.11 的证明使用了 Euclidean 球的体积，但巧妙地避免了实际计算这个体积。可以在 Exercises 4.27-4.29 中尝试用三种方式计算它：几何、概率和分析方式；并在 Exercise 4.30 中把它推广到 $\ell^p$ 球。
Remark 4.2.7 描述了构造 $\varepsilon$-net 的一般迭代算法。但对 Euclidean 球而言，也可以直接使用缩放后的整数格点（Exercise 4.31），甚至使用随机点（Exercise 4.39）。
刚才的体积论证很灵活，可用于许多其他场景。下面是一个重要例子。
Hamming 立方体 $\{0,1\}^n$ 由所有长度为 $n$ 的二进制字符串构成。为了把它变成度量空间，定义 Hamming 距离 $d_H(x,y)$ 为两个字符串 $x$ 和 $y$ 不同的比特数：
$$ d_H(x,y) := \#\{i:\ x(i)\ne y(i)\}, \qquad x,y\in\{0,1\}^n. $$可以验证这确实是一个度量。
查看学习笔记：Hamming 距离为何是度量Hamming 立方体 $K=\{0,1\}^n$ 的覆盖数和装填数满足：对任意整数 $m\in[0,n]$，
$$ \frac{2^n} {\sum_{k=0}^m \binom{n}{k}} \le \mathcal N(K,d_H,m) \le \mathcal P(K,d_H,m) \le \frac{2^n} {\sum_{k=0}^{\lfloor m/2\rfloor}\binom{n}{k}}. $$证明只是对体积论证做一个小修改：把体积替换为基数。请在 Exercise 4.32 中尝试证明。为进一步练习体积论证，可在 Exercise 4.50 中计算低秩矩阵的覆盖数。
4.3 应用：纠错码
Covering 和 packing 论证经常出现在编码理论中。这里给出两个例子，把 covering/packing numbers 与复杂度和纠错联系起来。
4.3.1 Metric entropy 与复杂度
直观上，覆盖数和装填数度量集合 $K$ 的复杂度。覆盖数的对数 $\log_2\mathcal N(K,\varepsilon)$ 常称为 $K$ 的 metric entropy。下面会看到，metric entropy 等价于用给定精度编码 $K$ 中点所需的比特数。
设 $(T,d)$ 是度量空间，$K\subset T$。令 $\mathcal C(K,d,\varepsilon)$ 表示用度量 $d$ 中精度 $\varepsilon$ 指定 $K$ 中每个点所需的最少比特数。那么
$$ \log_2\mathcal N(K,d,\varepsilon) \le \mathcal C(K,d,\varepsilon) \le \left\lceil \log_2\mathcal N(K,d,\varepsilon/2) \right\rceil. $$下界。 假设 $\mathcal C(K,d,\varepsilon)\le N$。这表示存在一个把点 $x\in K$ 编码为长度为 $N$ 的比特串的映射，并且能以精度 $\varepsilon$ 指定每个点。这个编码把定义域 $K$ 分成至多 $2^N$ 个子集，每个子集由映到同一个比特串的点组成；见图 4.3。每个子集的直径至多为 $\varepsilon$，因此可用一个中心在 $K$ 中、半径为 $\varepsilon$ 的球覆盖。于是 $K$ 可由至多 $2^N$ 个半径为 $\varepsilon$ 的球覆盖，即 $\mathcal N(K,d,\varepsilon)\le2^N$。取对数得到下界。
上界。 假设 $\log_2\mathcal N(K,d,\varepsilon/2)\le N$，其中 $N$ 是整数。这表示 $K$ 有一个 $(\varepsilon/2)$-net $\mathcal N$，其点数至多为 $2^N$。对每个 $x\in K$，指定一个最近的 $x_0\in\mathcal N$。由于 $\mathcal N$ 中至多有 $2^N$ 个点，$N$ 个比特足以指定 $x_0$。
如果 $x$ 和 $y$ 被编码为同一个 $x_0$，则由三角不等式，
$$ d(x,y) \le d(x,x_0)+d(y,x_0) \le \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon. $$因此该编码以精度 $\varepsilon$ 表示 $K$ 中点，从而 $\mathcal C(K,d,\varepsilon)\le N$。
4.3.2 纠错码
假设 Alice 想给 Bob 发送一条有 $k$ 个字母的消息，例如 “fill the glass”。再假设攻击者可以篡改 Alice 的消息，最多改变 $r$ 个字母。如果 $r=2$，Bob 可能收到类似 “bill the class” 的消息。有没有办法保护 Alice 和 Bob 之间的通信信道，使它可以纠正这种对抗性错误？
一种常见方法是使用冗余。Alice 把她的 $k$ 字母消息编码成更长的 $n$ 字母消息（$n>k$），希望额外信息能帮助 Bob 在最多 $r$ 个错误出现时恢复原消息。
Alice 可以简单地把消息重复若干次发送给 Bob。例如把 “fill the glass” 重复多遍。Bob 可以使用多数解码：检查每个位置收到的多个副本，选择出现次数最多的字母。如果原始消息 $x$ 被重复 $2r+1$ 次，那么即使 $E(x)$ 中有 $r$ 个字母被篡改，多数解码也能正确恢复 $x$。
多数解码的问题是效率低。它要用
$$ n=(2r+1)k \tag{4.19} $$个字母来编码一个 $k$ 字母消息。马上会看到，存在所需 $n$ 小得多的纠错码。
先形式化纠错码的概念：它是一种把 $k$ 字母字符串编码为 $n$ 字母字符串，并可纠正 $r$ 个错误的编码。为简单起见，我们使用二进制 alphabet，也就是只有 $0$ 和 $1$ 两个字母，而不是英文字母。
一个把 $k$-bit 字符串编码为 $n$-bit 字符串、并能纠正 $r$ 个错误的纠错码，由编码映射
$$ E:\{0,1\}^k\to\{0,1\}^n $$和解码映射
$$ D:\{0,1\}^n\to\{0,1\}^k $$组成，并满足：对任意 word $x\in\{0,1\}^k$，以及任意与 $E(x)$ 至多相差 $r$ 个 bit 的字符串 $y\in\{0,1\}^n$，都有
$$ D(y)=x. $$现在把纠错与 Hamming 立方体 $\{0,1\}^n$ 的装填数联系起来；这里使用 Definition 4.2.14 中引入的 Hamming 度量。
假设正整数 $k,n,r$ 满足
$$ \log_2 \mathcal P(\{0,1\}^n,d_H,2r) \ge k. $$那么存在一个纠错码，它把 $k$-bit 字符串编码为 $n$-bit 字符串，并能纠正 $r$ 个错误。
由假设，存在子集 $\mathcal N\subset\{0,1\}^n$，满足 $|\mathcal N|=2^k$，并且以 $\mathcal N$ 中点为中心、半径为 $r$ 的闭球两两不交。令编码器 $E:\{0,1\}^k\to\mathcal N$ 是任意一一映射，并令 $D:\{0,1\}^n\to\{0,1\}^k$ 是最近邻解码器。
如果 $y\in\{0,1\}^n$ 与 $E(x)$ 至多相差 $r$ 个 bit，那么 $y$ 落在以 $E(x)$ 为中心、半径为 $r$ 的闭球中。由于这些球两两不交，$y$ 严格更接近 $E(x)$，而不是任何其他 codeword $E(x')$。因此最近邻解码会正确解码 $y$，即 $D(y)=x$。
把 Proposition 4.2.15 中 Hamming 立方体的 packing number 界代入 Lemma 4.3.4，得到下面的保证。
假设正整数 $k,n,r$ 满足
$$ n-k \ge 2r\log_2\left(\frac{en}{2r}\right). $$那么存在一个纠错码，把 $k$-bit 字符串编码为 $n$-bit 字符串，并能纠正 $r$ 个错误。
先用 Lemma 4.2.8 从 packing 转到 covering，再使用 Proposition 4.2.15 中的覆盖数界，并用 Exercise 0.6 的估计化简，得到
$$ \begin{aligned} \mathcal P(\{0,1\}^n,d_H,2r) &\ge \mathcal N(\{0,1\}^n,d_H,2r)\\ &\ge \frac{2^n}{\sum_{i=0}^{2r}\binom{n}{i}}\\ &\ge 2^n\left(\frac{2r}{en}\right)^{2r}. \end{aligned} $$由定理假设，最后这个量至少为 $2^k$。应用 Lemma 4.3.4 即完成证明。
Theorem 4.3.5 表明，为纠正 $r$ 个错误，只需要 $n-k$ 近似按 $r$ 线性增长，忽略一个对数因子。这比重复码 (4.19) 高效得多，并且是最优的；见 Exercise 4.33。
4.4 次高斯随机矩阵的上界
现在可以进入随机矩阵的非渐近理论。随机矩阵理论研究具有随机元素的 $m\times n$ 矩阵 $A$。核心问题围绕奇异值、特征值（如果 $A$ 对称）和特征向量的分布。
Theorem 4.4.3 将给出第一个关于独立次高斯元素随机矩阵的算子范数（即最大奇异值）的界。它既不是最尖锐的，也不是最一般的结果；我们会在 Sections 4.6 和 6.4 中改进和推广它。
在此之前，先看看 $\varepsilon$-net 如何帮助计算矩阵的算子范数。
4.4.1 在 $\varepsilon$-net 上计算范数
Definition 4.1.8 中引入的 $m\times n$ 矩阵 $A$ 的算子范数为
$$ \|A\| = \max_{x\in S^{n-1}}\|Ax\|_2. $$
为了估计 $\|A\|$，需要在整个球面 $S^{n-1}$ 上一致控制 $\|Ax\|_2$，这有时很困难。下面说明，其实只需控制球面的一个 $\varepsilon$-net（Euclidean 度量下）即可。
设 $A$ 是 $m\times n$ 矩阵，$\varepsilon\in[0,1)$。那么对球面 $S^{n-1}$ 的任意 $\varepsilon$-net $\mathcal N$，有
$$ \sup_{x\in\mathcal N}\|Ax\|_2 \le \|A\| \le \frac{1}{1-\varepsilon} \sup_{x\in\mathcal N}\|Ax\|_2. $$下界显然成立，因为 $\mathcal N\subset S^{n-1}$。为证明上界，固定 $x\in S^{n-1}$ 使得 $\|A\|=\|Ax\|_2$，并选择 $x_0\in\mathcal N$ 逼近 $x$，使得 $\|x-x_0\|_2\le\varepsilon$。由算子范数定义，
$$ \|Ax-Ax_0\|_2 = \|A(x-x_0)\|_2 \le \|A\|\|x-x_0\|_2 \le \varepsilon\|A\|. $$由三角不等式，
$$ \|Ax_0\|_2 \ge \|Ax\|_2-\|Ax-Ax_0\|_2 \ge (1-\varepsilon)\|A\|. $$除以 $1-\varepsilon$ 即得上界。
Lemma 4.4.1 很灵活。下面是一个有用版本。由 (4.9)，$m\times n$ 矩阵 $A$ 的算子范数也可通过最大化双线性型得到：
$$ \|A\| = \max_{x\in S^{n-1},\,y\in S^{m-1}} |\langle Ax,y\rangle|. $$
如果 $A$ 对称，还可取 $x=y$；见 (4.10)。我们可以把两个球面都替换成各自的 net。
设 $A$ 是 $m\times n$ 矩阵，$\varepsilon\in[0,1/2)$。那么对球面 $S^{n-1}$ 的任意 $\varepsilon$-net $\mathcal N$ 和球面 $S^{m-1}$ 的任意 $\varepsilon$-net $\mathcal M$，有
$$ \sup_{x\in\mathcal N,\,y\in\mathcal M} |\langle Ax,y\rangle| \le \|A\| \le \frac{1}{1-2\varepsilon} \sup_{x\in\mathcal N,\,y\in\mathcal M} |\langle Ax,y\rangle|. $$此外，如果 $m=n$、$A$ 对称且 $\mathcal N=\mathcal M$，则可取 $x=y$。
这个结论可通过微调 Lemma 4.4.1 的证明得到；见 Exercise 4.36。另一种方法见 Exercise 4.34，更多练习见 Exercise 4.37。
4.4.2 次高斯随机矩阵的范数
现在给出第一个随机矩阵结果。它说明，具有独立次高斯元素的 $m\times n$ 随机矩阵 $A$ 的算子范数满足
$$ \|A\|\lesssim \sqrt m+\sqrt n \qquad \text{with high probability}. $$
设 $A$ 是 $m\times n$ 随机矩阵，其元素 $A_{ij}$ 独立、均值为零且次高斯。那么对任意 $t>0$，有
$$ \|A\| \le CK(\sqrt m+\sqrt n+t) $$以至少 $1-2\exp(-t^2)$ 的概率成立。这里
$$ K=\max_{i,j}\|A_{ij}\|_{\psi_2}. $$ 查看学习笔记完整证明这个证明是 $\varepsilon$-net argument 的典型例子。我们需要对单位球面上所有 $x,y$ 控制 $\langle Ax,y\rangle$。为此，先用 net 离散化球面（逼近步骤），再对来自 net 的固定 $x,y$ 建立集中界（集中步骤），最后对 net 中所有点做 union bound。
Step 1：逼近。 取 $\varepsilon=1/4$。由 Corollary 4.2.11，可取球面 $S^{n-1}$ 的 $\varepsilon$-net $\mathcal N$ 和球面 $S^{m-1}$ 的 $\varepsilon$-net $\mathcal M$，满足
$$ |\mathcal N|\le 9^n, \qquad |\mathcal M|\le 9^m. \tag{4.20} $$由 Lemma 4.4.2，
$$ \|A\| \le 2 \max_{x\in\mathcal N,\ y\in\mathcal M} |\langle Ax,y\rangle|. \tag{4.21} $$Step 2：集中。 固定 $x\in\mathcal N$ 和 $y\in\mathcal M$。双线性型
$$ \langle Ax,y\rangle = \sum_{i=1}^m\sum_{j=1}^n A_{ij}x_jy_i $$是独立次高斯随机变量之和。由 Proposition 2.7.1，
$$ \begin{aligned} \|\langle Ax,y\rangle\|_{\psi_2}^2 &\le C\sum_{i=1}^m\sum_{j=1}^n \|A_{ij}x_jy_i\|_{\psi_2}^2\\ &\le CK^2 \sum_{i=1}^m\sum_{j=1}^n x_j^2y_i^2\\ &= CK^2 \left(\sum_{j=1}^n x_j^2\right) \left(\sum_{i=1}^m y_i^2\right) = CK^2. \end{aligned} $$由 Proposition 2.6.6(i)，这可写成尾界
$$ \mathbb P\{|\langle Ax,y\rangle|\ge u\} \le 2\exp(-cu^2/K^2), \qquad u\ge0. \tag{4.22} $$Step 3：Union bound。 现在通过 union bound 解除 $x,y$ 固定的限制。事件
$$ \max_{x\in\mathcal N,\,y\in\mathcal M} |\langle Ax,y\rangle| \ge u $$表示存在 $x\in\mathcal N$ 和 $y\in\mathcal M$ 使得 $|\langle Ax,y\rangle|\ge u$。因此
$$ \begin{aligned} &\mathbb P\left\{ \max_{x\in\mathcal N,\,y\in\mathcal M} |\langle Ax,y\rangle| \ge u \right\}\\ &\qquad\le \sum_{x\in\mathcal N,\,y\in\mathcal M} \mathbb P\{|\langle Ax,y\rangle|\ge u\}. \end{aligned} $$利用尾界 (4.22) 和 net 大小估计 (4.20)，上式不超过
$$ 9^{n+m}\cdot 2\exp(-cu^2/K^2). \tag{4.23} $$取
$$ u=CK(\sqrt n+\sqrt m+t). \tag{4.24} $$则 $u^2\ge C^2K^2(n+m+t^2)$。若常数 $C$ 足够大，则指数足够大，例如 $cu^2/K^2\ge3(n+m)+t^2$。于是
$$ \mathbb P\left\{ \max_{x\in\mathcal N,\,y\in\mathcal M} |\langle Ax,y\rangle| \ge u \right\} \le 2\exp(-t^2). $$最后结合 (4.21)，得到
$$ \mathbb P\{\|A\|\ge2u\} \le 2\exp(-t^2). $$再代入 (4.24)，并把常数 $2$ 吸收到 $C$ 中，证明完成。
像 Theorem 4.4.3 这样的高概率界，通常可以通过 integrated tail formula（Lemma 1.6.1）转化为更简单但信息较少的期望界。尝试 Exercise 4.41，可得到
$$ \mathbb E\|A\| \le CK(\sqrt m+\sqrt n). $$Theorem 4.4.3 通常是紧的，因为矩阵的算子范数至少不小于任意一行或一列的 Euclidean 范数（Exercise 4.7）。例如，如果 $A$ 的元素是 Rademacher 随机变量，那么它的列范数为 $\sqrt m$，行范数为 $\sqrt n$，因此
$$ \|A\| \ge \max(\sqrt m,\sqrt n) \ge \frac{1}{2}(\sqrt m+\sqrt n) $$以概率 $1$ 成立。完全一般的下界见 Exercise 4.42。
Theorem 4.4.3 中的独立性假设可以放松：只需要 $A$ 的行（或列）独立，行内元素可相依；见 Exercise 4.43。
4.4.3 对称矩阵
Theorem 4.4.3 很容易推广到对称矩阵，给出高概率界
$$ \|A\|\lesssim \sqrt n. $$
设 $A$ 是 $n\times n$ 对称随机矩阵，其对角线及其上方的元素 $A_{ij}$ 独立、均值为零且次高斯。那么对任意 $t>0$，
$$ \|A\| \le CK(\sqrt n+t) $$以至少 $1-4\exp(-t^2)$ 的概率成立。这里 $K=\max_{i,j}\|A_{ij}\|_{\psi_2}$。
把 $A$ 分成上三角部分 $A^+$ 和下三角部分 $A^-$。对角线可以放到任意一边；为具体起见，把它放入 $A^+$。于是
$$ A=A^++A^-. $$Theorem 4.4.3 可分别应用于 $A^+$ 和 $A^-$。由 union bound，以至少 $1-4\exp(-t^2)$ 的概率，这两个界同时成立：
$$ \|A^+\|\le CK(\sqrt n+t), \qquad \|A^-\|\le CK(\sqrt n+t). $$再由三角不等式 $\|A\|\le\|A^+\|+\|A^-\|$，证明完成。
关于随机矩阵范数的更多练习见 Exercise 4.44。
4.5 应用：网络中的社区检测
随机矩阵理论有许多应用。这里给出一个网络分析中的例子。
真实世界的网络常有 communities，也就是紧密连接的节点簇。准确且高效地识别它们，是 community detection problem 的主要挑战。
4.5.1 Stochastic Block Model
我们在一个简单的两社区概率网络模型中研究 community detection。它是 Section 2.5 中介绍的 Erdős-Rényi 随机图模型的直接推广。
把 $n$ 个顶点分成两个大小均为 $n/2$ 的组，也就是两个 communities。构造随机图 $G$：每对顶点独立连接；如果两个顶点在同一个 community 中，则以概率 $p$ 连接；如果它们在不同 communities 中，则以概率 $q$ 连接。自环也按这个规则包含在模型中。这个随机图模型称为 stochastic block model，记为 $G(n,p,q)$。
当 $p=q$ 时，得到一个带自环的 Erdős-Rényi 模型 $G(n,p)$。但当 $p>q$ 时，community 内部的边比 community 之间的边更可能出现，于是形成 community structure；见图 4.4。
4.5.2 期望邻接矩阵包含关键信息
图 $G$ 可方便地由邻接矩阵 $A$ 表示；邻接矩阵已在 Definition 3.6.2 中引入。对随机图 $G\sim G(n,p,q)$，邻接矩阵 $A$ 是随机矩阵，因此可以用本章前面发展的工具分析它。
把 $A$ 分成确定性部分和随机部分：
$$ A=D+R, \qquad D=\mathbb EA. $$
把 $D$ 看作 signal（有信息的部分），把 $R$ 看作 noise。
为了看出为什么 $D$ 有信息，计算它的特征结构。元素 $A_{ij}$ 服从 Bernoulli 分布：根据顶点 $i$ 和 $j$ 是否属于同一个 community，分别是 $\operatorname{Ber}(p)$ 或 $\operatorname{Ber}(q)$。因此 $D$ 的元素根据 community 关系取值为 $p$ 或 $q$。例如，如果按 community 排列顶点，当 $n=4$ 时，
$$ D=\mathbb EA = \begin{bmatrix} p&p&q&q\\ p&p&q&q\\ q&q&p&p\\ q&q&p&p \end{bmatrix}. $$
更一般地，$D$ 由四个 $n/2\times n/2$ 常数块组成。它的秩为 $2$，非零特征值和对应特征向量为
$$ \lambda_1(D) = \left(\frac{p+q}{2}\right)n, \qquad u_1(D) = (1,\ldots,1,1,\ldots,1)^{\mathsf T}, $$
以及
$$ \lambda_2(D) = \left(\frac{p-q}{2}\right)n, \qquad u_2(D) = (1,\ldots,1,-1,\ldots,-1)^{\mathsf T}. $$
关键对象是第二个特征向量 $u_2(D)$，它包含了全部 community structure 信息。如果知道 $u_2(D)$，就可以根据它各坐标的符号识别两个 communities。
4.5.3 实际邻接矩阵是良好近似
但是我们不知道期望邻接矩阵 $D=\mathbb EA$，因此无法直接访问 $u_2(D)$。我们知道的是实际邻接矩阵 $A=D+R$，它是 $D$ 的噪声版本。signal $D$ 的水平为
$$ \|D\| = \lambda_1(D) \asymp n, $$
而 noise $R$ 的水平可用 Corollary 4.4.7 估计：
$$ \|R\| \le C\sqrt n \qquad \text{with probability at least }1-4e^{-n}. \tag{4.25} $$
因此，当 $n$ 很大时，noise $R$ 远小于 signal $D$。这表示 $A$ 接近 $D$，所以可以用 $A$ 代替 $D$ 来提取 community 信息。下面用 Section 4.1.6 中的矩阵扰动理论证明这一点。
4.5.4 扰动理论
对 $D$ 和 $A$ 应用 Davis-Kahan 不等式（Theorem 4.1.15），并关注第二大特征值。需要检查 $\lambda_2(D)$ 与 $D$ 的其余谱，也就是与 $0$ 和 $\lambda_1(D)$，分离得足够开。距离为
$$ \delta = \min\left(\lambda_2(D),\lambda_1(D)-\lambda_2(D)\right) = \min\left(\frac{p-q}{2},q\right)n =: \mu n. $$
回忆 (4.25) 中对 $R=A-D$ 的界，Davis-Kahan 不等式给出 $D$ 和 $A$ 的单位特征向量之间的夹角界。这里用上横线表示单位化后的向量：
$$ \sin\angle\left(\bar u_2(D),\bar u_2(A)\right) \le \frac{2\|R\|}{\delta} \lesssim \frac{\sqrt n}{\mu n} \lesssim \frac{1}{\mu\sqrt n}. $$
如果两个单位向量之间夹角的正弦很小，那么它们在差一个符号的意义下接近；见 Exercise 4.16。因此存在 $\theta\in\{-1,1\}$，使得
$$ \|\bar u_2(D)-\theta\bar u_2(A)\|_2 \lesssim \frac{1}{\mu\sqrt n}. $$
我们已经算出 $D$ 的特征向量 $u_2(D)$，但它不是单位向量；因为坐标均为 $\pm1$，所以范数为 $\sqrt n$。两边乘以 $\sqrt n$，得到
$$ \|u_2(D)-\theta u_2(A)\|_2 \lesssim \frac{1}{\mu}. $$
这意味着 $u_2(D)$ 和 $\theta u_2(A)$ 的大多数坐标符号必须一致。事实上，把上式平方写成
$$ \sum_{j=1}^n \left| u_2(D)_j-\theta u_2(A)_j \right|^2 \lesssim \frac{1}{\mu^2}, $$
并注意 $u_2(D)$ 的所有坐标都是 $\pm1$，可知每一个符号不一致的坐标至少贡献 $1$ 到这项和。因此，符号不一致的数量为 $\lesssim1/\mu^2$。
4.5.5 Spectral Clustering
总结一下，我们可以用向量 $u_2(A)$ 准确估计 $u_2=u_2(D)$；后者坐标为 $\pm1$，并识别两个 communities。这种 community detection 方法通常称为 spectral clustering。
Input: 图 $G$。
Output: 将 $G$ 的顶点分成两个 communities。
- 计算图的邻接矩阵 $A$。
- 计算 $A$ 第二大特征值对应的特征向量 $v_2(A)$。
- 根据 $v_2(A)$ 的坐标符号，把顶点分成两个 communities；零坐标可任意分配。
我们已经证明了如下结果。
设 $G\sim G(n,p,q)$，并令 $\min(q,p-q)=\mu>0$。那么以至少 $1-4e^{-n}$ 的概率，spectral clustering algorithm 能识别 $G$ 的 communities，且误分类顶点数至多为 $C/\mu^2$。
总结来说，只要随机图足够稠密（$q\ge\text{const}$）并且 community 内外连边概率分离良好（$p-q\ge\text{const}$），spectral clustering algorithm 就能正确分类除 $O(1)$ 个顶点以外的所有顶点。条件 $q\ge\text{const}$ 并非本质；可通过 Exercise 4.45 尝试去掉它。
Theorem 4.5.2 非平凡，也就是 $C/\mu^2\le n$，所允许的最稀疏图具有期望平均度
$$ \frac{n(p+q)}{2} \asymp \sqrt n. $$借助更多工具，我们将在 Section 5.5 处理稀疏得多的图。
4.6 次高斯矩阵的双侧界
回到 Theorem 4.4.3。它给出了 $m\times n$ 次高斯随机矩阵 $A$ 的奇异值上界：
$$ s_1(A)=\|A\| \le C(\sqrt m+\sqrt n) $$
以高概率成立。现在证明对 $A$ 整个谱更尖锐的双侧界：
$$ \sqrt m-C\sqrt n \le s_i(A) \le \sqrt m+C\sqrt n. $$
换句话说，我们将证明一个高矩阵 $(1/\sqrt m)A$（当 $m\gg n$）是近似等距映射；见 Section 4.1.7。
设 $A$ 是 $m\times n$ 随机矩阵，其行 $A_i$ 独立、均值为零、次高斯且各向同性。那么对任意 $t\ge0$，有
$$ \sqrt m - CK^2(\sqrt n+t) \le s_n(A) \le s_1(A) \le \sqrt m + CK^2(\sqrt n+t) \tag{4.26} $$以至少 $1-2\exp(-t^2)$ 的概率成立。这里 $K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记完整证明我们将证明比 (4.26) 稍强的结论：
$$ \left\| \frac{1}{m}A^{\mathsf T}A-I_n \right\| \le K^2\max(\delta,\delta^2), \qquad \delta = C\left( \sqrt{\frac{n}{m}} + \frac{t}{\sqrt m} \right). \tag{4.27} $$
利用 (4.15) 可以验证 (4.27) 确实推出 (4.26)。
像 Theorem 4.4.3 一样，我们用 $\varepsilon$-net argument 证明 (4.27)，但这次使用 Bernstein 集中不等式，而不是 Hoeffding 型界。
Step 1：逼近。 由 Corollary 4.2.11，可取单位球面 $S^{n-1}$ 的一个 $1/4$-net $\mathcal N$，满足
$$ |\mathcal N|\le9^n. $$由 Lemma 4.4.2，可在 $\mathcal N$ 上估计 (4.27) 中的算子范数：
$$ \begin{aligned} \left\| \frac{1}{m}A^{\mathsf T}A-I_n \right\| &\le 2\max_{x\in\mathcal N} \left| \left\langle \left( \frac{1}{m}A^{\mathsf T}A-I_n \right)x,x \right\rangle \right|\\ &= 2\max_{x\in\mathcal N} \left| \frac{1}{m}\|Ax\|_2^2-1 \right|. \end{aligned} $$因此，为证明 (4.27)，只需证明以所需概率有
$$ \max_{x\in\mathcal N} \left| \frac{1}{m}\|Ax\|_2^2-1 \right| \le \frac{\eta}{2}, \qquad \eta:=K^2\max(\delta,\delta^2). $$Step 2：集中。 固定 $x\in\mathcal N$，把 $\|Ax\|_2^2$ 写成独立随机变量之和：
$$ \|Ax\|_2^2 = \sum_{i=1}^m \langle A_i,x\rangle^2 =: \sum_{i=1}^m X_i^2. \tag{4.28} $$由假设，行 $A_i$ 是独立、各向同性、次高斯的随机向量，且 $\|A_i\|_{\psi_2}\le K$。因此 $X_i=\langle A_i,x\rangle$ 是独立次高斯随机变量，满足 $\mathbb E X_i^2=1$ 且 $\|X_i\|_{\psi_2}\le K$。于是 $X_i^2-1$ 是独立、均值为零的次指数随机变量，并且
$$ \|X_i^2-1\|_{\psi_1} \le CK^2. $$使用 Bernstein 不等式（Corollary 2.9.2），得到
$$ \begin{aligned} &\mathbb P\left\{ \left| \frac{1}{m}\|Ax\|_2^2-1 \right| \ge \frac{\eta}{2} \right\}\\ &\qquad= \mathbb P\left\{ \left| \frac{1}{m}\sum_{i=1}^m X_i^2-1 \right| \ge \frac{\eta}{2} \right\}\\ &\qquad\le 2\exp\left[ -c_1\min\left( \frac{\eta^2}{K^4}, \frac{\eta}{K^2} \right)m \right]\\ &\qquad= 2\exp(-c_1\delta^2m)\\ &\qquad\le 2\exp\left[-c_1C^2(n+t^2)\right]. \end{aligned} $$倒数第二步使用了 $\eta/K^2=\max(\delta,\delta^2)$，因而括号中的最小值等于 $\delta^2$。最后一步来自 $\delta$ 的定义和 $(a+b)^2\ge a^2+b^2$。
Step 3：Union bound。 现在对 $x\in\mathcal N$ 做 union bound。由 $|\mathcal N|\le9^n$，
$$ \begin{aligned} &\mathbb P\left\{ \max_{x\in\mathcal N} \left| \frac{1}{m}\|Ax\|_2^2-1 \right| \ge \frac{\eta}{2} \right\}\\ &\qquad\le 9^n\cdot 2\exp\left[-c_1C^2(n+t^2)\right] \le 2\exp(-t^2), \end{aligned} $$只要 (4.27) 中的绝对常数 $C$ 足够大。由 Step 1，这完成了 (4.27) 以及定理的证明。
如 Remark 4.4.4 所述，高概率界可转化为期望界。做 Exercise 4.41 可得到 Theorem 4.6.1 的如下期望形式：
$$ \mathbb E \left\| \frac{1}{m}A^{\mathsf T}A-I_n \right\| \le CK^2 \left( \sqrt{\frac{n}{m}} + \frac{n}{m} \right). $$Exercise 4.46 会给出 Theorem 4.6.1 的另一种证明。
4.7 应用：协方差估计与聚类
假设我们想分析一些高维数据，给定为从 $\mathbb R^n$ 中某个未知分布抽样得到的点 $X_1,\ldots,X_m$。探索这类数据的基本工具是主成分分析（PCA），我们在 Section 3.2.2 中已经接触过它。
PCA 把数据协方差矩阵的 top eigenvectors 作为 principal components。虽然我们不知道底层分布的协方差矩阵，也就是 population covariance matrix，但可以用样本 $X_1,\ldots,X_m$ 近似估计它。随后 Davis-Kahan theorem 4.1.15 可帮助估计底层分布的 principal components。
如何从数据估计协方差矩阵？令 $X$ 表示来自未知分布的随机向量。为简单起见，假设 $X$ 均值为零，并把协方差矩阵记为
$$ \Sigma=\mathbb E XX^{\mathsf T}. $$
为估计 $\Sigma$，使用由样本 $X_1,\ldots,X_m$ 计算得到的样本协方差矩阵
$$ \Sigma_m = \frac{1}{m} \sum_{i=1}^m X_iX_i^{\mathsf T}. $$
这里做的只是把总体平均替换为样本平均。由于 $X_i$ 与 $X$ 同分布，该估计是无偏的：
$$ \mathbb E\Sigma_m=\Sigma. $$
对 $\Sigma$ 的每个元素应用大数定律（Theorem 1.7.1），可得当样本量 $m\to\infty$ 时，
$$ \Sigma_m\to\Sigma \qquad \text{almost surely}. $$
这引出一个定量问题：样本量 $m$ 需要多大，才能保证
$$ \Sigma_m\approx\Sigma \qquad \text{with high probability?} $$
从维数角度看，至少需要 $m\gtrsim n$ 个样本点。下面说明 $m\asymp n$ 就足够。
设 $X$ 是 $\mathbb R^n$ 中的次高斯随机向量。更具体地，假设存在 $K\ge1$，使得对任意 $x\in\mathbb R^n$，
$$ \|\langle X,x\rangle\|_{\psi_2} \le K\|\langle X,x\rangle\|_{L^2}. \tag{4.29} $$那么对每个正整数 $m$，
$$ \mathbb E\|\Sigma_m-\Sigma\| \le CK^2 \left( \sqrt{\frac{n}{m}} + \frac{n}{m} \right) \|\Sigma\|. $$ 查看学习笔记完整证明先把随机向量 $X,X_1,\ldots,X_m$ 放到 isotropic position。为简单起见，假设 $\Sigma$ 可逆；这个条件可像 Exercise 3.10 那样去掉。令
$$ Z=\Sigma^{-1/2}X, \qquad Z_i=\Sigma^{-1/2}X_i. $$则 $Z,Z_1,\ldots,Z_m$ 是独立且各向同性的随机向量，并满足
$$ X=\Sigma^{1/2}Z, \qquad X_i=\Sigma^{1/2}Z_i. $$假设 (4.29) 推出
$$ \|Z\|_{\psi_2}\le K, \qquad \|Z_i\|_{\psi_2}\le K. $$于是
$$ \|\Sigma_m-\Sigma\| = \|\Sigma^{1/2}R_m\Sigma^{1/2}\| \le \|R_m\|\|\Sigma\|, \tag{4.30} $$其中
$$ R_m := \frac{1}{m} \sum_{i=1}^m Z_iZ_i^{\mathsf T} - I_n. $$考虑以 $Z_i^{\mathsf T}$ 为行的 $m\times n$ 随机矩阵 $A$。那么
$$ \frac{1}{m}A^{\mathsf T}A-I_n = \frac{1}{m} \sum_{i=1}^m Z_iZ_i^{\mathsf T} - I_n = R_m. $$应用 Theorem 4.6.1 的期望形式（Remark 4.6.2），得到
$$ \mathbb E\|R_m\| \le CK^2 \left( \sqrt{\frac{n}{m}} + \frac{n}{m} \right). $$代入 (4.30) 即得结论。
Theorem 4.7.1 表明，对任意 $\varepsilon\in(0,1)$，只要样本量满足
$$ m\asymp \varepsilon^{-2}n, $$就可以用小的相对误差估计协方差矩阵：
$$ \mathbb E\|\Sigma_m-\Sigma\| \le \varepsilon\|\Sigma\|. $$因此，如果样本量 $m$ 与维数 $n$ 成正比，样本协方差矩阵就能很好估计总体协方差矩阵。
上述论证也给出高概率界：对任意 $u\ge0$，以至少 $1-2e^{-u}$ 的概率有
$$ \|\Sigma_m-\Sigma\| \le CK^2 \left( \sqrt{\frac{n+u}{m}} + \frac{n+u}{m} \right) \|\Sigma\|. $$请在 Exercise 4.49 中验证这一点。
我们将在 Sections 5.6 和 9.2.3 中重新讨论协方差估计，处理 heavy-tailed 和近似低维分布。目前可尝试 Exercise 4.48，以小相对误差捕捉所有一维边缘。
4.7.1 应用：点集聚类
下面用一个聚类应用说明 Theorem 4.7.1。它遵循与 Section 4.5 类似的思想，但这次是在 $\mathbb R^n$ 的点集中寻找 clusters，而不是在网络中寻找 communities。虽然 cluster 的概念没有严格定义，常识上同一 cluster 中的点应比不同 cluster 中的点更接近。
和网络一样，先建立一个简单的 $\mathbb R^n$ 中双簇点集概率模型。
按如下方式在 $\mathbb R^n$ 中生成 $m$ 个随机点：抛一枚公平硬币；若为正面，则从 $N(\mu,I_n)$ 抽取一个点；若为反面，则从 $N(-\mu,I_n)$ 抽取一个点。这个分布称为均值为 $\pm\mu$ 的 Gaussian mixture model。
等价地，考虑随机向量
$$ X=\theta\mu+g, $$
其中 $\theta$ 是 Rademacher 随机变量，$g\sim N(0,I_n)$，并且 $\theta$ 与 $g$ 独立。抽取与 $X$ 同分布的独立样本 $X_1,\ldots,X_m$，该样本即服从 Gaussian mixture model；见图 4.5。
给定来自 Gaussian mixture model 的 $m$ 个样本点，目标是判断哪些点属于哪个 cluster。为此，可以使用 Section 4.5 中网络 spectral clustering algorithm 的一个变体。
为什么谱方法可能有效？注意 $X$ 的分布并非各向同性，而是在 $\mu$ 方向上被拉伸，也就是图 4.5 中的水平方向。因此，可以通过计算数据的第一主成分，即样本协方差矩阵最大特征值对应的特征向量，近似找到 $\mu$。然后把数据点投影到这个主成分上，并根据它们位于原点哪一侧进行分类。算法如下。
Input: 点 $X_1,\ldots,X_m\in\mathbb R^n$。
Output: 将点划分为两个 clusters。
- 计算样本协方差矩阵 $\Sigma_m=\frac{1}{m}\sum_{i=1}^m X_iX_i^{\mathsf T}$。
- 计算 top eigenvector $v=v_1(\Sigma_m)$。
- 根据 $\langle X_i,v\rangle$ 的符号，把点 $X_i$ 分到两个 clusters。
从均值为 $\mu$ 和 $-\mu$ 的 Gaussian mixture model 中抽取点 $X_1,\ldots,X_m\in\mathbb R^n$。若 $m\ge Cn$ 且 $\|\mu\|_2\ge C$，则以至少 $0.99$ 的概率，spectral clustering algorithm 能识别 communities，且误分类点数至多为 $1\%$。
现在轮到你了：请在 Exercise 4.51 中证明 Theorem 4.7.5。
值得注意的是，即使 cluster separation $\|\mu\|_2$ 远小于 cluster 直径 $\asymp\sqrt n$，仍然可以实现准确分类。
4.8 Notes
Min-max theorem（Theorem 4.1.6）也称为 Courant-Fischer-Weyl min-max principle。
Davis-Kahan theorem（Theorem 4.1.15 和 Lemma 4.1.16 的一种形式）最初由 [95] 证明，现在已成为数值分析和统计学中不可或缺的工具。这个定理有大量扩展、变体和不同证明，尤其可参见 [346, 352]、[41, Section VII.3]、[306, Chapter V]。对随机扰动而言，Davis-Kahan 还可以改进，见 [343, 120, 262, 263, 345]。
Section 4.2 引入了 covering numbers、packing numbers 和 metric entropy。进一步内容可见 [21, Chapter 4] 和 [272]；带有应用视角的阐述可见 [280]。
Section 4.3.2 涵盖了纠错码的一些基本结果。书籍 [334] 提供了更系统的介绍。Theorem 4.3.5 是纠错码 rate 的经典 Gilbert-Varshamov bound 的简化版本；其反向结果（Exercise 4.33）是 Hamming bound 的简化版本。
在 Section 4.5 中，我们给出了随机矩阵理论在网络中的一个应用。关于 network analysis 这一跨学科领域的系统介绍，可参见书籍 [257]。Stochastic block models（Definition 4.5.1）由 [163] 引入。Stochastic block models 中的 community detection problem 吸引了大量研究；可参见书籍 [257]、综述 [1, 126]，以及包括 [229, 353, 254, 153, 2, 48, 86, 206, 151, 175, 120] 在内的许多论文。
在 Section 4.7 中，我们讨论了 covariance estimation problem；更一般的结果会在 Sections 5.6 和 9.2.3 中出现。这个主题在高维统计中已有大量研究，参见例如 [340, 284, 190, 69, 211, 82, 320, 238, 4, 261]。
在 Section 4.7.1 中，我们给出了 Gaussian mixture models 聚类的一个应用。这个问题在统计学和计算机科学中都有研究，参见 [250, Chapter 6] 和 [181, 251, 33, 165, 19, 146, 212]。
Power method（Exercise 4.6）也称为 von Mises iteration，可用于寻找 top eigenvector。Schur bound，也称 Schur test（Exercise 4.8），最初由 I. Schur [298, p. 6] 证明。
Walsh matrices（Exercise 4.9）是 Hadamard matrices 的一个特殊情形，也就是具有 $\pm1$ 元素的正交矩阵。该练习为所有 $2^k$ 阶构造 Hadamard 矩阵，而人们猜想对所有 $4k$ 阶都存在 Hadamard 矩阵。
连接正交投影之差的范数与乘积的范数的等式（Exercise 4.12），有时称为 Krein-Krasnoselskii-Milman formula，归功于 [194]。Wedin [347] 的工作显式证明了这个公式。[264] 给出了一个几何证明，[239, p. 454] 给出了一个线性代数证明；Exercise 4.12 的提示指向后者。
Wedin theorem（Exercise 4.15 的一种形式）由 [346] 建立。
Hermitian dilation（Exercise 4.14）是一个简单但强大的技巧，有许多应用 [306, Chapter I, Section 4]。
Cut norm（Exercise 4.21）在理论计算机科学 [16]、组合学 [173]、数值逼近 [130] 等领域中很重要。Cut norm 与 $\infty\to1$ 范数的等价性（Exercise 4.21），以及计算 cut norm 的 SDP 松弛（Exercise 4.22），来自 N. Alon 和 A. Naor 的开创性论文 [16]。
$\varepsilon$-net expansion 的思想（Exercises 4.34、4.35）可追溯到 [246]。
Exercise 4.48 讨论 direction-aware covariance estimation；关于这个问题的更深结果，见 [3]。
Exercise 4.50 中低秩矩阵覆盖数的界归功于 E. Candes 和 Y. Plan [71]。
Exercises
设 $A$ 是 $n\times n$ 矩阵，奇异值分解为
$$ A=\sum_{i=1}^n s_i u_i v_i^{\mathsf T}. $$证明 $A$ 可逆当且仅当所有奇异值 $s_i$ 都非零。在这种情况下，验证
$$ A^{-1} = \sum_{i=1}^n s_i^{-1}v_i u_i^{\mathsf T}. $$ 查看学习笔记证明路线(a) 证明 Definition 4.1.8 中引入的算子范数 $\|A\|$ 确实是 $m\times n$ 矩阵空间上的范数。
(b) 对任意矩阵，证明
$$ \|A^{\mathsf T}\|=\|A\|. $$(c) 对任意维度匹配的矩阵，证明
$$ \|AB\|\le \|A\|\cdot\|B\|. $$找一个例子，使左侧为零但右侧不为零。
(d) 证明任意子矩阵的算子范数都不超过原矩阵的算子范数。
查看学习笔记证明路线算子范数通常很难用矩阵元素表示，但下面是两个例外。
(a) Rank-one：对任意 $u\in\mathbb R^m$ 和 $v\in\mathbb R^n$，验证
$$ \|uv^{\mathsf T}\| = \|uv^{\mathsf T}\|_F = \|u\|_2\|v\|_2. $$(b) Diagonal：对任意对角矩阵 $A$，其对角元素为 $a_1,\ldots,a_n$，验证
$$ \|A\|=\max_i|a_i|. $$ 查看学习笔记证明路线设 $A$ 是 $m\times n$ 矩阵。
(a) 如果 $A$ 的秩为 $r$，证明
$$ \|A\|\le \|A\|_F\le \sqrt r\,\|A\|. $$说明对任意 $m,n$ 和 $1\le r\le\min(m,n)$，两个界都可以达到。
(b) 如果 $Z$ 是 $\mathbb R^n$ 中的各向同性随机向量，证明
$$ \mathbb E\|AZ\|_2^2=\|A\|_F^2. $$(c) 如果 $B$ 是 $k\times m$ 矩阵，证明
$$ \|BA\|_F\le \|B\|\|A\|_F. $$(d) 如果 $A$ 是对角矩阵，把 (c) 改进为
$$ \|BA\|_F \le \|B\|_{1\to2}\|A\|_F, $$其中 $\|B\|_{1\to2}$ 表示 $B$ 的列的最大 Euclidean 范数。我们将在 Exercises 4.18、4.19 中进一步讨论 $1\to2$ 范数和一般 $p\to q$ 范数。
查看学习笔记证明路线证明任意矩阵 $A$ 的奇异值 $s_i(A)$ 满足
$$ s_k(A) \le \frac{\|A\|_F}{\sqrt k}, \qquad k=1,2,\ldots. $$ 查看学习笔记证明路线下面是一种计算友好的方法：不显式计算谱，也能近似矩阵的算子范数。设 $A$ 是 $m\times n$ 矩阵，$x\sim N(0,I_n)$。证明以概率 $1$，
$$ \sqrt[2k]{\|(A^{\mathsf T}A)^k x\|_2} \to \|A\| \qquad \text{as }k\to\infty. $$ 查看学习笔记证明路线矩阵的算子范数很难用元素表示，但本题和下一题会证明一些有用界。设 $A$ 是 $m\times n$ 矩阵，列为 $A_1,\ldots,A_n$。
(a) 证明
$$ \|A\| \ge \max_i\|A_i\|_2, $$当 $A_i$ 两两正交时取等号。
(b) 证明如果对某个 $i$ 有 $\|A\|=\|A_i\|_2$，则 $A_i$ 与所有其他列正交。
(c) 说明对行也有同样结论。
查看学习笔记证明路线设 $A$ 是 $m\times n$ 矩阵，行为 $A_{i:}$，列为 $A_{:j}$。证明
$$ \|A\| \le \sqrt{ \max_i\|A_{i:}\|_1 \cdot \max_j\|A_{:j}\|_1 }. $$ 查看学习笔记证明路线构造“最分散”的正交矩阵，也就是所有元素绝对值都相同的正交矩阵。从 $2\times2$ 矩阵
$$ W_1= \begin{bmatrix} 1&1\\ 1&-1 \end{bmatrix} $$开始，迭代定义分块矩阵
$$ W_{k+1} = \begin{bmatrix} W_k&W_k\\ W_k&-W_k \end{bmatrix}, \qquad k=1,2,\ldots. $$因此 $W_2$ 是 $4\times4$ 矩阵，$W_3$ 是 $8\times8$ 矩阵，依此类推。这些具有 $\pm1$ 元素的矩阵称为 Walsh 矩阵。证明对每个 $k$，$\frac{1}{\sqrt n}W_k$ 是正交矩阵，其中 $n$ 是 $W_k$ 的阶数。
查看学习笔记证明路线证明任意 $n\times n$、元素为 $\pm1$ 的矩阵 $A$ 都满足
$$ \sqrt n\le\|A\|\le n, $$并说明两个界都可在无穷多个 $n$ 上达到。
查看学习笔记证明路线证明 $\mathbb R^n$ 中任意两个正交投影 $P$ 和 $Q$ 都满足 $\|P-Q\|\le1$。如果想挑战一下，可以做下一题得到更精细的界。
查看学习笔记证明路线对 $\mathbb R^n$ 中任意两个正交投影 $P$ 和 $Q$，证明如下结论。
(a)
$$ \|P-Q\| = \max\bigl(\|P_{\perp}Q\|,\|PQ_{\perp}\|\bigr), $$其中 $P_{\perp}=I_n-P$ 且 $Q_{\perp}=I_n-Q$。
(b) 如果 $P$ 和 $Q$ 的秩不同，则 $\|P-Q\|=1$。
(c) 如果 $P$ 和 $Q$ 的秩相同，则
$$ \|P-Q\| = \|P_{\perp}Q\| = \|PQ_{\perp}\|. $$ 查看学习笔记证明路线证明 Davis-Kahan theorem（Theorem 4.1.15）关于 top $k$ eigenvectors 投影的一个版本。考虑两个对称矩阵 $A$ 和 $B$，谱分解为
$$ A=\sum_i\lambda_i u_i u_i^{\mathsf T}, \qquad B=\sum_i\mu_i v_i v_i^{\mathsf T}, $$其中特征值按非增顺序排列。证明谱投影
$$ P_A=\sum_{i=1}^k u_i u_i^{\mathsf T}, \qquad P_B=\sum_{i=1}^k v_i v_i^{\mathsf T} $$满足
$$ \|P_A-P_B\| \le \frac{2\|A-B\|}{\lambda_k-\lambda_{k+1}}. $$ 查看学习笔记证明路线把任意 $m\times n$ 矩阵 $A$ 变成对称矩阵的两种常见方式是：(1) 使用 $A^{\mathsf T}A$ 或 $AA^{\mathsf T}$；(2) 取它的 Hermitian dilation，即 $(m+n)\times(m+n)$ 分块矩阵
$$ H= \begin{bmatrix} 0&A\\ A^{\mathsf T}&0 \end{bmatrix}. $$Hermitian dilation 有几个优点：它是线性变换，并且保持稀疏性。设
$$ A=\sum_i s_i u_i v_i^{\mathsf T} $$是奇异值分解。证明 $H$ 的非零特征值只有 $\pm s_i$，对应特征向量为
$$ \begin{bmatrix} u_i\\ \pm v_i \end{bmatrix}. $$ 查看学习笔记证明路线Davis-Kahan inequality（Theorem 4.1.15）适用于对称矩阵。下面证明一般矩形矩阵的版本。设 $A$ 和 $B$ 是 $m\times n$ 矩阵，奇异值分解为
$$ A=\sum_i s_i u_i v_i^{\mathsf T}, \qquad B=\sum_i t_i w_i z_i^{\mathsf T}, $$其中奇异值按非增顺序排列。证明 top $k$ 左奇异向量上的投影
$$ P_A=\sum_{i=1}^k u_i u_i^{\mathsf T}, \qquad P_B=\sum_{i=1}^k w_i w_i^{\mathsf T} $$满足
$$ \|P_A-P_B\| \le \frac{2\|A-B\|}{s_k-s_{k+1}}. $$给出 top $k$ 右奇异向量投影的类似界。并证明第 $k$ 个奇异向量的 Davis-Kahan 型版本。
查看学习笔记证明路线简化 Davis-Kahan inequality（Theorem 4.1.15）的结论。设两个单位向量 $u,v\in\mathbb R^n$ 的夹角（取 $0$ 到 $\pi/2$ 之间的数）很小，即
$$ \sin\angle(u,v)\le\varepsilon \qquad \text{for some }\varepsilon>0. $$证明 $u$ 与 $v$ 在差一个符号意义下接近：
$$ \|u-\theta v\|_2 \le \sqrt2\,\varepsilon \qquad \text{for some }\theta\in\{-1,1\}. $$ 查看学习笔记证明路线为 Lemma 4.1.17 增加一个等价性质。设 $A$ 是 $m\times n$ 矩阵，$m\ge n$，$\varepsilon\ge0$。
(a) 证明 $A$ 是 isometry，当且仅当 $AA^{\mathsf T}$ 是 $\mathbb R^m$ 中到某个 $n$ 维子空间上的正交投影。
(b) 更一般地，证明 $A$ 是 $\varepsilon$-approximate isometry（即 Lemma 4.1.17 中三个等价性质成立），当且仅当存在 $\mathbb R^m$ 中秩为 $n$ 的正交投影 $P$，使得
$$ \|AA^{\mathsf T}-P\|\le\varepsilon. $$ 查看学习笔记证明路线(4.9) 中定义的 $m\times n$ 矩阵 $A$ 的算子范数，度量 $A$ 对向量的拉伸。这里使用的是 $\ell^2$ 范数；也可以使用任意两个范数，例如 $p,q\in[1,\infty]$ 的 $\ell^p$ 和 $\ell^q$。定义 $A$ 的 $\ell^p\to\ell^q$ operator norm，简称 $p\to q$ 范数，为
$$ \|A\|_{p\to q} = \max_{x\ne0} \frac{\|Ax\|_q}{\|x\|_p} = \max_{\|x\|_p=\|y\|_{q'}=1} |y^{\mathsf T}Ax|, \tag{4.31} $$其中 $q'$ 是 (1.5) 中定义的 $q$ 的共轭指数。
(a) 把 (4.9) 中的等式推广到 $p\to q$ 范数，并说明理由。
(b) 验证这确实定义了 $m\times n$ 矩阵空间上的一个范数。
(c) Duality：证明
$$ \|A^{\mathsf T}\|_{p\to q} = \|A\|_{q'\to p'}, $$其中 $p'$ 和 $q'$ 是 $p$ 和 $q$ 的共轭指数。
查看学习笔记证明路线设 $A$ 是 $m\times n$ 矩阵。对大多数 $p,q$，很难用元素表达 $\|A\|_{p\to q}$，但下面是一些例外。
(a) 证明 $1\to\infty$ 范数等于元素绝对值最大值：
$$ \|A\|_{1\to\infty} = \max_{i,j}|A_{ij}|. $$(b) 证明 $1\to2$ 范数等于列的最大 Euclidean 范数，而 $2\to\infty$ 范数等于行的最大 Euclidean 范数：
$$ \|A\|_{1\to2} = \max_{j\le n}\|A_{:j}\|_2, \qquad \|A\|_{2\to\infty} = \max_{i\le m}\|A_{i:}\|_2. $$ 查看学习笔记证明路线这个范数我们已经见过：它隐含在 Grothendieck 不等式（Theorem 3.5.1）的假设中。设 $A$ 是 $m\times n$ 矩阵。
(a) 证明
$$ \|A\|_{\infty\to1} = \max_{\substack{x\in\{-1,1\}^n\\ y\in\{-1,1\}^m}} |y^{\mathsf T}Ax|. \tag{4.32} $$(b) Duality：证明
$$ \|A\|_{\infty\to1} = \sup_{\|Z\|_{\infty}\le1,\ \operatorname{rank}(Z)=1} |\langle A,Z\rangle|, $$其中上确界取遍所有秩一 $m\times n$ 矩阵 $Z$，其所有元素绝对值不超过 $1$；矩阵内积定义在 (4.7) 中。
(c) 说明 (4.32) 的恒等式不能推广到二次型：找出 $n\times n$ 对称矩阵 $A$，使得
$$ \max_{x\in[-1,1]^n} |x^{\mathsf T}Ax| \ne \max_{x\in\{-1,1\}^n} |x^{\mathsf T}Ax|. $$ 查看学习笔记证明路线这个范数在理论计算机科学和图论中很重要。为了求 $m\times n$ 矩阵 $A$ 的 cut norm，我们对 $A$ 的每个子矩阵求元素和，取绝对值，再对所有子矩阵最大化。形式化地，定义
$$ \|A\|_{\mathrm{cut}} = \max_{I,J} \left| \sum_{i\in I,\ j\in J} A_{ij} \right|, $$其中最大值取遍所有 $I\subset\{1,\ldots,m\}$ 和 $J\subset\{1,\ldots,n\}$。证明 cut norm 与 $\infty\to1$ 范数在常数因子内等价：
$$ \|A\|_{\mathrm{cut}} \le \|A\|_{\infty\to1} \le 4\|A\|_{\mathrm{cut}}. $$ 查看学习笔记证明路线设 $A$ 是 $m\times n$ 矩阵。说明 $\|A\|_{\infty\to1}$、cut norm、$\|A\|_{\infty\to2}$ 和 $\|A\|_{2\to1}$ 都可以通过求解一个半定规划，在绝对常数因子内近似。
查看学习笔记证明路线若 $\mathcal N$ 是 $\mathcal M$ 的 $\varepsilon$-net，而 $\mathcal M$ 是 $K$ 的 $\delta$-net，证明 $\mathcal N$ 是 $K$ 的 $(\varepsilon+\delta)$-net。
查看学习笔记证明路线Remark 4.2.5 中我们指出：若 $\mathcal N$ 是 metric space $(T,d)$ 中的 $\varepsilon$-separated 子集，则以 $\mathcal N$ 中点为中心的闭 $\varepsilon/2$-balls 两两不交。
(a) 说明其逆命题在一般 metric space $(T,d)$ 中是假的。
(b) 证明其逆命题在任意 normed space $(T,d)$ 中是真的。
查看学习笔记证明路线在定义 $K$ 的 covering number 时，我们要求球心 $x_i$ 位于 $K$ 中。若放宽这一点，external covering number $\overline{\mathcal N}(K,d,\varepsilon)$ 允许球心位于 $K$ 外。证明通常 covering number 与 external covering number 本质等价：
$$ \overline{\mathcal N}(K,d,\varepsilon) \le \mathcal N(K,d,\varepsilon) \le \overline{\mathcal N}(K,d,\varepsilon/2). $$ 查看学习笔记证明路线Covering number 关于 $\varepsilon$ 是单调的（为什么？），但它不一定关于集合 $K$ 单调。
(a) 举例说明一般情形下并不总有
$$ L\subset K \quad\Longrightarrow\quad \mathcal N(L,d,\varepsilon) \le \mathcal N(K,d,\varepsilon). $$(b) 证明一个近似单调性版本：
$$ L\subset K \quad\Longrightarrow\quad \mathcal N(L,d,\varepsilon) \le \mathcal N(K,d,\varepsilon/2). $$ 查看学习笔记证明路线在本题和接下来的两题中，我们用三种方式计算 $\mathbb R^n$ 中单位 Euclidean ball 的体积：几何方式、概率方式和解析方式。先从几何方式开始。
(a) Canonical simplex $\Delta_n$ 如 Figure 4.6 阴影部分所示，由 $\mathbb R^n$ 中所有非负坐标且坐标和至多为 $1$ 的点组成。证明
$$ \operatorname{Vol}(\Delta_n)=\frac1{n!}. $$(b) 回忆 $\mathbb R^n$ 中单位 $\ell^1$ ball 为
$$ B_1^n:=\{x\in\mathbb R^n:\|x\|_1\le1\}. $$像 Figure 4.6 那样把它分割为 simplices，证明
$$ \operatorname{Vol}(B_1^n) = \frac{2^n}{n!} \le \left(\frac{2e}{n}\right)^n. $$(c) 像 Figure 4.6 那样，把单位 Euclidean ball $B_2^n$ 夹在适当缩放的 cube 与 $\ell^1$ ball 之间，从而推出
$$ \left(\frac2{\sqrt n}\right)^n \le \operatorname{Vol}(B_2^n) \le \left(\frac{2e}{\sqrt n}\right)^n. \tag{4.33} $$因此，高维单位球的体积是指数级小的。虽然这些界仍有松弛，但对多数用途已经足够。
查看学习笔记证明路线现在改进 (4.33) 中的上界。利用 small ball probability（Exercise 3.7）推出
$$ \operatorname{Vol}(B_2^n) \le \left(\sqrt{\frac{2\pi e}{n}}\right)^n. $$这个界是渐近尖锐的；下一题会看到这一点。
查看学习笔记证明路线最后精确计算 Euclidean ball 的体积。
(a) 设 $\|\cdot\|$ 是 $\mathbb R^n$ 上的一个范数。考虑该 normed space 的单位球
$$ B:=\{x\in\mathbb R^n:\|x\|\le1\}. $$令 $f:\mathbb R_+\to\mathbb R_+$ 为递减、可微函数，并满足 $\lim_{x\to\infty}f(x)=0$。验证恒等式
$$ \int_{\mathbb R^n} f(\|x\|)\,dx = -\operatorname{Vol}(B) \int_0^\infty t^n f'(t)\,dt. $$(b) 代入 $f(t)=e^{-t^2/2}$，推出
$$ \operatorname{Vol}(B_2^n) = \frac{\pi^{n/2}}{\Gamma(n/2+1)}. $$(c) 记 $R_n$ 为体积等于 $1$ 的 Euclidean ball 的半径。证明
$$ R_n = \sqrt{\frac{n}{2\pi e}}\,(1+o(1)) \quad\text{as } n\to\infty. $$$R_n$ 很大这一事实说明单位球 $B_2^n$ 的体积很小。
查看学习笔记证明路线令 $p\in[1,\infty]$。
(a) 重复 Exercise 4.27 中的几何论证，推出下面的界：
$$ \left(\frac2{n^{1/p}}\right)^n \le \operatorname{Vol}(B_p^n) \le \left(\frac{2e}{n^{1/p}}\right)^n. $$(b) 使用 Exercise 4.29 中的解析论证，精确计算体积：
$$ \operatorname{Vol}(B_p^n) = \frac{\bigl(2\Gamma(1/p+1)\bigr)^n} {\Gamma(n/p+1)}. $$ 查看学习笔记证明路线$\varepsilon$-net 的构造（Remark 4.2.7）并不高效，因为 nets 往往指数级大且难以存储。换一种方式：令 $\mathcal N$ 为缩放整数 lattice
$$ \frac{\varepsilon}{\sqrt n}\mathbb Z^n $$中落在单位球 $B_2^n$ 内的所有点。验证 $\mathcal N$ 在 Euclidean metric 下构成 $B_2^n$ 的 $\varepsilon$-net，并且
$$ |\mathcal N| \le e^n\left(\frac2\varepsilon+1\right)^n. $$这个界几乎匹配 Corollary 4.2.11 中的界。另请说明如何快速把单位球中的任意给定向量近似为 $\mathcal N$ 中的向量。
查看学习笔记证明路线通过调整 volumetric method，证明 Proposition 4.2.15。
查看学习笔记证明路线证明 Theorem 4.3.5 的一个逆向结果。对任意把 $k$-bit 字符串编码为 $n$-bit 字符串且能纠正 $r$ 个错误的 error correcting code，证明
$$ n-k \ge r\log_2\left(\frac nr\right). $$ 查看学习笔记证明路线$\varepsilon$-nets 可以帮助近似向量。下面说明如何用它们给出精确表示。
(a) 令 $\mathcal N$ 是 $\mathbb R^n$ 的单位球面 $S^{n-1}$ 的一个 $\varepsilon$-net。证明任意向量 $x\in S^{n-1}$ 都可以写成收敛级数
$$ x=\sum_{k=0}^\infty \lambda_k x_k \quad\text{for some coefficients }0\le\lambda_k\le\varepsilon^k, $$其中 $x_k\in\mathcal N$。
(b) 使用 $\varepsilon$-net expansion 给出 Lemma 4.4.1 的另一个证明。
查看学习笔记证明路线令 $x\in\mathbb R^n$，并令 $\mathcal N$ 是球面 $S^{n-1}$ 的一个 $\varepsilon$-net。证明
$$ \sup_{y\in\mathcal N}\langle x,y\rangle \le \|x\|_2 \le \frac1{1-\varepsilon} \sup_{y\in\mathcal N}\langle x,y\rangle. $$ 查看学习笔记证明路线通过修改 Lemma 4.4.1 的证明，证明 Lemma 4.4.2。
查看学习笔记证明路线令 $A$ 是 $m\times n$ 矩阵，$\mu\in\mathbb R$ 且 $\varepsilon\in[0,1/2)$。证明对球面 $S^{n-1}$ 的任意 $\varepsilon$-net $\mathcal N$，都有
$$ \sup_{x\in S^{n-1}} \bigl|\|Ax\|_2-\mu\bigr| \le \frac{C}{1-2\varepsilon} \sup_{x\in\mathcal N} \bigl|\|Ax\|_2-\mu\bigr|. $$ 查看学习笔记证明路线证明球面的 $\varepsilon$-net 会“吸收”一个略小的球，见 Figure 4.7。令 $\mathcal N$ 是单位球面 $S^{n-1}$ 的一个 $\varepsilon$-net，其中 $\varepsilon\in(0,1)$。证明
$$ (1-\varepsilon)B_2^n \subset \operatorname{conv}(\mathcal N). $$这里一如往常，$B_2^n$ 表示 $\mathbb R^n$ 中的单位 Euclidean ball，$\operatorname{conv}(\cdot)$ 表示 Appetizer 中介绍的 convex hull。
令 $g_1,\ldots,g_N$ 为独立的 $N(0,I_n)$ 随机向量。对任意 $R,\varepsilon>0$，证明只要 $N\ge e^{C(R,\varepsilon)n}$，则以至少 $1-e^{-cn}$ 的概率，集合
$$ \left\{ \frac{g_1}{\sqrt n},\ldots,\frac{g_N}{\sqrt n} \right\} \cap RB_2^n $$构成 $RB_2^n$ 的一个 $\varepsilon$-net（即半径为 $R$、中心在原点的球的 $\varepsilon$-net）。这里 $C(R,\varepsilon)$ 只允许依赖于 $R$ 与 $\varepsilon$。
查看学习笔记证明路线Exercise 3.23 中我们看到，如果 $N\le e^{cn}$，则独立 Gaussian 随机向量 $g_1,\ldots,g_N\sim N(0,I_n)$ 以高概率处于 convex position。证明其逆向结论：若 $N\ge e^{Cn}$，则这些向量以至少 $1-e^{-cn}$ 的概率不处于 convex position。
查看学习笔记证明路线(a) 从 Theorem 4.4.3 推出
$$ \mathbb E\|A\| \le CK(\sqrt m+\sqrt n). $$(b) 从 Theorem 4.6.1 推出
$$ \mathbb E \left\| \frac1m A^{\mathsf T}A-I_n \right\| \le CK^2 \left(\sqrt{\frac nm}+\frac nm\right), $$并且
$$ \sqrt m-CK^2\sqrt n \le \mathbb E\,s_n(A) \le \mathbb E\,s_1(A) \le \sqrt m+CK^2\sqrt n. $$ 查看学习笔记证明路线证明 Theorem 4.4.3 的匹配下界。令 $A$ 是 $m\times n$ 随机矩阵，其元素 $A_{ij}$ 独立、subgaussian，并满足 $\mathbb E A_{ij}^2=1$。证明对任意 $t>0$，都有
$$ \|A\| \ge \frac12(\sqrt m+\sqrt n-t) $$以至少 $1-2\exp(-ct^2/K^4)$ 的概率成立。这里
$$ K=\max_{i,j}\|A_{ij}\|_{\psi_2}. $$ 查看学习笔记证明路线(a) 如果 $A$ 是一个 subgaussian matrix（即 $A$ 是 $\mathbb R^{m\times n}$ 中的 subgaussian random vector，见 Definition 3.4.1），证明 Theorem 4.4.3 在不作任何独立性假设时仍成立，其中
$$ K=\|A\|_{\psi_2}. $$(b) 特别地，如果 $A$ 有独立、均值为零、subgaussian 的行（或列）$A_i$，证明 Theorem 4.4.3 仍成立，其中
$$ K=\max_i\|A_i\|_{\psi_2}. $$ 查看学习笔记证明路线Theorem 4.4.3 研究的是随机矩阵的 $2\to2$ operator norm。那么其他 $p\to q$ operator norm 呢？我们在 Exercise 4.18 中定义了它们，并在 Exercises 4.19、4.20、4.21 中给出了一些例子。令 $A$ 是 $m\times n$ 矩阵，其元素 $A_{ij}$ 独立、均值为零、方差为一且 subgaussian。记
$$ K=\max_{i,j}\|A_{ij}\|_{\psi_2}. $$(a) 证明
$$ \|A\|_{1\to\infty} \le CK(\sqrt{\log m}+\sqrt{\log n}). $$(b) 证明
$$ \|A\|_{1\to2} = \|A^{\mathsf T}\|_{2\to\infty} \le \sqrt m+CK^2\sqrt{\log n}. $$之后借助更高级的工具，我们将能够处理所有 $p\to q$ 范数（见 Exercise 8.41）。
(c) 检查 (a) 和 (b) 中的界本质上是最优的。如果 $A$ 的元素为独立标准正态随机变量，验证
$$ \|A\|_{1\to\infty} \ge c(\sqrt{\log m}+\sqrt{\log n}) \quad\text{and}\quad \|A\|_{1\to2} \ge c(\sqrt m+\sqrt{\log n}). $$ 查看学习笔记证明路线Community detection 的 spectral clustering algorithm 保证（Theorem 4.5.2）不仅假设 $p-q$ 不太小，也假设跨社区边的概率 $q$ 不太小。现在去掉后一个假设。设计一个 spectral clustering algorithm 的版本，使误分类顶点数至多为
$$ \frac{C}{(p-q)^2}. $$ 查看学习笔记证明路线给出 Theorem 4.6.1 的一个更简单证明：使用 Theorem 3.1.1 得到 $\|Ax\|_2$ 的 concentration bound，再用 Exercise 4.37 把问题化为 net 上的 union bound。
查看学习笔记证明路线从 Theorem 4.6.1 推出如下关于 intermediate singular values 的界。对任意固定 $1\le k\le n$ 和 $t\ge0$，都有
$$ s_k(A) \ge \sqrt m-CK^2(\sqrt k+t) $$以至少 $1-2\exp(-t^2)$ 的概率成立。
查看学习笔记证明路线给出 covariance estimation（Theorem 4.7.1）的一个更敏感版本：使用相对误差而非绝对误差。假设 $\Sigma$ 可逆，证明
$$ \mathbb E\sup_{v\in\mathbb R^n} \left| \frac{v^{\mathsf T}\Sigma_m v} {v^{\mathsf T}\Sigma v} -1 \right| \le CK^2 \left( \sqrt{\frac nm} + \frac nm \right). $$换言之，我们得到了 $X$ 的一维 marginals 的方差的 uniform relative approximation（回忆 (3.6)）。
查看学习笔记证明路线验证 Remark 4.7.3 中提到的 covariance estimation 的 high-probability 保证。
查看学习笔记证明路线秩为 $r$ 的 $m\times n$ 矩阵可以通过它的 SVD 用 $(m+n+1)r$ 个参数描述：左 singular vectors 需要 $mr$ 个参数，右 singular vectors 需要 $nr$ 个参数，singular values 需要 $r$ 个参数。由于 covering numbers 通常随维度指数增长（见 Corollary 4.2.11），我们可以猜测集合
$$ M_{m,n,r} = \{\,m\times n\text{ matrices }A \text{ of rank }r \text{ and }\|A\|_F\le1\,\} $$的 covering numbers 按 $(m+n+1)r$ 指数级增长。事实确实如此。
(a) 考虑由所有列正交归一的 $m\times r$ 矩阵组成的集合 $O_{m,r}$。证明对每个 $\varepsilon>0$，都有
$$ \mathcal N(O_{m,r},\|\cdot\|_{1\to2},\varepsilon) \le \left(\frac C\varepsilon\right)^{mr}. $$(b) 证明对每个 $\varepsilon>0$，都有
$$ \mathcal N(M_{m,n,r},\|\cdot\|_F,\varepsilon) \le \left(\frac C\varepsilon\right)^{(m+n+1)r}. $$(c) 反过来，证明对每个 $\varepsilon>0$，都有
$$ \mathcal N(M_{m,n,r},\|\cdot\|_F,\varepsilon) \ge \left(\frac c\varepsilon\right)^{(m+n)r/2}. $$ 查看学习笔记证明路线证明 Theorem 4.7.5，也就是 spectral clustering 可以学习 Gaussian mixture model。步骤如下。
(a) 计算 $X$ 的 covariance matrix $\Sigma$，并注意 top eigenvector $u$ 与 $\mu$ 共线。
(b) 推出 $\langle X_i,u\rangle$ 的符号可以正确分类大多数点 $X_i$。
(c) 使用 covariance estimation 的结果，说明 sample covariance matrix $\Sigma_m$ 近似 $\Sigma$。
(d) 使用 Davis-Kahan inequality（Theorem 4.1.15），推出 top eigenvector $v=v_1(\Sigma_m)$ 近似 $u$。
(e) 使用 (b)，推出 $\langle X_i,v\rangle$ 的符号可以正确分类大多数点 $X_i$。
查看学习笔记证明路线校对说明
- 本页已经迁移 Figure 4.1-4.7。
- 本页已覆盖 Exercises 4.1-4.51，并统一渲染为 exercise 卡片。
- 本页的公式优先采用 MathJax 兼容写法，避免 OCR 中常见的不兼容粗体命令、断裂定界符和错误空格。