设 $A$ 是 $n\times n$ 矩阵，奇异值分解为

证明 $A$ 可逆当且仅当所有奇异值 $s_i$ 都非零。在这种情况下，验证

(a) 证明 Definition 4.1.8 中引入的算子范数 $\|A\|$ 确实是 $m\times n$ 矩阵空间上的范数。

(b) 对任意矩阵，证明

(c) 对任意维度匹配的矩阵，证明

找一个例子，使左侧为零但右侧不为零。

(d) 证明任意子矩阵的算子范数都不超过原矩阵的算子范数。

算子范数通常很难用矩阵元素表示，但下面是两个例外。

(a) Rank-one：对任意 $u\in\mathbb R^m$ 和 $v\in\mathbb R^n$，验证

(b) Diagonal：对任意对角矩阵 $A$，其对角元素为 $a_1,\ldots,a_n$，验证

设 $A$ 是 $m\times n$ 矩阵。

(a) 如果 $A$ 的秩为 $r$，证明

说明对任意 $m,n$ 和 $1\le r\le\min(m,n)$，两个界都可以达到。

(b) 如果 $Z$ 是 $\mathbb R^n$ 中的各向同性随机向量，证明

(c) 如果 $B$ 是 $k\times m$ 矩阵，证明

(d) 如果 $A$ 是对角矩阵，把 (c) 改进为

其中 $\|B\|_{1\to2}$ 表示 $B$ 的列的最大 Euclidean 范数。我们将在 Exercises 4.18、4.19 中进一步讨论 $1\to2$ 范数和一般 $p\to q$ 范数。

证明任意矩阵 $A$ 的奇异值 $s_i(A)$ 满足

下面是一种计算友好的方法：不显式计算谱，也能近似矩阵的算子范数。设 $A$ 是 $m\times n$ 矩阵，$x\sim N(0,I_n)$。证明以概率 $1$，

矩阵的算子范数很难用元素表示，但本题和下一题会证明一些有用界。设 $A$ 是 $m\times n$ 矩阵，列为 $A_1,\ldots,A_n$。

(a) 证明

当 $A_i$ 两两正交时取等号。

(b) 证明如果对某个 $i$ 有 $\|A\|=\|A_i\|_2$，则 $A_i$ 与所有其他列正交。

(c) 说明对行也有同样结论。

设 $A$ 是 $m\times n$ 矩阵，行为 $A_{i:}$，列为 $A_{:j}$。证明

构造“最分散”的正交矩阵，也就是所有元素绝对值都相同的正交矩阵。从 $2\times2$ 矩阵

开始，迭代定义分块矩阵

因此 $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$ 都满足

并说明两个界都可在无穷多个 $n$ 上达到。

证明 $\mathbb R^n$ 中任意两个正交投影 $P$ 和 $Q$ 都满足 $\|P-Q\|\le1$。如果想挑战一下，可以做下一题得到更精细的界。

对 $\mathbb R^n$ 中任意两个正交投影 $P$ 和 $Q$，证明如下结论。

(a)

其中 $P_{\perp}=I_n-P$ 且 $Q_{\perp}=I_n-Q$。

(b) 如果 $P$ 和 $Q$ 的秩不同，则 $\|P-Q\|=1$。

(c) 如果 $P$ 和 $Q$ 的秩相同，则

证明 Davis-Kahan theorem（Theorem 4.1.15）关于 top $k$ eigenvectors 投影的一个版本。考虑两个对称矩阵 $A$ 和 $B$，谱分解为

其中特征值按非增顺序排列。证明谱投影

满足

把任意 $m\times n$ 矩阵 $A$ 变成对称矩阵的两种常见方式是：(1) 使用 $A^{\mathsf T}A$ 或 $AA^{\mathsf T}$；(2) 取它的 Hermitian dilation，即 $(m+n)\times(m+n)$ 分块矩阵

Hermitian dilation 有几个优点：它是线性变换，并且保持稀疏性。设

是奇异值分解。证明 $H$ 的非零特征值只有 $\pm s_i$，对应特征向量为

Davis-Kahan inequality（Theorem 4.1.15）适用于对称矩阵。下面证明一般矩形矩阵的版本。设 $A$ 和 $B$ 是 $m\times n$ 矩阵，奇异值分解为

其中奇异值按非增顺序排列。证明 top $k$ 左奇异向量上的投影

满足

给出 top $k$ 右奇异向量投影的类似界。并证明第 $k$ 个奇异向量的 Davis-Kahan 型版本。

简化 Davis-Kahan inequality（Theorem 4.1.15）的结论。设两个单位向量 $u,v\in\mathbb R^n$ 的夹角（取 $0$ 到 $\pi/2$ 之间的数）很小，即

证明 $u$ 与 $v$ 在差一个符号意义下接近：

为 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$，使得

(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$ 范数，为

其中 $q'$ 是 (1.5) 中定义的 $q$ 的共轭指数。

(a) 把 (4.9) 中的等式推广到 $p\to q$ 范数，并说明理由。

(b) 验证这确实定义了 $m\times n$ 矩阵空间上的一个范数。

(c) Duality：证明

其中 $p'$ 和 $q'$ 是 $p$ 和 $q$ 的共轭指数。

设 $A$ 是 $m\times n$ 矩阵。对大多数 $p,q$，很难用元素表达 $\|A\|_{p\to q}$，但下面是一些例外。

(a) 证明 $1\to\infty$ 范数等于元素绝对值最大值：

(b) 证明 $1\to2$ 范数等于列的最大 Euclidean 范数，而 $2\to\infty$ 范数等于行的最大 Euclidean 范数：

这个范数我们已经见过：它隐含在 Grothendieck 不等式（Theorem 3.5.1）的假设中。设 $A$ 是 $m\times n$ 矩阵。

(a) 证明

(b) Duality：证明

其中上确界取遍所有秩一 $m\times n$ 矩阵 $Z$，其所有元素绝对值不超过 $1$；矩阵内积定义在 (4.7) 中。

(c) 说明 (4.32) 的恒等式不能推广到二次型：找出 $n\times n$ 对称矩阵 $A$，使得

这个范数在理论计算机科学和图论中很重要。为了求 $m\times n$ 矩阵 $A$ 的 cut norm，我们对 $A$ 的每个子矩阵求元素和，取绝对值，再对所有子矩阵最大化。形式化地，定义

其中最大值取遍所有 $I\subset\{1,\ldots,m\}$ 和 $J\subset\{1,\ldots,n\}$。证明 cut norm 与 $\infty\to1$ 范数在常数因子内等价：

设 $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 本质等价：

Covering number 关于 $\varepsilon$ 是单调的（为什么？），但它不一定关于集合 $K$ 单调。

(a) 举例说明一般情形下并不总有

(b) 证明一个近似单调性版本：

在本题和接下来的两题中，我们用三种方式计算 $\mathbb R^n$ 中单位 Euclidean ball 的体积：几何方式、概率方式和解析方式。先从几何方式开始。

(a) Canonical simplex $\Delta_n$ 如 Figure 4.6 阴影部分所示，由 $\mathbb R^n$ 中所有非负坐标且坐标和至多为 $1$ 的点组成。证明

(b) 回忆 $\mathbb R^n$ 中单位 $\ell^1$ ball 为

像 Figure 4.6 那样把它分割为 simplices，证明

(c) 像 Figure 4.6 那样，把单位 Euclidean ball $B_2^n$ 夹在适当缩放的 cube 与 $\ell^1$ ball 之间，从而推出

因此，高维单位球的体积是指数级小的。虽然这些界仍有松弛，但对多数用途已经足够。

现在改进 (4.33) 中的上界。利用 small ball probability（Exercise 3.7）推出

这个界是渐近尖锐的；下一题会看到这一点。

最后精确计算 Euclidean ball 的体积。

(a) 设 $\|\cdot\|$ 是 $\mathbb R^n$ 上的一个范数。考虑该 normed space 的单位球

令 $f:\mathbb R_+\to\mathbb R_+$ 为递减、可微函数，并满足 $\lim_{x\to\infty}f(x)=0$。验证恒等式

(b) 代入 $f(t)=e^{-t^2/2}$，推出

(c) 记 $R_n$ 为体积等于 $1$ 的 Euclidean ball 的半径。证明

$R_n$ 很大这一事实说明单位球 $B_2^n$ 的体积很小。

令 $p\in[1,\infty]$。

(a) 重复 Exercise 4.27 中的几何论证，推出下面的界：

(b) 使用 Exercise 4.29 中的解析论证，精确计算体积：

$\varepsilon$-net 的构造（Remark 4.2.7）并不高效，因为 nets 往往指数级大且难以存储。换一种方式：令 $\mathcal N$ 为缩放整数 lattice

中落在单位球 $B_2^n$ 内的所有点。验证 $\mathcal N$ 在 Euclidean metric 下构成 $B_2^n$ 的 $\varepsilon$-net，并且

这个界几乎匹配 Corollary 4.2.11 中的界。另请说明如何快速把单位球中的任意给定向量近似为 $\mathcal N$ 中的向量。

通过调整 volumetric method，证明 Proposition 4.2.15。

证明 Theorem 4.3.5 的一个逆向结果。对任意把 $k$-bit 字符串编码为 $n$-bit 字符串且能纠正 $r$ 个错误的 error correcting code，证明

$\varepsilon$-nets 可以帮助近似向量。下面说明如何用它们给出精确表示。

(a) 令 $\mathcal N$ 是 $\mathbb R^n$ 的单位球面 $S^{n-1}$ 的一个 $\varepsilon$-net。证明任意向量 $x\in S^{n-1}$ 都可以写成收敛级数

其中 $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。证明

通过修改 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$，都有

证明球面的 $\varepsilon$-net 会“吸收”一个略小的球，见 Figure 4.7。令 $\mathcal N$ 是单位球面 $S^{n-1}$ 的一个 $\varepsilon$-net，其中 $\varepsilon\in(0,1)$。证明

这里一如往常，$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}$ 的概率，集合

