翻译状态说明

本页为第 6 章的精校翻译，覆盖正文、Notes 与 Exercises 6.1-6.38。第 6 章原文没有正式 Figure；OCR 目录中的图片主要是公式切图，因此不迁移为阅读图像。正文中的明确证明、跳步验证与习题均已加入学习笔记证明跳转。

第 6 章 二次型、对称化与收缩

本章介绍高维概率中的几种基本工具：第 6.1 节的 decoupling，第 6.2 节的二次型集中，也就是 Hanson-Wright 不等式，第 6.3 节的 symmetrization，以及第 6.6 节的 contraction。

这些工具会通过几个应用展示出来。第 6.4 节和 Exercise 6.28 说明：随机矩阵的算子范数本质上可以由行、列的最大 Euclidean 范数控制，至多损失一个对数因子。第 6.5 节再把这个结论用于 matrix completion，也就是从随机观测到的部分矩阵元素恢复低秩矩阵。

习题部分还会继续展开很多主题：次高斯随机向量的范数界、Hanson-Wright 的向量版本、均值估计、各向异性范数集中、子空间距离、图割、赋范空间的 type、$\ell^p$ 版近似 Caratheodory 定理，以及无有界性分布下的协方差估计。

6.1 Decoupling

第 2 章研究的是独立随机变量的线性和，例如

$$ \sum_{i=1}^n a_iX_i. \tag{6.1} $$

现在考虑二次型

$$ \sum_{i,j=1}^n a_{ij}X_iX_j =X^{\mathsf T}AX =\langle X,AX\rangle, \tag{6.2} $$

其中 $A=(a_{ij})$ 是 $n\times n$ 系数矩阵，$X=(X_1,\dots,X_n)$ 的坐标独立。这类二次型也称为 chaos。

如果 $X_i$ 均值为 $0$、方差为 $1$，期望很容易计算：

$$ \mathbb E X^{\mathsf T}AX =\sum_{i,j=1}^n a_{ij}\mathbb EX_iX_j =\sum_{i=1}^n a_{ii} =\operatorname{tr}A. $$

难点在集中性：式 (6.2) 中的求和项彼此不独立。decoupling 的目标就是把二次型替换成双线性型

$$ \sum_{i,j=1}^n a_{ij}X_iX'_j =X^{\mathsf T}AX' =\langle X,AX'\rangle, $$

其中 $X'$ 是 $X$ 的独立副本。双线性型比二次型好处理，因为条件化 $X'$ 后，它变成关于 $X_i$ 的独立和：

