第 6 章精校翻译：二次型、对称化与收缩
第 6 章二次型、对称化与收缩
本章介绍高维概率中的几种基本工具：第 6.1 节的解耦，第 6.2 节的二次型集中，也就是 Hanson-Wright 不等式，第 6.3 节的对称化，以及第 6.6 节的收缩。
我们用几个应用来说明这些工具。第 6.4 节（以及 习题 6.28）说明，随机矩阵的算子范数本质上等价于其行和列的最大欧氏范数。第 6.5 节把这个结果用于矩阵补全，也就是从矩阵条目的随机样本中恢复一个低秩矩阵。
习题中还会探索更多主题。你会界定次高斯随机向量的范数（习题 6.10），并把它用于推出次高斯随机向量的 Hanson-Wright 不等式（习题 6.11）以及次高斯分布的均值估计（习题 6.12）；把范数集中（定理 3.1.1）推广到各向异性随机向量（习题 6.13），并应用于随机向量到子空间的距离（习题 6.14）和图割（习题 6.15）；探索赋范空间的型（type）概念（习题 6.23、6.24），并用它把近似 Caratheodory 定理（定理 0.0.2）推广到 $\ell^p$ 范数；还会把协方差估计推广到无界分布（习题 6.34）。
6.1 解耦
第 2 章研究的是独立随机变量的线性和，例如
$$ \sum_{i=1}^n a_iX_i. \tag{6.1} $$
这里 $X_1,\ldots,X_n$ 是独立随机变量，$a_i$ 是固定系数。现在考虑二次型
$$ \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) 中的求和项彼此不独立。我们可以用解耦技巧克服这个困难；现在介绍这个技巧。
解耦的目标就是把二次型 (6.2) 替换成双线性型
$$ \sum_{i,j=1}^n a_{ij}X_iX'_j =X^{\mathsf T}AX' =\langle X,AX'\rangle, $$
其中 $X'=(X_1',\ldots,X_n')$ 是 $X$ 的独立副本，也就是一个与 $X$ 独立、并且与 $X$ 同分布的随机向量。双线性型比二次型好处理，因为它关于 $X$ 是线性的。若条件化在 $X'$ 上，就可以把双线性型看成独立随机变量之和：
$$ \sum_{i=1}^n \Bigl(\sum_{j=1}^n a_{ij}X'_j\Bigr)X_i =\sum_{i=1}^n b_iX_i. $$
这里 $b_i$ 是固定系数，处理方式就和前面的和 (6.1) 很相似。
设 $A$ 是一个 $n\times n$ 的无对角矩阵。设 $X\in\mathbb R^n$ 的坐标独立且均值为 $0$，设 $X'$ 是 $X$ 的独立副本。那么，对任意凸函数 $F:\mathbb R\to\mathbb R$，都有
$$ \mathbb EF(X^{\mathsf T}AX) \le \mathbb EF(4X^{\mathsf T}AX'). \tag{6.3} $$ 查看学习笔记：定理 6.1.1 完整证明先随机选择一个指标子集 $I\subset[n]$，把完整 chaos $X^{\mathsf T}AX=\sum_{i,j}a_{ij}X_iX_j$ 替换成 “partial chaos”
$$ \sum_{(i,j)\in I\times I^c}a_{ij}X_iX_j. $$这样 $i$ 和 $j$ 落在互不相交的指标集合里，因此可以把右侧的 $X_j$ 替换成独立副本 $X'_j$ 而不改变分布。最后用 Jensen 不等式把这个部分 chaos 扩展回完整和 $X^{\mathsf T}AX'=\sum_{i,j}a_{ij}X_iX'_j$。现在进入详细证明。
步骤 1：随机选择部分和。 为了指定随机指标集 $I$，引入选择变量，即独立 Bernoulli 随机变量 $\delta_1,\ldots,\delta_n\in\{0,1\}$，满足 $\mathbb P\{\delta_i=0\}=\mathbb P\{\delta_i=1\}=1/2$，并定义
$$ I:=\{i:\delta_i=1\}. $$条件化在 $X$ 上。由于假设 $a_{ii}=0$，且对所有 $i\ne j$ 有
$$ \mathbb E_\delta \delta_i(1-\delta_j)=\frac14, $$所以可把 chaos 表示为
$$ X^{\mathsf T}AX = \sum_{i\ne j}a_{ij}X_iX_j = 4\mathbb E_\delta\sum_{i\ne j}\delta_i(1-\delta_j)a_{ij}X_iX_j = 4\mathbb E_I \sum_{(i,j)\in I\times I^c}a_{ij}X_iX_j. $$下标 $\delta$ 和 $I$ 表示条件期望中的随机来源：由于 $X$ 固定，期望只对随机选择变量 $\delta=(\delta_1,\ldots,\delta_n)$ 或等价的随机指标集 $I$ 取。后面还会继续使用这种记号。
步骤 2：作用 $F$. 对两边作用 $F$，再对 $X$ 取期望。由 Jensen 不等式和 Fubini 定理，
$$ \mathbb E_XF(X^{\mathsf T}AX) \le \mathbb E_I\mathbb E_X F\left( 4\sum_{(i,j)\in I\times I^c}a_{ij}X_iX_j \right). $$于是存在某个确定的 $I$，使得
$$ \mathbb E_XF(X^{\mathsf T}AX) \le \mathbb E_XF\left( 4\sum_{(i,j)\in I\times I^c}a_{ij}X_iX_j \right). $$从现在到证明结束固定这个 $I$，并为简洁起见省略期望下标 $X$。由于 $(X_i)_{i\in I}$ 与 $(X_j)_{j\in I^c}$ 独立，右侧和的分布不会因为把 $X_j$ 替换成 $X'_j$ 而改变。因此
$$ \mathbb EF(X^{\mathsf T}AX) \le \mathbb EF\left( 4\sum_{(i,j)\in I\times I^c}a_{ij}X_iX'_j \right). $$步骤 3：补全部分和. 还需要把右侧的部分和补成所有指标对上的和。我们要证明
$$ \mathbb EF\left( 4\sum_{(i,j)\in I\times I^c}a_{ij}X_iX'_j \right) \le \mathbb EF\left( 4\sum_{(i,j)\in[n]\times[n]}a_{ij}X_iX'_j \right), \tag{6.4} $$其中 $[n]=\{1,\ldots,n\}$。为此，把完整和分解为
$$ \sum_{(i,j)\in[n]\times[n]}a_{ij}X_iX'_j = \underbrace{\sum_{(i,j)\in I\times I^c}a_{ij}X_iX'_j}_{Y} + \underbrace{ \sum_{(i,j)\in I\times I}a_{ij}X_iX'_j + \sum_{(i,j)\in I^c\times[n]}a_{ij}X_iX'_j }_{Z}. $$条件化在所有 $(X_i)_{i\in I}$ 与 $(X_j')_{j\in I^c}$ 上，并把这个条件期望记为 $\mathbb E'$。这会固定 $Y$，而 $Z$ 的条件期望为零（请检查）。因此由 Jensen 不等式，
$$ F(4Y) = F(4Y+\mathbb E'[4Z]) = F(\mathbb E'[4Y+4Z]) \le \mathbb E'F(4Y+4Z). $$最后，对剩余随机变量取期望，得到
$$ \mathbb EF(4Y)\le \mathbb EF(4Y+4Z). $$这证明了 (6.4)，也完成了整个论证。
查看学习笔记：为什么补全和时余项条件期望为 0定理 6.1.1 中的无对角假设是必要的。若 $A$ 是对角矩阵且 $F(x)=x$，结论会失败。
查看学习笔记：为什么对角项不能直接解耦不过，可以把对角项放入右侧：对任意矩阵 $A=(a_{ij})$，有
$$ \mathbb EF\Bigl(\sum_{i,j:i\ne j}a_{ij}X_iX_j\Bigr) \le \mathbb EF\Bigl(4\sum_{i,j}a_{ij}X_iX'_j\Bigr). \tag{6.5} $$ 查看学习笔记：习题 6.1在 习题 6.1 中验证这一点，并在 习题 6.2-6.4 中探索解耦的其他变体。
6.2 Hanson-Wright 不等式
先问一个热身问题：如果 $X$ 是 $\mathbb R^n$ 中的次高斯随机向量，我们能如何控制 $\|X\|_2$？如果 $X$ 的坐标独立，第 3 章已经给出范数集中；但一般情形下，范数未必在均值附近集中，甚至可能以很高概率过小（习题 3.37）。尽管如此，它不能过大。
设 $X$ 是 $\mathbb R^n$ 中均值为 $0$ 的次高斯随机向量，且 $\|X\|_{\psi_2}\le K$。那么，对所有 $t\ge0$，
$$ \mathbb P\{\|X\|_2\ge CK(\sqrt n+t)\}\le e^{-t^2}. $$ 查看学习笔记：命题 6.2.1 完整证明不失一般性，设 $K=1$。把两边平方、指数化，并使用 Markov 不等式，得到
$$ \mathbb P\{c\|X\|_2\ge \sqrt n+t\} \le e^{-(n+t^2)} \mathbb E\exp(c^2\|X\|_2^2). \tag{6.6} $$现在使用高斯替换技巧：对某个绝对常数 $c\gt 0$，我们声称
$$ \mathbb E\exp(c^2\|X\|_2^2) \le \mathbb E\exp(\|g\|_2^2/4), \qquad g\sim N(0,I_n). \tag{6.7} $$为证明这一点，先条件化在 $X$ 上，把它视为固定向量。由 推论 3.3.2，$\langle g,X\rangle\sim N(0,\|X\|_2^2)$，因此
$$ \exp(c^2\|X\|_2^2) = \mathbb E_g\exp(\sqrt2\,c\langle g,X\rangle), $$其中 $\mathbb E_g$ 表示在给定 $X$ 后对 $g$ 的条件期望。对两边再对 $X$ 取期望，并使用 Fubini，得到
$$ \mathbb E_X\exp(c^2\|X\|_2^2) = \mathbb E_X\mathbb E_g\exp(\sqrt2\,c\langle g,X\rangle) = \mathbb E_g\mathbb E_X\exp(\sqrt2\,c\langle X,g\rangle). \tag{6.8} $$当条件化在 $g$ 上时，$\langle X,g\rangle$ 的次高斯范数至多为 $\|g\|_2$，因为假设 $\|X\|_{\psi_2}=1$。于是 命题 2.6.6(iv) 给出，对某个绝对常数 $c\gt 0$，
$$ \mathbb E_X\exp(\sqrt2\,c\langle X,g\rangle) \le \exp(\|g\|_2^2/4). $$把它代入 (6.8)，就证明了 (6.7)。
最后，由于 $\|g\|_2^2=g_1^2+\cdots+g_n^2$，其中 $g_i\sim N(0,1)$ i.i.d.，所以
$$ \mathbb E_g\exp(\|g\|_2^2/4) = \left(\mathbb E\exp(g_1^2/4)\right)^n = (\sqrt2)^n \le e^n. $$把这个界代入 (6.7) 和 (6.6)，即可完成证明。
为了练习高斯替换，可以在习题 6.9 和 6.10 中证明命题 6.2.1 的各向异性版本。
刚刚学到的高斯替换技巧会在证明混沌的集中时派上用场；Hanson-Wright 不等式可以看作 Bernstein 不等式的二次型版本。
设 $A$ 是 $n\times n$ 矩阵，设 $X=(X_1,\dots,X_n)\in\mathbb R^n$ 的坐标独立、均值为 $0$ 且次高斯。那么，对所有 $t\ge0$，
$$ \mathbb P\{|X^{\mathsf T}AX-\mathbb E X^{\mathsf T}AX|\ge t\} \le 2\exp\left[ -c\min\left( \frac{t^2}{K^4\|A\|_F^2}, \frac{t}{K^2\|A\|} \right) \right], $$其中 $K=\max_i\|X_i\|_{\psi_2}$。
查看学习笔记：定理 6.2.2 完整证明证明将基于控制 $X^{\mathsf T}AX$ 的 MGF。计划如下：
(a) 通过解耦，把 $X^{\mathsf T}AX$ 替换为 $X^{\mathsf T}AX'$；
(b) 通过高斯替换，把 $X^{\mathsf T}AX'$ 替换为 $g^{\mathsf T}Ag'$，其中 $g\sim N(0,I_n)$；
(c) 利用 $N(0,I_n)$ 的旋转不变性，对 $A$ 对角化，并计算 $g^{\mathsf T}Ag'$。
先从步骤 (b) 开始。这是 命题 6.2.1 证明中高斯替换的一个版本。读者也可以先不看证明，尝试自己证明。
设 $A$ 是 $n\times n$ 矩阵。设 $X$ 是均值为 $0$ 的次高斯随机向量，$\|X\|_{\psi_2}\le K$，$X'$ 是其独立副本。设 $g,g'\sim N(0,I_n)$ 独立。那么，对任意 $\lambda\in\mathbb R$，
$$ \mathbb E\exp(\lambda X^{\mathsf T}AX') \le \mathbb E\exp(CK^2\lambda g^{\mathsf T}Ag'). $$ 查看学习笔记：引理 6.2.3 完整证明条件化在 $X'$ 上，并对 $X$ 取期望，记为 $\mathbb E_X$。此时
$$ X^{\mathsf T}AX'=\langle X,AX'\rangle $$在条件意义下是次高斯，其次高斯范数至多为 $K\|AX'\|_2$。由 命题 2.6.6(iv)，对所有 $\lambda\in\mathbb R$，有
$$ \mathbb E_X\exp(\lambda X^{\mathsf T}AX') \le \exp(C\lambda^2K^2\|AX'\|_2^2). \tag{6.9} $$把它与正态 MGF 公式 (2.16) 比较。对正态随机变量
$$ g^{\mathsf T}AX'=\langle g,AX'\rangle $$使用该公式（仍然条件化在 $X'$ 上），得到
$$ \mathbb E_g\exp(\mu g^{\mathsf T}AX') = \exp(\mu^2\|AX'\|_2^2/2), \qquad \mu\in\mathbb R. \tag{6.10} $$令 $\mu=\sqrt{2C}K\lambda$，便匹配了 (6.9) 与 (6.10) 的右端，因此
$$ \mathbb E_X\exp(\lambda X^{\mathsf T}AX') \le \mathbb E_g\exp(\sqrt{2C}K\lambda\, g^{\mathsf T}AX'). $$对两边再对 $X'$ 取期望，我们就把 chaos 中的 $X$ 替换成了 $g$，代价是多出因子 $\sqrt{2C}K$。对 $X'$ 重复同样论证，就可以把它替换为 $g'$，再付出一个因子 $\sqrt{2C}K$，从而得到所需的 $CK^2$ 因子。读者也可以自己把这一步完整写出。
查看学习笔记：为什么可以对 $X'$ 再重复一次高斯替换现在进入计划中的步骤 (c)。
设 $A$ 是 $n\times n$ 矩阵，$g,g'\sim N(0,I_n)$ 独立。那么只要 $|\lambda|\le 1/(2\|A\|)$，就有
$$ \mathbb E\exp(\lambda g^{\mathsf T}Ag') \le \exp(\lambda^2\|A\|_F^2). $$ 查看学习笔记：引理 6.2.4 完整证明用正态分布的旋转不变性来对角化 $A$。设 $A=U\Sigma V^{\mathsf T}$ 是奇异值分解 (4.4)，则
$$ g^{\mathsf T}Ag' = (U^{\mathsf T}g)^{\mathsf T}\Sigma(V^{\mathsf T}g'). $$由 命题 3.3.1，$U^{\mathsf T}g$ 与 $V^{\mathsf T}g'$ 仍是独立的标准正态随机向量。因此
$$ g^{\mathsf T}Ag' \overset{\mathrm{dist}}{=} g^{\mathsf T}\Sigma g' = \sum_{i=1}^n s_i g_i g_i', $$这里 $\overset{\mathrm{dist}}{=}$ 表示同分布，$s_i$ 是 $A$ 的奇异值。右侧是独立随机变量之和，所以
$$ \mathbb E\exp(\lambda g^{\mathsf T}Ag') = \mathbb E\prod_i\exp(\lambda s_i g_i g_i') = \prod_i\mathbb E\exp(\lambda s_i g_i g_i'). \tag{6.11} $$现在，对每个 $i$ 和 $t\in\mathbb R$，先条件化在 $g_i$ 上，并对 $g_i'$ 使用正态 MGF 公式 (2.16)，可得
$$ \mathbb E\exp(tg_i g_i') = \mathbb E\exp(t^2g_i^2/2) = \frac1{\sqrt{1-t^2}} \le \exp(t^2), \qquad t^2\le\frac12. $$第一个等号来自条件化 $g_i$ 后对正态变量 $g_i'$ 使用 MGF 公式；其余步骤是直接计算（请检查）。把这个界以 $t=\lambda s_i$ 代入 (6.11)，得到
$$ \mathbb E\exp(\lambda g^{\mathsf T}Ag') \le \exp\left(\lambda^2\sum_i s_i^2\right), \qquad \lambda^2\le\frac1{2\max_i s_i^2}. $$由于 $s_i$ 是 $A$ 的奇异值，$\sum_i s_i^2=\|A\|_F^2$，且 $\max_i s_i=\|A\|$（回忆 引理 4.1.11），引理得证。
查看学习笔记：乘积高斯 MGF 的计算细节不失一般性，设 $K=1$（为什么可以这样？）。照常，只需控制单侧上尾
$$ p:=\mathbb P\{X^{\mathsf T}AX-\mathbb EX^{\mathsf T}AX\ge t\}. $$一旦上尾有界，下尾也可通过把 $A$ 替换为 $-A$ 得到同类界；合并两侧尾部即可完成证明。
用 $A=(a_{ij})_{i,j=1}^n$ 的元素表示，有
$$ X^{\mathsf T}AX = \sum_{i,j}a_{ij}X_iX_j, \qquad \mathbb EX^{\mathsf T}AX = \sum_i a_{ii}\mathbb EX_i^2, $$这里用了均值为零假设和独立性。因此
$$ X^{\mathsf T}AX-\mathbb EX^{\mathsf T}AX = \sum_i a_{ii}(X_i^2-\mathbb EX_i^2) + \sum_{i,j:i\ne j}a_{ij}X_iX_j. $$于是问题归约为估计对角和与非对角和：
$$ \begin{aligned} p &\le \mathbb P\left\{ \sum_i a_{ii}(X_i^2-\mathbb EX_i^2)\ge t/2 \right\}\\ &\quad+ \mathbb P\left\{ \sum_{i,j:i\ne j}a_{ij}X_iX_j\ge t/2 \right\} =:p_1+p_2. \end{aligned} $$步骤 1：对角和. 由于 $X_i$ 独立且次高斯，随机变量 $X_i^2-\mathbb EX_i^2$ 独立、均值为零且次指数，并且由中心化性质 (2.26) 与 引理 2.8.5，
$$ \|X_i^2-\mathbb EX_i^2\|_{\psi_1} \lesssim \|X_i^2\|_{\psi_1} \lesssim \|X_i\|_{\psi_2}^2 \lesssim 1. $$由 Bernstein 不等式（推论 2.9.2），
$$ p_1 \le \exp\left[ -c\min\left( \frac{t^2}{\sum_i a_{ii}^2}, \frac{t}{\max_i|a_{ii}|} \right) \right] \le \exp\left[ -c\min\left( \frac{t^2}{\|A\|_F^2}, \frac{t}{\|A\|} \right) \right]. $$步骤 2：非对角和. 令
$$ S:=\sum_{i,j:i\ne j}a_{ij}X_iX_j. $$取稍后优化的参数 $\lambda\gt 0$。由 Markov 不等式，
$$ p_2 = \mathbb P\{S\ge t/2\} = \mathbb P\{\lambda S\ge \lambda t/2\} \le \exp(-\lambda t/2)\mathbb E\exp(\lambda S). \tag{6.12} $$另一方面，
$$ \begin{aligned} \mathbb E\exp(\lambda S) &\le \mathbb E\exp(4\lambda X^{\mathsf T}AX') &&\text{由解耦 (6.5)}\\ &\le \mathbb E\exp(C_1\lambda g^{\mathsf T}Ag') &&\text{由 引理 6.2.3}\\ &\le \exp(C\lambda^2\|A\|_F^2) &&\text{由 引理 6.2.4}, \end{aligned} $$只要 $|\lambda|\le1/(2\|A\|)$。代入 (6.12)，得到
$$ p_2 \le \exp\left(-\lambda t/2+C\lambda^2\|A\|_F^2\right). $$对 $0\le\lambda\le1/(2\|A\|)$ 优化，得到
$$ p_2 \le \exp\left[ -c\min\left( \frac{t^2}{\|A\|_F^2}, \frac{t}{\|A\|} \right) \right]. $$综上，我们分别得到了对角偏差 $p_1$ 与非对角偏差 $p_2$ 的所需界。把二者合并，再恢复一般 $K$，即可完成 定理 6.2.2 的证明。
查看学习笔记：为什么可先设 $K=1$ 查看学习笔记：为什么下尾可用 $-A$ 处理 查看学习笔记：优化 $\lambda$ 的细节请熟练掌握这些技术：习题 6.7 要求为高斯分布找一个 Hanson-Wright 的直接证明；习题 6.8 处理 $X_i$ 是随机向量的版本；习题 6.11 处理相依元素的版本；习题 6.12 将它用于均值估计；习题 6.13 推导各向异性分布的范数集中；习题 6.14 处理随机向量到子空间的距离；习题 6.15 处理图割。
6.3 对称化
如果随机变量 $X$ 与 $-X$ 同分布，则称 $X$ 是对称。Rademacher 随机变量和均值为 $0$ 的正态变量都是对称，而 Poisson 或指数随机变量不是。
本节介绍对称化：这是一个有用技巧，可以把问题归约到对称分布，有时甚至归约到 Rademacher 分布。它基于下面这个简单观察。
设 $X$ 是随机变量，$\xi$ 是与 $X$ 独立的 Rademacher 随机变量。
(a) $\xi X$ 与 $\xi|X|$ 同分布，并且都是对称。
(b) 如果 $X$ 对称，那么 $\xi X$ 与 $\xi|X|$ 都和 $X$ 同分布。
(c) 如果 $X'$ 是 $X$ 的独立副本，那么 $X-X'$ 对称。
查看学习笔记：引理 6.3.1 完整证明这里只检查 $\xi X$ 是对称；其余部分留到 习题 6.16。对任意区间 $A\subset\mathbb R$，由全概率公式 (1.17)，
$$ \begin{aligned} \mathbb P\{\xi X\in A\} &= \mathbb P\{\xi X\in A\mid \xi=1\}\cdot\frac12 + \mathbb P\{\xi X\in A\mid \xi=-1\}\cdot\frac12\\ &= \frac12\left(\mathbb P\{X\in A\} + \mathbb P\{-X\in A\}\right). \end{aligned} $$对 $-\xi X$ 做同样计算会得到同一个结果（请检查）。因此 $\xi X$ 与 $-\xi X$ 有相同的 CDF，也就是有相同分布。
查看学习笔记：引理 6.3.1 其余部分的完整验证作为练习，可以尝试把 Bernoulli 和指数等分布改造成对称版本；见 习题 6.17。
设 $X_1,\dots,X_N$ 是赋范空间中的独立、均值为 $0$ 的随机向量，$\varepsilon_1,\dots,\varepsilon_N$ 是独立 Rademacher 随机变量。那么
$$ \frac12\mathbb E\left\|\sum_{i=1}^N\varepsilon_iX_i\right\| \le \mathbb E\left\|\sum_{i=1}^N X_i\right\| \le 2\mathbb E\left\|\sum_{i=1}^N\varepsilon_iX_i\right\|. $$ 查看学习笔记：引理 6.3.2 完整证明这个引理让我们可以把一般随机变量 $X_i$ 替换为对称变量 $\varepsilon_iX_i$。
上界. 令 $(X_i')$ 是 $(X_i)$ 的独立副本。因为 $\sum_iX_i'$ 均值为零，有
$$ p:= \mathbb E\left\|\sum_iX_i\right\| \le \mathbb E\left\|\sum_iX_i-\sum_iX_i'\right\| = \mathbb E\left\|\sum_i(X_i-X_i')\right\|. $$上面的不等式来自如下事实：若随机向量 $Y,Z$ 独立且 $\mathbb EZ=0$，则
$$ \mathbb E\|Y\|\le \mathbb E\|Y+Z\|. \tag{6.13} $$接着，由于 $X_i-X_i'$ 是对称随机向量，它们与 $\varepsilon_i(X_i-X_i')$ 同分布（习题 6.16(b)）。因此
$$ \begin{aligned} p &\le \mathbb E\left\|\sum_i\varepsilon_i(X_i-X_i')\right\|\\ &\le \mathbb E\left\|\sum_i\varepsilon_iX_i\right\| + \mathbb E\left\|\sum_i\varepsilon_iX_i'\right\| \qquad\text{由三角不等式}\\ &= 2\mathbb E\left\|\sum_i\varepsilon_iX_i\right\|, \end{aligned} $$最后一步用了两项同分布。这证明了上界。
下界. 论证类似：
$$ \begin{aligned} \mathbb E\left\|\sum_i\varepsilon_iX_i\right\| &\le \mathbb E\left\|\sum_i\varepsilon_i(X_i-X_i')\right\| &&\text{条件化 }(\varepsilon_i)\text{ 并使用 (6.13)}\\ &= \mathbb E\left\|\sum_i(X_i-X_i')\right\| &&\text{同分布}\\ &\le \mathbb E\left\|\sum_iX_i\right\| + \mathbb E\left\|\sum_iX_i'\right\| &&\text{由三角不等式}\\ &= 2\mathbb E\left\|\sum_iX_i\right\| &&\text{由同分布}. \end{aligned} $$由此得到下界。读完证明后应检查：$X_i$ 的独立性在哪里使用？上下界是否都需要均值为零假设？
查看学习笔记：式 (6.13) 的 Jensen 证明 查看学习笔记：独立性和零均值的使用位置可以自己证明对称化引理的几个变体；见 习题 6.19-6.21。
6.4 非 i.i.d. 随机矩阵
对称化的典型用法分两步：先把随机变量 $X_i$ 替换为对称的 $\varepsilon_iX_i$；再条件化 $X_i$，使所有随机性都来自 Rademacher 符号。下面用它控制独立但非同分布矩阵元素形成的随机矩阵范数。
设 $A$ 是 $n\times n$ 对称随机矩阵，其对角线上及上三角部分的元素独立、均值为 $0$。记 $A_i$ 为第 $i$ 行。那么
$$ \mathbb E\max_i\|A_i\|_2 \le \mathbb E\|A\| \le C\sqrt{\log n}\, \mathbb E\max_i\|A_i\|_2. $$ 查看学习笔记：定理 6.4.1 完整证明虽然矩阵的算子范数通常很难直接用元素表达，但对随机矩阵来说可以非常接近：定理 6.4.1 说明它大致等于行的最大欧氏范数，只差一个对数因子。并且与之前的结果不同，这里对元素完全不需要矩假设。
下界应当已经熟悉：由 习题 4.7，$\|A_i\|_2=\|Ae_i\|_2\le\|A\|$，所以 $\max_i\|A_i\|_2\le\|A\|$。
为了证明上界，我们使用对称化和矩阵 Khintchine 不等式（定理 5.4.14）。像 定理 5.5.1 的证明那样，按元素分解 $A$，同时保持对称性。记 $e_1,\ldots,e_n$ 为 $\mathbb R^n$ 中的标准基向量，写成独立、均值为零的随机矩阵之和：
$$ A=\sum_{i\le j}Z_{ij}, $$其中
$$ Z_{ij} = \begin{cases} A_{ij}(e_ie_j^{\mathsf T}+e_je_i^{\mathsf T}),& i\lt j,\\ A_{ii}e_ie_i^{\mathsf T},& i=j. \end{cases} $$应用对称化（引理 6.3.2），得到
$$ \mathbb E\|A\| = \mathbb E\left\|\sum_{i\le j}Z_{ij}\right\| \le 2\mathbb E\left\|\sum_{i\le j}\varepsilon_{ij}Z_{ij}\right\|. \tag{6.14} $$这里 $(\varepsilon_{ij})$ 是独立 Rademacher 随机变量。条件化在 $(Z_{ij})$ 上，对 $p=1$ 应用矩阵 Khintchine 不等式（定理 5.4.14），再用全期望公式对 $(Z_{ij})$ 取期望，得到
$$ \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} $$现在，仍像 定理 5.5.1 的证明那样，每个 $Z_{ij}^2$ 都是对角矩阵：
$$ Z_{ij}^2 = \begin{cases} A_{ij}^2(e_ie_i^{\mathsf T}+e_je_j^{\mathsf T}),& i\lt j,\\ A_{ii}^2e_ie_i^{\mathsf T},& i=j. \end{cases} $$因此
$$ \sum_{i\le j}Z_{ij}^2 = \sum_{i=1}^n \left(\sum_{j=1}^n A_{ij}^2\right)e_ie_i^{\mathsf T} = \sum_{i=1}^n\|A_i\|_2^2e_ie_i^{\mathsf T}. $$换句话说，$\sum_{i\le j}Z_{ij}^2$ 是对角矩阵，其对角元素等于 $\|A_i\|_2^2$。由于对角矩阵的算子范数等于其元素的最大绝对值，
$$ \left\|\sum_{i\le j}Z_{ij}^2\right\| = \max_i\|A_i\|_2^2. $$把这个结果代入 (6.15)，再代入 (6.14)，即可完成证明。
查看学习笔记：$Z_{ij}^2$ 为什么给出行范数为了练习对称化技巧，可以现在尝试 习题 6.22-6.29。
6.5 应用：矩阵补全
我们学到的方法有一个令人兴奋的应用：矩阵补全，也就是从部分观测矩阵中恢复缺失元素。当然，如果对矩阵一无所知，这件事不可能完成。下面说明，对低秩矩阵，可以用算法恢复缺失元素。
为了用数学语言描述这个问题，考虑一个 $n\times n$ 矩阵 $X$，且
$$ \operatorname{rank}(X)=r, $$
其中 $r\ll n$。假设我们只能看到 $X$ 的若干随机选择的元素。每个元素 $X_{ij}$ 以概率 $p\in(0,1)$ 独立地被展示给我们，并以概率 $1-p$ 被隐藏。换句话说，我们观测到 $n\times n$ 矩阵 $Y$，其元素为
$$ Y_{ij}:=\delta_{ij}X_{ij}, \qquad \delta_{ij}\sim\operatorname{Ber}(p)\text{ 独立}. $$
这些 $\delta_{ij}$ 是选择变量，也就是选择我们观测哪些元素的 Bernoulli 随机变量；所有未观测元素都被替换为零。若
$$ p=\frac{m}{n^2}, \tag{6.16} $$
则平均会观测到 $m$ 个元素。
怎样从 $Y$ 恢复 $X$？虽然 $X$ 的秩很小，$Y$ 却未必有小秩（为什么？）。为了解决这一点，我们可以取 $Y$ 的最佳秩 $r$ 近似（见第 4.1.5 节）。适当缩放后，这会给出 $X$ 的好估计。
令 $\widehat X$ 为 $p^{-1}Y$ 的最佳秩 $r$ 近似。那么只要 $m\ge n\log n$，就有
$$ \mathbb E\frac1n\|\widehat X-X\|_F \le C\sqrt{\frac{rn\log n}{m}}\, \|X\|_\infty, $$其中 $\|X\|_\infty=\max_{i,j}|X_{ij}|$ 是 $X$ 的最大元素绝对值。
查看学习笔记：定理 6.5.1 完整证明在证明 定理 6.5.1 之前，注意恢复误差
$$ \frac1n\|\widehat X-X\|_F = \left( \frac1{n^2}\sum_{i,j=1}^n|\widehat X_{ij}-X_{ij}|^2 \right)^{1/2} $$
表示每个元素的平均误差（以 $L^2$ 意义）。如果选择平均观测数 $m$ 满足
$$ m\ge C'rn\log n $$
且常数 $C'$ 足够大，那么 定理 6.5.1 保证平均误差远小于 $\|X\|_\infty$。因此，只要观测元素的数量比 $rn$ 多一个对数余量，矩阵补全就是可能的。
我们先控制算子范数中的恢复误差，然后用低秩假设转到 Frobenius 范数。
步骤 1：控制算子范数误差. 由三角不等式，
$$ \|\widehat X-X\| \le \|\widehat X-p^{-1}Y\|+\|p^{-1}Y-X\|. $$由于 $\widehat X$ 被选为 $p^{-1}Y$ 的最佳秩 $r$ 近似，第二项支配第一项，即 $\|\widehat X-p^{-1}Y\|\le\|p^{-1}Y-X\|$。因此
$$ \|\widehat X-X\| \le 2\|p^{-1}Y-X\| = \frac2p\|Y-pX\|. \tag{6.17} $$注意，难以处理的矩阵 $\widehat X$ 已经从上界中消失。现在出现的是更容易理解的 $Y-pX$，因为其元素
$$ (Y-pX)_{ij}=(\delta_{ij}-p)X_{ij} $$是独立均值为零随机变量。使用 定理 6.4.1，更准确地说使用它的非对称版本（见 习题 6.28），得到
$$ \mathbb E\|Y-pX\| \le C\sqrt{\log n} \left( \mathbb E\max_{i\le n}\|(Y-pX)_{i:}\|_2 + \mathbb E\max_{j\le n}\|(Y-pX)_{:j}\|_2 \right). \tag{6.18} $$为了控制 $Y-pX$ 的行范数，写成
$$ \|(Y-pX)_{i:}\|_2^2 = \sum_{j=1}^n(\delta_{ij}-p)^2X_{ij}^2 \le \sum_{j=1}^n(\delta_{ij}-p)^2\|X\|_\infty^2, $$列同理。这些独立随机变量的和可以用 Bernstein（或 Chernoff）不等式容易控制，得到
$$ \mathbb E\max_{i\in[n]}\sum_{j=1}^n(\delta_{ij}-p)^2 \lesssim pn. $$这个计算留给 习题 6.30。把它与列的同类估计合并，并代入 (6.18)，得到
$$ \mathbb E\|Y-pX\| \lesssim \sqrt{pn\log n}\,\|X\|_\infty. $$再由 (6.17)，
$$ \mathbb E\|\widehat X-X\| \lesssim \sqrt{\frac{n\log n}{p}}\,\|X\|_\infty. \tag{6.19} $$步骤 2：转为 Frobenius 范数. 到目前为止还没有使用低秩假设，现在使用它。由假设 $\operatorname{rank}(X)\le r$，且由构造 $\operatorname{rank}(\widehat X)\le r$，所以
$$ \operatorname{rank}(\widehat X-X)\le 2r. $$这推出
$$ \|\widehat X-X\|_F \le \sqrt{2r}\,\|\widehat X-X\|. $$这是 引理 4.1.11 的直接结果；见 习题 4.4。取期望并使用算子范数误差界 (6.19)，得到
$$ \mathbb E\|\widehat X-X\|_F \lesssim \sqrt{\frac{rn\log n}{p}}\,\|X\|_\infty. $$两边除以 $n$，可改写为
$$ \mathbb E\frac1n\|\widehat X-X\|_F \lesssim \sqrt{\frac{rn\log n}{pn^2}}\,\|X\|_\infty. $$最后回忆 $p$ 的定义 (6.16)，即 $pn^2=m$，定理得证。
查看学习笔记：最佳秩 $r$ 近似如何推出 (6.17) 查看学习笔记：行列最大范数估计定理 6.5.1 可以用许多方式推广和改进。可以尝试把它推广到矩形矩阵（习题 6.31）和带噪观测（习题 6.32）。去掉误差界中的对数因子并非平凡，但也是可能的；对于无噪声观测，还可以实现零误差。细节见本章后的注记。
6.6 收缩原理
本章最后介绍一个常用的不等式。
设 $x_1,\dots,x_N$ 是赋范空间中的固定向量，$a=(a_1,\dots,a_N)\in\mathbb R^N$，$\varepsilon_i$ 是独立 Rademacher 随机变量。那么
$$ \mathbb E\left\|\sum_{i=1}^N a_i\varepsilon_i x_i\right\| \le \|a\|_\infty \mathbb E\left\|\sum_{i=1}^N \varepsilon_i x_i\right\|. $$ 查看学习笔记：定理 6.6.1 完整证明不失一般性，假设 $\|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$ 是凸函数；这点可在 习题 6.35 中检查。
我们要在所有满足 $\|a\|_\infty\le1$ 的点上控制 $f$，也就是在单位立方体 $[-1,1]^N$ 上控制它。由最大值原理（习题 1.4 和 1.5），凸函数在立方体上的最大值可在某个顶点处取得；在顶点处，所有 $a_i=\pm1$。
对这样的 $a$，由对称性，随机变量 $(\varepsilon_ia_i)$ 与 $(\varepsilon_i)$ 同分布。因此
$$ \mathbb E\left\|\sum_{i=1}^N a_i\varepsilon_i x_i\right\| = \mathbb E\left\|\sum_{i=1}^N\varepsilon_i x_i\right\|. $$所以只要 $\|a\|_\infty\le1$，就有
$$ f(a)\le \mathbb E\left\|\sum_{i=1}^N\varepsilon_i x_i\right\|. $$这证明了归一化情形；一般情形通过按 $\|a\|_\infty$ 缩放得到。
查看学习笔记：为什么 $f$ 是凸函数 查看学习笔记：为什么可先设 $\|a\|_\infty\le1$ 查看学习笔记：为什么顶点处不改变 Rademacher 分布作为一个应用，我们证明 引理 6.3.2 的高斯版本：把 Rademacher 随机变量换成高斯随机变量 $g_i\sim N(0,1)$。
设 $X_1,\dots,X_N$ 是赋范空间中的独立、均值为 $0$ 的随机向量。设 $g_1,\dots,g_N\sim N(0,1)$ 独立，且与 $X_i$ 独立。那么
$$ \frac{c}{\sqrt{\log N}} \mathbb E\left\|\sum_{i=1}^N g_iX_i\right\| \le \mathbb E\left\|\sum_{i=1}^N X_i\right\| \le 3 \mathbb E\left\|\sum_{i=1}^N g_iX_i\right\|. $$ 查看学习笔记：引理 6.6.2 完整证明上界. 由对称化（引理 6.3.2），
$$ E:= \mathbb E\left\|\sum_{i=1}^N X_i\right\| \le 2\mathbb E\left\|\sum_{i=1}^N\varepsilon_iX_i\right\|. $$为了把 Rademacher 随机变量换成高斯随机变量，回忆 $\mathbb E|g_i|=\sqrt{2/\pi}$。于是可继续估计为
$$ \begin{aligned} E &\le 2\sqrt{\frac\pi2}\, \mathbb E_X\left\| \sum_{i=1}^N\varepsilon_i\mathbb E_g|g_i|X_i \right\|\\ &\le 2\sqrt{\frac\pi2}\, \mathbb E\left\| \sum_{i=1}^N\varepsilon_i|g_i|X_i \right\| \qquad\text{由 Jensen 不等式}\\ &= 2\sqrt{\frac\pi2}\, \mathbb E\left\| \sum_{i=1}^N g_iX_i \right\|. \end{aligned} $$最后一个等号成立，是因为 $(\varepsilon_i|g_i|)$ 与 $(g_i)$ 有相同的联合分布（引理 6.3.1(b)）。调整绝对常数即可得到右侧不等式中的常数 $3$。
下界. 下界由收缩原理（定理 6.6.1）和对称化（引理 6.3.2）推出。令 $\xi_i$ 为另一组独立 Rademacher 随机变量，且与 $g_i,X_i$ 独立。由高斯的对称性，
$$ \mathbb E\left\|\sum_{i=1}^N g_iX_i\right\| = \mathbb E\left\|\sum_{i=1}^N \xi_i g_iX_i\right\|. $$条件化在 $g=(g_1,\ldots,g_N)$ 和 $X_i$ 上，对固定向量 $X_i$ 与系数 $g_i$ 应用收缩原理，得到
$$ \mathbb E_\xi\left\|\sum_{i=1}^N \xi_i g_iX_i\right\| \le \|g\|_\infty \mathbb E_\xi\left\|\sum_{i=1}^N \xi_iX_i\right\|. $$于是
$$ \begin{aligned} \mathbb E\left\|\sum_{i=1}^N g_iX_i\right\| &\le \mathbb E_g\left[ \|g\|_\infty\, \mathbb E_X\mathbb E_\xi \left\|\sum_{i=1}^N \xi_iX_i\right\| \right]\\ &\le 2\mathbb E_g\left[ \|g\|_\infty\, \mathbb E_X \left\|\sum_{i=1}^N X_i\right\| \right]\\ &= 2(\mathbb E\|g\|_\infty) \left(\mathbb E\left\|\sum_{i=1}^N X_i\right\|\right), \end{aligned} $$其中第二步使用 引理 6.3.2，最后一步使用 $g$ 与 $X_i$ 的独立性。最后回忆
$$ \mathbb E\|g\|_\infty\le C\sqrt{\log N}, $$见 命题 2.7.6 或 习题 2.38(a)。整理即得左侧不等式，证明完成。
引理 6.6.2 中的 $\sqrt{\log N}$ 因子一般不能去掉，见 习题 6.37。因此高斯对称化在一般赋范空间中弱于 Rademacher 对称化。
继续练习收缩：可以证明一般分布的版本（习题 6.36）以及范数的凸函数版本（习题 6.38）。
6.7 注记
定理 6.1.1 中的解耦不等式最初由 J. Bourgain 和 L. Tzafriri [55] 证明。关于相关结果和扩展，可参见论文 [97] 以及书籍 [96]、[127, 第 8.4 节]。
原始 Hanson-Wright 不等式比 定理 6.2.2 稍弱，可追溯到 [154, 350]。Hanson-Wright 不等式的现代版本（定理 6.2.2）以及第 6.2 节中的证明来自 [292]。若干特殊情形更早已经出现：Bernoulli 随机变量的版本见 [127, 命题 8.13]，高斯随机变量的版本见 [315, 引理 2.5.1]，无对角矩阵的版本见 [31]。
在 [176] 中，定理 6.2.2 里关于 $K$ 的依赖被改进了，假设是 $X_i$ 的方差为一。关于 Hanson-Wright 不等式的一些扩展，可参见 [6, 34, 354, 8, 188, 145, 293, 159]。
各向异性随机向量的集中（习题 6.13）以及随机向量到子空间距离的界（习题 6.14）来自 [292]。
对称化 引理 6.3.2 及其证明可见例如 [210, 引理 6.3]、[127, 第 8.2 节]。
虽然 定理 6.4.1 的精确陈述在现有文献中不容易定位，但它可以从 [324, 327] 中的不等式推出。定理 6.4.1 中的 $\sqrt{\log n}$ 因子，可以通过把 Y. Seginer [299, 定理 3.1] 的结果与对称化（引理 6.3.2）结合，改进为 $\log^{1/4}n$；关于 Seginer 定理的另一种处理，见 [27, 推论 4.7]。这个改进后的因子是最优的，习题 6.29 中的结果展示了这一点；该结果归功于 Y. Seginer [299, 定理 3.2]。此外，对于很多矩阵类别，$\log^{1/4}n$ 因子可以完全去掉；特别地，i.i.d. 元素的矩阵 [299] 和高斯元素的矩阵 [203] 都属于这种情形。关于用元素的方差描述随机矩阵 $A$ 的算子范数的更精细结果，可参见 [331, 第 4 节]、[203, 25, 26, 59, 204]。
定理 6.5.1 关于矩阵补全的结论及其证明来自 [278, 第 2.5 节]，虽然它的某些版本可能更早已经出现。特别地，Keshavan、Montanari 和 Oh [182] 说明了如何通过“修剪”（trimming）随机矩阵 $Y$ 得到稍好的界，即去掉对数因子；这里修剪指删除 $Y$ 中非零元素数量比期望大很多（比如两倍）的行和列。E. Candes 和 B. Recht [72] 证明，在额外非相干性假设下，精确矩阵补全（零误差）可以用 $m\gtrsim rn\log^2(n)$ 个随机采样元素实现。关于矩阵补全的后续发展，见 [74, 282, 148, 92]。
收缩原理（定理 6.6.1）来自 [210, 第 4.2 节]；另见 [210, 推论 3.17, 定理 4.12] 中的不同版本。高斯对称化（引理 6.6.2）可见 [210, 不等式 (4.9)]。其中对数因子一般是需要的，但如果赋范空间有非平凡 cotype，则可以去掉；见 [210, 命题 9.14]。
在 习题 6.4 中，对对称矩阵，常数 $4$ 可以改进为 $2$ [323]。
习题 6.10 中关于各向异性次高斯随机向量范数的一个版本最早由 D. Hsu、S. Kakade 和 T. Zhang [166] 证明；他们使用精确次高斯范数（习题 2.40 中引入）得到了尖锐界。
习题 6.22 中的对称性假设是必要的，不能省略 [135, 例 2.8]。
习题
如 评注 6.1.2 所说，定理 6.1.1 的无对角假设不能去掉。但可以把对角项放在右侧。证明：对任意实数 $(a_{ij})_{i,j=1}^n$，有
$$ \mathbb EF\left(\sum_{i,j:i\ne j}a_{ij}X_iX_j\right) \le \mathbb EF\left(4\sum_{i,j}a_{ij}X_iX'_j\right). $$ 查看学习笔记：习题 6.1 完整证明令 $(a_{ij})_{i,j=1}^n$ 为实数。令 $X_1,\ldots,X_n$ 独立、均值为 $0$，并令 $(X_i')$ 为其独立副本。
(a) 对任意 $p\in[1,\infty)$，证明
$$ \left\| \sum_{i,j:i\ne j}a_{ij}X_iX_j \right\|_{L^p} \le 4 \left\| \sum_{i,j}a_{ij}X_iX'_j \right\|_{L^p}. $$(b) 证明
$$ \left\| \sum_{i,j:i\ne j}a_{ij}X_iX_j \right\|_{\psi_2} \le 4 \left\| \sum_{i,j}a_{ij}X_iX'_j \right\|_{\psi_2}. $$ 查看学习笔记：习题 6.2 完整证明(a) 令 $(v_{ij})_{i,j=1}^n$ 是某个向量空间 $V$ 中的向量。令 $X_1,\ldots,X_n$ 独立、均值为 $0$，并令 $(X_i')$ 为其独立副本。证明：对任意凸函数 $F:V\to\mathbb R$，
$$ \mathbb EF\left( \sum_{i,j:i\ne j}v_{ij}X_iX_j \right) \le \mathbb EF\left( 4\sum_{i,j}v_{ij}X_iX'_j \right). $$(b) 令 $X_1,\ldots,X_n$ 为 $\mathbb R^N$ 中独立、均值为 $0$ 的随机向量。证明：对任意凸函数 $F:\mathbb R\to\mathbb R$，
$$ \mathbb EF\left( \sum_{i,j:i\ne j}a_{ij}\langle X_i,X_j\rangle \right) \le \mathbb EF\left( 4\sum_{i,j}a_{ij}\langle X_i,X'_j\rangle \right). $$(c) 在同样假设下，证明：对任意凸函数 $F:\mathbb R^{N\times N}\to\mathbb R$，
$$ \mathbb EF\left( \sum_{i,j:i\ne j}a_{ij}X_iX_j^{\mathsf T} \right) \le \mathbb EF\left( 4\sum_{i,j}a_{ij}X_i(X'_j)^{\mathsf T} \right). $$ 查看学习笔记：习题 6.3 完整证明令 $A$ 为 $n\times n$ 无对角矩阵。随机子集 $J\subset\{1,\ldots,n\}$ 由独立地以概率 $p\in(0,1)$ 保留每个指标得到。令 $J'$ 是 $J$ 的独立副本。证明
$$ \mathbb E\|A_{J\times J}\| \le 4\mathbb E\|A_{J\times J'}\|. $$这里 $A_{I\times J}$ 表示取 $A$ 中行指标来自 $I$、列指标来自 $J$ 的子矩阵。
查看学习笔记：习题 6.4 完整证明人们也许会猜测 命题 6.2.1 中的一阶项应当是 $\|X\|$ 的均值，约为 $\sqrt n$，而不是 $CK\sqrt n$。这是错误的。构造例子说明如下界不总成立：
$$ \mathbb P\{\|X\|_2\ge C(\sqrt n+Kt)\}\le e^{-t^2} \qquad\text{for all }t\ge0. $$ 查看学习笔记：习题 6.5 完整证明(a) 把最大不等式 习题 3.13 推广到次高斯随机向量，即使这些向量的坐标不独立也可以。
(b) 把 习题 4.44(a),(b) 中关于 $1\to\infty$ 与 $1\to2$ 范数的界，推广到列独立且每列为次高斯随机向量的随机矩阵；每一列内部的坐标不必独立。
查看学习笔记：习题 6.6 完整证明在正态分布情形下，给出 Hanson-Wright 不等式的另一种证明：不要把对角部分单独分离，也不要使用解耦。
查看学习笔记：习题 6.7 完整证明令 $A=(a_{ij})$ 为 $n\times n$ 矩阵。令 $X_1,\ldots,X_n$ 为 $\mathbb R^d$ 中独立、均值为 $0$、次高斯的随机向量。证明：对所有 $t\ge0$，
$$ \mathbb P\left\{ \left| \sum_{i,j:i\ne j}a_{ij}\langle X_i,X_j\rangle \right|\ge t \right\} \le 2\exp\left[ -c\min\left( \frac{t^2}{K^4d\|A\|_F^2}, \frac{t}{K^2\|A\|} \right) \right], $$其中 $K=\max_i\|X_i\|_{\psi_2}$。
查看学习笔记：习题 6.8 完整证明令 $B$ 为 $m\times n$ 矩阵，令 $X$ 为 $\mathbb R^n$ 中均值为 $0$ 的次高斯随机向量，且 $\|X\|_{\psi_2}\le K$。证明：只要 $|\lambda|\le c/(K\|B\|)$，就有
$$ \mathbb E\exp\left(\lambda^2\|BX\|_2^2\right) \le \exp\left(CK^2\lambda^2\|B\|_F^2\right). $$ 查看学习笔记：习题 6.9 完整证明把 命题 6.2.1 推广到各向异性情形。令 $B$ 为 $m\times n$ 矩阵，令 $X$ 为 $\mathbb R^n$ 中均值为 $0$ 的次高斯随机向量，且 $\|X\|_{\psi_2}\le K$。证明：对所有 $t\ge0$，
$$ \mathbb P\{\|BX\|_2\ge CK(\|B\|_F+t\|B\|)\} \le e^{-t^2}. $$ 查看学习笔记：习题 6.10 完整证明下面是 Hanson-Wright 不等式的一个有用版本，不要求坐标独立。令 $A$ 为 $n\times n$ 对称正半定矩阵，令 $X$ 为 $\mathbb R^n$ 中均值为 $0$ 的次高斯随机向量，且 $\|X\|_{\psi_2}\le K$。证明：对任意 $s\ge0$，
$$ \mathbb P\left\{ X^{\mathsf T}AX \ge CK^2(\operatorname{tr}A+s\|A\|) \right\} \le e^{-s}. $$为了和 定理 6.2.2 比较，可令 $t=CK^2s\|A\|$，并注意各向同性 $X$ 时 $\operatorname{tr}A=\mathbb E X^{\mathsf T}AX$。解释为什么这里即使 $X$ 是各向同性，也只能有单侧界。
查看学习笔记：习题 6.11 完整证明回到第 2.4 节的均值估计问题。设 $X_1,\ldots,X_N$ 是从 $\mathbb R^n$ 中某个未知分布抽取的 i.i.d. 样本，该分布均值为 $\mu$、协方差为 $\Sigma$。假设该分布次高斯：
$$ \|\langle X_i-\mu,u\rangle\|_{\psi_2} \le K\|\langle X_i-\mu,u\rangle\|_{L^2} \qquad\text{for all }u\in\mathbb R^n. $$证明：对任意 $\alpha\in(0,1)$，样本均值 $\mu_N=N^{-1}\sum_{i=1}^NX_i$ 满足
$$ \|\mu_N-\mu\|_2 \le CK\sqrt{\frac{\operatorname{tr}\Sigma}{N}} + CK\sqrt{\frac{\|\Sigma\|\log(1/\alpha)}{N}} $$的概率至少为 $1-\alpha$。
查看学习笔记：习题 6.12 完整证明把 定理 3.1.1 推广到各向异性分布。令 $B$ 为 $m\times n$ 矩阵，令 $X=(X_1,\ldots,X_n)\in\mathbb R^n$ 的坐标独立、均值为 $0$、方差为 $1$ 且次高斯。证明
$$ \left\| \|BX\|_2-\|B\|_F \right\|_{\psi_2} \le CK^2\|B\|, $$其中 $K=\max_i\|X_i\|_{\psi_2}$。
查看学习笔记：习题 6.13 完整证明令 $E$ 是 $\mathbb R^n$ 中维数为 $d$ 的子空间。令 $X=(X_1,\ldots,X_n)\in\mathbb R^n$ 的坐标独立、均值为 $0$、方差为 $1$ 且次高斯。
(a) 验证
$$ \left(\mathbb E\operatorname{dist}(X,E)^2\right)^{1/2} = \sqrt{n-d}. $$(b) 从 习题 6.13 推出：对任意 $t\ge0$，
$$ \mathbb P\left\{ \left| \operatorname{dist}(X,E)-\sqrt{n-d} \right|\gt t \right\} \le 2\exp(-ct^2/K^4), $$其中 $K=\max_i\|X_i\|_{\psi_2}$。
查看学习笔记：习题 6.14 完整证明取任意有 $E$ 条边的图，并随机把顶点分成两组。命题 3.6.3 说明跨割边数的期望为 $E/2$。证明它紧密集中在该值附近：对任意 $s\ge1$，
$$ \mathbb P\left\{ \left|\operatorname{cut}-\frac E2\right| \ge s\sqrt E \right\} \le 2e^{-cs}. $$ 查看学习笔记：习题 6.15 完整证明证明 引理 6.3.1 中的全部陈述。
查看学习笔记：习题 6.16 完整证明引理 6.3.1(c) 说：若 $X'$ 是 $X$ 的独立副本，则 $X-X'$ 是对称。对两个例子计算 $X-X'$ 的分布。
(a) 若 $X\sim\operatorname{Ber}(p)$，计算 $X-X'$ 的概率质量函数。
(b) 若 $X\sim\operatorname{Exp}(1)$，证明 $X-X'\sim\operatorname{Lap}(0,1)$，也就是密度为 $\frac12e^{-|x|}$，$x\in\mathbb R$。
查看学习笔记：习题 6.17 完整证明令 $X$ 是取值于某个赋范空间的对称随机向量，即 $X$ 与 $-X$ 同分布。令 $v$ 是该空间中的固定向量。证明
$$ \mathbb E\|X+v\| \asymp \mathbb E\|X\|+\|v\|. $$这里 $\asymp$ 隐含正的绝对常数因子。
查看学习笔记：习题 6.18 完整证明(a) 证明对称化引理 引理 6.3.2 对非零均值随机向量的推广：
$$ \mathbb E\left\| \sum_{i=1}^N X_i-\sum_{i=1}^N\mathbb E X_i \right\| \le 2\mathbb E\left\| \sum_{i=1}^N\varepsilon_iX_i \right\|. $$(b) 说明不存在任何非平凡的反向不等式。
查看学习笔记：习题 6.19 完整证明证明对称化引理 引理 6.3.2 的如下推广。令 $F:\mathbb R_+\to\mathbb R$ 为递增凸函数。证明：若把范数 $\|\cdot\|$ 替换为 $F(\|\cdot\|)$，引理 6.3.2 中同样成立，即
$$ \mathbb EF\left( \frac12 \left\| \sum_{i=1}^N\varepsilon_iX_i \right\| \right) \le \mathbb EF\left( \left\| \sum_{i=1}^NX_i \right\| \right) \le \mathbb EF\left( 2 \left\| \sum_{i=1}^N\varepsilon_iX_i \right\| \right). $$ 查看学习笔记：习题 6.20 完整证明令 $X_1,\ldots,X_N$ 为独立、均值为 $0$ 的随机变量。证明 $\sum_iX_i$ 为次高斯当且仅当 $\sum_i\varepsilon_iX_i$ 为次高斯，并且
$$ c \left\| \sum_{i=1}^N\varepsilon_iX_i \right\|_{\psi_2} \le \left\| \sum_{i=1}^NX_i \right\|_{\psi_2} \le C \left\| \sum_{i=1}^N\varepsilon_iX_i \right\|_{\psi_2}. $$ 查看学习笔记：习题 6.21 完整证明令 $X_1,\ldots,X_N$ 为独立对称随机变量。证明：对任意 $t\gt 0$，
$$ \mathbb P\left\{ \left| \sum_{i=1}^NX_i \right| \ge t \left( \sum_{i=1}^NX_i^2 \right)^{1/2} \right\} \le 2e^{-t^2/2}. $$这个结论非常一般，不需要次高斯假设，也不需要矩假设。
查看学习笔记：习题 6.22 完整证明从更广的角度看，赋范空间 $X$ 称为具有型 $p$（type $p$），如果存在常数 $K$，使得对任意 $N$ 和任意向量 $x_1,\ldots,x_N\in X$，都有
$$ \mathbb E\left\|\sum_{i=1}^N\varepsilon_i x_i\right\|^p \le K^p\sum_{i=1}^N\|x_i\|^p. $$
本题和下一题说明：$\ell^p$ 当且仅当 $p\in[1,2]$ 时具有型 $p$，并且当且仅当 $p\in[2,\infty)$ 时具有型 $2$。
令 $p\in[1,2]$。
(a) 对任意固定向量 $x_1,\ldots,x_N\in\mathbb R^n$，验证
$$ \mathbb E \left\| \sum_{i=1}^N\varepsilon_ix_i \right\|_p^p \le \sum_{i=1}^N\|x_i\|_p^p. $$(b) 推广 (a)：令 $X_1,\ldots,X_N$ 为 $\mathbb R^n$ 中均值为 $0$ 且独立的随机向量。证明
$$ \mathbb E \left\| \sum_{i=1}^NX_i \right\|_p^p \le \sum_{i=1}^N\mathbb E\|X_i\|_p^p. $$(c) 构造例子说明 (a)-(b) 对任意 $p\gt 2$ 都失败。
查看学习笔记：习题 6.23 完整证明(a) 对任意固定向量 $x_1,\ldots,x_N\in\mathbb R^n$，验证
$$ \mathbb E \left\| \sum_{i=1}^N\varepsilon_ix_i \right\|_p^2 \le Cp \sum_{i=1}^N\|x_i\|_p^2. $$(b) 推广 (a)：令 $X_1,\ldots,X_N$ 为 $\mathbb R^n$ 中均值为 $0$ 且独立的随机向量。证明
$$ \mathbb E \left\| \sum_{i=1}^NX_i \right\|_p^2 \le Cp \sum_{i=1}^N\mathbb E\|X_i\|_p^2. $$(c) 构造例子说明 (a)-(b) 对任意 $p\lt 2$ 都失败。
查看学习笔记：习题 6.24 完整证明对任意 $p\in[1,\infty)$，陈述并证明近似 Caratheodory 定理（定理 0.0.2）在 $\ell^p$ 范数下的版本。
查看学习笔记：习题 6.25 完整证明令 $X_1,\ldots,X_N$ 为独立、均值为 $0$ 的随机变量，且 $p\in[2,\infty)$。证明
$$ \left\| \sum_{i=1}^NX_i \right\|_{L^p}^2 \le Cp \sum_{i=1}^N \|X_i\|_{L^p}^2. $$ 查看学习笔记：习题 6.26 完整证明如果你想看更广的视角，这个不等式基本说明 $p\ge2$ 时的 $L^p$ 空间具有型 $2$，这与习题 6.24 中考察的 $\ell^p$ 空间类似。
在更弱的有限矩条件下证明 定理 3.1.1 的一个版本。令 $X=(X_1,\ldots,X_n)\in\mathbb R^n$，其坐标满足 $\mathbb E X_i^2=1$ 且 $\|X_i\|_{L^{2p}}\le K$，其中 $p\ge2$、$K\ge0$。证明
$$ \left\| \|X\|_2-\sqrt n \right\|_{L^p} \le C\sqrt p\,K^2. $$ 查看学习笔记：习题 6.27 完整证明把 定理 6.4.1 推广到非对称的矩形矩阵。令 $A$ 为 $m\times n$ 随机矩阵，元素独立且均值为 $0$。证明其期望算子范数与行、列欧氏范数最大值的期望相当，至多差一个对数因子：
$$ \mathbb E \max\left\{ \max_i\|A_{i:}\|_2, \max_j\|A_{:j}\|_2 \right\} \le \mathbb E\|A\| $$ $$ \le C\sqrt{\log(m+n)} \mathbb E \max\left\{ \max_i\|A_{i:}\|_2, \max_j\|A_{:j}\|_2 \right\}. $$ 查看学习笔记：习题 6.28 完整证明证明 定理 6.4.1 中的对数因子一般不能完全去掉。构造满足该定理假设的随机矩阵 $A$，使得
$$ \mathbb E\|A\| \ge c\log^{1/4}(n)\cdot \mathbb E\max_i\|A_i\|_2. $$ 查看学习笔记：习题 6.29 完整证明考虑 i.i.d. 随机变量 $\delta_{ij}\sim\operatorname{Ber}(p)$，其中 $i,j=1,\ldots,n$。假设 $pn\ge\log n$，证明
$$ \mathbb E \max_{i\le n} \sum_{j=1}^n(\delta_{ij}-p)^2 \le Cpn. $$ 查看学习笔记：习题 6.30 完整证明对一般 $m\times n$ 矩阵，陈述并证明矩阵补全（定理 6.5.1）的一个版本。
查看学习笔记：习题 6.31 完整证明把矩阵补全（定理 6.5.1）推广到带噪观测：我们看到的是某些条目的噪声版本 $X_{ij}+\nu_{ij}$。这里 $\nu_{ij}$ 是独立、均值为 $0$ 的次高斯随机变量，代表观测噪声。
查看学习笔记：习题 6.32 完整证明很少有结果完全不对随机矩阵的分布作假设。证明下面这个无界随机矩阵版本的矩阵 Bernstein 不等式 (5.17)。令 $Z_1,\ldots,Z_N$ 为独立的 $n\times n$ 正半定随机矩阵。证明
$$ S:=\sum_{i=1}^NZ_i \qquad\text{满足}\qquad \mathbb E\|S-\mathbb ES\| \le C\left( \sqrt{\|\mathbb ES\|\cdot L}+L \right), $$其中
$$ L=\log(n)\,\mathbb E\max_i\|Z_i\|. $$ 查看学习笔记：习题 6.33 完整证明放宽一般协方差估计结果 (5.27) 中的有界性假设 (5.20)。令 $X$ 是 $\mathbb R^n$ 中的随机向量，$\Sigma=\mathbb EXX^{\mathsf T}$。令 $X_1,\ldots,X_m$ 为 $X$ 的 i.i.d. 副本。假设存在 $K\ge1$ 使得
$$ \mathbb E\max_{i\le m}\|X_i\|_2^2 \le K^2\mathbb E\|X\|_2^2. $$并令
$$ \Sigma_m=\frac1m\sum_{i=1}^mX_iX_i^{\mathsf T}. $$证明
$$ \mathbb E\|\Sigma_m-\Sigma\| \le C\left( \sqrt{\frac{K^2r\log n}{m}} + \frac{K^2r\log n}{m} \right)\|\Sigma\|, $$其中 $r=\operatorname{tr}(\Sigma)/\|\Sigma\|$ 是 $\Sigma$ 的有效秩。
查看学习笔记：习题 6.34 完整证明令 $z_1,\ldots,z_N$ 是赋范空间中的任意向量，令 $a=(a_1,\ldots,a_N)\in\mathbb R^N$，并令 $\varepsilon_1,\ldots,\varepsilon_N$ 为独立 Rademacher 随机变量。证明函数
$$ f(a):= \mathbb E \left\| \sum_{i=1}^Na_i\varepsilon_iz_i \right\| $$是凸函数。
查看学习笔记：习题 6.35 完整证明证明 定理 6.6.1 的如下推广。令 $a=(a_1,\ldots,a_N)\in\mathbb R^N$，令 $X_1,\ldots,X_N$ 为取值于某个赋范空间的独立、均值为 $0$ 的随机向量。证明
$$ \mathbb E \left\| \sum_{i=1}^Na_iX_i \right\| \le 4\|a\|_\infty \mathbb E \left\| \sum_{i=1}^NX_i \right\|. $$ 查看学习笔记：习题 6.36 完整证明证明 引理 6.6.2 中的 $\sqrt{\log N}$ 因子一般是最优的。
查看学习笔记：习题 6.37 完整证明令 $F:\mathbb R_+\to\mathbb R$ 为递增凸函数。把收缩（定理 6.6.1）和高斯对称化（引理 6.6.2）推广到把范数 $\|\cdot\|$ 全部替换为 $F(\|\cdot\|)$ 的版本。
查看学习笔记：习题 6.38 完整证明