构成 $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 推出

(b) 从 Theorem 4.6.1 推出

并且

证明 Theorem 4.4.3 的匹配下界。令 $A$ 是 $m\times n$ 随机矩阵，其元素 $A_{ij}$ 独立、subgaussian，并满足 $\mathbb E A_{ij}^2=1$。证明对任意 $t>0$，都有

以至少 $1-2\exp(-ct^2/K^4)$ 的概率成立。这里

(a) 如果 $A$ 是一个 subgaussian matrix（即 $A$ 是 $\mathbb R^{m\times n}$ 中的 subgaussian random vector，见 Definition 3.4.1），证明 Theorem 4.4.3 在不作任何独立性假设时仍成立，其中

(b) 特别地，如果 $A$ 有独立、均值为零、subgaussian 的行（或列）$A_i$，证明 Theorem 4.4.3 仍成立，其中

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。记

(a) 证明

(b) 证明

之后借助更高级的工具，我们将能够处理所有 $p\to q$ 范数（见 Exercise 8.41）。

(c) 检查 (a) 和 (b) 中的界本质上是最优的。如果 $A$ 的元素为独立标准正态随机变量，验证

Community detection 的 spectral clustering algorithm 保证（Theorem 4.5.2）不仅假设 $p-q$ 不太小，也假设跨社区边的概率 $q$ 不太小。现在去掉后一个假设。设计一个 spectral clustering algorithm 的版本，使误分类顶点数至多为

给出 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$，都有

以至少 $1-2\exp(-t^2)$ 的概率成立。

给出 covariance estimation（Theorem 4.7.1）的一个更敏感版本：使用相对误差而非绝对误差。假设 $\Sigma$ 可逆，证明

换言之，我们得到了 $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），我们可以猜测集合

的 covering numbers 按 $(m+n+1)r$ 指数级增长。事实确实如此。

(a) 考虑由所有列正交归一的 $m\times r$ 矩阵组成的集合 $O_{m,r}$。证明对每个 $\varepsilon>0$，都有

(b) 证明对每个 $\varepsilon>0$，都有

(c) 反过来，证明对每个 $\varepsilon>0$，都有

证明 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$。

证明思路

SVD 把 $A$ 写成 $U\Sigma V^{\mathsf T}$。矩阵可逆当且仅当对角矩阵 $\Sigma$ 可逆；逆矩阵就是 $V\Sigma^{-1}U^{\mathsf T}$。

完整证明

由 SVD，$A=U\Sigma V^{\mathsf T}$，其中 $\Sigma=\operatorname{diag}(s_1,\ldots,s_n)$，$U,V$ 正交。由于正交矩阵可逆，$A$ 可逆当且仅当 $\Sigma$ 可逆，也就是当且仅当所有 $s_i\ne0$。

在这种情况下，

证明思路

始终回到定义 $\|A\|=\sup_{\|x\|_2=1}\|Ax\|_2$。转置不变性可用最大奇异值或双线性形式。

完整证明

(a) 非负性和齐次性直接来自 Euclidean 范数。若 $\|A\|=0$，则 $Ax=0$ 对所有单位向量成立，故 $A=0$。三角不等式为

(b) $\|A\|=s_1(A)$，而 $A$ 与 $A^{\mathsf T}$ 有相同奇异值，所以 $\|A^{\mathsf T}\|=\|A\|$。

(c) 对任意单位向量 $x$，

取上确界得 $\|AB\|\le\|A\|\|B\|$。例子：$A=\operatorname{diag}(1,0)$，$B=\operatorname{diag}(0,1)$，则 $AB=0$ 但 $\|A\|\|B\|=1$。

(d) 子矩阵可写成 $PAQ$，其中 $P,Q$ 是坐标投影，且 $\|P\|,\|Q\|\le1$。所以 $\|PAQ\|\le\|A\|$。

证明思路

rank-one 矩阵只把向量沿 $v$ 方向的分量送到 $u$ 方向；对角矩阵逐坐标缩放。

完整证明

(a) 对任意单位向量 $x$，

取 $x=v/\|v\|$ 达到等号，所以 $\|uv^{\mathsf T}\|=\|u\|\|v\|$。Frobenius 范数满足

(b) 若 $A=\operatorname{diag}(a_i)$，则

取 $x=e_j$，其中 $|a_j|=\max_i|a_i|$，得到等号。

证明思路

用奇异值表达 Frobenius 范数；用 trace 表达各向同性向量下的二阶矩；用 $\|Bz\|\le\|B\|\|z\|$ 控制左乘。

完整证明

(a) 若 $\operatorname{rank}(A)=r$，则只有 $r$ 个非零奇异值。因此

rank-one 矩阵使左侧等号成立；$r$ 个相等非零奇异值使右侧等号成立。

(b) 若 $Z$ 各向同性，$\mathbb EZZ^{\mathsf T}=I$，则

(c) 设 $A_1,\ldots,A_n$ 是 $A$ 的列，或直接逐列看 $BA$。有

(d) 若 $A$ 对角，则 $BA$ 的第 $j$ 列是 $a_jB_j$，所以

证明思路

Frobenius 范数平方是所有奇异值平方之和，而前 $k$ 个奇异值都至少为 $s_k$。

完整证明

奇异值按降序排列，因此

开平方得到 $s_k(A)\le \|A\|_F/\sqrt k$。

