证明思路

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^{-1} = V\Sigma^{-1}U^{\mathsf T} = \sum_{i=1}^n s_i^{-1}v_i u_i^{\mathsf T}. $$

证明思路

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

完整证明

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

$$ \|A+B\| = \sup_{\|x\|=1}\|(A+B)x\| \le \sup_{\|x\|=1}(\|Ax\|+\|Bx\|) \le \|A\|+\|B\|. $$

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

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

$$ \|ABx\|\le\|A\|\|Bx\|\le\|A\|\|B\|. $$

取上确界得 $\|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$，

$$ uv^{\mathsf T}x=u\langle v,x\rangle, \qquad \|uv^{\mathsf T}x\|\le\|u\|\|v\|. $$

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

$$ \|uv^{\mathsf T}\|_F^2 = \sum_{ij}u_i^2v_j^2 = \|u\|^2\|v\|^2. $$

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

$$ \|Ax\|_2^2=\sum_i a_i^2x_i^2\le(\max_i|a_i|)^2\|x\|_2^2. $$

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

证明思路

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

完整证明

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

$$ \|A\|=s_1\le\left(\sum_i s_i^2\right)^{1/2}=\|A\|_F \le \sqrt r\,s_1=\sqrt r\,\|A\|. $$

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

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

$$ \mathbb E\|AZ\|_2^2 = \mathbb E\,Z^{\mathsf T}A^{\mathsf T}AZ = \operatorname{tr}(A^{\mathsf T}A\mathbb EZZ^{\mathsf T}) = \operatorname{tr}(A^{\mathsf T}A) = \|A\|_F^2. $$

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

$$ \|BA\|_F^2 = \sum_j\|B A_j\|_2^2 \le \|B\|^2\sum_j\|A_j\|_2^2 = \|B\|^2\|A\|_F^2. $$

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

$$ \|BA\|_F^2 = \sum_j a_j^2\|B_j\|_2^2 \le \|B\|_{1\to2}^2\sum_j a_j^2 = \|B\|_{1\to2}^2\|A\|_F^2. $$

证明思路

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

完整证明

奇异值按降序排列，因此

$$ \|A\|_F^2 = \sum_i s_i(A)^2 \ge \sum_{i=1}^k s_i(A)^2 \ge k\,s_k(A)^2. $$

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

证明思路

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

完整证明

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

$$ x=\sum_i\alpha_i v_i. $$

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

$$ (A^{\mathsf T}A)^kx = \sum_i \alpha_i s_i^{2k}v_i. $$

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

$$ \|(A^{\mathsf T}A)^kx\|_2 = s_1^{2k} \left(\sum_i\alpha_i^2(s_i/s_1)^{4k}\right)^{1/2}. $$

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

$$ \sqrt[2k]{\|(A^{\mathsf T}A)^kx\|_2}\to s_1=\|A\|. $$

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

证明思路

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

完整证明

(a) 对每个 $i$，

$$ \|A\|\ge\|Ae_i\|_2=\|A_i\|_2. $$

若列两两正交，则

$$ \|Ax\|_2^2 = \left\|\sum_i x_iA_i\right\|_2^2 = \sum_i x_i^2\|A_i\|_2^2 \le \max_i\|A_i\|_2^2\|x\|_2^2, $$

所以等号成立。