$$ \sum_{i=1}^n \Bigl(\sum_{j=1}^n a_{ij}X'_j\Bigr)X_i. $$

证明思想如下：先随机选择一个指标子集 $I\subset[n]$，把完整 chaos 替换成跨越 $I\times I^c$ 的“部分 chaos”

$$ \sum_{(i,j)\in I\times I^c}a_{ij}X_iX_j. $$

这样 $i$ 和 $j$ 落在互不相交的指标集合里，因此可以把右侧的 $X_j$ 替换成独立副本 $X'_j$ 而不改变分布。最后用 Jensen 不等式把部分和补成完整的双线性型。

证明的核心步骤是：令 $\delta_1,\dots,\delta_n$ 为独立 Bernoulli selectors，且 $\mathbb P\{\delta_i=1\}=1/2$，令 $I=\{i:\delta_i=1\}$。因为 $a_{ii}=0$，且对 $i\ne j$ 有

$$ \mathbb E_\delta \delta_i(1-\delta_j)=\frac14, $$

所以

$$ X^{\mathsf T}AX =4\mathbb E_I \sum_{(i,j)\in I\times I^c}a_{ij}X_iX_j. $$

对两边作用凸函数 $F$，再对 $X$ 取期望，由 Jensen 和 Fubini 得到存在一个确定的 $I$，使得

$$ \mathbb EF(X^{\mathsf T}AX) \le \mathbb EF\Bigl( 4\sum_{(i,j)\in I\times I^c}a_{ij}X_iX_j \Bigr). $$

固定这个 $I$。因为 $(X_i)_{i\in I}$ 与 $(X_j)_{j\in I^c}$ 独立，右侧中的 $X_j$ 可以替换为 $X'_j$。最后把

$$ \sum_{i,j}a_{ij}X_iX'_j=Y+Z $$

分解为目标部分 $Y=\sum_{(i,j)\in I\times I^c}a_{ij}X_iX'_j$ 和余项 $Z$。条件化固定 $Y$ 的随机变量后，余项满足 $\mathbb E'Z=0$，因此

$$ F(4Y)=F\bigl(\mathbb E'(4Y+4Z)\bigr) \le \mathbb E'F(4Y+4Z). $$

再取总期望即得到 (6.3)。

查看学习笔记：为什么补全和时余项条件期望为 0

6.2 Hanson-Wright 不等式

先问一个热身问题：如果 $X$ 是 $\mathbb R^n$ 中的次高斯随机向量，我们能如何控制 $\|X\|_2$？如果 $X$ 的坐标独立，第 3 章已经给出范数集中；但一般情形下，范数未必在均值附近集中。尽管如此，它不能过大。

证明使用 Gaussian replacement：把 $\exp(c^2\|X\|_2^2)$ 写成关于标准高斯向量 $g$ 的条件 MGF，再利用 $\langle X,g\rangle$ 的次高斯性将其控制为 $\exp(\|g\|_2^2/4)$，最后计算 $\chi^2$ 型 MGF。

查看学习笔记：Gaussian replacement 在范数证明中的细节

现在进入 Hanson-Wright 不等式，它是 Bernstein 不等式的二次型版本。

证明路线分三步：先用 decoupling 把 $X^{\mathsf T}AX$ 替换成 $X^{\mathsf T}AX'$；再用 Gaussian replacement 把 $X,X'$ 替换成高斯向量 $g,g'$；最后利用高斯旋转不变性和奇异值分解计算 $g^{\mathsf T}Ag'$ 的 MGF。

在 Hanson-Wright 的证明中，先把二次型偏差拆成对角部分与非对角部分：

$$ X^{\mathsf T}AX-\mathbb E X^{\mathsf T}AX = \sum_i a_{ii}(X_i^2-\mathbb E X_i^2) + \sum_{i,j:i\ne j}a_{ij}X_iX_j. $$

对角部分由 Bernstein 不等式控制；非对角部分由 decoupling、Gaussian replacement 与 Lemma 6.2.4 的 MGF 界控制。最后优化 $\lambda$ 得到

$$ \exp\left[ -c\min\left( \frac{t^2}{\|A\|_F^2}, \frac{t}{\|A\|} \right) \right]. $$

查看学习笔记：为什么可先设 $K=1$ 查看学习笔记：为什么下尾可用 $-A$ 处理 查看学习笔记：优化 $\lambda$ 的细节

6.3 Symmetrization

如果随机变量 $X$ 与 $-X$ 同分布，则称 $X$ 是 symmetric。Rademacher 随机变量和均值为 $0$ 的正态变量都是 symmetric，而 Poisson 或 exponential 随机变量不是。

Symmetrization 的用途是把一般随机变量归约到对称分布，甚至归约到 Rademacher 随机符号。

证明中的基本事实是：如果 $Y,Z$ 是独立随机向量且 $\mathbb EZ=0$，那么

$$ \mathbb E\|Y\|\le \mathbb E\|Y+Z\|. \tag{6.13} $$

查看学习笔记：式 (6.13) 的 Jensen 证明

读完证明后应检查两个问题：$X_i$ 的独立性在哪里使用？均值为 $0$ 是否在上下界中都需要？

查看学习笔记：独立性和零均值的使用位置

6.4 非 i.i.d. 随机矩阵

对称化的典型用法分两步：先把随机变量 $X_i$ 替换为 symmetric 的 $\varepsilon_iX_i$；再条件化 $X_i$，使所有随机性都来自 Rademacher 符号。下面用它控制独立但非同分布矩阵元素形成的随机矩阵范数。

下界来自 $\|A_i\|_2\le\|A\|$。上界先把矩阵分解为独立均值零矩阵

$$ A=\sum_{i\le j}Z_{ij}, $$

然后对称化：

$$ \mathbb E\|A\| \le 2\mathbb E\left\|\sum_{i\le j}\varepsilon_{ij}Z_{ij}\right\|. \tag{6.14} $$

条件化 $Z_{ij}$ 后用矩阵 Khintchine 不等式，得到

$$ \mathbb E\left\|\sum_{i\le j}\varepsilon_{ij}Z_{ij}\right\| \le C\sqrt{\log n}\, \mathbb E\left\|\sum_{i\le j}Z_{ij}^2\right\|^{1/2}. \tag{6.15} $$

直接计算可得 $\sum_{i\le j}Z_{ij}^2$ 是对角矩阵，其第 $i$ 个对角元为 $\|A_i\|_2^2$，于是结论成立。

查看学习笔记：$Z_{ij}^2$ 为什么给出行范数

6.5 应用：矩阵补全

Matrix completion 的目标是从随机观测到的部分条目恢复一个矩阵。若没有额外结构，这是不可能的；本节假设矩阵低秩，并说明低秩结构足以产生一个可计算的恢复算法。

设 $X$ 是 $n\times n$ 矩阵，$\operatorname{rank}(X)=r\ll n$。每个元素 $X_{ij}$ 以概率 $p$ 被独立观测。观测矩阵为

$$ Y_{ij}=\delta_{ij}X_{ij}, \qquad \delta_{ij}\sim\operatorname{Ber}(p). $$

若

$$ p=\frac{m}{n^2}, \tag{6.16} $$

则平均观测 $m$ 个元素。虽然 $X$ 低秩，$Y$ 未必低秩；因此我们取 $p^{-1}Y$ 的最佳 rank $r$ 近似。

查看学习笔记：为什么 $Y$ 未必低秩

证明先控制算子范数误差：

$$ \|\widehat X-X\| \le 2\|p^{-1}Y-X\| =\frac2p\|Y-pX\|. \tag{6.17} $$

矩阵 $Y-pX$ 的元素独立、均值为 $0$，应用 Theorem 6.4.1 的矩形版本可得

$$ \mathbb E\|Y-pX\| \lesssim \sqrt{pn\log n}\,\|X\|_\infty. $$

然后用低秩把算子范数误差转成 Frobenius 误差：因为 $\operatorname{rank}(\widehat X-X)\le2r$，

$$ \|\widehat X-X\|_F \le \sqrt{2r}\,\|\widehat X-X\|. $$

最后代入 $pn^2=m$ 得到定理。

查看学习笔记：最佳 rank $r$ 近似如何推出 (6.17) 查看学习笔记：行列最大范数估计

6.6 收缩原理

本章最后介绍一个常用的不等式。

证明可先归一化到 $\|a\|_\infty\le1$，然后定义

$$ f(a)=\mathbb E\left\|\sum_{i=1}^N a_i\varepsilon_i x_i\right\|. \tag{6.20} $$

函数 $f:\mathbb R^N\to\mathbb R$ 是凸函数。最大原则说明，凸函数在 cube $[-1,1]^N$ 上的最大值可在顶点取得；而顶点处 $a_i=\pm1$，符号 $a_i\varepsilon_i$ 与 $\varepsilon_i$ 同分布，所以得到收缩结论。

查看学习笔记：为什么 $f$ 是凸函数 查看学习笔记：为什么可先设 $\|a\|_\infty\le1$

上界用 Rademacher symmetrization 后，把 $\varepsilon_i$ 替换为 $\varepsilon_i|g_i|$；下界用 contraction principle，并使用 $\mathbb E\|g\|_\infty\le C\sqrt{\log N}$。

6.7 Notes

Theorem 6.1.1 的 decoupling inequality 最初由 Bourgain 和 Tzafriri 证明。Hanson-Wright 不等式的现代版本与本节证明来自 Rudelson 与 Vershynin 的工作，早期特殊情形包括 Bernoulli、高斯和无对角矩阵。

Exercise 6.13 的各向异性随机向量集中与 Exercise 6.14 的子空间距离界来自 Hanson-Wright 技术。Symmetrization Lemma 6.3.2 是经验过程和随机矩阵理论中的标准工具。

Theorem 6.4.1 中的 $\sqrt{\log n}$ 可由更精细的 Seginer 型结果改进为 $\log^{1/4}n$，并且 Exercise 6.29 表明不能完全删除对数损失。对于 i.i.d. 元素或高斯矩阵等特殊类别，这个对数损失可以进一步消失。

Theorem 6.5.1 的 matrix completion 证明来自相关矩阵补全文献。后续研究说明，在额外 incoherence 假设下，可以用约 $rn\log^2 n$ 个随机观测实现无噪声精确恢复。

Contraction principle 可见 Ledoux-Talagrand 体系；Gaussian symmetrization 的对数因子在一般赋范空间中必要，但在具有非平凡 cotype 的空间中可以改进。

Exercises