证明思路

在右奇异向量基下展开 Gaussian 初始向量。最高奇异值对应的分量几乎必然非零，反复作用会让最大奇异值主导。

完整证明

设 $A^{\mathsf T}A=V\operatorname{diag}(s_i^2)V^{\mathsf T}$，并写

因为 $x$ 是标准 Gaussian，任意固定方向上的系数 $\alpha_i$ 几乎必然非零。于是

令 $s_1=\|A\|$。若 $s_1>0$，则

括号中的量在 $2k$ 次根下趋于 $1$，因为至少一个 top singular direction 的系数非零。因此

若 $A=0$，结论平凡。

证明思路

列向量就是 $Ae_i$。若某个列向量已经达到算子范数，则 $e_i$ 是 $A^{\mathsf T}A$ 的最大特征向量，迫使该列与其余列正交。

完整证明

(a) 对每个 $i$，

若列两两正交，则

所以等号成立。

(b) 若 $\|A\|=\|A_i\|_2$，则 $e_i$ 使 Rayleigh quotient $x^{\mathsf T}A^{\mathsf T}Ax$ 取到最大值。因此 $e_i$ 是 $A^{\mathsf T}A$ 的特征向量。于是对 $j\ne i$，

(c) 对行应用同样结论于 $A^{\mathsf T}$。

证明思路

对每一行使用 Cauchy-Schwarz 的加权版本，再交换求和，把行和、列和分别提出来。

完整证明

记

对任意 $x$，

对 $i$ 求和得到

取单位向量上的上确界，$\|A\|\le\sqrt{RC}$。

证明思路

用归纳法检查 $W_kW_k^{\mathsf T}=nI_n$，其中 $n$ 是矩阵阶数。

完整证明

当 $k=1$ 时，

假设 $W_kW_k^{\mathsf T}=nI_n$。则

所以若 $W_{k+1}$ 阶数为 $2n$，则 $W_{k+1}W_{k+1}^{\mathsf T}=(2n)I_{2n}$。归纳完成，故 $W_k/\sqrt n$ 正交。

证明思路

上界由 Frobenius 范数给出；下界由 Frobenius 范数和秩给出。全 $1$ 矩阵达到上界，Walsh 矩阵达到下界。

完整证明

因为 $A$ 有 $n^2$ 个元素且每个绝对值为 $1$，

上界由 $\|A\|\le\|A\|_F$ 得到：$\|A\|\le n$。下界由 Exercise 4.4(a) 得到：

所以 $\|A\|\ge\sqrt n$。

全 $1$ 矩阵秩为 $1$，唯一非零奇异值为 $n$，达到上界。对 $n=2^k$，Walsh 矩阵满足 $WW^{\mathsf T}=nI_n$，所有奇异值都是 $\sqrt n$，因此达到下界。

证明思路

$P-Q$ 是自伴矩阵。对自伴矩阵，算子范数由 Rayleigh quotient 控制；而 $\langle(P-Q)x,x\rangle=\|Px\|^2-\|Qx\|^2$ 位于 $[-1,1]$。

完整证明

因为 $P,Q$ 是正交投影，$P=P^{\mathsf T}=P^2$，$Q=Q^{\mathsf T}=Q^2$，所以 $P-Q$ 自伴。对任意单位向量 $x$，

两个平方范数都在 $[0,1]$ 中，因此该差属于 $[-1,1]$。由自伴矩阵的变分刻画，

证明思路

先把 $P-Q$ 写成两个正交分量之和，再利用秩相等时 $PQ$ 与 $QP$ 的非零奇异值相同。

完整证明

先证明 (a)。恒等式

来自 $Q_\perp=I-Q$ 和 $P_\perp=I-P$。对任意单位向量 $x$，两个向量 $PQ_\perp x$ 与 $P_\perp Qx$ 分别落在 $\operatorname{range}(P)$ 与 $\operatorname{range}(P)^\perp$，所以正交。因此

其中 $M=\max(\|PQ_\perp\|,\|P_\perp Q\|)$。这给出 $\|P-Q\|\le M$。反向不等式也直接成立，因为

而投影的算子范数不超过 $1$。故

下面证明 (b)。若 $\operatorname{rank}(P)>\operatorname{rank}(Q)$，则

所以存在单位向量 $x\in\operatorname{range}(P)\cap\ker(Q)$。于是 $(P-Q)x=x$，故 $\|P-Q\|\ge1$。结合 Exercise 4.11 的 $\|P-Q\|\le1$，得到 $\|P-Q\|=1$。若 $\operatorname{rank}(Q)>\operatorname{rank}(P)$，同理。

最后证明 (c)。令两个秩都为 $k$。有

在 $\operatorname{range}(Q)$ 上，$QPQ$ 的非零特征值等于算子 $PQ$ 的奇异值平方；在 $\operatorname{range}(P)$ 上，$PQP$ 的非零特征值也是同一批数。由于两个空间维数都为 $k$，零特征值的重数也相同。因此 $QP_\perp Q=Q-QPQ$ 与 $PQ_\perp P=P-PQP$ 有相同特征值，从而两个范数相等。结合 (a)，得到

证明思路

把 top $k$ 特征值看成一个谱簇。只要该谱簇与其余谱相隔 $\lambda_k-\lambda_{k+1}$，Davis-Kahan 定理直接控制两个谱投影。

完整证明

设 $\delta=\lambda_k-\lambda_{k+1}>0$。若 $2\|A-B\|\ge\delta$，右侧至少为 $1$，而 $\|P_A-P_B\|\le1$，结论平凡。

否则令 $\varepsilon=\|A-B\|<\delta/2$。由 Weyl 不等式，对 $j>k$ 有

而 $A$ 的 top $k$ 谱簇位于 $[\lambda_k,\infty)$ 中，所以该谱簇与 $B$ 的 bottom 谱簇 $\{\mu_j:j>k\}$ 的距离至少

把 Theorem 4.1.15 证明中的谱投影分离引理用于 $A$ 的 top $k$ 投影 $P_A$ 和 $B$ 的 bottom 投影 $I-P_B$，得到

由于 $P_A$ 与 $P_B$ 秩相同，Exercise 4.12(c) 给出 $\|P_A-P_B\|=\|(I-P_B)P_A\|$。因此

证明思路

把 SVD 中的左右奇异向量拼成分块向量，直接作用分块矩阵。

完整证明

若 $Av_i=s_iu_i$ 且 $A^{\mathsf T}u_i=s_iv_i$，则

并且

因此每个非零奇异值 $s_i$ 产生两个特征值 $\pm s_i$。剩余维度对应 $A$ 或 $A^{\mathsf T}$ 的核，特征值为 $0$。

证明思路

构造 $H_A$ 和 $H_B$。它们的谱投影差由 Davis-Kahan 控制；左奇异子空间投影只是该分块谱投影的左上角压缩，所以范数不会增大。

完整证明

令

由 Exercise 4.14，$H_A$ 的正特征值是 $s_i(A)$，对应特征向量为 $[u_i;v_i]$ 的归一化版本。并且

令 $R_A$ 为 $H_A$ 对谱簇 $\{\pm s_1,\ldots,\pm s_k\}$ 的谱投影，并令 $R_B$ 为 $H_B$ 对对应谱簇的谱投影。这个投影同时包含正、负两组特征向量；对每个 $i\le k$，两个归一化特征向量 $[u_i;v_i]/\sqrt2$ 与 $[u_i;-v_i]/\sqrt2$ 的投影相加为

所以 $R_A$ 的左上角分块正是 $P_A$，右下角分块正是 top $k$ 右奇异向量投影。