(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$，

$$ \langle A_i,A_j\rangle = e_i^{\mathsf T}A^{\mathsf T}Ae_j = 0. $$

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

证明思路

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

完整证明

记

$$ R=\max_i\sum_j|a_{ij}|,\qquad C=\max_j\sum_i|a_{ij}|. $$

对任意 $x$，

$$ |(Ax)_i|^2 = \left|\sum_j a_{ij}x_j\right|^2 \le \left(\sum_j|a_{ij}|\right) \left(\sum_j|a_{ij}||x_j|^2\right) \le R\sum_j|a_{ij}||x_j|^2. $$

对 $i$ 求和得到

$$ \|Ax\|_2^2 \le R\sum_j\left(\sum_i|a_{ij}|\right)|x_j|^2 \le RC\|x\|_2^2. $$

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

证明思路

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

完整证明

当 $k=1$ 时，

$$ W_1W_1^{\mathsf T}=2I_2. $$

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

$$ W_{k+1}W_{k+1}^{\mathsf T} = \begin{bmatrix} W_k&W_k\\ W_k&-W_k \end{bmatrix} \begin{bmatrix} W_k^{\mathsf T}&W_k^{\mathsf T}\\ W_k^{\mathsf T}&-W_k^{\mathsf T} \end{bmatrix} = \begin{bmatrix} 2nI_n&0\\ 0&2nI_n \end{bmatrix}. $$

所以若 $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\|_F=n. $$

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

$$ \|A\|_F\le\sqrt{\operatorname{rank}(A)}\,\|A\| \le \sqrt n\,\|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$，

$$ \langle(P-Q)x,x\rangle = \langle Px,x\rangle-\langle Qx,x\rangle = \|Px\|_2^2-\|Qx\|_2^2. $$

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

$$ \|P-Q\| = \sup_{\|x\|_2=1}|\langle(P-Q)x,x\rangle| \le1. $$

证明思路

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

完整证明

先证明 (a)。恒等式

$$ P-Q=PQ_\perp-P_\perp Q $$

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

$$ \|(P-Q)x\|_2^2 = \|PQ_\perp x\|_2^2+\|P_\perp Qx\|_2^2 \le M^2\bigl(\|Q_\perp x\|_2^2+\|Qx\|_2^2\bigr) = M^2, $$

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

$$ PQ_\perp=(P-Q)Q_\perp, \qquad P_\perp Q=-P_\perp(P-Q), $$

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

$$ \|P-Q\| = \max(\|P_\perp Q\|,\|PQ_\perp\|). $$

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

$$ \dim\operatorname{range}(P)+\dim\ker(Q)>n, $$

所以存在单位向量 $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$。有

$$ \|P_\perp Q\|^2 = \|QP_\perp Q\|, \qquad \|PQ_\perp\|^2 = \|P Q_\perp P\|. $$

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

$$ \|P-Q\|=\|P_\perp Q\|=\|PQ_\perp\|. $$

证明思路

把 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$ 有

$$ \mu_j\le\lambda_j+\varepsilon\le\lambda_{k+1}+\varepsilon. $$

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

$$ \lambda_k-(\lambda_{k+1}+\varepsilon) = \delta-\varepsilon \ge \delta/2. $$

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

$$ \|(I-P_B)P_A\| \le \frac{\varepsilon}{\delta/2} = \frac{2\|A-B\|}{\delta}. $$

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

$$ \|P_A-P_B\| \le \frac{2\|A-B\|}{\lambda_k-\lambda_{k+1}}. $$

证明思路

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

完整证明

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

$$ H\begin{bmatrix}u_i\\ v_i\end{bmatrix} = \begin{bmatrix}Av_i\\ A^{\mathsf T}u_i\end{bmatrix} = s_i\begin{bmatrix}u_i\\ v_i\end{bmatrix}, $$

并且

$$ H\begin{bmatrix}u_i\\ -v_i\end{bmatrix} = \begin{bmatrix}-Av_i\\ A^{\mathsf T}u_i\end{bmatrix} = -s_i\begin{bmatrix}u_i\\ -v_i\end{bmatrix}. $$

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

证明思路

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

完整证明

令

$$ H_A=\begin{bmatrix}0&A\\ A^{\mathsf T}&0\end{bmatrix}, \qquad H_B=\begin{bmatrix}0&B\\ B^{\mathsf T}&0\end{bmatrix}. $$

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

$$ \|H_A-H_B\|=\|A-B\|. $$

令 $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$ 的投影相加为

$$ \begin{bmatrix} u_i u_i^{\mathsf T} & 0\\ 0 & v_i v_i^{\mathsf T} \end{bmatrix}. $$

所以 $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，得到

$$ \|R_A-R_B\| \le \frac{2\|A-B\|}{s_k-s_{k+1}}. $$

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

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

$$ \Delta_k=\min(s_{k-1}-s_k,\ s_k-s_{k+1}) $$

（端点处只保留存在的项），则投影误差至多 $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$。则

$$ \|u-\theta v\|_2^2 = 2-2\cos\angle(u,v). $$

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

$$ \|u-\theta v\|_2^2 \le 2(1-\cos^2\angle(u,v)) = 2\sin^2\angle(u,v) \le 2\varepsilon^2. $$

开平方得到结论。

证明思路

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

完整证明

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

$$ (AA^{\mathsf T})^2=A(A^{\mathsf T}A)A^{\mathsf T}=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$ 的正交投影。则

$$ AA^{\mathsf T}=U\Sigma^2U^{\mathsf T}, \qquad AA^{\mathsf T}-P=U(\Sigma^2-I)U^{\mathsf T}. $$

因此

$$ \|AA^{\mathsf T}-P\| = \|\Sigma^2-I\| = \|A^{\mathsf T}A-I\|. $$

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

证明思路

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

完整证明

(a) 对任意 $x$，

$$ \|Ax\|_q = \max_{\|y\|_{q'}=1}|y^{\mathsf T}Ax|. $$

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

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

(c) 由双线性表达，

$$ \|A^{\mathsf T}\|_{p\to q} = \max_{\|x\|_p=1,\ \|y\|_{q'}=1} |y^{\mathsf T}A^{\mathsf T}x| = \max_{\|y\|_{q'}=1,\ \|x\|_p=1} |x^{\mathsf T}Ay| = \|A\|_{q'\to p'}. $$

证明思路

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

完整证明

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

$$ |(Ax)_i| \le \sum_j |A_{ij}||x_j| \le \max_j|A_{ij}|. $$

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

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

$$ \|Ax\|_2 = \left\|\sum_jx_jA_j\right\|_2 \le \sum_j|x_j|\|A_j\|_2 \le \max_j\|A_j\|_2. $$

取 $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$ 对偶，

$$ \|A\|_{\infty\to1} = \max_{\|x\|_\infty\le1,\ \|y\|_\infty\le1}|y^{\mathsf T}Ax|. $$

该双线性函数在两个盒子上最大，固定一边时另一边的最大值都在顶点取得，所以可取 $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) 取

$$ A= \begin{bmatrix} -1&0\\ 0&2 \end{bmatrix}. $$

在顶点 $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$。因此

$$ \left|\sum_{i\in I,j\in J}A_{ij}\right| = |y^{\mathsf T}Ax| \le \|A\|_{\infty\to1}. $$

所以 $\|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$ 是四个矩形和的带符号组合：

$$ S(I_+,J_+)-S(I_+,J_-)-S(I_-,J_+)+S(I_-,J_-). $$

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

$$ |y^{\mathsf T}Ax|\le4\|A\|_{\mathrm{cut}}. $$

对符号向量取最大，即得 $\|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$，目标变为

$$ \max \sum_{ij}A_{ij}\langle v_i,u_j\rangle, $$

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

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

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

$$ \|A\|_{\infty\to2}^2 = \max_{x\in\{-1,1\}^n}x^{\mathsf T}A^{\mathsf T}Ax $$

在常数因子意义下可由正半定二次 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$ 使

$$ d(x,m)\le\delta. $$

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

$$ d(m,y)\le\varepsilon. $$

由三角不等式，

$$ d(x,y)\le d(x,m)+d(m,y)\le\delta+\varepsilon. $$

这对任意 $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-x\|=\|z-y\|=\frac12\|x-y\|\le\frac\varepsilon2. $$

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

证明思路

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

完整证明

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

$$ \overline{\mathcal N}(K,d,\varepsilon)\le \mathcal N(K,d,\varepsilon). $$

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

$$ M=\overline{\mathcal N}(K,d,\varepsilon/2). $$

丢掉那些半径 $\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$，则

$$ d(z,x_i)\le d(z,y_i)+d(y_i,x_i)\le\varepsilon. $$

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

$$ \mathcal N(K,d,\varepsilon)\le\overline{\mathcal N}(K,d,\varepsilon/2). $$

证明思路

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

完整证明

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

$$ \mathcal N(K,d,\varepsilon_2)\le \mathcal N(K,d,\varepsilon_1). $$

(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$ 覆盖，则

$$ d(z,y_i)\le d(z,x_i)+d(x_i,y_i)\le\varepsilon. $$

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

$$ \mathcal N(L,d,\varepsilon)\le\mathcal N(K,d,\varepsilon/2). $$

证明思路

先算 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\}$，按最后一个坐标积分：

$$ \operatorname{Vol}(\Delta_n) = \int_0^1 \operatorname{Vol}\{x_1,\ldots,x_{n-1}\ge0,\ \sum_{i=1}^{n-1}x_i\le1-t\}\,dt. $$

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

$$ \operatorname{Vol}(\Delta_n) = \frac1{(n-1)!}\int_0^1(1-t)^{n-1}\,dt = \frac1{n!}. $$

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

$$ \operatorname{Vol}(B_1^n)=\frac{2^n}{n!}. $$

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

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

$$ [-1/\sqrt n,1/\sqrt n]^n\subset B_2^n. $$

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

$$ B_2^n\subset \sqrt n\,B_1^n. $$

因此

$$ \operatorname{Vol}(B_2^n) \le n^{n/2}\operatorname{Vol}(B_1^n) \le n^{n/2}\left(\frac{2e}{n}\right)^n = \left(\frac{2e}{\sqrt n}\right)^n. $$

证明思路

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

完整证明

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

$$ (2\pi)^{-n/2}e^{-\|x\|_2^2/2} \ge (2\pi)^{-n/2}e^{-n/2}. $$

因此

$$ 1 \ge \mathbb P\{g\in\sqrt n B_2^n\} \ge (2\pi)^{-n/2}e^{-n/2}\operatorname{Vol}(\sqrt n B_2^n). $$

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

$$ \operatorname{Vol}(B_2^n) \le \left(\sqrt{\frac{2\pi e}{n}}\right)^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$，层集积分给出

$$ \int_{\mathbb R^n}f(\|x\|)\,dx = \int_0^\infty f(t)\,d\bigl(t^n\operatorname{Vol}(B)\bigr). $$

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

$$ \int_{\mathbb R^n}f(\|x\|)\,dx = -\operatorname{Vol}(B)\int_0^\infty t^n f'(t)\,dt. $$

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

$$ \int_{\mathbb R^n}e^{-\|x\|_2^2/2}\,dx=(2\pi)^{n/2}. $$

右侧中的积分为

$$ -\int_0^\infty t^n f'(t)\,dt = \int_0^\infty t^{n+1}e^{-t^2/2}\,dt = 2^{n/2}\Gamma(n/2+1). $$

所以

$$ \operatorname{Vol}(B_2^n) = \frac{(2\pi)^{n/2}}{2^{n/2}\Gamma(n/2+1)} = \frac{\pi^{n/2}}{\Gamma(n/2+1)}. $$

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

$$ R_n^n\operatorname{Vol}(B_2^n)=1. $$

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

$$ \operatorname{Vol}(B_2^n)^{1/n} = \sqrt{\frac{2\pi e}{n}}\,(1+o(1)). $$

因此

$$ R_n=\operatorname{Vol}(B_2^n)^{-1/n} = \sqrt{\frac{n}{2\pi e}}\,(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$，所以

$$ [-n^{-1/p},n^{-1/p}]^n\subset B_p^n. $$

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

$$ B_p^n\subset n^{1-1/p}B_1^n. $$

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

$$ \operatorname{Vol}(B_p^n) \le n^{n(1-1/p)}\left(\frac{2e}{n}\right)^n = \left(\frac{2e}{n^{1/p}}\right)^n. $$

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

$$ \int_{\mathbb R^n}e^{-\|x\|_p^p}\,dx = \left(2\int_0^\infty e^{-s^p}\,ds\right)^n = \bigl(2\Gamma(1+1/p)\bigr)^n. $$

右侧的径向积分为

$$ -\int_0^\infty t^n f'(t)\,dt = p\int_0^\infty t^{n+p-1}e^{-t^p}\,dt = \Gamma(n/p+1). $$

因此

$$ \operatorname{Vol}(B_p^n) = \frac{\bigl(2\Gamma(1/p+1)\bigr)^n}{\Gamma(n/p+1)}. $$

证明思路

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

完整证明

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

$$ |y_i|=h\left\lfloor\frac{|x_i|}{h}\right\rfloor. $$

则 $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$，故

$$ \|x-y\|_2\le \sqrt n\,h=\varepsilon. $$

因此 $\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$ 中。于是

$$ |\mathcal N|h^n \le \operatorname{Vol}((1+\varepsilon)B_2^n). $$

用 Exercise 4.28 的体积上界，

$$ |\mathcal N| \le \left(\frac{\sqrt n}{\varepsilon}\right)^n (1+\varepsilon)^n \left(\sqrt{\frac{2\pi e}{n}}\right)^n = \left(\frac{\sqrt{2\pi e}(1+\varepsilon)}{\varepsilon}\right)^n. $$

对通常的 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 的基数为

$$ V_m=\sum_{k=0}^m\binom nk, $$

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

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

$$ \mathcal N(K,d_H,m)\ge\frac{2^n}{V_m}. $$

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

$$ \mathcal N(K,d_H,m)\le\mathcal P(K,d_H,m). $$

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

$$ V_{\lfloor m/2\rfloor}=\sum_{k=0}^{\lfloor m/2\rfloor}\binom nk. $$

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

$$ |\mathcal P|V_{\lfloor m/2\rfloor}\le2^n. $$

取最大的 packing，即得

$$ \mathcal P(K,d_H,m) \le \frac{2^n}{\sum_{k=0}^{\lfloor m/2\rfloor}\binom nk}. $$

证明思路

若 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 的大小为

$$ \sum_{j=0}^r\binom nj \ge \binom nr. $$

不交性给出 Hamming bound：

$$ 2^k\sum_{j=0}^r\binom nj\le2^n. $$

因此

$$ 2^{n-k}\ge \binom nr. $$

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

$$ n-k \ge \log_2\binom nr \ge r\log_2\left(\frac nr\right). $$

这就是所需限制。

证明思路

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

完整证明

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

$$ \left\|\frac{r_k}{\|r_k\|_2}-x_k\right\|_2\le\varepsilon, \qquad \lambda_k=\|r_k\|_2, $$

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

$$ \|r_{k+1}\|_2 = \lambda_k \left\|\frac{r_k}{\|r_k\|_2}-x_k\right\|_2 \le \varepsilon\lambda_k. $$

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

$$ x=\sum_{k=0}^{\infty}\lambda_kx_k. $$

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

$$ \|Ax\|_2 \le \sum_{k=0}^{\infty}\lambda_k\|Ax_k\|_2 \le M\sum_{k=0}^{\infty}\varepsilon^k = \frac{M}{1-\varepsilon}. $$

对 $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 给出：

$$ \sup_{y\in\mathcal N}\langle x,y\rangle\le\|x\|_2. $$

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

$$ \|x\|_2 = \langle x,u\rangle = \langle x,y\rangle+\langle x,u-y\rangle \le \sup_{z\in\mathcal N}\langle x,z\rangle + \varepsilon\|x\|_2. $$

移项得

$$ \|x\|_2 \le \frac1{1-\varepsilon} \sup_{z\in\mathcal N}\langle x,z\rangle. $$

证明思路

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

完整证明

记

$$ M=\sup_{x\in\mathcal N,\ y\in\mathcal M}|\langle Ax,y\rangle|. $$

下界 $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$ 满足

$$ \|x-x_0\|_2\le\varepsilon, \qquad \|y-y_0\|_2\le\varepsilon. $$

则

$$ \begin{aligned} |\langle Ax,y\rangle| &\le |\langle Ax_0,y_0\rangle| + |\langle A(x-x_0),y\rangle| + |\langle Ax_0,y-y_0\rangle|\\ &\le M+2\varepsilon\|A\|. \end{aligned} $$

取上确界并整理，得到

$$ \|A\|\le\frac{M}{1-2\varepsilon}. $$

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

证明思路

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

完整证明

记

$$ \Delta=\sup_{x\in\mathcal N}\bigl|\|Ax\|_2-\mu\bigr|. $$

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

$$ \sup_{x\in S^{n-1}}\|Ax\|_2 \le \frac{1}{1-\varepsilon} \sup_{x\in\mathcal N}\|Ax\|_2 \le \frac{\Delta}{1-\varepsilon}, $$

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

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

$$ \sup_{x\in S^{n-1}}\|Ax\|_2 \le \frac{2\Delta}{1-\varepsilon}, $$

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

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

$$ B=A^{\mathsf T}A-\mu^2I_n. $$

对 $x\in\mathcal N$，

$$ |x^{\mathsf T}Bx| = \bigl|\|Ax\|_2^2-\mu^2\bigr| = \bigl|\|Ax\|_2-\mu\bigr|(\|Ax\|_2+\mu) \le \Delta(2\mu+\Delta) \le 3\mu\Delta. $$

由 Lemma 4.4.2 的对称情形，

$$ \|B\| \le \frac{3\mu\Delta}{1-2\varepsilon}. $$

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

$$ \bigl|\|Ax\|_2-\mu\bigr| = \frac{\bigl|\|Ax\|_2^2-\mu^2\bigr|}{\|Ax\|_2+\mu} \le \frac{\|B\|}{\mu} \le \frac{3\Delta}{1-2\varepsilon}. $$

合并三种情形即可得到题设不等式，其中 $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$。由

$$ \|u-z\|_2^2 = 2-2\langle u,z\rangle $$

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

$$ \sup_{w\in C}\langle u,w\rangle\ge1-\varepsilon \qquad\text{for all }u\in S^{n-1}. $$

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

$$ \langle u,y\rangle> \sup_{w\in C}\langle u,w\rangle. $$

但 $\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$，满足

$$ |\mathcal M|\le\left(\frac{CR}{\varepsilon}\right)^n. $$

对每个 $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 密度在固定半径球内的指数阶下界给出

$$ \mathbb P\{\|Z_i-y'\|_2\le\varepsilon/8\} \ge \exp[-C(R,\varepsilon)n] =:p. $$

这里可以直接验证：在球 $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 中心都被命中的失败概率至多

$$ |\mathcal M|e^{-Np}. $$

只要 $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$，

$$ \mathbb P\left\{ \|A\|>CK(\sqrt m+\sqrt n+t) \right\} \le 2e^{-t^2}. $$

由尾积分公式，

$$ \mathbb E\|A\| \le CK(\sqrt m+\sqrt n) + CK\int_0^\infty 2e^{-t^2}\,dt \le C'K(\sqrt m+\sqrt n). $$

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

$$ \left\| \frac1mA^{\mathsf T}A-I_n \right\| \le CK^2\left( \sqrt{\frac nm}+\frac{t}{\sqrt m} + \frac nm+\frac{t^2}{m} \right) $$

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

$$ \mathbb E \left\| \frac1mA^{\mathsf T}A-I_n \right\| \le CK^2\left( \sqrt{\frac nm}+\frac nm \right). $$

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

$$ \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. $$

证明思路

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

完整证明

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

$$ \|Ae_1\|_2 \ge \sqrt m-t $$

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

$$ \|A^{\mathsf T}e_1\|_2 \ge \sqrt n-t $$

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

在该事件上，

$$ \|A\| \ge \max\{\|Ae_1\|_2,\|A^{\mathsf T}e_1\|_2\} \ge \max\{\sqrt m-t,\sqrt n-t\}. $$

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

$$ \|A\| \ge \frac12(\sqrt m+\sqrt n-2t). $$

把 $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}$，

$$ \langle Ax,y\rangle = \langle A,yx^{\mathsf T}\rangle_F, \qquad \|yx^{\mathsf T}\|_F=1. $$

因此

$$ \|\langle Ax,y\rangle\|_{\psi_2} \le \|A\|_{\psi_2}. $$

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

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

$$ \langle Ax,y\rangle = \sum_{i=1}^m y_i\langle A_i,x\rangle. $$

这些项独立、均值为零，并满足 $\|\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) 由定义，

$$ \|A\|_{1\to\infty} = \max_{i,j}|A_{ij}|. $$

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

$$ \max_{i,j}|A_{ij}| \le CK\sqrt{\log(mn)} \le CK(\sqrt{\log m}+\sqrt{\log n}). $$

(b) 对任意矩阵，

$$ \|A\|_{1\to2} = \max_{j\le n}\|Ae_j\|_2, \qquad \|A^{\mathsf T}\|_{2\to\infty} = \max_{j\le n}\|Ae_j\|_2, $$

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

$$ \|Ae_j\|_2 \le \sqrt m+CK^2t $$

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

$$ \|A\|_{1\to2} \le \sqrt m+CK^2\sqrt{\log n} $$

以高概率成立。

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

$$ \max_{i,j}|A_{ij}| \ge c\sqrt{\log(mn)} \ge c'(\sqrt{\log m}+\sqrt{\log n}) $$

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

$$ \|A\|_{1\to2} = \max_j\|Ae_j\|_2 \ge \|Ae_1\|_2 \ge c\sqrt m $$

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

$$ \|A\|_{1\to2} \ge c(\sqrt m+\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$，考虑中心化矩阵

$$ \widetilde A=PAP. $$

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

$$ u=(1,\ldots,1,-1,\ldots,-1), $$

对应特征值

$$ \lambda=\frac{p-q}{2}n. $$

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

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

$$ \|\widetilde R\|\le C\sqrt n $$

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

$$ \sin\angle(\bar u,\bar v) \le \frac{C\sqrt n}{(p-q)n} = \frac{C}{(p-q)\sqrt n}, $$

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

$$ \|u-\theta\sqrt n\,\bar v\|_2 \le \frac{C}{p-q}. $$

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

$$ \frac{C}{(p-q)^2}. $$

算法就是：计算 $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 给出

$$ \mathbb P\left\{ \bigl|\|Ax\|_2-\sqrt m\bigr|>CK^2t \right\} \le 2e^{-t^2}. $$

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

$$ \sup_{x\in\mathcal N} \bigl|\|Ax\|_2-\sqrt m\bigr| \le CK^2(\sqrt n+u). $$

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

$$ \sup_{x\in S^{n-1}} \bigl|\|Ax\|_2-\sqrt m\bigr| \le CK^2(\sqrt n+u). $$

最后注意

$$ s_1(A)=\sup_{x\in S^{n-1}}\|Ax\|_2, \qquad s_n(A)=\inf_{x\in S^{n-1}}\|Ax\|_2. $$

于是得到 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}$ 的概率，

$$ s_k(A_E) \ge \sqrt m-CK^2(\sqrt k+t). $$

由 Courant-Fischer 变分刻画，

$$ s_k(A) = \max_{\dim F=k} \min_{x\in F\cap S^{n-1}}\|Ax\|_2 \ge \min_{x\in E\cap S^{n-1}}\|Ax\|_2 = s_k(A_E). $$

合并即得

$$ s_k(A) \ge \sqrt m-CK^2(\sqrt k+t). $$

证明思路

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

完整证明

设

$$ Y=\Sigma^{-1/2}X, \qquad Y_i=\Sigma^{-1/2}X_i. $$

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

$$ \frac1m\sum_{i=1}^mY_iY_i^{\mathsf T} = \Sigma^{-1/2}\Sigma_m\Sigma^{-1/2} =:\widetilde\Sigma_m. $$

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

$$ \mathbb E\|\widetilde\Sigma_m-I\| \le CK^2\left(\sqrt{\frac nm}+\frac nm\right). $$

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

$$ \frac{v^{\mathsf T}\Sigma_m v}{v^{\mathsf T}\Sigma v} = \frac{w^{\mathsf T}\widetilde\Sigma_m w}{\|w\|_2^2}. $$

因此

$$ \sup_{v\in\mathbb R^n} \left| \frac{v^{\mathsf T}\Sigma_m v}{v^{\mathsf T}\Sigma v}-1 \right| = \|\widetilde\Sigma_m-I\|. $$

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

证明思路

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}$ 的概率，

$$ \left\| \frac1m\sum_{i=1}^mY_iY_i^{\mathsf T}-I \right\| \le CK^2\left( \sqrt{\frac{n+u}{m}} + \frac{n+u}{m} \right). $$

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

$$ -\delta\Sigma \preceq \Sigma_m-\Sigma \preceq \delta\Sigma, $$

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

$$ \|\Sigma_m-\Sigma\| \le \delta\|\Sigma\|. $$

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

证明思路

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

完整证明

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

$$ \|U-V\|_{1\to2} = \max_{j\le r}\|U_{:j}-V_{:j}\|_2. $$

取单位球面 $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，数量不增加。于是

$$ \mathcal N(O_{m,r},\|\cdot\|_{1\to2},\varepsilon) \le \left(\frac C\varepsilon\right)^{mr}. $$

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

$$ A=U\operatorname{diag}(s)V^{\mathsf T}, \qquad U\in O_{m,r},\quad V\in O_{n,r},\quad \|s\|_2\le1. $$

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

$$ \|U\operatorname{diag}(s)V^{\mathsf T} - U_0\operatorname{diag}(s_0)V_0^{\mathsf T}\|_F \le \|U-U_0\|_{1\to2}\|s\|_2 + \|s-s_0\|_2 + \|V-V_0\|_{1\to2}\|s_0\|_2 \le \varepsilon. $$

三个 net 的大小相乘，得到

$$ \mathcal N(M_{m,n,r},\|\cdot\|_F,\varepsilon) \le \left(\frac C\varepsilon\right)^{mr} \left(\frac C\varepsilon\right)^{nr} \left(\frac C\varepsilon\right)^r = \left(\frac C\varepsilon\right)^{(m+n+1)r}. $$

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

$$ A=[B\ 0], \qquad B\in\mathbb R^{m\times r}, \qquad \|B\|_F\le1. $$

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

$$ N\cdot \operatorname{Vol}(\varepsilon B_2^{mr}) \ge \operatorname{Vol}(B_2^{mr}), $$

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

$$ \mathcal N(M_{m,n,r},\|\cdot\|_F,\varepsilon) \ge \left(\frac c\varepsilon\right)^{(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$ 独立且均值为零，

$$ \Sigma=\mathbb EXX^{\mathsf T} = \mu\mu^{\mathsf T}+I_n. $$

因此 top eigenvector 为

$$ u=\frac{\mu}{\|\mu\|_2}, $$

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

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

$$ \langle X,u\rangle = \theta\|\mu\|_2+\langle g,u\rangle. $$

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

$$ \theta_i\langle X_i,u\rangle = M+\theta_i\langle g_i,u\rangle. $$

因此真实方向误分类概率为 $\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$，

$$ \|\langle X,x\rangle\|_{\psi_2} \le C\left(|\langle\mu,x\rangle|+\|x\|_2\right) \le C\|\langle X,x\rangle\|_{L^2}. $$

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

$$ \|\Sigma_m-\Sigma\| \le c\|\mu\|_2^2 $$

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

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

$$ \|v-u\|_2\le \eta, $$

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

$$ \|\Sigma_m\| \le \|\Sigma\|+\|\Sigma_m-\Sigma\| \le C(1+M^2). $$

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

$$ \theta_i\langle X_i,u\rangle\ge M/2 \quad\text{且}\quad |\langle X_i,h\rangle|<M/2, $$

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

$$ \theta_i\langle X_i,v\rangle = \theta_i\langle X_i,u\rangle + \theta_i\langle X_i,h\rangle > 0. $$

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

$$ \#\{i:|\langle X_i,h\rangle|\ge M/2\} \le \frac{4}{M^2} \sum_{i=1}^m\langle X_i,h\rangle^2 = \frac{4m}{M^2}h^{\mathsf T}\Sigma_m h. $$

在 (d) 的好事件上，

$$ h^{\mathsf T}\Sigma_m h \le \|\Sigma_m\|\|h\|_2^2 \le C(1+M^2)\eta^2. $$

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