翻译状态说明
本页为第 3 章的精校翻译，已覆盖正文、Notes、Exercises 3.1-3.58、明确 Proof 卡片和原书 Figure 3.1-3.11。
第 3 章 高维随机向量
本章研究高维随机向量
$$ X=(X_1,\ldots,X_n)\in\mathbb R^n, $$
其中维度 $n$ 通常很大。数据科学中经常出现这样的对象。例如，计算生物学会同时研究约 $10^4$ 个基因的表达量，并把一个随机个体的基因表达向量建模为高维随机向量。
高维空间带来新困难，因为维度增加会让空间体积爆炸。边长为 $2$ 的立方体体积是单位立方体的 $2^n$ 倍，这就是“维数灾难”的几何根源之一。
高维概率的作用，是用随机结构绕过这些困难。本章先研究独立坐标随机向量的欧氏范数集中，再引入协方差矩阵、PCA、各类高维分布、次高斯随机向量，并以 Grothendieck 不等式、半定规划和最大割近似算法作为应用。
3.1 范数的集中
随机向量
$$ X=(X_1,\ldots,X_n)\in\mathbb R^n $$
最可能出现在空间的哪里？先假设坐标 $X_i$ 是独立随机变量，均值为零、方差为一。$X$ 的典型长度是多少？我们有
$$ \mathbb E\|X\|_2^2 = \mathbb E\sum_{i=1}^n X_i^2 = \sum_{i=1}^n \mathbb EX_i^2 =n. $$
因此，我们应当预期 $X$ 的长度满足
$$ \|X\|_2\approx\sqrt n. $$
下面将证明，$X$ 确实以很高概率接近 $\sqrt n$。
设 $X=(X_1,\ldots,X_n)\in\mathbb R^n$ 是随机向量，坐标 $X_i$ 独立、次高斯，并满足 $\mathbb EX_i^2=1$。则
$$ \left\|\|X\|_2-\sqrt n\right\|_{\psi_2} \le CK^2, \tag{3.1} $$其中
$$ K=\max_i\|X_i\|_{\psi_2}, $$$C$ 是绝对常数。
由 Proposition 2.6.6，(3.1) 等价于下面的 Gaussian 型尾界：
$$ \mathbb P\left\{ \left|\|X\|_2-\sqrt n\right|\ge t \right\} \le 2\exp\left(-\frac{ct^2}{K^4}\right) \quad\text{for all }t\ge0. \tag{3.2} $$我们用 Bernstein 不等式证明这个尾界。先观察
$$ \frac1n\|X\|_2^2-1 = \frac1n\sum_{i=1}^n(X_i^2-1), $$这是独立、均值为零的随机变量之和。由于 $X_i$ 是次高斯，$X_i^2-1$ 是次指数。更精确地，由中心化界 (2.26) 和 Lemma 2.8.5，
$$ \|X_i^2-1\|_{\psi_1} \le C\|X_i^2\|_{\psi_1} = C\|X_i\|_{\psi_2}^2 \le CK^2. $$对 $N=n$ 和 $a_i=1/n$ 应用 Bernstein 不等式（Corollary 2.9.2），得到对任意 $u\ge0$，
$$ \begin{aligned} \mathbb P\left\{ \left|\frac1n\|X\|_2^2-1\right| \ge u \right\} &\le 2\exp\left[ -c_1\min\left( \frac{u^2n}{K^4}, \frac{un}{K^2} \right) \right] \\ &\le 2\exp\left[ -\frac{cn}{K^4}\min(u^2,u) \right]. \end{aligned} \tag{3.3} $$最后一步用到 $K$ 被一个绝对常数从下方控制；这是因为 $1=\|X_1\|_{L^2}\le C\|X_1\|_{\psi_2}\le CK$。
我们已经得到 $\|X\|_2^2$ 的集中。现在把它转化为 $\|X\|_2$ 的集中。对任意 $z,\delta\ge0$，有初等事实
$$ |z-1|\ge\delta \quad\Longrightarrow\quad |z^2-1|\ge\max(\delta,\delta^2). \tag{3.4} $$因此，对任意 $\delta\ge0$，
$$ \begin{aligned} \mathbb P\left\{ \left|\frac1{\sqrt n}\|X\|_2-1\right| \ge\delta \right\} &\le \mathbb P\left\{ \left|\frac1n\|X\|_2^2-1\right| \ge\max(\delta,\delta^2) \right\} \\ &\le 2\exp\left(-\frac{cn}{K^4}\delta^2\right). \end{aligned} $$令 $t=\delta\sqrt n$，就得到所需的次高斯尾界 (3.2)。
Theorem 3.1.1 表明，$\mathbb R^n$ 中的随机向量大多停留在半径 $\sqrt n$ 球面附近一个常数厚度的薄壳中。乍看这可能有些反直觉。直观解释如下：平方范数
$$ S_n:=\|X\|_2^2 $$均值为 $n$，标准差为 $O(\sqrt n)$。于是 $\|X\|_2=\sqrt{S_n}$ 围绕 $\sqrt n$ 的波动应当只有 $O(1)$，因为在 $n$ 附近，函数 $z\mapsto\sqrt z$ 的斜率约为 $1/\sqrt n$。
为了进一步熟悉薄壳现象，可以做 Exercises 3.1-3.3；这些题会说明通常有
$$ \operatorname{Var}(\|X\|_2)=\Theta(1), \qquad \mathbb E\|X\|_2 = \sqrt n-\Theta(1/\sqrt n). $$
3.2 协方差矩阵与主成分分析
假设随机向量坐标独立并不总是现实。为了处理更一般的情形，我们快速回顾高维概率分布的一些基础概念；这些概念在 Section 1.3 中已经简要出现过。
取值于 $\mathbb R^n$ 的随机向量 $X$ 的协方差矩阵定义为
$$ \operatorname{cov}(X) = \mathbb E(X-\mu)(X-\mu)^{\mathsf T} = \mathbb EXX^{\mathsf T}-\mu\mu^{\mathsf T}, \qquad \mu=\mathbb EX. $$
请检查上面的恒等式。因此，$\operatorname{cov}(X)$ 是 $n\times n$ 对称半正定矩阵。它是随机变量方差的高维推广；若随机变量 $Z$ 的均值为 $\mu=\mathbb EZ$，则
$$ \operatorname{Var}(Z) = \mathbb E(Z-\mu)^2 = \mathbb EZ^2-\mu^2. $$
若 $X=(X_1,\ldots,X_n)$，协方差矩阵的元素就是坐标对之间的协方差：
$$ \operatorname{cov}(X)_{ij} = \mathbb E\left[ (X_i-\mathbb EX_i)(X_j-\mathbb EX_j) \right]. \tag{3.5} $$
有时忽略均值会更方便，因此考虑二阶矩矩阵
$$ \Sigma(X)=\mathbb EXX^{\mathsf T}. $$
这是一维随机变量二阶矩 $\mathbb EZ^2$ 的高维推广。通过平移，也就是把 $X$ 换成 $X-\mu$，许多问题都可化为均值为零的情形；在这种情形下，协方差矩阵和二阶矩矩阵相同：
$$ \operatorname{cov}(X)=\Sigma(X). $$
因此，后文多数时候会关注二阶矩矩阵 $\Sigma=\Sigma(X)$。
3.2.1 可以从协方差矩阵中读出什么？
协方差矩阵告诉我们的远不止坐标之间的协方差。下面的结果说明如何用它计算：(a) $X$ 的一维边缘，也就是把 $X$ 投影到给定方向 $v\in\mathbb R^n$ 后得到的随机变量 $\langle X,v\rangle$ 的方差；(b) $X$ 的欧氏范数；(c) $X$ 的两个独立副本之间的夹角信息。
设 $X$ 是 $\mathbb R^n$ 中的随机向量，二阶矩矩阵为 $\Sigma=\mathbb EXX^{\mathsf T}$。
(a) 一维边缘。对任意固定向量 $v\in\mathbb R^n$，
$$ \mathbb E\langle X,v\rangle^2 = v^{\mathsf T}\Sigma v. \tag{3.6} $$(b) 范数。
$$ \mathbb E\|X\|_2^2 = \operatorname{tr}(\Sigma). $$(c) 独立副本内积。若 $Y$ 是 $X$ 的独立副本，则
$$ \mathbb E\langle X,Y\rangle^2 = \|\Sigma\|_F^2. $$这里 $\operatorname{tr}(\Sigma)=\sum_i\Sigma_{ii}$，而 $\|\Sigma\|_F=(\sum_{i,j}\Sigma_{ij}^2)^{1/2}$ 是 Frobenius 范数。
(a) 由期望线性性，
$$ \mathbb E\langle X,v\rangle^2 = \mathbb E(v^{\mathsf T}X)(X^{\mathsf T}v) = v^{\mathsf T}\mathbb E[XX^{\mathsf T}]v = v^{\mathsf T}\Sigma v. $$(b) 二阶矩矩阵的对角元为 $\Sigma_{ii}=\mathbb EX_i^2$，所以
$$ \mathbb E\|X\|_2^2 = \mathbb E\sum_{i=1}^n X_i^2 = \sum_{i=1}^n \mathbb EX_i^2 = \sum_{i=1}^n\Sigma_{ii}. $$(c) 可把内积写成求和并展开平方；利用 $X$ 与 $Y$ 独立即可得到结论。
3.2.2 主成分分析
理解随机向量 $X$ 的最有用信息，往往藏在其协方差矩阵 $\Sigma=\operatorname{cov}(X)$ 的特征值和特征向量中。由于 $\Sigma$ 是对称矩阵，谱定理告诉我们：$\Sigma$ 的特征值 $\lambda_i$ 都是实数，并且 $\mathbb R^n$ 中存在由特征向量 $v_i$ 构成的标准正交基。把单位矩阵写成
$$ I_n=\sum_{i=1}^n v_i v_i^{\mathsf T}, $$
两侧乘以 $\Sigma$ 并使用 $\Sigma v_i=\lambda_i v_i$，得到 $\Sigma$ 的谱分解：
$$ \Sigma = \sum_{i=1}^n \lambda_i v_i v_i^{\mathsf T}. \tag{3.7} $$
通常我们把特征值 $\lambda_i$ 按非增顺序排列。
特征值有一个很方便的优化刻画。最大特征值 $\lambda_1$ 可通过在所有单位向量 $v\in\mathbb R^n$ 上最大化二次型 $v^{\mathsf T}\Sigma v$ 得到，并且最大值在首个特征向量 $v=v_1$ 处取得。去掉 $v_1$ 后，在与 $v_1$ 正交的单位向量上最大化同一个二次型，就得到第二大特征值 $\lambda_2$，最大值在 $v_2$ 处取得。依此类推。
设 $\Sigma$ 是 $n\times n$ 对称矩阵，特征值为 $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n$，对应单位特征向量为 $v_1,\ldots,v_n$。则对每个 $k=1,\ldots,n$，
$$ \lambda_k = \max_{\substack{ v\perp\{v_1,\ldots,v_{k-1}\}\\ \|v\|_2=1 }} v^{\mathsf T}\Sigma v, \tag{3.8} $$并且最大值在 $v_k$ 处取得。
查看学习笔记完整证明取任意单位向量 $v\in\mathbb R^n$，并假设它与 $\{v_1,\ldots,v_{k-1}\}$ 正交。由谱分解 (3.7)，
$$ \begin{aligned} v^{\mathsf T}\Sigma v &= v^{\mathsf T} \left(\sum_{i=1}^n\lambda_i v_i v_i^{\mathsf T}\right)v \\ &= \sum_{i=1}^n\lambda_i\langle v,v_i\rangle^2 = \sum_{i=k}^n\lambda_i\langle v,v_i\rangle^2 \\ &\le \lambda_k \sum_{i=k}^n\langle v,v_i\rangle^2 \le \lambda_k. \end{aligned} $$最后一步使用 Bessel 不等式，因为 $v_i$ 是标准正交向量。另一方面，
$$ v_k^{\mathsf T}\Sigma v_k = v_k^{\mathsf T}(\lambda_k v_k) = \lambda_k. $$所以最大值正好是 $\lambda_k$，且在 $v_k$ 处取得。
把 (3.8) 与 (3.6) 结合起来，就得到协方差矩阵特征值和特征向量的概率解释。
设 $X$ 是 $\mathbb R^n$ 中的随机向量，其协方差矩阵的特征值为 $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n\ge0$，对应特征向量为 $v_1,\ldots,v_n$。则
$$ \lambda_k = \max_{\substack{ v\perp\{v_1,\ldots,v_{k-1}\}\\ \|v\|_2=1 }} \operatorname{Var}(\langle X,v\rangle), $$并且最大值在 $v_k$ 处取得。
设随机向量 $X\in\mathbb R^n$ 表示数据，例如第 59 页提到的基因数据。根据 Corollary 3.2.3，协方差矩阵的首个特征向量 $v_1$ 给出第一主成分，也就是数据展开最充分的方向；$\lambda_1$ 是该方向上的方差。下一个特征向量 $v_2$ 给出在剩余正交方向中捕捉数据方差的第二好方向，对应方差为 $\lambda_2$，依此类推。见图 3.3。Exercise 3.4 会给出 explained variance 的更一般解释。
真实数据中经常只有少数几个特征值 $\lambda_i$ 很大并携带信息，其余特征值较小，通常被视为噪声。在这种情况下，少数几个主成分就能捕捉数据大部分变异。尽管数据生活在高维空间 $\mathbb R^n$ 中，它本质上接近低维，围绕前几个主成分 $v_i$ 张成的子空间 $E$ 聚集。
Principal Component Analysis（PCA）就是寻找前几个主成分 $v_i$，再把数据投影到它们张成的子空间 $E$ 上。这会降低数据维度，使分析更容易。如果 $E$ 是二维或三维的，PCA 还可用于可视化数据。
3.2.3 各向同性分布
你可能记得，在基础概率课程中，假设随机变量均值为零、方差为一通常很方便。这个思想可推广到高维，其中各向同性是单位方差概念的高维版本。
$\mathbb R^n$ 中的随机向量 $X$ 称为各向同性，如果
$$ \mathbb EXX^{\mathsf T}=I_n, $$其中 $I_n$ 表示 $\mathbb R^n$ 中的单位矩阵。
由 Proposition 3.2.1 可知，$X$ 各向同性当且仅当
$$ \mathbb E\langle X,v\rangle^2 = \|v\|_2^2 \quad\text{for any fixed vector }v\in\mathbb R^n. \tag{3.9} $$
请检查“only if”的方向。因为右侧不依赖于 $v$ 的方向，(3.9) 实质上说明：各向同性分布在所有方向上展开程度相同。
回忆一维情形：任意方差为正的随机变量 $X$ 都可通过平移和缩放化为 standard score，即均值为零、方差为一的随机变量
$$ Z=\frac{X-\mu}{\sqrt{\operatorname{Var}(X)}}, \qquad X=\mu+\operatorname{Var}(X)^{1/2}Z. $$
高维中也有同样思想。任意协方差矩阵可逆的随机向量 $X$，都可通过平移和线性缩放化为 standard score：
$$ Z=\operatorname{cov}(X)^{-1/2}(X-\mu), \qquad X=\mu+\operatorname{cov}(X)^{1/2}Z. \tag{3.10} $$
这通常允许我们不失一般性地假设随机向量均值为零且各向同性。即使协方差矩阵不可逆，这个思想仍然有效：任意随机向量 $X$ 仍可写成
$$ X=\mu+\operatorname{cov}(X)^{1/2}Z, $$
其中 $Z$ 是某个均值为零、各向同性的随机向量；见 Exercise 3.10。
3.3 高维分布示例
下面给出几类基本的高维分布示例。
3.3.1 标准正态分布
最具代表性的高维分布是 Gaussian 分布，也称 multivariate normal 分布。若随机向量
$$ Z=(Z_1,\ldots,Z_n) $$
的坐标 $Z_i$ 是独立标准正态随机变量 $N(0,1)$，则称 $Z$ 在 $\mathbb R^n$ 中服从标准正态分布，记作
$$ Z\sim N(0,I_n). $$
$Z$ 的密度是 $n$ 个标准正态密度的乘积：
$$ f_Z(z) = \prod_{i=1}^n\frac1{\sqrt{2\pi}}e^{-z_i^2/2} = \frac1{(2\pi)^{n/2}}e^{-\|z\|_2^2/2}, \qquad z\in\mathbb R^n. \tag{3.11} $$
标准正态分布是各向同性的，请自行检查。
注意，$f_Z(z)$ 只依赖于向量 $z$ 的长度，而不依赖方向。因此标准正态密度是旋转不变的，也就是说任意旋转都不会改变它。形式化地说：
设 $Z\sim N(0,I_n)$，$U$ 是固定的 $n\times n$ 正交矩阵。则
$$ UZ\sim N(0,I_n). $$特别地，考察 $UZ$ 的第一个坐标，有
$$ (UZ)_1=\langle U_1,Z\rangle\sim N(0,1), $$
其中 $U_1$ 表示 $U$ 的第一行。因为这一行可以是 $\mathbb R^n$ 中任意单位向量，所以标准正态分布的所有一维边缘都是标准正态。更一般地，缩放后得到：
设 $Z\sim N(0,I_n)$，$v\in\mathbb R^n$ 固定。则
$$ \langle Z,v\rangle \sim N(0,\|v\|_2^2). $$这推出一个基础概率课程中的经典结论。
设 $X_i\sim N(\mu_i,\sigma_i^2)$ 相互独立。则
$$ \sum_{i=1}^n X_i \sim N(\mu,\sigma^2), \qquad \mu=\sum_{i=1}^n\mu_i, \quad \sigma^2=\sum_{i=1}^n\sigma_i^2. $$可写 $X_i=\mu_i+\sigma_iZ_i$，其中 $Z_i$ 是独立标准正态随机变量。于是
$$ \sum_{i=1}^nX_i = \mu+\sum_{i=1}^n\sigma_iZ_i = \mu+\langle Z,v\rangle, \qquad v=(\sigma_1,\ldots,\sigma_n). $$由 Corollary 3.3.2，$\langle Z,v\rangle\sim N(0,\sigma^2)$，所以 $\mu+\langle Z,v\rangle\sim N(\mu,\sigma^2)$。
3.3.2 一般正态分布
回忆 Section 1.7：若随机变量 $X$ 可由标准正态随机变量 $Z\sim N(0,1)$ 平移和缩放得到，也就是
$$ X=\mu+\sigma Z, $$
则称 $X$ 服从正态分布。这样的 $X$ 均值为 $\mu$，方差为 $\sigma^2$，记作 $X\sim N(\mu,\sigma^2)$。现在把这个思想推广到高维。
$\mathbb R^n$ 中的随机向量 $X$ 称为正态分布，如果它可由某个标准正态随机向量 $Z\sim N(0,I_k)$ 经过仿射变换得到，即
$$ X=\mu+AZ, $$其中 $\mu\in\mathbb R^n$ 固定，$A$ 是 $n\times k$ 矩阵。这样的 $X$ 均值为 $\mu$，协方差矩阵为 $\Sigma=AA^{\mathsf T}$，记作 $X\sim N(\mu,\Sigma)$。
$X$ 的分布由 $\mu$ 和 $\Sigma$ 唯一决定。具体地，若 $\Sigma=AA^{\mathsf T}$，则 $X$ 与
$$ Y=\mu+\Sigma^{1/2}Z', \qquad Z'\sim N(0,I_n), \tag{3.12} $$具有相同分布。
我们使用 Cramér-Wold device 的一个版本：$\mathbb R^n$ 中随机向量的所有一维边缘分布唯一决定其联合分布。也就是说，若对所有 $u\in\mathbb R^n$，$\langle X,u\rangle$ 与 $\langle Y,u\rangle$ 同分布，则 $X$ 与 $Y$ 同分布。
只需检查 $AZ$ 与 $\Sigma^{1/2}Z'$ 同分布。由 Corollary 3.3.2，对每个 $v\in\mathbb R^n$，
$$ \langle AZ,v\rangle = \langle Z,A^{\mathsf T}v\rangle \sim N(0,\|A^{\mathsf T}v\|_2^2), $$且
$$ \langle \Sigma^{1/2}Z',v\rangle \sim N(0,\|\Sigma^{1/2}v\|_2^2). $$又因为 $\Sigma=AA^{\mathsf T}$，有 $\|A^{\mathsf T}v\|_2^2=\|\Sigma^{1/2}v\|_2^2$。因此 $AZ$ 与 $\Sigma^{1/2}Z'$ 的所有一维边缘相同，Cramér-Wold device 完成证明。
如果 $\Sigma$ 可逆，那么 $X$ 的密度存在，并且可用 $\mu$ 和 $\Sigma$ 表示。公式看上去较复杂，但含义很简单：一般正态密度就是标准正态密度 (3.11) 的仿射变换。
若 $\Sigma$ 可逆，且 $X\sim N(\mu,\Sigma)$，则 $X$ 的概率密度函数为
$$ f(x) = \frac1{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\left[ -\frac12(x-\mu)^{\mathsf T}\Sigma^{-1}(x-\mu) \right], \qquad x\in\mathbb R^n. \tag{3.13} $$这里 $|\Sigma|$ 表示 $\Sigma$ 的行列式。
你将在 Exercise 3.15 中通过变量替换证明这个公式。图 3.4 展示了两个多元正态分布密度的例子。
你可能记得，独立随机变量一定不相关；但反过来并不总成立。不过，对 jointly normal 随机变量，反方向也成立。
若随机向量 $X=(X_1,\ldots,X_n)$ 服从正态分布，则称随机变量 $X_1,\ldots,X_n$ jointly normal。联合正态随机变量相互独立，当且仅当它们两两不相关。
若 $X_i$ 不相关，则 $X$ 的协方差矩阵是对角矩阵。于是密度 (3.13) 可分解为
$$ f(x)=f_1(x_1)\cdots f_n(x_n), \qquad x=(x_1,\ldots,x_n)\in\mathbb R^n. $$回忆独立性的经典判据：联合密度可分解为边缘密度乘积，当且仅当随机变量相互独立。
注意：某些正态随机变量并不是 jointly normal；它们可以不相关但不独立，见 Exercise 3.17。
3.3.3 球面均匀分布
各向同性随机向量的坐标总是不相关，但不一定独立。球面均匀分布就是这种情形。
以原点为中心、半径为 $\sqrt n$ 的欧氏球面上的均匀分布
$$ \operatorname{Unif}(\sqrt n\,S^{n-1}) $$是各向同性的。
先令 $X=(X_1,\ldots,X_n)\sim\operatorname{Unif}(S^{n-1})$。由对称性，对任意 $i\ne j$，坐标对 $(X_i,X_j)$ 与 $(-X_i,X_j)$ 同分布。因此
$$ \mathbb EX_iX_j=-\mathbb EX_iX_j, $$从而 $\mathbb EX_iX_j=0$。另一方面，总有 $\|X\|_2=1$，所以
$$ 1=\mathbb E\|X\|_2^2 = \mathbb EX_1^2+\cdots+\mathbb EX_n^2. $$由于 $X_i$ 同分布，上式中 $n$ 项相同，因此 $\mathbb EX_i^2=1/n$。于是 $\sqrt n\,X$ 的坐标不相关，且二阶矩等于 $1$，所以 $\sqrt n\,X$ 各向同性。
各向同性随机向量几乎正交
高维空间经常违背低维直觉。随机选取两个点，它们很可能几乎正交。
具体地，令 $X,Y$ 是独立随机向量，均匀分布在单位球面 $S^{n-1}$ 上。由 Proposition 3.3.8，$\sqrt n\,X$ 与 $\sqrt n\,Y$ 独立同分布且各向同性。由 Proposition 3.2.1(c)，
$$ \mathbb E\langle \sqrt n\,X,\sqrt n\,Y\rangle^2 = \operatorname{tr}(I_n) =n. $$
两边除以 $n^2$，得到
$$ \mathbb E\langle X,Y\rangle^2 = \frac1n. $$
再由 Markov 不等式，
$$ |\langle X,Y\rangle| = O(1/\sqrt n) \quad\text{with high probability}. \tag{3.14} $$
这说明 $X$ 与 $Y$ 通常几乎正交。低维情形完全不同，例如平面中两条随机方向的平均夹角为 $\pi/4$。维度越高，空间越宽，随机方向越容易彼此分散。
Gaussian 分布与球面分布很相似
球面均匀分布和标准正态分布都具有旋转不变性。因此若 $g\sim N(0,I_n)$，则归一化向量 $g/\|g\|_2$ 在 $S^{n-1}$ 上也有旋转不变分布。而球面上的旋转不变概率分布是唯一的，所以
$$ g\sim N(0,I_n) \quad\Longrightarrow\quad \frac{g}{\|g\|_2} \sim \operatorname{Unif}(S^{n-1}). \tag{3.15} $$
标准正态分布 $N(0,I_n)$ 的密度 (3.11) 在原点处最大，这可能让人误以为 $g\sim N(0,I_n)$ 会集中在原点附近。但 Section 3.1 已经说明并非如此。正态分布实际集中在半径 $\sqrt n$ 附近的薄球壳上：
$$ \|g\|_2\approx\sqrt n \quad\text{with high probability}. \tag{3.16} $$
把它与 (3.15) 结合，可以非正式地说：标准正态分布大致类似于半径 $\sqrt n$ 球面上的均匀分布：
$$ N(0,I_n) \approx \operatorname{Unif}(\sqrt n\,S^{n-1}). \tag{3.17} $$
这与低维直觉相反，见图 3.5。关键在于：原点附近几乎没有体积。半径为 $o(\sqrt n)$ 的球体积呈指数小（你将在 Exercise 4.27 中计算），抵消了密度在原点处的峰值，使随机向量远离 $0$。Exercise 3.7 会让你亲自检验这一点。
球面的一维投影近似正态
对启发式 (3.17) 的严格版本是：球面均匀分布的一维边缘近似正态。虽然后文不会用到这个漂亮事实，我们仍然证明它，并把它看作 Berry-Esseen 中心极限定理 2.1.4 的“球面版本”。
设 $X$ 均匀分布在 $\mathbb R^n$ 的单位球面上，即 $X\sim\operatorname{Unif}(S^{n-1})$。则
$$ \sqrt n\,\langle X,v\rangle \to N(0,1) \quad\text{in distribution} $$当 $n\to\infty$。事实上，分布函数一致收敛：
$$ \sup_{v\in S^{n-1}}\sup_{t\in\mathbb R} \left| \mathbb P\{\sqrt n\,\langle X,v\rangle\le t\} - \mathbb P\{g_1\le t\} \right| \to0, $$其中 $g_1\sim N(0,1)$。
由 (3.15)，可令 $X=g/\|g\|_2$，其中 $g\sim N(0,I_n)$。由旋转不变性，$\langle X,v\rangle$ 的分布对所有 $v$ 相同，因此可取 $v=(1,0,\ldots,0)$，于是
$$ \langle X,v\rangle = \frac{g_1}{\|g\|_2}. $$启发式 (3.16) 表明 $\|g\|_2$ 可被 $\sqrt n$ 替代。为严格证明，使用一个分解技巧：在“好事件”上使用这个近似，在“坏事件”上用其概率很小来忽略。
由 (3.2)，好事件
$$ E_n := \left\{ \left|\|g\|_2-\sqrt n\right| \le \ln n \right\} $$以高概率发生；记 $p_n=\mathbb P(E_n^c)\to0$。
若 $E_n$ 发生且 $t\ge0$，则事件 $\sqrt n\,\langle X,v\rangle\le t$ 蕴含
$$ g_1 \le \frac{t\|g\|_2}{\sqrt n} \le t\left(1+\frac{\ln n}{\sqrt n}\right) =:t_n. $$把事件按 $E_n$ 是否发生拆开，得到
$$ \begin{aligned} \mathbb P\{\sqrt n\,\langle X,v\rangle\le t\} &\le \mathbb P\{\sqrt n\,\langle X,v\rangle\le t\text{ and }E_n\} +\mathbb P(E_n^c) \\ &\le \mathbb P\{g_1\le t_n\}+p_n. \end{aligned} $$因此
$$ \mathbb P\{\sqrt n\,\langle X,v\rangle\le t\} - \mathbb P\{g_1\le t\} \le \mathbb P\{g_1\in[t,t_n]\}+p_n. \tag{3.18} $$$g_1$ 的密度在 $[t,t_n]$ 上由 $e^{-t^2/2}$ 控制，所以
$$ (3.18) \le e^{-t^2/2}(t_n-t)+p_n = e^{-t^2/2}t\frac{\ln n}{\sqrt n}+p_n \le \frac{C\ln n}{\sqrt n}+p_n. $$右端不依赖于 $v$ 或 $t$，并且随 $n\to\infty$ 收敛到 $0$。类似论证可给出反向差值 $\mathbb P\{g_1\le t\}-\mathbb P\{\sqrt n\,\langle X,v\rangle\le t\}$ 的同样控制。合并两边即得结论。
半径 $\sqrt n$ 球面上均匀分布的一维边缘密度可以显式计算。你将在 Exercise 3.27 中看到，它正比于
$$ \left(1-\frac{x^2}{n}\right)^{(n-3)/2}. $$当 $n$ 很大时，这近似于 $e^{-x^2/2}$，与 Gaussian 极限一致。
3.3.4 凸集上的均匀分布
这个例子来自凸几何和计算几何。若有界凸集 $K\subset\mathbb R^n$ 具有非空内部，则称 $K$ 为 convex body。令 $X$ 在 $K$ 上均匀分布：
$$ X\sim\operatorname{Unif}(K). $$
$X$ 的密度在 $K$ 上等于 $1/\operatorname{Vol}(K)$，在 $K$ 外等于 $0$。$X$ 的均值
$$ \mu=\mathbb EX = \frac1{\operatorname{Vol}(K)} \int_K x\,dx $$
是 $K$ 的重心。若 $\Sigma=\operatorname{cov}(X)$ 是 $K$ 的协方差矩阵，则 standard score
$$ Z:=\Sigma^{-1/2}(X-\mu) $$
是各向同性随机向量，正如我们在 (3.10) 中观察到的。同时，$Z$ 均匀分布在 $K$ 的仿射变换副本上：
$$ Z\sim \operatorname{Unif}\left(\Sigma^{-1/2}(K-\mu)\right). $$
请检查这一点。总结一下，我们找到了一个仿射变换 $T$，使得 $T(K)$ 上的均匀分布是各向同性的。凸体 $T(K)$ 本身常被称为 isotropic convex body。
在算法凸几何中，可以把各向同性凸体 $T(K)$ 看作 $K$ 的良条件版本，其中 $T$ 扮演预条件器的角色，见图 3.6。像计算 $K$ 体积这样的算法，通常在 $K$ 条件良好时工作得更好。
3.3.5 Frames
frame 的概念广泛用于信号处理。它推广了基的概念，但不要求线性无关。frame 与离散各向同性分布有密切联系。
对任意向量 $u_1,\ldots,u_N\in\mathbb R^n$，以下命题等价：
(i) Parseval identity. 对每个 $x\in\mathbb R^n$，
$$ \|x\|_2^2 = \sum_{i=1}^N\langle u_i,x\rangle^2. $$(ii) Frame expansion. 对每个 $x\in\mathbb R^n$，
$$ x= \sum_{i=1}^N\langle u_i,x\rangle u_i. $$(iii) 单位矩阵分解。
$$ I_n=\sum_{i=1}^N u_i u_i^{\mathsf T}. $$(iv) 各向同性。 随机向量
$$ X\sim \operatorname{Unif}\{\sqrt N\,u_1,\ldots,\sqrt N\,u_N\} $$是各向同性的。
满足这些等价性质的向量族称为 Parseval frame。
(i) $\Rightarrow$ (iv). (i) 中的恒等式可写作
$$ \|x\|_2^2 = \frac1N \sum_{i=1}^N \left\langle \sqrt N\,u_i,x\right\rangle^2 = \mathbb E\langle X,x\rangle^2. $$它对所有 $x\in\mathbb R^n$ 成立，所以由 (3.9)，$X$ 各向同性。
(iv) $\Rightarrow$ (iii). $X$ 各向同性意味着
$$ I_n = \mathbb EXX^{\mathsf T} = \frac1N\sum_{i=1}^N (\sqrt N\,u_i)(\sqrt N\,u_i)^{\mathsf T} = \sum_{i=1}^N u_i u_i^{\mathsf T}. $$(iii) $\Rightarrow$ (ii) 只需两侧同乘 $x$。最后，(ii) $\Rightarrow$ (i) 来自两侧与 $x$ 取内积。
$\mathbb R^n$ 中的标准基 $\{e_1,\ldots,e_n\}$ 是 Parseval frame。因此，坐标随机向量
$$ X\sim \operatorname{Unif} \{\sqrt n\,e_1,\ldots,\sqrt n\,e_n\} $$是各向同性的。在所有高维分布中，Gaussian 分布通常最容易处理，可以把它看作“最好”的分布；坐标分布高度离散，通常可看作“最坏”的分布。
Parseval frame 的一个经典非线性无关例子，是半径为 $\sqrt{2/N}$ 的圆上 $N$ 个等间距点。图 3.7 展示了其中 $N=3$ 的情形；可尝试 Exercise 3.30。
最后，再给出两个各向同性分布的例子。
Rademacher 随机向量 $X=(X_1,\ldots,X_n)$ 的坐标是独立 Rademacher 随机变量。等价地，$X$ 在 $\mathbb R^n$ 中的单位离散立方体上均匀分布：
$$ X\sim \operatorname{Unif}(\{-1,1\}^n). $$Rademacher 分布是各向同性的，请自行检查。
更一般地，任意随机向量 $X=(X_1,\ldots,X_n)$，只要坐标 $X_i$ 独立、均值为零、方差为一，就是各向同性的。请自行验证。
3.4 高维中的次高斯分布
我们把第 2.6 节引入的次高斯分布概念推广到高维。为了获得动机，先注意多元正态分布完全由它的一维边缘分布，也就是到直线上的投影决定：$\mathbb R^n$ 中的随机向量 $X$ 是正态的，当且仅当对任意 $v\in\mathbb R^n$，$\langle X,v\rangle$ 都是正态随机变量；见 Exercise 3.16。这提示了定义多元次高斯分布的自然方式。
$\mathbb R^n$ 中的随机向量 $X$ 称为次高斯随机向量，如果对所有 $v\in\mathbb R^n$，一维边缘 $\langle X,v\rangle$ 都是次高斯随机变量。$X$ 的次高斯范数定义为所有单位向量方向上一维边缘次高斯范数的最大值：
$$ \|X\|_{\psi_2} = \sup_{v\in S^{n-1}} \|\langle X,v\rangle\|_{\psi_2}. $$下面看几个基本例子。
3.4.1 Gaussian, Rademacher, and more
具有独立次高斯坐标的随机向量给出了大量例子。
设
$$ X=(X_1,\ldots,X_n) $$是 $\mathbb R^n$ 中的随机向量，其坐标 $X_i$ 相互独立、均值为零且次高斯。那么 $X$ 是次高斯随机向量，并且
$$ \max_{i\le n}\|X_i\|_{\psi_2} \le \|X\|_{\psi_2} \le C\max_{i\le n}\|X_i\|_{\psi_2}. $$下界来自在 Definition 3.4.1 中把 $v$ 取为标准基向量。为证明上界，任取 $v=(v_1,\ldots,v_n)\in S^{n-1}$。由 Proposition 2.7.1，
$$ \begin{aligned} \|\langle X,v\rangle\|_{\psi_2}^2 &= \left\|\sum_{i=1}^n v_iX_i\right\|_{\psi_2}^2 \\ &\le C\sum_{i=1}^n\|v_iX_i\|_{\psi_2}^2 \\ &= C\sum_{i=1}^n v_i^2\|X_i\|_{\psi_2}^2 \\ &\le C\max_{i\le n}\|X_i\|_{\psi_2}^2, \end{aligned} $$其中最后一步使用了 $\sum_{i=1}^n v_i^2=1$。由于 $v$ 任意，证明完成。
作为上面引理的直接结果，Example 3.3.14 中引入的 Rademacher 随机向量是次高斯随机向量，并且
$$ c_1\le \|X\|_{\psi_2}\le c_2, $$其中 $c_1,c_2>0$ 是绝对常数。
标准正态随机向量 $X\sim N(0,I_n)$ 也具有同样性质。你将在 Exercise 3.38 中把这个结论强化并推广到 $N(0,\Sigma)$。
3.4.2 球面均匀分布
投影中心极限定理 3.3.9 告诉我们：$\mathbb R^n$ 中半径为 $\sqrt n$ 的球面上的均匀分布，其一维边缘近似高斯。因此下一个自然问题是：这些边缘是否是次高斯的，并且其次高斯范数是否由一个常数控制？下面证明答案是肯定的。这个事实可以看作投影中心极限定理的集中版本，正如第 2.2 节 Hoeffding 不等式是经典中心极限定理的集中版本。
设 $X$ 是 $\mathbb R^n$ 中单位球面上的均匀随机向量，即
$$ X\sim \operatorname{Unif}(S^{n-1}). $$那么对任意 $v\in S^{n-1}$ 和 $t\ge 0$，有
$$ \mathbb P\{\langle X,v\rangle\ge t\} \le 2\exp\left(-\frac{t^2n}{2}\right). \tag{3.19} $$特别地，$X$ 是次高斯随机向量，并且
$$ \|X\|_{\psi_2}\le \frac{C}{\sqrt n}. $$ 查看学习笔记完整证明由旋转不变性，可假设
$$ X=\frac{g}{\|g\|_2}, \qquad g\sim N(0,I_n), $$这正是 (3.15) 中提到的表示。仍由旋转不变性，$\langle X,v\rangle$ 的分布不依赖于 $v$，所以取 $v=(1,0,\ldots,0)$ 即可，此时 $\langle X,v\rangle=X_1$。
于是事件 $\langle X,v\rangle\ge t$ 等价于
$$ g_1\ge t\|g\|_2. $$将两边平方，把右侧的 $g_1^2$ 移到左侧并化简，可得
$$ g_1\ge s\|\bar g\|_2, \qquad s=\frac{t}{\sqrt{1-t^2}}, \qquad \bar g=(g_2,\ldots,g_n). $$为了求这个事件的概率，使用第 1.5 节的条件化技巧。先对 $\bar g$ 条件化，从而固定 $\|\bar g\|_2$；这不会改变 $g_1$ 的分布，因为 $g_1$ 与 $\bar g$ 独立。再对 $\bar g$ 取期望解除条件。全期望公式 (1.16) 给出
$$ \begin{aligned} \mathbb P\{\langle X,v\rangle\ge t\} &= \mathbb P\{g_1\ge s\|\bar g\|_2\} \\ &= \mathbb E\left[ \mathbb P\{g_1\ge s\|\bar g\|_2\mid \bar g\} \right]. \end{aligned} \tag{3.20} $$在条件化之后，$s\|\bar g\|_2$ 是固定值，所以上式中的条件概率就是一个高斯尾概率。使用 Exercise 2.6 中的界 $\mathbb P\{g_1\ge u\}\le \exp(-u^2/2)$，得到
$$ \begin{aligned} (3.20) &\le \mathbb E\exp\left( -\frac{s^2\|\bar g\|_2^2}{2} \right) \\ &= \left[ \mathbb E\exp\left( -\frac{s^2g_1^2}{2} \right) \right]^{n-1}. \end{aligned} \tag{3.21} $$最后一个等式来自 $\|\bar g\|_2^2=g_2^2+\cdots+g_n^2$，以及所有 $g_i$ 独立同分布且 $g_i\sim N(0,1)$。通过把期望写成积分并作变量替换，可验证
$$ \mathbb E\exp\left(-\frac{s^2g_1^2}{2}\right) = \frac{1}{\sqrt{1+s^2}}. $$ 查看学习笔记：Gaussian Laplace transform 验证因此
$$ (3.21) = \left(\frac{1}{1+s^2}\right)^{(n-1)/2} = (1-t^2)^{(n-1)/2} \le \exp\left(-\frac{t^2(n-1)}{2}\right), $$其中使用了对所有 $x$ 成立的 $1-x\le e^{-x}$。
最后，若 $t\ge 1$，则 (3.19) 左侧概率为零，因为 Cauchy-Schwarz 不等式给出 $\langle X,v\rangle\le \|X\|_2\|v\|_2=1$。若 $0\le t\le 1$，则
$$ \exp\left(-\frac{t^2(n-1)}{2}\right) \le e^{1/2}\exp\left(-\frac{t^2n}{2}\right) \le 2\exp\left(-\frac{t^2n}{2}\right). $$于是 (3.19) 得证。由球面对称性同样可控制左尾，从而一维边缘的双侧次高斯尾界给出 $\|X\|_{\psi_2}\le C/\sqrt n$。
3.4.3 反例
$\mathbb R^n$ 中有些分布虽然在定性意义上是次高斯的，但次高斯范数非常大，因此在定量分析中把它们当作次高斯分布并不实用。下面是几个例子。
设 $K$ 是 $\mathbb R^n$ 中的凸体，并且
$$ X\sim \operatorname{Unif}(K) $$像第 3.3.4 节那样是各向同性的。定性地说，$X$ 总是次高斯的，因为 $K$ 有界。但定量上如何？$X$ 的次高斯范数是否能由绝对常数控制？
对于某些各向同性凸体，这确实成立，例如单位立方体 $[-1,1]^n$，这可由 Lemma 3.4.2 得到；再如半径为 $\sqrt{n+2}$ 的 Euclidean 球，见 Exercises 3.25 和 3.42。但对另一些凸体，例如各向同性 cross-polytope，也就是 $\ell^1$ 范数下的球，$X$ 的次高斯范数可能随 $n$ 增长；见 Exercise 3.44。
即便如此，一个较弱的结果始终成立：$X$ 的一维边缘是次指数的，并且对所有单位向量 $v$ 都有
$$ \|\langle X,v\rangle\|_{\psi_1}\le C. $$这来自 C. Borell 引理；该引理可由 Brunn-Minkowski 不等式推出，参见 [134, Section 2.2.b3]。
回忆 Example 3.3.12 中的“最坏”各向同性分布：
$$ X\sim \operatorname{Unif} \left\{ \sqrt n\,e_1,\ldots,\sqrt n\,e_n \right\}, $$其中 $\{e_1,\ldots,e_n\}$ 是 $\mathbb R^n$ 的标准基。$X$ 是次高斯的吗？定性意义上，是的：任何只取有限多个值的分布都是次高斯的。但 $X$ 的次高斯范数随 $n$ 增长；你将在 Exercise 3.43 中看到
$$ \|X\|_{\psi_2} \asymp \sqrt{\frac{n}{\log n}}. $$因此，在定量意义上，把 $X$ 看作次高斯随机向量并没有太大用处。
有些各向同性离散分布的次高斯范数可以由常数控制，例如 Example 3.4.3 中的 Rademacher 分布。不过，这类分布必须取指数多个值；见 Exercise 3.46。
特别地，这排除了把 frame（见第 3.3.5 节）当作好的次高斯分布来使用，除非它们有指数多个项；而在这种情况下，它们在实践中通常没有什么用处。
3.5 应用：Grothendieck 不等式与半定规划
在本节和下一节，我们用高维高斯来处理一些看起来与概率毫无关系的问题。我们从 Grothendieck 不等式的概率证明开始。这是一个非常出色的结果，稍后会用来分析计算上困难的问题。
考虑一个实数 $m\times n$ 矩阵 $(a_{ij})$。假设
$$ \left| \sum_{i,j}a_{ij}x_iy_j \right|\le 1 \qquad \text{for any } x_i,y_j\in\{-1,1\}. $$那么，对任意 Hilbert 空间 $H$，都有
$$ \left| \sum_{i,j}a_{ij}\langle u_i,v_j\rangle \right| \le K \qquad \text{for any unit vectors }u_i,v_j\in H. $$这里 $K\le 1.783$ 是一个绝对常数。
查看学习笔记完整证明这个定理的陈述中没有任何随机性，但我们的证明将是概率性的。实际上，本书会给出两个 Grothendieck 不等式的证明。本节的证明常数要差得多，只能得到 $K\le 14.1$；第 3.7 节中的另一种方法会把常数改进到 Theorem 3.5.1 中陈述的 $K\le 1.783$。
进入第一个论证之前，先记录一个简单观察。
Grothendieck 不等式的假设可以等价地写成：对任意实数 $x_i,y_j$，
$$ \left| \sum_{i,j}a_{ij}x_iy_j \right| \le \max_i|x_i|\cdot \max_j|y_j|. \tag{3.22} $$你将在 Exercise 3.47 中验证这一点。Grothendieck 不等式的结论也可以等价地写成：对任意 Hilbert 空间 $H$ 和任意向量 $u_i,v_j\in H$，
$$ \left| \sum_{i,j}a_{ij}\langle u_i,v_j\rangle \right| \le K\max_i\|u_i\|\cdot \max_j\|v_j\|. \tag{3.23} $$这可由简单缩放得到。
Step 1：约化。 如果允许 $K$ 依赖矩阵 $A=(a_{ij})$，Grothendieck 不等式就会变得平凡；例如 $K=\sum_{ij}|a_{ij}|$ 就足够。令 $K=K(A)$ 表示使结论 (3.23) 对给定矩阵 $A$、任意 Hilbert 空间 $H$ 和任意向量 $u_i,v_j\in H$ 成立的最小数。目标是证明 $K$ 实际上不依赖于 $A$ 以及维数 $m,n$。
由于这里只涉及有限多个向量，可以把它们张成的有限维子空间看作某个欧氏空间。于是，不失一般性，可在 $H=\mathbb R^N$ 且范数为 Euclidean 范数 $\|\cdot\|_2$ 的情形中证明。由 $K=K(A)$ 的定义，可取单位向量 $u_i,v_j\in\mathbb R^N$ 使得
$$ \sum_{i,j}a_{ij}\langle u_i,v_j\rangle=K, \qquad \|u_i\|_2=\|v_j\|_2=1. $$Step 2：引入随机性。 证明的关键思想是用高斯随机变量表达向量 $u_i,v_j$：
$$ U_i:=\langle g,u_i\rangle, \qquad V_j:=\langle g,v_j\rangle, \qquad g\sim N(0,I_N). $$那么 $U_i$ 和 $V_j$ 都是标准正态随机变量，并且它们的相关性精确地等于原向量的内积：
$$ \mathbb E U_iV_j = \langle u_i,v_j\rangle. $$这直接来自 Corollary 3.3.2 和 Exercise 3.9。因此
$$ K = \sum_{i,j}a_{ij}\langle u_i,v_j\rangle = \mathbb E \sum_{i,j}a_{ij}U_iV_j. \tag{3.24} $$暂时假设随机变量 $|U_i|$ 和 $|V_j|$ 几乎必然由某个常数 $R$ 控制。由假设 (3.22)，几乎必然有
$$ \left| \sum_{i,j}a_{ij}U_iV_j \right| \le R^2. $$代入 (3.24) 就得到 $K\le R^2$，证明完成。
Step 3：截断。 上面的推理当然有缺陷，因为高斯随机变量 $U_i,V_j\sim N(0,1)$ 无界。不过它们的尾部足够轻，因而接近于有界。为了落实这个启发式，取截断水平 $R\ge 1$，并作分解
$$ U_i=U_i^-+U_i^+, \qquad U_i^-=U_i\mathbf 1_{\{|U_i|\le R\}}, \qquad U_i^+=U_i\mathbf 1_{\{|U_i|>R\}}. $$同样分解 $V_j=V_j^-+V_j^+$。此时 $U_i^-$ 和 $V_j^-$ 如愿被 $R$ 控制。余项 $U_i^+$ 和 $V_j^+$ 在 $L^2$ 范数中很小：高斯尾界（Exercise 2.4(b)）给出
$$ \|U_i^+\|_{L^2}^2 \le 2\left(R+\frac{1}{R}\right) \frac{1}{\sqrt{2\pi}}e^{-R^2/2} < \frac{4}{R^2}. \tag{3.25} $$对 $V_j^+$ 也有同样的界。
Step 4：拆分和式。 在 (3.24) 中用 $(U_i^-+U_i^+)(V_j^-+V_j^+)$ 替换 $U_iV_j$，并展开求和，得到
$$ K = \underbrace{ \mathbb E\sum_{i,j}a_{ij}U_i^-V_j^- }_{S_-} + \underbrace{ \mathbb E\sum_{i,j}a_{ij}U_i^+V_j^- }_{S_{\pm}} + \underbrace{ \mathbb E\sum_{i,j}a_{ij}U_i^-V_j^+ }_{S_{\mp}} + \underbrace{ \mathbb E\sum_{i,j}a_{ij}U_i^+V_j^+ }_{S_+}. $$下面分别估计各项。$S_-$ 最简单：由构造，$|U_i^-|$ 与 $|V_j^-|$ 都被 $R$ 控制，所以如 Step 2 所述，
$$ S_-\le R^2. $$对 $S_{\pm}$ 不能使用同一推理，因为 $U_i^+$ 无界。将随机变量 $U_i^+$ 和 $V_j^-$ 视为 Hilbert 空间 $L^2$ 中的元素，其内积为 $\langle X,Y\rangle_{L^2}=\mathbb E XY$。于是
$$ S_{\pm} = \sum_{i,j}a_{ij} \langle U_i^+,V_j^-\rangle_{L^2}. $$由 (3.25)，$\|U_i^+\|_{L^2}<2/R$；由构造，$\|V_j^-\|_{L^2}\le \|V_j\|_{L^2}=1$。把 (3.23) 应用于 Hilbert 空间 $H=L^2$，得到
$$ S_{\pm} \le K\cdot \frac{2}{R}. $$另外两项 $S_{\mp}$ 和 $S_+$ 可以用相同方法估计；其中 $S_{\mp}\le 2K/R$，而 $S_+\le 4K/R^2\le 2K/R$（因为本证明最终取 $R=12$）。
Step 5：合并估计。 把四项估计代入 (3.24)，可得
$$ K\le R^2+\frac{6K}{R}. $$取 $R=12$ 并整理，得到 $K\le 288$。若在 (3.25) 中不使用粗略的 $4/R^2$ 上界，而做更精细分析，则可得到 $K\le 14.1$；见 Exercise 3.48。
Grothendieck 不等式的假设常常可以通过令 $x_i=y_i$ 来放松，从而控制一个二次型而不是双线性型。设 $A=(a_{ij})$ 是一个 $n\times n$ 矩阵，它要么是对称正半定的，要么是零对角的。假设
$$ \left| \sum_{i,j}a_{ij}x_ix_j \right| \le 1 \qquad \text{for any }x_i\in\{-1,1\}. $$那么，对任意 Hilbert 空间 $H$，都有
$$ \left| \sum_{i,j}a_{ij}\langle u_i,u_j\rangle \right| \le 2K \qquad \text{for any unit vectors }u_i\in H. $$这里 $K$ 是 Grothendieck 不等式中的绝对常数。你将在 Exercises 3.49 和 3.50 中验证这一点。
3.5.1 半定规划
一些困难的计算问题可以松弛成更容易、计算上更可处理的问题。松弛常常通过半定规划实现，而 Grothendieck 不等式可以帮助我们保证松弛的质量。下面看看这是怎样发生的。
半定规划是如下形式的优化问题：
$$ \operatorname{maximize}\quad \langle A,X\rangle \quad \text{subject to}\quad X\succeq 0,\quad \langle B_i,X\rangle\le b_i \text{ for } i=1,\ldots,N. \tag{3.26} $$这里 $A$ 和 $B_i$ 是给定的 $n\times n$ 矩阵，$b_i$ 是给定数。变量 $X$ 是一个 $n\times n$ 对称正半定矩阵，记作 $X\succeq 0$。内积是 $n\times n$ 矩阵空间上的标准内积：
$$ \langle A,X\rangle = \operatorname{tr}(A^{\mathsf T}X) = \sum_{i,j=1}^n A_{ij}X_{ij}. \tag{3.27} $$如果在 (3.26) 中把最大化改为最小化，仍然得到半定规划；把某些 $\le$ 约束替换为 $\ge$ 或 $=$ 约束也一样。
每个半定规划都是凸规划，因为它是在一个凸矩阵集合上最大化线性函数 $\langle A,X\rangle$。正半定矩阵的集合是凸的；它与约束 $\langle B_i,X\rangle\le b_i$ 定义的半空间相交后仍是凸集。这是好消息，因为凸规划通常在算法上可处理。一般凸规划有高效求解器，半定规划也有专门求解器。
半定松弛
半定规划可以给计算困难的问题提供有效松弛。例如考虑
$$ \operatorname{maximize}\quad \sum_{i,j=1}^n A_{ij}x_ix_j \quad \text{subject to}\quad x_i=\pm 1 \text{ for }i=1,\ldots,n, \tag{3.28} $$
其中 $A$ 是给定的 $n\times n$ 对称矩阵。这是一个二次整数优化问题，其可行集由 $2^n$ 个向量 $x=(x_i)\in\{-1,1\}^n$ 构成。穷举最大值需要指数时间。有没有更聪明的方法？一般来说不太可能，因为 (3.28) 是计算困难的，也就是 NP-hard。
不过，我们仍然可以把问题 (3.28) 松弛为一个半定规划，使它在常数因子内近似最大值。为此，在 (3.28) 中把数 $x_i=\pm 1$ 替换为其高维类似物：$\mathbb R^n$ 中的单位向量 $X_i$。这得到优化问题
$$ \operatorname{maximize}\quad \sum_{i,j=1}^n A_{ij}\langle X_i,X_j\rangle \quad \text{subject to}\quad \|X_i\|_2=1 \text{ for }i=1,\ldots,n. \tag{3.29} $$
优化问题 (3.29) 等价于如下半定规划：
$$ \operatorname{maximize}\quad \langle A,Z\rangle \quad \text{subject to}\quad Z\succeq 0,\quad Z_{ii}=1 \text{ for }i=1,\ldots,n. \tag{3.30} $$回忆向量 $X_1,\ldots,X_n$ 的 Gram 矩阵是矩阵 $Z$，其元素为 $Z_{ij}=\langle X_i,X_j\rangle$。两个问题的等价性来自两个线性代数事实：第一，任意一组向量的 Gram 矩阵都是对称正半定的；第二，反过来，每个对称正半定矩阵都是某组向量的 Gram 矩阵；见 Exercise 3.51。
松弛的保证
现在通过证明 SDP (3.29) 在常数因子内近似 (3.28)，来检查这个半定松弛的精度。
设 $A$ 是 $n\times n$ 对称正半定矩阵。令 $\operatorname{int}(A)$ 表示整数优化问题 (3.28) 中的最大值，令 $\operatorname{sdp}(A)$ 表示半定问题 (3.29) 中的最大值。那么
$$ \operatorname{int}(A) \le \operatorname{sdp}(A) \le 2K\cdot \operatorname{int}(A), $$其中 $K\le 1.783$ 是 Grothendieck 不等式中的常数。
第一个不等式由取 $X_i=(x_i,0,0,\ldots,0)^{\mathsf T}$ 得到：任何整数可行解都给出一个 SDP 可行解，并且目标值相同。第二个不等式来自 Remark 3.5.3 中的二次 Grothendieck 不等式。这里可以去掉绝对值，因为 $A\succeq 0$ 且 Gram 矩阵 $Z=(\langle X_i,X_j\rangle)$ 也正半定，所以 $\sum_{i,j}A_{ij}\langle X_i,X_j\rangle=\langle A,Z\rangle\ge 0$。
虽然 Theorem 3.5.7 帮助我们近似了 (3.28) 的最大值，但它并没有直接说明如何找到实际的解 $x_1,\ldots,x_n$，使其达到这个近似值。我们能否把给出 SDP (3.29) 解的向量 $X_i$ 转换为标签 $x_i=\pm 1$，从而近似求解 (3.28)？
答案是肯定的。不过在处理 (3.30) 之前，我们先在另一个著名的 NP-hard 问题，也就是最大割问题上完成这件事。完成之后，你就可以自己处理 (3.30)，并得到比 $2K$ 更好的近似常数；见 Exercise 3.58。
3.6 应用：图的最大割
下面看看半定松弛如何帮助处理一个著名的 NP-hard 问题：寻找图的最大割。
无向图 $G=(V,E)$ 由顶点集合 $V$ 和边集合 $E$ 构成；每条边是两个顶点组成的无序对。我们只考虑有限简单图，也就是有限、无自环、无重边的图。为方便起见，把顶点标号为整数，即 $V=\{1,\ldots,n\}$。
如果把图 $G$ 的顶点划分为两个不相交子集，那么割就是横跨这两个子集的边数。$G$ 的最大割记为 $\operatorname{maxcut}(G)$，定义为所有顶点划分中割的最大值。图 3.8 给出了示意。
一般来说，寻找最大割是计算困难问题，即 NP-hard。
3.6.1 一个简单的 0.5 近似算法
我们先用第 3.5.1 节的方法，把最大割问题松弛为一个半定规划。为此，首先把问题翻译成线性代数语言。
顶点为 $V=\{1,\ldots,n\}$ 的图 $G$ 的邻接矩阵 $A$ 是一个对称的 $n\times n$ 矩阵：如果顶点 $i$ 和 $j$ 之间有边，则 $A_{ij}=1$；否则 $A_{ij}=0$。
顶点的一个二分划分可以由标签向量
$$ x=(x_i)\in\{-1,1\}^n $$
描述，其中 $x_i$ 的符号表示顶点 $i$ 属于哪一侧。例如，在图 3.8 中，三个黑色顶点可以取 $x_i=1$，四个白色顶点可以取 $x_i=-1$。这个划分给出的割就是标签相反的顶点之间的边数：
$$ \operatorname{cut}(G,x) = \frac{1}{2} \sum_{i,j:\,x_ix_j=-1}A_{ij} = \frac{1}{4} \sum_{i,j=1}^n A_{ij}(1-x_ix_j). \tag{3.31} $$
最大割可通过在所有划分 $x$ 上最大化 $\operatorname{cut}(G,x)$ 得到：
$$ \operatorname{maxcut}(G) = \frac{1}{4} \max \left\{ \sum_{i,j=1}^n A_{ij}(1-x_ix_j): x_i=\pm 1\ \forall i \right\}. \tag{3.32} $$
先给出一个简单的最大割 $0.5$ 近似算法：它能找到至少包含图中一半边数的割。
如果在所有 $2^n$ 个顶点划分中均匀随机地把 $G$ 的顶点分成两部分，那么期望割至少是 $0.5\,\operatorname{maxcut}(G)$。
随机割由 Rademacher 随机向量 $x$ 生成，其坐标是独立 Rademacher 随机变量；回忆 Example 3.3.14。于是对 $i\ne j$，有 $\mathbb E x_ix_j=0$；而当 $i=j$ 时，由于图没有自环，$A_{ij}=0$。因此由期望线性性和 (3.31)，
$$ \mathbb E\operatorname{cut}(G,x) = \frac{1}{4} \sum_{i,j=1}^n A_{ij} = \frac{1}{2}|E| \ge \frac{1}{2}\operatorname{maxcut}(G), $$其中 $|E|$ 表示 $G$ 的边数。证明完成。
3.6.2 半定松弛
现在我们做得更好，给出 Goemans 和 Williamson 提出的最大割 $0.878$ 近似算法。它基于 NP-hard 问题 (3.32) 的半定松弛。结合 (3.29)，这个松弛很容易猜出：考虑半定问题
$$ \operatorname{sdp}(G) := \frac{1}{4} \max \left\{ \sum_{i,j=1}^n A_{ij} \bigl(1-\langle X_i,X_j\rangle\bigr): X_i\in\mathbb R^n,\ \|X_i\|_2=1\ \forall i \right\}. \tag{3.33} $$
它为什么是一个半定规划？理由与 Proposition 3.5.6 相同：向量内积矩阵可用正半定 Gram 矩阵表示。
我们将证明 $\operatorname{sdp}(G)$ 在 $0.878$ 因子内近似 $\operatorname{maxcut}(G)$，并说明如何把解 $(X_i)$ 转成实际划分的标签 $x_i=\pm 1$。方法是随机舍入：在 $\mathbb R^n$ 中随机选一个过原点的超平面，把超平面一侧的向量 $X_i$ 标为 $x_i=1$，另一侧标为 $x_i=-1$；见图 3.9。更正式地，取标准正态随机向量 $g\sim N(0,I_n)$，并定义
$$ x_i := \operatorname{sign}\langle X_i,g\rangle, \qquad i=1,\ldots,n. \tag{3.34} $$
设 $G$ 是邻接矩阵为 $A$ 的图。令 $(X_i)$ 是半定规划 (3.33) 的一个解，令 $x=(x_i)$ 是对 $(X_i)$ 做随机舍入得到的标签。那么
$$ \mathbb E\operatorname{cut}(G,x) \ge 0.878\,\operatorname{sdp}(G) \ge 0.878\,\operatorname{maxcut}(G). $$ 查看学习笔记完整证明证明基于一个初等不等式。在证明 Grothendieck 不等式（Theorem 3.5.1）时，我们使用了如下事实：如果 $g\sim N(0,I_n)$，那么对任意固定向量 $u,v\in\mathbb R^n$，
$$ \mathbb E\langle g,u\rangle\langle g,v\rangle = \langle u,v\rangle. $$
这是 Exercise 3.9 的内容。现在需要这个恒等式的一个稍强版本；你将在 Exercise 3.53 中证明它。
设随机向量 $g\sim N(0,I_n)$。那么对任意固定向量 $u,v\in S^{n-1}$，
$$ \mathbb E \operatorname{sign}\langle g,u\rangle \operatorname{sign}\langle g,v\rangle = \frac{2}{\pi}\arcsin\langle u,v\rangle. $$Grothendieck identity 的一个缺点是出现了非线性函数 $\arcsin$，不太方便直接处理。可以用下面的线性下界替换它：
$$ 1-\frac{2}{\pi}\arcsin t = \frac{2}{\pi}\arccos t \ge 0.878(1-t), \qquad t\in[-1,1]. \tag{3.35} $$
这个不等式可以很容易用软件检查；见图 3.10。
由 (3.31) 和期望线性性，
$$ \mathbb E\operatorname{cut}(G,x) = \frac{1}{4} \sum_{i,j=1}^n A_{ij}\bigl(1-\mathbb E x_ix_j\bigr). $$由舍入定义 (3.34)，
$$ \begin{aligned} 1-\mathbb E x_ix_j &= 1- \mathbb E \operatorname{sign}\langle X_i,g\rangle \operatorname{sign}\langle X_j,g\rangle \\ &= 1- \frac{2}{\pi} \arcsin\langle X_i,X_j\rangle \qquad \text{(by Lemma 3.6.5)}\\ &\ge 0.878\bigl(1-\langle X_i,X_j\rangle\bigr) \qquad \text{(by (3.35)).} \end{aligned} $$因此
$$ \mathbb E\operatorname{cut}(G,x) \ge 0.878\cdot \frac{1}{4} \sum_{i,j=1}^n A_{ij}\bigl(1-\langle X_i,X_j\rangle\bigr) = 0.878\,\operatorname{sdp}(G). $$这证明了定理中的第一个不等式。第二个不等式是直接的，因为 $\operatorname{sdp}(G)\ge \operatorname{maxcut}(G)$：每个整数划分都可嵌入为一个可行的向量解。
现在可以尝试 Exercises 3.56-3.58，以便更熟悉随机舍入、Grothendieck identity 和半定松弛。
3.7 核技巧与 Grothendieck 不等式的加强
第 3.5 节给出的 Grothendieck 不等式证明只能得到非常松的绝对常数界。现在我们换一种方法，得到目前已知几乎最好的界：
$$ K\le 1.783. $$
新的论证建立在 Grothendieck identity（Lemma 3.6.5）之上，但函数 $\arcsin(x)$ 的非线性带来了困难。如果没有这个非线性，并且我们拥有理想恒等式
$$ \mathbb E \operatorname{sign}\langle g,u\rangle \operatorname{sign}\langle g,v\rangle = \frac{2}{\pi}\langle u,v\rangle, $$
那么 Grothendieck 不等式（Theorem 3.5.1）会很容易推出：
$$ \frac{2}{\pi} \sum_{i,j}a_{ij}\langle u_i,v_j\rangle = \mathbb E \sum_{i,j}a_{ij} \underbrace{\operatorname{sign}\langle g,u_i\rangle}_{x_i} \underbrace{\operatorname{sign}\langle g,v_j\rangle}_{y_j} \le 1. $$
最后一步来自 Grothendieck 不等式的假设，因为 $x_i,y_j\in\{-1,1\}$。这样会得到 $K\le \pi/2\approx 1.57$。
当然，这个论证是错误的。为了正确处理内积函数 $f(\langle u,v\rangle)$ 的非线性，可以使用一个非常强大的技巧：把它改写成另一个 Hilbert 空间中某些新向量 $u',v'$ 的线性内积 $\langle u',v'\rangle$。在机器学习文献中，这称为 kernel trick。
我们将显式构造非线性变换 $u'=\Phi(u)$ 和 $v'=\Psi(v)$。描述这些变换的最好方式是使用张量；张量可看作矩阵在更高维度上的推广。
3.7.1 张量
张量可以理解为多维数组。矩阵有两个维度（行和列），而张量可以有任意多个维度。
一个 $k$ 阶张量 $(a_{i_1\ldots i_k})$ 是一个 $n_1\times n_2\times\cdots\times n_k$ 的实数数组。$\mathbb R^{n_1\times\cdots\times n_k}$ 上的标准内积定义了张量的内积：对 $A=(a_{i_1\ldots i_k})$ 和 $B=(b_{i_1\ldots i_k})$，令
$$ \langle A,B\rangle := \sum_{i_1,\ldots,i_k} a_{i_1\ldots i_k}b_{i_1\ldots i_k}. \tag{3.36} $$向量是一阶张量，矩阵是二阶张量。张量内积 (3.36) 推广了向量内积 (1.2) 和矩阵内积 (3.27)。
对向量 $u\in\mathbb R^n$，$k$ 阶张量积 $u\otimes\cdots\otimes u$ 是一个张量，其元素是 $u$ 的所有 $k$ 元坐标乘积：
$$ u^{\otimes k} := u\otimes\cdots\otimes u = (u_{i_1}\cdots u_{i_k}) \in \mathbb R^{n\times\cdots\times n}. $$例如，当 $k=2$ 时，张量积 $u\otimes u$ 是 $n\times n$ 矩阵
$$ u\otimes u = (u_iu_j)_{i,j=1}^n = uu^{\mathsf T}. $$对任意向量 $u,v\in\mathbb R^n$ 和任意 $k\in\mathbb N$，有
$$ \langle u^{\otimes k},v^{\otimes k}\rangle = \langle u,v\rangle^k. $$以 $k=3$ 为例检查：
$$ \begin{aligned} \langle u^{\otimes 3},v^{\otimes 3}\rangle &= \sum_{i,j,\ell=1}^n (u_iu_ju_\ell)(v_iv_jv_\ell)\\ &= \left(\sum_{i=1}^n u_iv_i\right) \left(\sum_{j=1}^n u_jv_j\right) \left(\sum_{\ell=1}^n u_\ell v_\ell\right)\\ &= \langle u,v\rangle^3. \end{aligned} $$一般情形完全类似。
Lemma 3.7.4 揭示了一个有趣事实：像 $\langle u,v\rangle^k$ 这样的非线性表达式，可以写成另一个空间中的标准线性内积。具体来说，存在 Hilbert 空间 $H$ 和变换 $\Phi:\mathbb R^n\to H$，使得
$$ \langle \Phi(u),\Phi(v)\rangle = \langle u,v\rangle^k \qquad \text{for any }u,v\in\mathbb R^n. $$
事实上，可以取 $H=\mathbb R^{n^k}$，也就是 $k$ 阶张量空间，并取 $\Phi(u)=u^{\otimes k}$。
学会处理幂函数之后，可以转向更一般的非线性函数。
存在 Hilbert 空间 $H$ 和变换 $\Phi:\mathbb R^n\to H$，使得
$$ \langle \Phi(u),\Phi(v)\rangle = 2\langle u,v\rangle^2 + 5\langle u,v\rangle^3 \qquad \text{for all }u,v\in\mathbb R^n. $$可以取
$$ \Phi(u) = (\sqrt2\,u\otimes u) \oplus (\sqrt5\,u\otimes u\otimes u), $$其中 $\oplus$ 表示拼接，也就是直和中的向量连接。因此目标空间是 $H=\mathbb R^{n^2+n^3}$。
含有负系数的多项式可能使任务变得不可能，因为 $\langle \Phi(u),\Phi(u)\rangle$ 总是非负的。不过有一个简洁的绕法：允许使用两个可能不同的变换 $\Phi,\Psi:\mathbb R^n\to H$，使得
$$ \langle \Phi(u),\Psi(v)\rangle = 2\langle u,v\rangle^2 - 5\langle u,v\rangle^3 \qquad \text{for all }u,v\in\mathbb R^n. $$可以取
$$ \begin{aligned} \Phi(u) &= (\sqrt2\,u\otimes u) \oplus (\sqrt5\,u\otimes u\otimes u),\\ \Psi(v) &= (\sqrt2\,v\otimes v) \oplus (-\sqrt5\,v\otimes v\otimes v). \end{aligned} $$注意，这些变换会控制向量长度。对任意单位向量 $u$，
$$ \|\Phi(u)\|_2^2 = \|\Psi(u)\|_2^2 = 2\langle u,u\rangle^2 + 5\langle u,u\rangle^3 = 7, $$这正是系数绝对值之和。
沿着这个思路，可以处理任意多项式
$$ f(x)=\sum_{k=1}^N a_kx^k. $$
再通过取多项式极限，可以处理更多函数。
考虑函数
$$ f(x)=\sum_{k=0}^{\infty}a_kx^k, $$并假设这个级数对所有 $x\in\mathbb R$ 收敛。那么存在 Hilbert 空间 $H$ 和变换 $\Phi,\Psi:\mathbb R^n\to H$，使得
$$ \langle \Phi(u),\Psi(v)\rangle = f(\langle u,v\rangle) \qquad \text{for all }u,v\in\mathbb R^n. $$并且，对任意单位向量 $u$，有
$$ \|\Phi(u)\|_2^2 = \|\Psi(u)\|_2^2 = \sum_{k=0}^{\infty}|a_k|. $$你将在 Exercise 3.55 中形式化验证这一步。
令 $c>0$。函数 $f(x)=\sin(cx)$ 是实解析的：
$$ \sin(cx) = cx - \frac{(cx)^3}{3!} + \frac{(cx)^5}{5!} - \frac{(cx)^7}{7!} +\cdots. $$因此，存在 Hilbert 空间 $H$ 和变换 $\Phi,\Psi:\mathbb R^n\to H$，使得
$$ \langle \Phi(u),\Psi(v)\rangle = \sin(c\langle u,v\rangle) \qquad \text{for all }u,v\in\mathbb R^n. $$此外，当
$$ 1 = c+\frac{c^3}{3!}+\frac{c^5}{5!}+\frac{c^7}{7!}+\cdots = \frac{e^c-e^{-c}}{2} = \sinh c $$时，$\Phi$ 和 $\Psi$ 会把单位向量映到单位向量。解这个方程得到
$$ c=\ln(1+\sqrt2). $$3.7.2 Theorem 3.5.1 的证明
现在可以证明 Grothendieck 不等式（Theorem 3.5.1），并得到常数
$$ K \le \frac{\pi}{2\ln(1+\sqrt2)} \approx 1.783. $$
和第 3.5 节中第一次证明 Grothendieck 不等式一样，不失一般性可假设 $u_i,v_j\in\mathbb R^N$，其中 $N=n+m$。由 Example 3.7.8，取 $c=\ln(1+\sqrt2)$，可在某个 Hilbert 空间 $H$ 中找到单位向量 $u_i',v_j'$，使得
$$ \langle u_i',v_j'\rangle = \sin(c\langle u_i,v_j\rangle) \qquad \text{for all }i,j. \tag{3.37} $$同样地，由于只涉及有限多个向量，可把它们所在的张成空间视为某个 Euclidean 空间。应用 Grothendieck identity（Lemma 3.6.5），得到
$$ \begin{aligned} \mathbb E \operatorname{sign}\langle g,u_i'\rangle \operatorname{sign}\langle g,v_j'\rangle &= \frac{2}{\pi} \arcsin\langle u_i',v_j'\rangle\\ &= \frac{2}{\pi} \arcsin\bigl(\sin(c\langle u_i,v_j\rangle)\bigr)\\ &= \frac{2c}{\pi}\langle u_i,v_j\rangle. \end{aligned} $$最后一步成立是因为 $|\langle u_i,v_j\rangle|\le1$ 且 $c<\pi/2$。因此
$$ \frac{2c}{\pi} \sum_{i,j}a_{ij}\langle u_i,v_j\rangle = \mathbb E \sum_{i,j}a_{ij} \underbrace{\operatorname{sign}\langle g,u_i'\rangle}_{x_i} \underbrace{\operatorname{sign}\langle g,v_j'\rangle}_{y_j}. $$对每个 $g$ 的取值，$x_i,y_j\in\{-1,1\}$，所以 Grothendieck 不等式的假设给出右侧绝对值至多为 $1$。于是
$$ \left| \sum_{i,j}a_{ij}\langle u_i,v_j\rangle \right| \le \frac{\pi}{2c} = \frac{\pi}{2\ln(1+\sqrt2)}. $$证明完成。
这个证明给出了一个随机算法：输入矩阵 $(a_{ij})$ 和单位向量 $u_i,v_j$，输出标签 $x_i,y_j\in\{-1,1\}$，并满足
$$ \mathbb E \sum_{i,j}a_{ij}x_iy_j \ge \frac{1}{K} \sum_{i,j}a_{ij}\langle u_i,v_j\rangle. $$算法如下。首先找到单位向量 $u_i',v_j'$，使其具有预先指定的内积 (3.37)；这可以写成一个半定规划。然后做随机舍入：取相应维度的标准正态向量 $g$，并令
$$ x_i=\operatorname{sign}\langle g,u_i'\rangle, \qquad y_j=\operatorname{sign}\langle g,v_j'\rangle. $$3.7.3 核与特征映射
既然 kernel trick 在 Grothendieck 不等式中如此有效，我们自然会问：它还能处理哪些非线性？给定某个集合 $\mathcal X$ 上的二元函数
$$ K:\mathcal X\times\mathcal X\to\mathbb R, $$
什么时候可以找到 Hilbert 空间 $H$ 和变换 $\Phi:\mathcal X\to H$，使得
$$ \langle \Phi(u),\Phi(v)\rangle = K(u,v) \qquad \text{for all }u,v\in\mathcal X? \tag{3.38} $$
答案由 Mercer 定理，更精确地说由 Moore-Aronszajn 定理给出。必要且充分条件是 $K$ 是正半定核：对任意点 $u_1,\ldots,u_N\in\mathcal X$，矩阵
$$ \bigl(K(u_i,u_j)\bigr)_{i,j=1}^N $$
都是对称正半定的。变换 $\Phi$ 称为 feature map，Hilbert 空间 $H$ 称为再生核 Hilbert 空间（reproducing kernel Hilbert space，RKHS）。
机器学习中常见的正半定核包括 Gaussian 核和多项式核：
$$ K(u,v) = \exp\left( -\frac{\|u-v\|_2^2}{2\sigma^2} \right), \qquad K(u,v) = (\langle u,v\rangle+r)^k, \qquad u,v\in\mathbb R^n, $$
其中 $\sigma>0$、$r>0$ 且 $k\in\mathbb N$ 是参数。kernel trick (3.38) 把核 $K(u,v)$ 表达为内积，因此在机器学习中很常用：它让我们可以用线性模型的技术处理由 $K$ 决定的非线性模型。通常并不需要知道 Hilbert 空间 $H$ 和 feature map $\Phi$ 的具体形式。要计算 $H$ 中的内积 $\langle \Phi(u),\Phi(v)\rangle$，甚至不需要知道 $\Phi$；恒等式 (3.38) 允许我们直接计算 $K(u,v)$。
3.8 Notes
Theorem 3.1.1 及其证明来自 [213]，不过这个结果的一些版本也属于 folklore。该定理中对 $K$ 的依赖不是最优的。Jeong、Li、Plan 和 Yilmaz [176] 把它从 $K^2$ 改进为 $K\sqrt{\log K}$，并证明一般情形下这是最佳可能的。这也会强化本书中若干依赖 Theorem 3.1.1 的其他结果。
与 Theorem 3.1.1 相关的一个自然问题是：当随机向量 $X$ 的坐标不独立时，范数 $\|X\|_2$ 如何集中？当 $X$ 均匀分布在凸集 $K$ 中时，这是几何泛函分析中的一个核心问题；参见 [150, Section 2] 和 [61, Chapter 12]。
“投影中心极限定理”（Theorem 3.3.9）在某种形式上可追溯到 Borel [49, Chapter V]；关于它的历史、定量版本以及高维边缘分布的推广，可参见 [102]。
Section 3.3.4 和 Example 3.4.6 讨论了凸集上的均匀随机向量。书籍 [21, 61] 对这一主题有详细研究，综述 [303, 336] 则讨论了高维凸集体积计算中的算法方面。
关于 Section 3.3.5 中引入的 frames，可参见 [78, 193]。
Theorem 3.4.5 及相关结果有若干证明；一个简单的几何证明可见 [23]。利用显式密度公式（Exercise 3.27）还可以略微改进该界；参见 [52, Exercise 7.9]，该练习基于 [62]。
Grothendieck 不等式（Theorem 3.5.1）最初由 A. Grothendieck 于 1953 年证明 [149]，当时得到的界为
$$ K\le \sinh(\pi/2)\approx 2.30. $$
原始论证的一个版本可见 [215, Section 2]。此后出现了许多替代证明，有些给出更好或更差的 $K$ 的界；历史概述见 [60]。综述 [185, 273] 介绍了 Grothendieck 不等式在数学和计算机科学中的影响。
我们在 Section 3.5 中的第一个证明遵循 [14, Section 8.1]，该证明由 Mark Rudelson 提醒作者注意。Section 3.7 中的第二个证明归功于 J.-L. Krivine [195]；这一论证的版本可见 [16] 和 [205]。Krivine 方法给出目前最好的显式界
$$ K\le \frac{\pi}{2\ln(1+\sqrt2)} \approx 1.783. $$
实际最优界严格小于这个数 [60]，但目前还没有显式表达式。
在 Section 3.5.1 中，我们研究了组合优化问题的半定松弛。关于凸优化和半定规划的入门，可参见 [58, 64, 205, 51]。关于用 Grothendieck 不等式分析半定松弛，可参见 [185, 16, 151]。
我们对最大割问题的介绍（Section 3.6）遵循 [64, Section 6.6] 和 [205, Chapter 7]。半定方法（Section 3.6.2）由 M. Goemans 和 D. Williamson [139] 开创。近似比
$$ \frac{2}{\pi} \min_{0\le \theta\le \pi} \frac{\theta}{1-\cos\theta} \approx 0.878 $$
仍是目前已知最佳的。如果 Unique Games Conjecture 成立，则不存在更好的多项式时间近似比：任何更好的近似都将是 NP-hard 的 [184]。
在 Section 3.7 中，我们按照 Alon 和 Naor [16] 的阐述介绍了 Krivine 对 Grothendieck 不等式的证明 [195]，并简要涉及了 kernel methods。关于 kernels、再生核 Hilbert 空间及其在机器学习中的作用，可参见 [162]。
对标准正态分布而言，Exercise 3.13 可以改进为
$$ \mathbb E\max_{i\le N}\|X_i\|_2 \le \sqrt n+\sqrt{2\ln N}, $$
这推广了 Exercise 2.38；见 [127, Proposition 8.2]。
Gaussian 随机向量的期望 $\ell^p$ 范数（Exercises 3.5 和 3.6）最早由 G. Schechtman 和 J. Zinn [296] 计算；他们把下界（Exercise 3.6）归功于 J. Bourgain。
随机点处于凸位置的概率（Exercise 3.23）可追溯到随机几何中的 Sylvester 问题 [29]。相关问题包括凸包包含原点的概率 [348]（见 [297, Theorem 8.2.1]），以及随机多面体几何的更广泛研究 [170, 297]。
Exercises 3.18 和 3.19 引入了两个经典随机矩阵系综：Ginibre 和 GOE。关于这些以及其他不变系综，可参见经典文献 [231] 和随机矩阵理论的系统入门 [20]。我们将在第 4 章更深入地研究随机矩阵。
在 Exercise 3.57 中，我们将对正半定矩阵证明 Grothendieck 不等式，常数为 $K\le \pi/2$。这个结果最初归功于 Rietz [283]，Grothendieck 证明了常数 $\pi/2$ 是最优的 [149]。Exercises 3.56、3.57 和 3.58 遵循开创性论文 [16] 中的阐述。
Exercises
设 $X=(X_1,\ldots,X_n)\in\mathbb R^n$ 是随机向量，坐标 $X_i$ 独立、次高斯，并满足 $\mathbb E X_i^2=1$。由 Theorem 3.1.1 推出
$$ \operatorname{Var}\left(\|X\|_2\right) \le CK^4. $$ 查看学习笔记证明路线放松 Exercise 3.1 的假设，并对任意四阶矩有界的分布证明方差界。设 $X=(X_1,\ldots,X_n)\in\mathbb R^n$ 是随机向量，坐标 $X_i$ 独立，并满足 $\mathbb E X_i^2=1$ 和 $\mathbb E X_i^4\le K^4$。证明
$$ \operatorname{Var}\left(\|X\|_2\right) \le K^4 \qquad\text{and}\qquad \sqrt n-\frac{K^4}{\sqrt n} \le \mathbb E\|X\|_2 \le \sqrt n. $$ 查看学习笔记证明路线证明 Exercise 3.2 中界的反向形式。设 $X=(X_1,\ldots,X_n)\in\mathbb R^n$ 是随机向量，坐标 $X_i$ 独立，并满足 $\mathbb E X_i^2=1$、$\operatorname{Var}(X_i^2)>\alpha$ 和 $\mathbb E X_i^6\le \beta$，其中 $\alpha,\beta>0$。证明：当 $n$ 足够大（依赖于 $\alpha$ 和 $\beta$）时，
$$ \operatorname{Var}\bigl(\|X\|_2\bigr) \ge c\alpha \qquad\text{and}\qquad \mathbb E\|X\|_2 \le \sqrt n-\frac{c\alpha}{\sqrt n}. $$解释为什么方差的下界是一个必要假设。
查看学习笔记证明路线设 $X$ 是 $\mathbb R^n$ 中均值为零的随机向量，其协方差矩阵的特征值为 $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n$，对应特征向量为 $v_1,\ldots,v_n$。
(a) 证明投影到 $\operatorname{span}(v_1,\ldots,v_k)$ 上的正交投影 $P_k$ 满足
$$ \mathbb E\|P_kX\|_2^2 = \sum_{i=1}^k \operatorname{Var}\left(\langle X,v_i\rangle\right) = \sum_{i=1}^k\lambda_i. $$(b) 证明 $\mathbb R^n$ 中任意秩为 $k$ 的正交投影 $P$ 都满足
$$ \mathbb E\|PX\|_2^2 \le \mathbb E\|P_kX\|_2^2. $$把这些结果解释为：PCA 最大化数据的解释方差，解释比例为 $s_k/s_n$，其中 $s_k=\lambda_1+\cdots+\lambda_k$。
查看学习笔记证明路线设 $n\in\mathbb N$ 且 $p\in[1,\infty]$。考虑随机向量 $X=(X_1,\ldots,X_n)$，其坐标是独立次高斯随机变量。证明
$$ \mathbb E\|X\|_p \le \begin{cases} CK\sqrt p\,n^{1/p}, & p\le \log n,\\ CK\sqrt{\log n}, & p\ge \log n, \end{cases} $$其中 $C$ 是绝对常数，$K=\max_i\|X_i\|_{\psi_2}$。
查看学习笔记证明路线证明 Exercise 3.5 中的界对标准 Gaussian 随机向量可反向成立。具体地，设 $n\in\mathbb N$ 且 $p\in[1,\infty]$，随机向量 $X=(X_1,\ldots,X_n)$ 的坐标是独立 $N(0,1)$ 随机变量。证明
$$ \mathbb E\|X\|_p \ge \begin{cases} c\sqrt p\,n^{1/p}, & p\le \log n,\\ c\sqrt{\log n}, & p\ge \log n, \end{cases} $$其中 $c>0$ 是绝对常数。
查看学习笔记证明路线设 $X=(X_1,\ldots,X_n)\in\mathbb R^n$ 是随机向量，坐标独立且具有连续分布，并且这些坐标密度都由 $K$ 控制。
(a) 证明 $X$ 极不可能落入任意给定的半径为 $o(\sqrt n)$ 的球中。具体地，对任意固定 $a\in\mathbb R^n$ 和 $\varepsilon>0$，证明
$$ \mathbb P\left\{\|X-a\|_2\le \varepsilon\sqrt n\right\} \le \left(\sqrt{2\pi e}\,K\varepsilon\right)^n. $$在 Exercises 4.28-4.29 中我们会看到，对小 $\varepsilon$ 而言，这在渐近意义上是尖锐的。
(b) 对 $n\ge2$ 推出
$$ \mathbb E\left[\frac{1}{\|X\|_2}\right] \le \frac{CK}{\sqrt n}. $$解释为什么当 $n=1$ 时，这个期望可能为无穷大。
查看学习笔记证明路线(a) 证明 $\mathbb R^n$ 中任意各向同性随机向量 $X$ 都满足 $\|\mathbb E X\|_2\le1$。
(b) 说明这个界一般而言是最优的：对每个 $n\in\mathbb N$，找出一个 $\mathbb R^n$ 中的各向同性随机向量 $X$，使得 $\|\mathbb E X\|_2=1$。
查看学习笔记证明路线设 $X$ 是 $\mathbb R^n$ 中的各向同性随机向量。对任意 $u\in\mathbb R^n$，考虑随机变量 $X_u:=\langle X,u\rangle$。验证
$$ \mathbb E X_uX_v = \langle u,v\rangle \qquad\text{and}\qquad \|X_u-X_v\|_{L^2} = \|u-v\|_2. $$ 查看学习笔记证明路线(a) 设 $\mu\in\mathbb R^n$ 是固定向量，$\Sigma$ 是固定的 $n\times n$ 对称正半定矩阵，$Z$ 是 $\mathbb R^n$ 中均值为零的各向同性随机向量。验证随机向量
$$ X=\mu+\Sigma^{1/2}Z $$具有均值 $\mu$ 和协方差矩阵 $\Sigma$。
(b) 反过来，设 $X$ 是均值为 $\mu$、协方差矩阵为 $\Sigma$ 的随机向量。找出一个均值为零的各向同性随机向量 $Z$，使得 $X=\mu+\Sigma^{1/2}Z$ 几乎必然成立。
查看学习笔记证明路线给定向量 $x=(x_1,\ldots,x_n)\in\mathbb R^n$，满足 $x_1+\cdots+x_n=0$ 和 $x_1^2+\cdots+x_n^2=1$。令 $X$ 是通过随机置换 $x$ 的坐标得到的随机向量。具体地，令 $\sigma$ 是从 $\{1,\ldots,n\}$ 的所有 $n!$ 个排列中均匀选出的随机排列，并对每个 $i=1,\ldots,n$ 令 $X_i=x_{\sigma(i)}$。
(a) 计算 $X$ 的均值和协方差矩阵。
(b) 你会发现 $X$ 的坐标负相关。能否从启发式角度解释原因？
查看学习笔记证明路线设 $X$ 和 $Y$ 是 $\mathbb R^n$ 中独立、均值为零的各向同性随机向量。验证
$$ \mathbb E\|X-Y\|_2^2 = 2n. $$ 查看学习笔记证明路线证明 (2.22) 的一个高维版本。
(a) 设 $X_1,\ldots,X_N\in\mathbb R^n$ 是随机向量，不要求相互独立。假设每个随机向量 $X_i$ 的坐标 $X_{ij}$ 独立、次高斯，并满足 $\mathbb E X_{ij}^2=1$。证明
$$ \mathbb E\max_{i\le N}\|X_i\|_2 \le \sqrt n+CK^2\sqrt{\log N}, $$其中 $K=\max_{ij}\|X_{ij}\|_{\psi_2}$。
(b) 说明该界对 i.i.d. 标准正态随机向量是紧的。具体地，如果 $X_1,\ldots,X_N\sim N(0,I_n)$ 独立，证明
$$ \mathbb E\max_{i\le N}\|X_i\|_2 \ge c\left(\sqrt n+\sqrt{\log N}\right). $$ 查看学习笔记证明路线证明：如果 $X\sim N(\mu,\Sigma)$，那么对任意固定向量 $v\in\mathbb R^n$，
$$ \langle X,v\rangle \sim N\left(\langle \mu,v\rangle,\ v^{\mathsf T}\Sigma v\right). $$ 查看学习笔记证明路线按下面步骤证明 Proposition 3.3.6。
(a) 回忆随机向量 $X$ 的密度定义：它是一个函数 $f_X$，对任意 Borel 子集 $B\subset\mathbb R^n$ 满足
$$ \mathbb P\{X\in B\} = \int_B f_X(x)\,dx. $$(b) 说明可以假设 $\mu=0$ 且 $X=\Sigma^{1/2}Z$，其中 $Z\sim N(0,I_n)$。
(c) 通过变量替换 $x=\Sigma^{1/2}z$ 计算
$$ \mathbb P\{X\in B\} = \mathbb P\{Z\in \Sigma^{-1/2}(B)\}, $$把结果表示为 $B$ 上的积分，并使用标准正态密度公式 (3.11)。由 (a)，即可从被积函数读出 $X$ 的密度。
查看学习笔记证明路线(a) 证明 $\mathbb R^n$ 中的随机向量 $X$ 服从正态分布，当且仅当所有一维边缘 $\langle X,u\rangle$（$u\in\mathbb R^n$）都服从正态分布。
(b) 推出：随机变量 $X_1,\ldots,X_n$ 联合正态，当且仅当它们的所有固定系数线性组合
$$ a_1X_1+\cdots+a_nX_n $$都是正态随机变量。
查看学习笔记证明路线找出正态随机变量 $X$ 和 $Y$，使得它们不相关但并不独立。
查看学习笔记证明路线随机矩阵的一个基本模型是 Ginibre ensemble。Ginibre 随机矩阵是一个 $n\times n$ 矩阵 $G$，其元素独立且服从 $N(0,1)$。证明 Ginibre 分布在乘以正交矩阵下不变：对任意固定的 $n\times n$ 正交矩阵 $U$，$UG$ 和 $GU$ 都与 $G$ 同分布。
查看学习笔记证明路线对称随机矩阵的一个基本模型是 Gaussian orthogonal ensemble（GOE）。GOE 随机矩阵是一个 $n\times n$ 对称矩阵 $A$，其对角线上及其上方的元素独立；对角元素服从 $N(0,2)$，非对角元素服从 $N(0,1)$。
(a) 验证 $A$ 与 $(G+G^{\mathsf T})/\sqrt2$ 同分布，其中 $G$ 是 Exercise 3.18 中的 Ginibre 随机矩阵。这解释了定义中 $A$ 的对角与非对角元素为什么采用不同缩放。
(b) 证明 GOE 分布在正交共轭下不变：对任意固定的 $n\times n$ 正交矩阵 $U$，矩阵 $UAU^{\mathsf T}$ 与 $A$ 同分布。这解释了 “Gaussian orthogonal(-invariant) ensemble” 这个名称。
查看学习笔记证明路线设 $G$ 是一个 $m\times n$ 随机矩阵，元素独立且服从 $N(0,1)$。设 $u,v\in\mathbb R^n$ 是固定的单位正交向量。证明 $Gu$ 和 $Gv$ 是独立的 $N(0,I_m)$ 随机向量。
查看学习笔记证明路线设 $X$ 和 $Y$ 是独立的 $N(0,I_n)$ 随机向量。证明
$$ \frac{X+Y}{\sqrt2} \qquad\text{and}\qquad \frac{X-Y}{\sqrt2} $$是独立的 $N(0,I_n)$ 随机向量。
查看学习笔记证明路线证明标准正态随机向量 $g\sim N(0,I_n)$ 的长度 $\|g\|_2$ 与方向 $g/\|g\|_2$ 相互独立。
查看学习笔记证明路线如果 $\mathbb R^n$ 中的有限点集没有任何一个点落在其余点的凸包中，就称该点集处于凸位置；见图 3.11。设 $N\le e^{cn}$，其中 $c>0$ 是可选择的绝对常数。按照下面步骤证明：独立 Gaussian 随机向量 $g_1,\ldots,g_N\sim N(0,I_n)$ 以至少 $1-e^{-cn}$ 的概率处于凸位置。令人惊讶的是，这说明指数多个随机点可以处于凸位置。
(a) 证明以高概率，$g_1$ 与其他点可以线性分离：存在 $x\in\mathbb R^n$（可以是随机的）满足
$$ \langle g_1,x\rangle > \max_{j=2,\ldots,N}\langle g_j,x\rangle. $$在 $\mathbb R^2$ 中，可以把这个条件想象为存在一条直线把 $g_1$ 与其他点分开；在高维中，直线对应为超平面。
(b) 推出以高概率，$g_1$ 不在其他点的凸包中。
(c) 用 union bound 完成证明。
查看学习笔记证明路线设 $X$ 均匀分布在 $\mathbb R^n$ 中以原点为中心的单位 Euclidean 球内。把 $X$ 分解为
$$ X=rZ, $$其中 $Z\sim\operatorname{Unif}(S^{n-1})$，$r$ 是 $[0,1]$ 上密度为 $nx^{n-1}$ 的随机变量，并且 $r$ 与 $Z$ 独立。
查看学习笔记证明路线设 $Y$ 均匀分布在 $\mathbb R^n$ 中以原点为中心、半径为 $\sqrt{n+2}$ 的 Euclidean 球内。验证 $Y$ 是各向同性的。
查看学习笔记证明路线$\mathbb R^n$ 中最“分散”或最 delocalized 的单位向量 $x$，其所有坐标大小相同，即对所有 $i$，$|x_i|=1/\sqrt n$。随机向量几乎也是 delocalized 的。证明：均匀分布在 $\mathbb R^n$ 的单位 Euclidean 球面上的随机向量 $X$ 满足
$$ \mathbb E\|X\|_{\infty} \asymp \sqrt{\frac{\log n}{n}}. $$这里和往常一样，$\asymp$ 表示在绝对常数因子内等价。
查看学习笔记证明路线设 $X$ 和 $Y$ 分别均匀分布在 $\mathbb R^n$ 的 Euclidean 单位球面和 Euclidean 单位球内。
(a) 证明 $Y$ 的任意一维边缘密度正比于
$$ (1-x^2)^{(n-1)/2}, \qquad x\in[-1,1]. $$(b) 证明 $X$ 的任意一维边缘密度正比于
$$ (1-x^2)^{(n-3)/2}, \qquad x\in[-1,1]. $$令人惊讶的是，三维球面的任意一维边缘都是均匀分布的。
查看学习笔记证明路线证明一个惊人的事实：$\mathbb R^n$ 中的标准正态随机向量很可能非常接近某个边长为常数的立方体，但又极不可能落入一个甚至大一百倍的立方体中。
(a) 令 $\pi_a$ 表示到立方体 $[-a,a]^n$ 上的 metric projection，即把输入点 $x$ 映为立方体中与 $x$ Euclidean 距离最近的点 $y=\pi_a(x)$。证明这个投影可由坐标裁剪得到：
$$ y_i= \begin{cases} x_i, & |x_i|\le a,\\ a\,\operatorname{sign}(x_i), & |x_i|>a, \end{cases} \qquad i=1,\ldots,n. $$(b) 证明存在绝对常数 $n_0$ 和 $a>0$，使得对每个 $n>n_0$，随机向量 $g\sim N(0,I_n)$ 以至少 $0.99$ 的概率满足
$$ \operatorname{dist}\left(g,[-a,a]^n\right) < 0.01\|g\|_2 \qquad\text{and}\qquad g\notin[-100a,100a]^n. $$这里 $\operatorname{dist}(x,T)=\inf_{y\in T}\|x-y\|_2$ 表示点 $x$ 到集合 $T$ 的距离。
查看学习笔记证明路线证明：向量 $u_1,\ldots,u_N\in\mathbb R^n$ 构成 Parseval frame，当且仅当以 $u_i$ 为列的 $n\times N$ 矩阵具有正交归一的行。
查看学习笔记证明路线考虑圆上 $N$ 个等距点，圆半径为 $\sqrt{2/N}$；当 $N=3$ 时见图 3.7。证明这些点在 $\mathbb R^2$ 中构成 Parseval frame。
查看学习笔记证明路线设 $X$ 是 $\mathbb R^n$ 中的各向同性随机向量，它以概率 $p_1,\ldots,p_N$ 取值 $x_1,\ldots,x_N$。验证向量
$$ \sqrt{p_1}x_1,\ldots,\sqrt{p_N}x_N $$在 $\mathbb R^n$ 中构成 Parseval frame。
查看学习笔记证明路线设 $X$ 是 $\mathbb R^n$ 中的次高斯随机向量。验证对任意向量 $v\in\mathbb R^n$，
$$ \|\langle X,v\rangle\|_{\psi_2} \le \|X\|_{\psi_2}\|v\|_2. $$ 查看学习笔记证明路线Proposition 3.3.1 表明标准正态分布是旋转不变的。次高斯分布不一定旋转不变，但次高斯范数是旋转不变的。证明：对任意正交 $n\times n$ 矩阵 $U$ 和次高斯向量 $X\in\mathbb R^n$，$UX$ 仍是次高斯的，并且
$$ \|UX\|_{\psi_2} = \|X\|_{\psi_2}. $$ 查看学习笔记证明路线设 $A$ 是一个 $m\times n$ 随机矩阵，其行 $A_i$ 独立、均值为零且次高斯。证明：对任意固定的 $u\in\mathbb R^m$ 和 $v\in\mathbb R^n$，$u^{\mathsf T}Av$ 是次高斯随机变量，并且
$$ \|u^{\mathsf T}Av\|_{\psi_2} \le C\|u\|_2\|v\|_2 \max_i\|A_i\|_{\psi_2}. $$解释为什么如果把同样假设放在 $A$ 的列上，而不是行上，结论仍然成立。
查看学习笔记证明路线Proposition 2.7.1 可推广到高维。设 $X_1,\ldots,X_N$ 是 $\mathbb R^n$ 中独立、均值为零的次高斯向量。证明
$$ \left\| \sum_{i=1}^N X_i \right\|_{\psi_2}^2 \le C\sum_{i=1}^N \|X_i\|_{\psi_2}^2, $$其中 $C$ 是绝对常数。
查看学习笔记证明路线如果去掉 Lemma 3.4.2 中的独立性假设，会发生什么？$X$ 仍然是次高斯的，但界会差很多。
(a) 设 $X=(X_1,\ldots,X_n)$ 是随机向量，坐标 $X_i$ 是次高斯的，但不要求独立。证明 $X$ 是次高斯的，并且
$$ \max_{i\le n}\|X_i\|_{\psi_2} \le \|X\|_{\psi_2} \le \sqrt n\max_{i\le n}\|X_i\|_{\psi_2}. $$(b) 用例子说明 (a) 中两个界在所有维数 $n$ 中都是最优的。
查看学习笔记证明路线人们可能会猜想，范数集中结论（Theorem 3.1.1）可以更一般地适用于任意各向同性次高斯随机向量 $X$，其中 $K=\|X\|_{\psi_2}$，因此坐标独立性并非必要。请用一个例子说明这个猜想是错误的。
不过，我们将在 Proposition 6.2.1 中证明一个关于范数的上界。
查看学习笔记证明路线在 Exercise 2.24(c) 中，我们证明了正态随机变量 $N(0,\sigma^2)$ 的次高斯范数等于 $\sqrt{8/3}\,\sigma$。把这个结果推广到高维：证明随机向量 $X\sim N(0,\Sigma)$ 满足
$$ \|X\|_{\psi_2} = \sqrt{\frac{8}{3}}\, \|\Sigma\|^{1/2}, $$其中 $\|\Sigma\|$ 表示 $\Sigma$ 的最大特征值，也就是 operator norm。
查看学习笔记证明路线(a) 设 $X_1,\ldots,X_n$ 是次高斯随机变量，不要求相互独立。证明
$$ \left\| \left(\sum_{i=1}^n X_i^2\right)^{1/2} \right\|_{\psi_2} \le \left( \sum_{i=1}^n \|X_i\|_{\psi_2}^2 \right)^{1/2}. $$(b) 设 $X$ 是 $\mathbb R^n$ 中的次高斯随机向量。证明 $\|X\|_2$ 是次高斯随机变量，并且
$$ \left\|\|X\|_2\right\|_{\psi_2} \le \sqrt n\,\|X\|_{\psi_2}. $$解释为什么一般而言 $\sqrt n$ 是最佳缩放因子。我们将在 Proposition 6.2.1 中证明一个更有信息量的界。
查看学习笔记证明路线在 (3.14) 中，我们看到来自球面 $S^{n-1}$ 均匀分布的两个独立随机向量很可能几乎正交。下面推广这个观察。
(a) 设 $X$ 是 $\mathbb R^n$ 中的随机向量，坐标独立、均值为零、方差为一，并且次高斯范数都由 $K$ 控制。定义 $\theta=X/\|X\|_2$（当 $X\ne0$）且在 $X=0$ 时令 $\theta=0$。令 $\eta$ 是 $\theta$ 的独立副本。证明
$$ |\langle \theta,\eta\rangle| \le \frac{C(K)}{\sqrt n} $$以至少 $0.99$ 的概率成立，其中 $C(K)$ 只依赖于 $K$。
(b) 说明 (a) 中坐标独立性是关键的。找出 $\mathbb R^n$ 中独立同分布、各向同性的随机向量 $X$ 和 $Y$，其次高斯范数由绝对常数控制，并且满足 $X=Y$ 的概率至少为 $0.99$。
查看学习笔记证明路线线性代数告诉我们，$\mathbb R^n$ 中不可能有超过 $n$ 个正交向量。但令人惊讶的是，可以有指数多个几乎正交向量。对任意整数 $N\le e^{cn}$，按照下面步骤找到点 $X_1,\ldots,X_N\in S^{n-1}$，使得
$$ |\langle X_i,X_j\rangle| \le 0.01 \qquad \text{for all distinct }i,j. \tag{3.39} $$(a) 说明独立随机向量 $X,Y\sim\operatorname{Unif}(S^{n-1})$ 满足 $|\langle X,Y\rangle|\le0.01$ 的概率至少为 $1-4\exp(-c_0n)$，其中 $c_0$ 是绝对常数。
(b) 对所有不同点对 $(i,j)$ 使用 union bound，并推出 (3.39) 中的事件以正概率成立。
查看学习笔记证明路线设 $Y$ 均匀分布在 $\mathbb R^n$ 中以原点为中心的 Euclidean 单位球内。说明 $Y$ 满足 Theorem 3.4.5 的结论。
查看学习笔记证明路线设 $n\ge2$，随机向量 $X$ 均匀分布在 $\mathbb R^n$ 的标准基向量集合上。证明
$$ \|X\|_{\psi_2} \asymp \frac{1}{\sqrt{\log n}}. $$和往常一样，$\asymp$ 表示在绝对常数因子内等价。
查看学习笔记证明路线考虑 $\mathbb R^n$ 中 $\ell^1$ 范数下的球
$$ K := \{x\in\mathbb R^n:\|x\|_1\le r\}. $$令随机向量 $X$ 均匀分布在 $K$ 中。
(a) 计算 $X_1$，即 $X$ 第一坐标的密度。
(b) 说明对某个 $r\asymp n$，随机向量 $X$ 是各向同性的。
(c) 对这个 $r$，证明 $\|X\|_{\psi_2}>c\sqrt n$，其中 $c>0$ 是绝对常数。
查看学习笔记证明路线设 $X$ 是 $\mathbb R^n$ 中的次高斯随机向量。证明对任意 $x\in\mathbb R^n$，
$$ \mathbb P\{X=x\} \le 2\exp\left( -\frac{\|x\|_2^2}{K^2} \right), $$其中 $K=\|X\|_{\psi_2}$。
查看学习笔记证明路线若离散随机向量 $X$ 以概率 $p_i$ 取值 $x_i$，它的熵定义为
$$ H(X) = -\sum_i p_i\ln p_i. $$启发式地，$H(X)$ 与编码 $X$ 所需的期望比特数成正比；这可由 Shannon source coding theorem 形式化。
(a) 非常离散的分布熵低：对任意只取 $N$ 个值的随机向量 $X$，证明 $H(X)\le \ln N$。
(b) 各向同性次高斯分布熵高：对任意 $\mathbb R^n$ 中离散、各向同性、次高斯的随机向量 $X$，证明
$$ H(X) \ge \frac{n}{K^2}-\ln2, \qquad K=\|X\|_{\psi_2}. $$(c) 各向同性次高斯分布的支撑很大：推出 (b) 中的随机向量必须至少取
$$ \frac{1}{2}\exp(K^{-2}n) $$个不同的值。
查看学习笔记证明路线设 $A$ 是一个 $m\times n$ 矩阵。证明下面性质等价。
(a) 对任意 $x\in\{-1,1\}^m$ 和 $y\in\{-1,1\}^n$，有 $x^{\mathsf T}Ay\le1$。
(b) 对任意 $x\in[-1,1]^m$ 和 $y\in[-1,1]^n$，有 $x^{\mathsf T}Ay\le1$。
(c) 对任意 $x\in\mathbb R^m$ 和 $y\in\mathbb R^n$，有
$$ x^{\mathsf T}Ay \le \|x\|_{\infty}\|y\|_{\infty}. $$(d) 上述三个性质中任意一个，把 $x^{\mathsf T}Ay$ 替换为 $|x^{\mathsf T}Ay|$ 后仍成立。
查看学习笔记证明路线改进 Theorem 3.5.1 的证明：不要使用 (3.25) 中粗略的 $4/R^2$ 上界，并在最后对 $R$ 做数值优化。推出 $K\le14.1$。
查看学习笔记证明路线本题和下一题中，我们按照 Remark 3.5.3 的说法，通过假设 $x_i=y_i$ 来放松 Grothendieck 不等式的假设。
(a) Polarization identity：证明对任意 $n\times n$ 对称矩阵 $A$ 和向量 $x,y\in\mathbb R^n$，有
$$ x^{\mathsf T}Ay = \bar x^{\mathsf T}A\bar x - \bar y^{\mathsf T}A\bar y, \qquad \bar x=\frac{x+y}{2}, \qquad \bar y=\frac{x-y}{2}. $$(b) Quadratic Grothendieck：设 $A=(a_{ij})$ 是一个 $n\times n$ 对称正半定矩阵。假设对任意 $x_i\in\{-1,1\}$，
$$ \sum_{i,j}a_{ij}x_ix_j \le 1. $$证明对任意 Hilbert 空间 $H$，以及任意单位向量 $u_i,v_j\in H$，有
$$ \left| \sum_{i,j}a_{ij}\langle u_i,v_j\rangle \right| \le 2K, $$其中 $K$ 是 Grothendieck 不等式中的绝对常数。
(c) 说明如果没有正半定假设，(b) 的结论可能失败。
查看学习笔记证明路线(a) Separate convexity：函数 $f(x_1,\ldots,x_n)$ 称为 separately convex，如果它对每个单独变量 $x_i$ 都是凸的。这样的函数本身不一定是凸函数；请举例。证明：separately convex 函数 $f:[-1,1]^n\to\mathbb R$ 在立方体的某个极点达到最大值，也就是在 $\{-1,1\}^n$ 中某点达到最大值。
(b) Quadratic Grothendieck：设 $A=(a_{ij})$ 是一个 $n\times n$ 零对角矩阵。假设对任意 $x_i\in\{-1,1\}$，
$$ \left| \sum_{i,j}a_{ij}x_ix_j \right| \le1. $$证明对任意 Hilbert 空间 $H$，以及任意单位向量 $u_i,v_j\in H$，有
$$ \left| \sum_{i,j}a_{ij}\langle u_i,v_j\rangle \right| \le 2K, $$其中 $K$ 是 Grothendieck 不等式中的绝对常数。
查看学习笔记证明路线向量 $v_1,\ldots,v_n$ 的 Gram 矩阵是 $n\times n$ 矩阵 $(\langle v_i,v_j\rangle)$。证明如下事实。
(a) 任意一组向量的 Gram 矩阵都是对称正半定的。
(b) 反过来，任意对称正半定矩阵都是某组向量的 Gram 矩阵。
查看学习笔记证明路线考虑如下整数优化问题：
$$ \operatorname{maximize}\quad \sum_{i=1}^m\sum_{j=1}^n A_{ij}x_iy_j \quad \text{subject to}\quad x_i,y_j=\pm1. \tag{3.40} $$其中 $A$ 是 $m\times n$ 矩阵。像 (3.29) 一样，把它松弛为如下问题：
$$ \operatorname{maximize}\quad \sum_{i,j}A_{ij}\langle X_i,Y_j\rangle \quad \text{subject to}\quad \|X_i\|_2=\|Y_j\|_2=1 \text{ for all }i,j, \tag{3.41} $$其中最大值取遍某个固定维数 $k\in\mathbb N$ 的 $\mathbb R^k$ 中所有单位向量 $X_i,Y_j$。
(a) 把 (3.41) 表示为半定规划。
(b) 说明这个松弛在绝对常数因子内近似原问题 (3.40)。
查看学习笔记证明路线证明 Grothendieck identity（Lemma 3.6.5）。
查看学习笔记证明路线Goemans-Williamson Theorem 3.6.4 只保证期望意义下的割很大。对任意 $\varepsilon>0$，给出一个最大割的 $(0.878-\varepsilon)$ 近似算法：它总能找到一个有效的割，但运行时间可以是随机的。请给出期望运行时间的上界。
查看学习笔记证明路线证明 Lemma 3.7.7。为此，需要一个 $\mathbb R^n$ 的无穷维版本。一个理想选择是 $\ell^2$，即所有平方可和序列 $x=(x_1,x_2,\ldots)$ 构成的空间。它有与 $\mathbb R^n$ 相同形式的范数和内积，只是有限求和被替换为收敛级数：
$$ \|x\|_2 = \left(\sum_{i=1}^{\infty}x_i^2\right)^{1/2}, \qquad \langle x,y\rangle = \sum_{i=1}^{\infty}x_iy_i. $$现在定义 $\Phi,\Psi:\mathbb R^n\to\ell^2$，使 Lemma 3.7.7 成立。
查看学习笔记证明路线通过添加校正项来消除 Grothendieck identity（Lemma 3.6.5）中的非线性 $\arcsin$。设 $g\sim N(0,I_n)$，且 $u,v\in\mathbb R^n$ 是固定单位向量。证明：
(a)
$$ \mathbb E \langle g,u\rangle \operatorname{sign}\langle g,v\rangle = \sqrt{\frac{2}{\pi}}\langle u,v\rangle. $$(b)
$$ \mathbb E \operatorname{sign}\langle g,u\rangle \operatorname{sign}\langle g,v\rangle = \frac{2}{\pi}\langle u,v\rangle + \mathbb E[Z_uZ_v], $$其中
$$ Z_w = \sqrt{\frac{2}{\pi}}\langle g,w\rangle - \operatorname{sign}\langle g,w\rangle. $$ 查看学习笔记证明路线对正半定矩阵，Grothendieck 不等式（Theorem 3.5.1）有更好的常数 $\pi/2\approx1.571$，并且证明更简单。设 $A=(a_{ij})$ 是 $n\times n$ 对称正半定矩阵。假设对任意 $x_i\in\{-1,1\}$，
$$ \sum_{i,j}a_{ij}x_ix_j \le 1. $$使用 Exercise 3.56 证明：对任意 Hilbert 空间 $H$ 和任意单位向量 $u_i\in H$，有
$$ \sum_{i,j}a_{ij}\langle u_i,u_j\rangle \le \frac{\pi}{2}. $$ 查看学习笔记证明路线使用 Exercise 3.57 的结果改进 Theorem 3.5.7。设 $A$ 是 $n\times n$ 对称正半定矩阵。令 $\operatorname{int}(A)$ 表示整数优化问题 (3.28) 中的最大值，令 $\operatorname{sdp}(A)$ 表示半定问题 (3.29) 中的最大值。
(a) 证明
$$ \operatorname{int}(A) \le \operatorname{sdp}(A) \le \frac{\pi}{2}\operatorname{int}(A). $$(b) 设计一个随机算法，把 (3.29) 的解 $(X_i)$ 转换为标签 $x_i=\pm1$，使其在期望意义下近似求解 (3.28)。
查看学习笔记证明路线校对说明
- 本页已经迁移 Figure 3.1-3.11。
- 本页的公式优先采用 MathJax 兼容写法，避免 OCR 中常见的不兼容粗体命令、断裂定界符和错误空格。
- 本页已把正文中的明确 Proof 渲染为 proof 卡片，并把 Exercises 3.1-3.58 渲染为 exercise 卡片。