若 $2\|A-B\|\ge s_k-s_{k+1}$，则右侧至少为 $1$，而两个正交投影之差的范数不超过 $1$，结论成立。否则 Weyl 不等式保证 $H_B$ 中对应的 $\pm t_1,\ldots,\pm t_k$ 谱簇仍与其余谱相隔至少 $(s_k-s_{k+1})/2$。对这个分离谱簇应用投影型 Davis-Kahan，得到

取左上角分块不会增加算子范数，于是 top $k$ 左奇异向量投影满足题中界。取右下角分块得到 top $k$ 右奇异向量投影的同样界。

单个第 $k$ 个奇异向量的版本作用于只含 $\pm s_k$ 的谱簇。若 $s_k$ 与相邻奇异值的间隔为

（端点处只保留存在的项），则投影误差至多 $2\|A-B\|/\Delta_k$；再用 Exercise 4.16 可把一维投影距离转为奇异向量在差一个全局符号意义下的 Euclidean 距离界。

证明思路

选取符号让内积非负。距离平方等于 $2-2|\langle u,v\rangle|$，再用 $\sin$ 控制。

完整证明

取 $\theta\in\{-1,1\}$ 使 $\langle u,\theta v\rangle=|\langle u,v\rangle|=\cos\angle(u,v)\ge0$。则

对 $c\in[0,1]$ 有 $1-c\le1-c^2$。因此

开平方得到结论。

证明思路

用 SVD。$A^{\mathsf T}A$ 和 $AA^{\mathsf T}$ 共享非零特征值；这些特征值就是奇异值平方。

完整证明

(a) 若 $A$ 是 isometry，则 $A^{\mathsf T}A=I_n$。矩阵 $AA^{\mathsf T}$ 对称，且

所以它是到 $\operatorname{range}(A)$ 的正交投影。反过来，若 $AA^{\mathsf T}$ 是秩为 $n$ 的正交投影，则其非零特征值全为 $1$。这些正是 $A^{\mathsf T}A$ 的特征值，所以 $A^{\mathsf T}A=I_n$，即 $A$ 是 isometry。

(b) 写完整的 $n$ 个右奇异方向版本：$A=U\Sigma V^{\mathsf T}$，其中 $U$ 是 $m\times n$ 的列正交矩阵；若 $A$ 有零奇异值，就把对应左奇异向量任意补成正交列。令 $P=UU^{\mathsf T}$，这是秩为 $n$ 的正交投影。则

因此

这正是 approximate isometry 的二次型表述，故两者等价。

证明思路

用 $\ell^q$ 与 $\ell^{q'}$ 的对偶性：$\|z\|_q=\max_{\|y\|_{q'}=1}|y^{\mathsf T}z|$。

完整证明

(a) 对任意 $x$，

再对 $\|x\|_p=1$ 最大化，得到 (4.31)。

(b) 非负性、齐次性和三角不等式都由 $\|Ax\|_q/\|x\|_p$ 的定义直接推出；若范数为 $0$，则 $Ax=0$ 对所有 $x$ 成立，所以 $A=0$。

(c) 由双线性表达，

证明思路

$\ell^1$ 单位球的极点是 $\pm e_j$；$\ell^\infty$ 输出看行，$\ell^2$ 输出看列。

完整证明

(a) 对任意 $\|x\|_1\le1$，

再对 $i$ 取最大，得 $\|A\|_{1\to\infty}\le\max_{ij}|A_{ij}|$。取 $x=\pm e_j$ 达到最大元素，故等号成立。

(b) 设 $A_j$ 为第 $j$ 列。若 $\|x\|_1\le1$，则

取 $x=e_j$ 得等号。因此 $\|A\|_{1\to2}=\max_j\|A_{:j}\|_2$。对 $2\to\infty$，第 $i$ 个坐标是行向量 $A_{i:}$ 与 $x$ 的内积，Cauchy-Schwarz 给出上界，取 $x$ 平行于最大行得到等号。

证明思路

线性函数在盒子上最大值取在顶点。rank-one 表述把 $y^{\mathsf T}Ax$ 写成矩阵内积。二次型反例来自非凸二次函数在盒子内部达到更大绝对值。

完整证明

(a) 由 $\ell^1$ 与 $\ell^\infty$ 对偶，

该双线性函数在两个盒子上最大，固定一边时另一边的最大值都在顶点取得，所以可取 $x,y\in\{-1,1\}$。

(b) 对秩一矩阵 $Z=yx^{\mathsf T}$，有 $\langle A,Z\rangle=y^{\mathsf T}Ax$。若 $\|x\|_\infty,\|y\|_\infty\le1$，则 $|Z_{ij}|\le1$。反过来，任意秩一 $Z=uv^{\mathsf T}$ 且 $|Z_{ij}|\le1$，可重新缩放为 $Z=yx^{\mathsf T}$，其中 $\|x\|_\infty,\|y\|_\infty\le1$。于是得到所需上确界。

(c) 取

在顶点 $x\in\{-1,1\}^2$ 上，$x^{\mathsf T}Ax=1$，所以最大绝对值为 $1$。但在 $x=(0,1)$ 处，$x^{\mathsf T}Ax=2$。因此二次型版本不能只检查符号顶点。

证明思路

cut norm 是用 $0/1$ 指示向量选择子矩阵；$\infty\to1$ 范数是用 $\pm1$ 符号向量。两者可通过把符号向量分解为正负集合互相转换。

完整证明

对任意 $I,J$，令 $y=\mathbf 1_I$、$x=\mathbf 1_J$，它们的 $\ell^\infty$ 范数不超过 $1$。因此

所以 $\|A\|_{\mathrm{cut}}\le\|A\|_{\infty\to1}$。

反过来，由 Exercise 4.20，只需考虑 $x\in\{-1,1\}^n$、$y\in\{-1,1\}^m$。令 $I_\pm=\{i:y_i=\pm1\}$，$J_\pm=\{j:x_j=\pm1\}$。则 $y^{\mathsf T}Ax$ 是四个矩形和的带符号组合：

每个矩形和的绝对值都不超过 cut norm，因此

对符号向量取最大，即得 $\|A\|_{\infty\to1}\le4\|A\|_{\mathrm{cut}}$。

证明思路

核心是把符号或盒约束优化松弛为向量 Gram 矩阵优化。Grothendieck 不等式保证 $\infty\to1$ 的 SDP 松弛只损失常数；其他范数通过等价关系或平方化归约到同类 SDP。

完整证明

对 $\|A\|_{\infty\to1}$，Exercise 4.20 把它写成符号双线性优化。把符号 $x_j,y_i$ 放松为单位向量 $u_j,v_i$，目标变为

这是 Gram 矩阵变量上的 SDP。Grothendieck 不等式说明这个 SDP 值与原值只差绝对常数因子。

cut norm 与 $\infty\to1$ 范数由 Exercise 4.21 在常数因子内等价，因此也可常数近似。

对于 $\|A\|_{\infty\to2}$，有

在常数因子意义下可由正半定二次 Grothendieck/SDP 松弛近似。最后 $\|A\|_{2\to1}=\|A^{\mathsf T}\|_{\infty\to2}$，所以同样可由 SDP 常数近似。

证明思路

对 $K$ 中任意点，先用 $\mathcal M$ 近似，再用 $\mathcal N$ 近似 $\mathcal M$ 中的点。两次误差相加。

完整证明

任取 $x\in K$。因为 $\mathcal M$ 是 $K$ 的 $\delta$-net，存在 $m\in\mathcal M$ 使

又因为 $\mathcal N$ 是 $\mathcal M$ 的 $\varepsilon$-net，存在 $y\in\mathcal N$ 使

由三角不等式，

这对任意 $x\in K$ 成立，所以 $\mathcal N$ 是 $K$ 的 $(\varepsilon+\delta)$-net。

证明思路

一般 metric space 可能没有两个点之间的“中点”。normed space 有中点；若两中心距离不超过 $\varepsilon$，中点会同时落入两个闭球。

完整证明

(a) 取 $T=\{a,b\}$，定义 $d(a,b)=0.75\varepsilon$。以 $a,b$ 为中心的闭 $\varepsilon/2$-balls 分别为 $\{a\}$ 和 $\{b\}$，因为 $0.75\varepsilon>\varepsilon/2$，所以它们不交。但 $d(a,b)<\varepsilon$，因此 $\{a,b\}$ 不是 $\varepsilon$-separated。这给出一般 metric space 中的反例。

(b) 设 $T$ 是 normed space 的子集，且以 $\mathcal N$ 中点为中心的闭 $\varepsilon/2$-balls 两两不交。若存在不同 $x,y\in\mathcal N$ 满足 $\|x-y\|\le\varepsilon$，则中点 $z=(x+y)/2$ 满足

于是 $z$ 同时落入两个闭 $\varepsilon/2$-balls，矛盾。因此任意不同中心距离都大于 $\varepsilon$，即 $\mathcal N$ 是 $\varepsilon$-separated。

证明思路

内部 covering 是 external covering 的特殊情形，所以外部覆盖数不比内部覆盖数大。反向时，把每个外部中心移动到它所覆盖到的一个 $K$ 中点上，半径从 $\varepsilon/2$ 增大到 $\varepsilon$。

完整证明

第一部分直接成立：普通 covering 要求中心在 $K$ 中，是 external covering 的特殊情形，所以

下面证明第二个不等式。设 $y_1,\ldots,y_M$ 是 $K$ 的 external $\varepsilon/2$-net，其中

丢掉那些半径 $\varepsilon/2$ 球与 $K$ 没有交集的中心。对每个剩余的 $y_i$，选取一个 $x_i\in K$ 满足 $d(x_i,y_i)\le\varepsilon/2$。若 $z\in K$ 被 $y_i$ 覆盖，即 $d(z,y_i)\le\varepsilon/2$，则

所以这些 $x_i\in K$ 构成 $K$ 的普通 $\varepsilon$-net，且数量不超过 $M$。因此

证明思路

反例来自“内部球心”的限制：大集合可能包含一个中心点，可以同时覆盖小集合的两端；小集合自身没有这个中心点。近似单调性用 Exercise 4.25 的移动中心技巧。

完整证明

关于 $\varepsilon$ 的单调性是直接的：半径越大，每个球覆盖越多，所以 $\varepsilon_1\le\varepsilon_2$ 时

(a) 取实线中的 $K=\{-1,0,1\}$，$L=\{-1,1\}$，并令 $\varepsilon=1.1$。集合 $K$ 可由一个以 $0\in K$ 为中心的 $\varepsilon$-ball 覆盖，所以 $\mathcal N(K,d,\varepsilon)=1$。但 $L$ 的中心必须在 $L$ 中；以 $-1$ 或 $1$ 为中心的半径 $1.1$ 球都不能覆盖另一个点，因为两点距离为 $2$。因此 $\mathcal N(L,d,\varepsilon)=2$，这与普通单调性相反。

(b) 设 $L\subset K$。取 $K$ 的一个 $\varepsilon/2$-net，中心为 $x_1,\ldots,x_M\in K$，其中 $M=\mathcal N(K,d,\varepsilon/2)$。只保留那些 $\varepsilon/2$-球与 $L$ 相交的中心；对每个保留中心 $x_i$，选一个 $y_i\in L$ 满足 $d(x_i,y_i)\le\varepsilon/2$。若 $z\in L$ 被 $x_i$ 覆盖，则

于是这些 $y_i\in L$ 构成 $L$ 的 $\varepsilon$-net，数量不超过 $M$。所以

证明思路

先算 canonical simplex 的体积，再把 $\ell^1$ ball 分成 $2^n$ 个 simplex。Euclidean ball 夹在一个 cube 和缩放的 $\ell^1$ ball 之间。

完整证明

(a) 对 $\Delta_n=\{x_i\ge0,\ \sum_i x_i\le1\}$，按最后一个坐标积分：

由归纳假设，该截面体积为 $(1-t)^{n-1}/(n-1)!$。因此

(b) $B_1^n$ 被 $2^n$ 个正交象限分割；每个象限中的部分都是一个 canonical simplex。因此

由 $n!\ge(n/e)^n$，得到 $\operatorname{Vol}(B_1^n)\le(2e/n)^n$。

(c) 若 $\|x\|_\infty\le1/\sqrt n$，则 $\|x\|_2\le1$，所以

这给出下界 $\operatorname{Vol}(B_2^n)\ge(2/\sqrt n)^n$。另一方面，由 Cauchy-Schwarz，$\|x\|_1\le\sqrt n\|x\|_2$，所以

因此

证明思路

把 Gaussian 落入半径 $\sqrt n$ 球的概率用密度下界控制。概率不超过 $1$，于是反推出球体积上界。

完整证明

设 $g\sim N(0,I_n)$。在球 $\sqrt n B_2^n$ 上，Gaussian 密度满足

因此

而 $\operatorname{Vol}(\sqrt n B_2^n)=n^{n/2}\operatorname{Vol}(B_2^n)$，所以

证明思路

范数球满足 $\operatorname{Vol}(tB)=t^n\operatorname{Vol}(B)$。把积分按层集写成 Stieltjes 积分，再分部积分。代入 Gaussian kernel 后使用 Gamma 函数和 Stirling 公式。

完整证明

(a) 因为 $\{x:\|x\|\le t\}=tB$，其体积为 $t^n\operatorname{Vol}(B)$。对递减可微且趋于 $0$ 的 $f$，层集积分给出

分部积分，边界项为零，于是

(b) 对 Euclidean norm 取 $f(t)=e^{-t^2/2}$。左侧为

右侧中的积分为

所以

(c) 体积为 $1$ 的 Euclidean ball 半径 $R_n$ 满足

由 Stirling 公式 $\Gamma(n/2+1)=\sqrt{\pi n}(n/(2e))^{n/2}(1+o(1))$，得到

因此

证明思路

粗界来自 cube 与缩放 $\ell^1$ ball 的夹逼。精确公式沿用 Exercise 4.29 的径向积分，取 $f(t)=e^{-t^p}$。

完整证明

(a) 若 $\|x\|_\infty\le n^{-1/p}$，则 $\|x\|_p\le1$，所以

这给出下界 $(2/n^{1/p})^n$。另一方面，Hölder 不等式给出 $\|x\|_1\le n^{1-1/p}\|x\|_p$，因此

结合 $\operatorname{Vol}(B_1^n)\le(2e/n)^n$，得到

(b) 在 Exercise 4.29 的公式中取 $\|\cdot\|=\|\cdot\|_p$ 和 $f(t)=e^{-t^p}$。左侧分解为坐标积分：

右侧的径向积分为

因此

证明思路

对每个坐标向零取整，保证格点仍在单位球内，同时每个坐标误差不超过 $\varepsilon/\sqrt n$。大小估计用格点小立方体和 Euclidean ball 的体积上界。

完整证明

令格距 $h=\varepsilon/\sqrt n$。给定 $x\in B_2^n$，定义 $y_i$ 为与 $x_i$ 同号且满足

则 $y\in h\mathbb Z^n$，并且 $|y_i|\le |x_i|$，所以 $\|y\|_2\le\|x\|_2\le1$，即 $y\in\mathcal N$。同时 $|x_i-y_i|\le h$，故

因此 $\mathcal N$ 是 $B_2^n$ 的 $\varepsilon$-net。这个构造也给出了快速近似算法：逐坐标向零取整即可。

下面估计大小。以每个 $y\in\mathcal N$ 为角放置半开小立方体 $y+[0,h)^n$；这些小立方体互不相交，并且每个点到 $y$ 的 Euclidean 距离至多 $\sqrt n h=\varepsilon$。因此它们都包含在 $(1+\varepsilon)B_2^n$ 中。于是

用 Exercise 4.28 的体积上界，

对通常的 net 范围 $0<\varepsilon\le1$，右侧被 $e^n(2/\varepsilon+1)^n$ 控制；若 $\varepsilon>1$，该界更平凡成立。故得到题中估计。

证明思路

把 Euclidean 体积换成 Hamming ball 的基数。半径 $m$ 的 Hamming ball 大小为 $\sum_{k=0}^m\binom nk$。

完整证明

在 $\{0,1\}^n$ 中，任意中心的半径 $m$ Hamming ball 的基数为

因为可以选择至多 $m$ 个坐标翻转。

若 $M$ 个半径 $m$ 球覆盖整个 cube，则 $M V_m\ge2^n$。因此

另一方面，取极大的 $m$-separated 子集。极大性保证它是一个 $m$-net，所以

最后，若 $\mathcal P$ 是一个 $m$-separated 集，则以其点为中心、半径 $\lfloor m/2\rfloor$ 的 Hamming balls 两两不交。每个这样的球大小为

这些不交球都包含在 cube 中，因此

取最大的 packing，即得

证明思路

若 code 能纠正 $r$ 个错误，则不同 codewords 的半径 $r$ Hamming balls 必须两两不交。比较这些球的总基数与整个 Hamming cube 的基数。

完整证明

一个把 $k$-bit 字符串编码为 $n$-bit 字符串的 code 有 $2^k$ 个 codewords。若它能纠正 $r$ 个错误，则以不同 codeword 为中心、半径 $r$ 的 Hamming balls 必须两两不交；否则某个接收词会同时位于两个 codeword 的 $r$ 邻域内，无法唯一解码。

每个半径 $r$ Hamming ball 的大小为

不交性给出 Hamming bound：

因此

使用标准组合估计 $\binom nr\ge(n/r)^r$，得到

这就是所需限制。

证明思路

反复用 net 点逼近当前残差方向。每一步残差长度最多乘以 $\varepsilon$，因此系数按 $\varepsilon^k$ 衰减。

完整证明

(a) 令 $r_0=x$。若 $r_k\ne0$，从 net 中取 $x_k\in\mathcal N$ 使

并定义 $r_{k+1}=r_k-\lambda_kx_k$。则

由 $\lambda_0=1$ 归纳得 $0\le\lambda_k\le\varepsilon^k$，且 $\|r_k\|_2\to0$。因此

(b) 令 $M=\sup_{z\in\mathcal N}\|Az\|_2$。对任意 $x\in S^{n-1}$ 使用 (a)，

对 $x$ 取上确界得到 Lemma 4.4.1 的上界；下界来自 $\mathcal N\subset S^{n-1}$，即在 net 上取上确界不会超过在整个球面上取上确界。

证明思路

范数是 $\sup_{u\in S^{n-1}}\langle x,u\rangle$。用 net 点逼近最大方向 $u=x/\|x\|_2$。

完整证明

下界直接由 Cauchy-Schwarz 给出：

若 $x=0$，上界两边都为 $0$。若 $x\ne0$，令 $u=x/\|x\|_2$。取 $y\in\mathcal N$ 使 $\|u-y\|_2\le\varepsilon$。则

移项得

证明思路

取几乎达到 $\|A\|$ 的方向 $x,y$，分别用 net 点 $x_0,y_0$ 逼近。两个逼近误差各贡献至多 $\varepsilon\|A\|$。

完整证明

记

下界 $M\le\|A\|$ 来自 $\mathcal N\subset S^{n-1}$、$\mathcal M\subset S^{m-1}$。为证上界，先假设 $0<\varepsilon<1/2$；否则分母 $1-2\varepsilon$ 不为正，该形式的估计没有内容。取 $x\in S^{n-1}$、$y\in S^{m-1}$ 使 $|\langle Ax,y\rangle|$ 任意接近 $\|A\|$。选择 $x_0\in\mathcal N$、$y_0\in\mathcal M$ 满足

则

取上确界并整理，得到

若 $A$ 对称且只用同一个 net，则从 $|\langle Ax,x\rangle|$ 的变分刻画出发，同样用 $x_0$ 逼近 $x$，误差仍至多 $2\varepsilon\|A\|$，得到相同结论。

证明思路

当 net 偏差已经大于中心量级时，Lemma 4.4.1 直接给出粗控制；否则先控制平方范数对应的二次型，再除回长度偏差。

完整证明

记

若 $\mu<0$，则 $|\|Ax\|_2-\mu|=\|Ax\|_2+|\mu|$。由 Lemma 4.4.1，

且 $|\mu|\le\Delta$，所以结论成立。下面只考虑 $\mu\ge0$。

若 $\Delta\ge\mu$，则 $\sup_{\mathcal N}\|Ax\|_2\le\mu+\Delta\le2\Delta$。再次由 Lemma 4.4.1，

于是 $\sup_{S^{n-1}}|\|Ax\|_2-\mu|\le C\Delta/(1-2\varepsilon)$。

剩下情形是 $0\le\Delta<\mu$。设

对 $x\in\mathcal N$，

由 Lemma 4.4.2 的对称情形，

因此对任意 $x\in S^{n-1}$，

合并三种情形即可得到题设不等式，其中 $C$ 为绝对常数。

证明思路

对任意方向 $u$，net 中有点 $z$ 与 $u$ 接近，因此 $\langle u,z\rangle\ge1-\varepsilon$。这说明凸包在每个方向上的支撑函数至少为 $1-\varepsilon$。

完整证明

令 $C=\operatorname{conv}(\mathcal N)$。对任意 $u\in S^{n-1}$，取 $z\in\mathcal N$ 使 $\|u-z\|_2\le\varepsilon$。由

可得 $\langle u,z\rangle\ge1-\varepsilon^2/2\ge1-\varepsilon$。因此

若存在 $y\in(1-\varepsilon)B_2^n$ 但 $y\notin C$，由超平面分离定理，存在 $u\in S^{n-1}$ 使

但 $\langle u,y\rangle\le\|y\|_2\le1-\varepsilon$，与上式的支撑函数下界矛盾。因此 $(1-\varepsilon)B_2^n\subset C$。

证明思路

先取 $RB_2^n$ 的一个确定性细 net。对每个 net 中心，Gaussian 缩放点落入它附近的概率至少为 $e^{-C(R,\varepsilon)n}$。指数多个独立点加 union bound 即覆盖所有中心。

完整证明

令 $Z_i=g_i/\sqrt n$。取 $RB_2^n$ 的一个 $(\varepsilon/4)$-net $\mathcal M$，满足

对每个 $y\in\mathcal M$，把它稍微向内收缩为 $y'=(1-\varepsilon/(8R))y$。若 $\|Z_i-y'\|_2\le\varepsilon/8$，则 $Z_i\in RB_2^n$，且 $\|Z_i-y\|_2\le\varepsilon/4$。

Gaussian 密度在固定半径球内的指数阶下界给出

这里可以直接验证：在球 $B(y',\varepsilon/8)$ 中所有点范数不超过 $R$，所以 $Z_i$ 的密度至少为 $(n/2\pi)^{n/2}e^{-nR^2/2}$；再用 $\operatorname{Vol}(B_2^n)\ge(c/\sqrt n)^n$，得到上述指数型下界。

因此某个固定 $y\in\mathcal M$ 没有被任何样本点命中的概率至多 $(1-p)^N\le e^{-Np}$。由 union bound，所有 net 中心都被命中的失败概率至多

只要 $N\ge\exp(C'(R,\varepsilon)n)$，上式至多为 $e^{-cn}$。在好事件上，每个 $x\in RB_2^n$ 先找 $y\in\mathcal M$ 使 $\|x-y\|_2\le\varepsilon/4$，再找样本点 $Z_i\in RB_2^n$ 使 $\|Z_i-y\|_2\le\varepsilon/4$，于是 $\|x-Z_i\|_2\le\varepsilon$。这正是所需 net 性质。

证明思路

把点分成两批。第一批足够多，缩放后在 $2B_2^n$ 内形成细 net，从而其凸包包含一个固定小球；第二批中高概率至少有一个点落入这个小球，于是该点在其他点的凸包内。

完整证明

缩放不改变 convex position，所以考虑 $Z_i=g_i/\sqrt n$。把样本分成两组，各有指数多个点。由 Exercise 4.39，若第一组大小至少为 $e^{C_1n}$，则以至少 $1-e^{-c_1n}$ 的概率，第一组中落在 $2B_2^n$ 内的点构成 $2B_2^n$ 的一个足够小的 net。

特别地，它包含球面 $S^{n-1}$ 的一个 $\varepsilon$-net。由 Exercise 4.38，第一组点的凸包包含 $(1-\varepsilon)B_2^n$。

另一方面，对单个 $Z_i$，事件 $\|Z_i\|_2\le1-\varepsilon$ 有概率至少 $e^{-C_2n}$。如果第二组大小至少为 $e^{C_3n}$ 且 $C_3>C_2$，则第二组至少有一个点落在 $(1-\varepsilon)B_2^n$ 内的概率至少为 $1-e^{-c_2n}$。

在两件好事件同时发生时，第二组中的这个点属于第一组点的凸包，因此它不是整个点集凸包的极点。于是这些 Gaussian 点不处于 convex position。选择 $C$ 足够大并合并失败概率，得到至少 $1-e^{-cn}$ 的结论。

证明思路

使用尾积分公式：若 $Z\le a+bt$ 以概率至少 $1-2e^{-t^2}$ 成立，则 $\mathbb EZ\le a+Cb$。

完整证明

(a) Theorem 4.4.3 给出对所有 $t\ge0$，

由尾积分公式，

(b) Theorem 4.6.1 证明中的矩阵形式给出

以至少 $1-2e^{-t^2}$ 的概率成立。再次积分尾部，得到

同理，把 Theorem 4.6.1 的奇异值双侧尾界积分，得到

证明思路

算子范数至少不小于任意一列和任意一行的 Euclidean 范数。分别对第一列和第一行使用范数集中下界。

完整证明

对第一列 $Ae_1$，它是 $m$ 维独立、方差为一、次高斯坐标向量。范数集中下界给出

以至少 $1-\exp(-ct^2/K^4)$ 的概率成立。同理，对第一行 $A^{\mathsf T}e_1$，

也以同样概率成立。两者同时成立的概率至少为 $1-2\exp(-ct^2/K^4)$。

在该事件上，

由于 $\max(a,b)\ge(a+b)/2$，得到

把 $2t$ 重新记为 $t$ 并调整常数，即得题设形式。

证明思路

对固定 $x,y$，$\langle Ax,y\rangle$ 是矩阵随机向量 $A$ 在 Frobenius 单位方向 $yx^{\mathsf T}$ 上的投影。只要这个投影次高斯，后续 net 和 union bound 完全相同。

完整证明

(a) 把 $A$ 看成 $\mathbb R^{mn}$ 中的随机向量。对固定 $x\in S^{n-1}$、$y\in S^{m-1}$，

因此

对两个球面的 $1/4$-net 使用 union bound，并用 Lemma 4.4.2 从 net 回到整个球面，得到 Theorem 4.4.3 的同阶结论，其中 $K=\|A\|_{\psi_2}$。

(b) 若 $A$ 的行 $A_i$ 独立、均值为零且次高斯，则

这些项独立、均值为零，并满足 $\|\langle A_i,x\rangle\|_{\psi_2}\le K$，其中 $K=\max_i\|A_i\|_{\psi_2}$。独立次高斯和的估计给出 $\|\langle Ax,y\rangle\|_{\psi_2}\le CK$。于是 (a) 中的 net argument 仍然适用。列独立情形对 $A^{\mathsf T}$ 使用同样论证。

证明思路

$1\to\infty$ 范数就是最大元素；$1\to2$ 范数就是最大列范数。分别用最大次高斯变量和列范数集中。

完整证明

(a) 由定义，

对 $mn$ 个次高斯变量使用 union bound，得到以高概率

(b) 对任意矩阵，

所以二者相等。每一列是 $m$ 维独立、方差为一、次高斯坐标向量，范数集中给出

以概率至少 $1-2e^{-t^2}$ 成立。取 $t=C\sqrt{\log n}$ 并对列作 union bound，得到

以高概率成立。

(c) 若 $A_{ij}$ 为独立标准正态，则最大元素满足

以高概率成立，证明 (a) 的量级最优。另一方面，

以高概率成立；同时 $\|A\|_{1\to2}\ge\max_j|A_{1j}|\ge c\sqrt{\log n}$。合并两个下界，得到

以高概率成立。

证明思路

原证明中 $q$ 出现在 $\lambda_1(D)$ 与 $\lambda_2(D)$ 的间隔。改用中心化或投影到 $\mathbf1^\perp$ 的谱聚类，只追踪 community 方向，此时谱间隙为 $(p-q)n/2$。

完整证明

设 $\mathbf1=(1,\ldots,1)$，令 $P$ 是到 $\mathbf1^\perp$ 的正交投影。对邻接矩阵 $A=D+R$，考虑中心化矩阵

在 $\mathbf1^\perp$ 上，信号部分 $\widetilde D=PDP$ 只有一个非零特征方向，即 community 向量

对应特征值

因此在 $\mathbf1^\perp$ 上的相关谱间隙是 $\lambda$，不再涉及 $q$。

噪声部分为 $\widetilde R=PRP$，且 $\|\widetilde R\|\le\|R\|$。由于 Bernoulli 噪声有界、中心化且次高斯，Corollary 4.4.7 给出

以高概率成立。Davis-Kahan 不等式给出单位化特征向量的误差

其中 $\bar v$ 是 $\widetilde A$ 在 $\mathbf1^\perp$ 上 top eigenvector。乘以 $\sqrt n$ 后，存在全局符号 $\theta$ 使

每个误分类坐标至少贡献一个常数量级的平方误差，因此误分类数至多

算法就是：计算 $PAP$ 在 $\mathbf1^\perp$ 上的 top eigenvector，并按其坐标符号分类。

证明思路

固定 $x$ 时，$Ax$ 是有独立次高斯坐标的向量，Theorem 3.1.1 控制 $\|Ax\|_2$。再在球面 net 上 union bound，并用 Exercise 4.37 推回所有方向。

完整证明

固定 $x\in S^{n-1}$。矩阵行 $A_i$ 独立、各向同性、次高斯，因此随机变量 $\langle A_i,x\rangle$ 独立、均值为零、方差为一且次高斯范数由 $K$ 控制。Theorem 3.1.1 给出

取 $S^{n-1}$ 的 $1/4$-net $\mathcal N$，满足 $|\mathcal N|\le9^n$。令 $t=C(\sqrt n+u)$，对 net 点作 union bound，可得以至少 $1-2e^{-u^2}$ 的概率，

由 Exercise 4.37，把 net 上的偏差推广到整个球面：

最后注意

于是得到 Theorem 4.6.1 的双侧奇异值界。

证明思路

把 $A$ 限制到任意固定 $k$ 维子空间，例如前 $k$ 个坐标。限制矩阵是 $m\times k$ 次高斯矩阵；其最小奇异值给出原矩阵第 $k$ 个奇异值的下界。

完整证明

令 $E\subset\mathbb R^n$ 为前 $k$ 个坐标张成的子空间，令 $A_E$ 表示 $A$ 在 $E$ 上的限制，即 $A$ 的前 $k$ 列。它是 $m\times k$ 随机矩阵，行仍独立、各向同性且次高斯范数由 $K$ 控制。

由 Theorem 4.6.1 应用于 $A_E$，以至少 $1-2e^{-t^2}$ 的概率，

由 Courant-Fischer 变分刻画，

合并即得

证明思路

令 $Y=\Sigma^{-1/2}X$。则 $Y$ 各向同性，样本协方差为 $\Sigma^{-1/2}\Sigma_m\Sigma^{-1/2}$。相对误差正是这个白化样本协方差与 $I$ 的算子范数距离。

完整证明

设

则 $\mathbb EYY^{\mathsf T}=I_n$，并且

条件 (4.29) 在白化后给出 $\|Y\|_{\psi_2}\le K$。由 Theorem 4.7.1 应用于 $Y$，

另一方面，对任意 $v\ne0$，令 $w=\Sigma^{1/2}v$，则

因此

取期望即得所需相对误差界。

证明思路

Theorem 4.7.1 的证明本质上对白化样本矩阵应用 Theorem 4.6.1。保留其中的尾参数并令 $t=\sqrt u$ 即得高概率形式。

完整证明

先假设 $\Sigma$ 可逆，令 $Y=\Sigma^{-1/2}X$。如 Exercise 4.48，$Y$ 各向同性且次高斯参数由 $K$ 控制。Theorem 4.6.1 的矩阵形式给出：对任意 $u\ge0$，以至少 $1-2e^{-u}$ 的概率，

乘回 $\Sigma^{1/2}$，得到 Loewner 意义下

其中 $\delta$ 为右侧。于是

若 $\Sigma$ 不可逆，可在 $\Sigma+\eta I$ 上做上述论证后令 $\eta\downarrow0$，或限制到 $\Sigma$ 的值域。于是得到 Remark 4.7.3 的高概率界。

证明思路

上界直接离散化 SVD 的三个部分：左奇异向量、右奇异向量、奇异值。下界不必使用流形理论；只要把一个全维矩阵球嵌入低秩矩阵类即可。

完整证明

(a) 注意 $\|U-V\|_{1\to2}$ 就是列差的最大 Euclidean 范数：

取单位球面 $S^{m-1}$ 的一个 $(\varepsilon/2)$-net $\mathcal N$，满足 $|\mathcal N|\le(C/\varepsilon)^m$。对 $U\in O_{m,r}$ 的每一列 $U_{:j}$，选择 $u_j\in\mathcal N$ 使 $\|U_{:j}-u_j\|_2\le\varepsilon/2$。所有 $r$ 元组 $(u_1,\ldots,u_r)$ 构成 $O_{m,r}$ 的一个外部 $(\varepsilon/2)$-net；这些近似矩阵本身不必仍在 $O_{m,r}$ 中。由 Exercise 4.25，可把外部中心移回 $O_{m,r}$，并得到内部 $\varepsilon$-net，数量不增加。于是

(b) 任意 $A\in M_{m,n,r}$ 可写成 SVD

分别取 $O_{m,r}$、$O_{n,r}$ 和 Euclidean 单位球 $B_2^r$ 的 $\varepsilon/3$-nets。若 $U,V,s$ 分别由 $U_0,V_0,s_0$ 逼近，则

三个 net 的大小相乘，得到

(c) 先假设 $m\ge n$。考虑所有只在前 $r$ 列可能非零的矩阵

其中满列秩的 $B$ 给出 rank 正好为 $r$ 的矩阵，且满列秩矩阵在 $\mathbb R^{mr}$ 的单位 Frobenius 球中占满测度。若 $M_{m,n,r}$ 可由 $N$ 个 Frobenius 半径 $\varepsilon$ 的球覆盖，则这些球也覆盖上述满秩子集。忽略测度为零的秩亏集合并比较 $\mathbb R^{mr}$ 中体积，得到

所以 $N\ge(c/\varepsilon)^{mr}$（当 $\varepsilon$ 大于固定常数时右侧至多为 $1$，结论平凡）。由于 $m\ge n$，有 $mr\ge (m+n)r/2$，故

若 $n>m$，则改为只让前 $r$ 行可能非零，得到 $N\ge(c/\varepsilon)^{nr}$，同样推出所需下界。这说明上界中的指数阶在常数因子意义下正确。

证明思路

总体协方差是 $I+\mu\mu^{\mathsf T}$，top eigenvector 是 $\mu$ 方向。协方差估计给出样本 top eigenvector 接近该方向；投影到近似方向后，Gaussian 噪声不能改变大多数点的符号。

完整证明

(a) 写 $X=\theta\mu+g$，其中 $\theta$ 是 Rademacher 变量，$g\sim N(0,I_n)$。由于 $\theta$ 与 $g$ 独立且均值为零，

因此 top eigenvector 为

对应特征值 $1+\|\mu\|_2^2$；其余方向特征值为 $1$，谱间隙为 $\|\mu\|_2^2$。

(b) 若使用真实方向 $u$ 分类，则

令 $M=\|\mu\|_2$。若真实标签为 $\theta_i$，则

因此真实方向误分类概率为 $\mathbb P\{N(0,1)\le-M\}$。更强地，真实方向 margin 小于 $M/2$ 的概率为 $\mathbb P\{N(0,1)\le-M/2\}$。当 $M\ge C$ 且 $C$ 足够大时，这个概率小于 $0.001$。对 $m$ 个样本用 Chernoff 或 Hoeffding 不等式，可得至少以概率 $0.997$，满足 $\theta_i\langle X_i,u\rangle<M/2$ 的样本比例至多 $0.3\%$。

(c) 该 mixture 分布满足 Theorem 4.7.1 的相对次高斯条件，且参数为绝对常数：对任意 $x$，

若 $m\ge Cn$ 且常数 $C$ 足够大，covariance estimation 的高概率版本给出

以概率至少 $0.995$ 成立，其中 $c>0$ 可任意小。

(d) 由 Davis-Kahan 不等式和谱间隙 $\|\mu\|_2^2$，样本 top eigenvector $v$ 满足，在差一个全局符号后，

其中 $\eta>0$ 可通过增大样本量常数取得足够小。同时在同一好事件上，

(e) 现在处理关键的依赖性问题：$v$ 是由样本算出的，不能把 $\langle X_i,v-u\rangle$ 当作固定方向上的独立噪声。我们改用确定性计数。记 $h=v-u$。若某个样本满足

则它按 $v$ 的符号也会被正确分类，因为

因此额外错误只能来自 $|\langle X_i,h\rangle|\ge M/2$ 的样本。由 Markov 型计数，

在 (d) 的好事件上，

由于 $M\ge C\ge1$，额外错误比例至多 $C'\eta^2$。选择样本量常数使 $\eta$ 足够小，可令它小于 $0.3\%$。再加上 (b) 中真实方向 margin 不足的样本，误分类比例至多 $1\%$。合并两个好事件，概率至少 $0.99$。这证明了 Theorem 4.7.5。