第 7 章精校翻译：随机过程
第 7 章随机过程
本章转向随机过程，即一族定义在同一概率空间上的随机变量 $(X_t)_{t\in T}$。这些随机变量可以彼此相关。在经典例子布朗运动中，$t$ 表示时间，$T\subset\mathbb R$；但在高维概率中，$T$ 可以是抽象集合。最重要的例子是典范高斯过程：
$$ X_t=\langle g,t\rangle,\qquad t\in T, $$
其中 $T\subset\mathbb R^n$，$g\sim N(0,I_n)$。我们会在第 7.1 节引入它。
第 7.2 节介绍高斯过程的强大比较不等式：Slepian、Sudakov-Fernique 和 Gordon 不等式，并使用一个新技巧：高斯插值。第 7.3 节用这些工具证明 $m\times n$ 高斯随机矩阵算子范数的尖锐界。
高斯过程 $(X_t)_{t\in T}$ 如何捕捉 $T$ 的几何？第 7.4 节证明 Sudakov 不等式，它用覆盖数给出 Gaussian width 的下界
$$ w(T)=\mathbb E\sup_{t\in T}\langle g,t\rangle. $$
上界会在第 8 章出现。Gaussian width 是连接概率与度量几何的关键概念；第 7.5 节会更仔细地研究它，并把它和有效维数等其他概念联系起来。
第 7.6 节计算任意有界集 $T\subset\mathbb R^n$ 的随机投影大小。决定它的关键量正是 Gaussian width。
你会有很多机会练习这些想法：证明随机过程的对称化与收缩不等式（Exercises 7.2-7.4、7.8），推出高斯过程的重要极小极大不等式，也就是 Gordon 不等式（Exercise 7.9），得到高斯矩阵的尖锐界（Exercises 7.11 和 7.13），计算 $\ell^p$ 球的高斯宽度（Exercise 7.17），探索核范数（Exercises 7.18 和 7.19）、有效维数（Exercises 7.21-7.22）、一般集合的随机投影（Exercises 7.25 和 7.26）以及矩阵草图（Exercise 7.27）。
7.1 基本概念与例子
随机过程就是一族随机变量 $(X_t)_{t\in T}$，它们定义在同一概率空间上，并由集合 $T$ 中的元素索引。
当 $T=\{1,\dots,n\}$ 时，随机过程就是随机向量 $(X_1,\dots,X_n)$。当 $T=\mathbb N$ 时，随机过程是一个随机变量序列。
令 $Z_1,Z_2,\dots$ 为独立且均值为 $0$ 的随机变量。随机游走定义为
$$ X_n=\sum_{i=1}^n Z_i, $$它给出一个由 $T=\mathbb N$ 索引的随机过程。
标准布朗运动 $(X_t)_{t\ge0}$ 又称 Wiener 过程，可由两条性质刻画：样本路径几乎处处连续；并且对 $t\ge s$，增量独立且
$$ X_t-X_s\sim N(0,t-s). $$当 $T\subset\mathbb R^n$ 时，随机过程也称为空间随机过程或随机场。例如，地球表面每一点的水温可以视为一个随机场。
7.1.1 协方差与增量
为简化讨论，先假设 $\mathbb EX_t=0$。随机过程的协方差函数定义为
$$ \Sigma(t,s)=\operatorname{cov}(X_t,X_s)=\mathbb EX_tX_s. $$
过程的增量定义为
$$ d(t,s)=\|X_t-X_s\|_{L^2} =\bigl(\mathbb E(X_t-X_s)^2\bigr)^{1/2}. \tag{7.1} $$
布朗运动的增量满足 $d(t,s)=\sqrt{t-s}$，$t\ge s$。若随机游走的增量满足 $\mathbb EZ_i^2=1$，则
$$ d(n,m)=\sqrt{n-m},\qquad n\ge m. $$ 查看学习笔记：随机游走增量计算即使索引集合 $T$ 本身没有几何结构，增量 $d(t,s)$ 也会在 $T$ 上定义一个度量，从而自动把 $T$ 变成一个度量空间。不过这个度量未必等于 $T\subset\mathbb R^n$ 时的欧氏距离。
协方差和增量携带的信息大致相同。展开平方得
$$ d(t,s)^2=\Sigma(t,t)-2\Sigma(t,s)+\Sigma(s,s). $$如果过程包含零随机变量，则也可以由增量恢复协方差，见 Exercise 7.1。
查看学习笔记：Exercise 7.1 证明7.1.2 高斯过程
随机过程 $(X_t)_{t\in T}$ 称为高斯过程，如果任意有限子集 $T_0\subset T$ 上的随机向量 $(X_t)_{t\in T_0}$ 都服从正态分布。等价地，任意有限线性组合 $\sum_{t\in T_0}a_tX_t$ 都是正态随机变量。
均值为 $0$ 的高斯随机向量的分布由协方差矩阵决定。类似地，均值为 $0$ 的高斯过程的分布由协方差函数决定；在过程包含零随机变量的情形下，也可由增量决定。
设 $(X_t)_{t\in T}$ 是高斯过程，且 $T$ 有限。那么
$$ \left\| \sup_{t\in T}X_t-\mathbb E\sup_{t\in T}X_t \right\|_{\psi_2} \le C\sup_{t\in T}\sqrt{\operatorname{Var}(X_t)}. $$ 查看学习笔记：Theorem 7.1.11 完整证明这是 Exercise 5.9(b) 的直接重述；如果之前跳过了，现在应当补做。
典范高斯过程定义为
$$ X_t=\langle g,t\rangle,\qquad t\in T\subset\mathbb R^n,\quad g\sim N(0,I_n). \tag{7.2} $$
它的增量就是欧氏距离：
$$ \|X_t-X_s\|_{L^2}=\|t-s\|_2. $$
设 $X$ 是 $\mathbb R^n$ 中均值为 $0$ 的高斯随机向量。那么存在点 $t_1,\dots,t_n\in\mathbb R^n$，使得
$$ X\stackrel{d}{=}(\langle g,t_i\rangle)_{i=1}^n, \qquad g\sim N(0,I_n). $$ 查看学习笔记：Lemma 7.1.12 完整证明设 $\Sigma$ 是 $X$ 的协方差矩阵。由 (3.12)，
$$ X\stackrel{d}{=}\Sigma^{1/2}g, \qquad g\sim N(0,I_n). $$$\Sigma^{1/2}g$ 的第 $i$ 个坐标可以写成 $\langle t_i,g\rangle$，其中 $t_i$ 是 $\Sigma^{1/2}$ 的第 $i$ 行。因此
$$ X\stackrel{d}{=}(\langle g,t_i\rangle)_{i=1}^n. $$因此，对任意高斯过程 $(X_s)_{s\in S}$，其所有有限维边缘分布 $(X_s)_{s\in S_0}$，$|S_0|=n$，都可表示为典范高斯过程 (7.2) 在某个 $T_0\subset\mathbb R^n$ 上的限制。
7.2 Slepian、Sudakov-Fernique 与 Gordon 不等式
很多应用需要控制随机过程的统一上界：
$$ \mathbb E\sup_{t\in T}X_t. $$
为避免可测性问题，本章把 $\mathbb E\sup_{t\in T}X_t$ 理解为所有有限子集 $T_0\subset T$ 上 $\mathbb E\max_{t\in T_0}X_t$ 的上确界。这样只需证明有限索引集情形；一般情形由有限子集近似推出。
设 $(X_t)_{t\in T}$ 与 $(Y_t)_{t\in T}$ 是两个均值为 $0$ 的高斯过程。假设对所有 $t,s\in T$，
$$ \mathbb EX_t^2=\mathbb EY_t^2, \qquad \mathbb E(X_t-X_s)^2\le\mathbb E(Y_t-Y_s)^2. \tag{7.3} $$那么 $\sup_tX_t$ 被 $\sup_tY_t$ 随机支配：对任意 $\tau\in\mathbb R$，
$$ \mathbb P\{\sup_{t\in T}X_t\ge\tau\} \le \mathbb P\{\sup_{t\in T}Y_t\ge\tau\}. \tag{7.4} $$从而
$$ \mathbb E\sup_{t\in T}X_t \le \mathbb E\sup_{t\in T}Y_t. \tag{7.5} $$ 查看学习笔记：Slepian 不等式完整证明7.2.1 高斯插值
我们将用一个叫做高斯插值的技巧证明 Slepian 不等式。假设 $T$ 有限；于是可以把 $X=(X_t)_{t\in T}$ 和 $Y=(Y_t)_{t\in T}$ 看成 $\mathbb R^n$ 中的高斯随机向量，其中 $n=|T|$。也可以假设 $X$ 与 $Y$ 独立。
定义高斯随机向量 $Z(u)$，使它在 $Z(0)=Y$ 与 $Z(1)=X$ 之间连续插值：
$$ Z(u)=\sqrt u\,X+\sqrt{1-u}\,Y,\qquad u\in[0,1]. \tag{7.8} $$
那么 $Z(u)$ 的协方差矩阵在线性意义上连续插值于 $Y$ 和 $X$ 的协方差矩阵：
$$ \Sigma(Z(u))=u\Sigma(X)+(1-u)\Sigma(Y). $$
给定函数 $f:\mathbb R^n\to\mathbb R$，我们研究当 $u$ 从 $0$ 增加到 $1$ 时，$\mathbb Ef(Z(u))$ 如何变化。我们特别关心
$$ f(x)=\mathbf 1_{\{\max_i x_i\lt \tau\}}. $$
我们将证明在这种情形下 $\mathbb Ef(Z(u))$ 随 $u$ 增加而增加。这会立即推出 Slepian 不等式的结论，因为此时
$$ \mathbb Ef(Z(1))\ge \mathbb Ef(Z(0)), \qquad\text{即}\qquad \mathbb P\{\max_iX_i\lt \tau\}\ge \mathbb P\{\max_iY_i\lt \tau\}. $$
现在进入详细论证。为了发展高斯插值，先从一个有用恒等式开始。
设 $X\sim N(0,1)$。对可微函数 $f:\mathbb R\to\mathbb R$，在期望存在时有
$$ \mathbb EXf(X)=\mathbb Ef'(X). $$ 查看学习笔记：Lemma 7.2.3 完整证明先假设 $f$ 有有界支撑。记高斯密度为
$$ p(x)=\frac1{\sqrt{2\pi}}e^{-x^2/2}. $$把期望写成积分并分部积分，得到
$$ \mathbb Ef'(X) = \int_{\mathbb R}f'(x)p(x)\,dx = -\int_{\mathbb R}f(x)p'(x)\,dx. \tag{7.6} $$直接检查可知 $p'(x)=-xp(x)$，因此 (7.6) 中的积分等于
$$ \int_{\mathbb R}f(x)p(x)x\,dx = \mathbb EXf(X), $$这就是所需结论。一般函数情形可通过逼近论证推出。
通过重新缩放，可把高斯分部积分推广到 $X\sim N(0,\sigma^2)$：
$$ \mathbb EXf(X)=\sigma^2\mathbb Ef'(X). $$
只需写 $X=\sigma Z$，其中 $Z\sim N(0,1)$，再应用 Lemma 7.2.3。它也可以推广到高维。
设 $X\sim N(0,\Sigma)$。对可微函数 $f:\mathbb R^n\to\mathbb R$，若期望均存在，则
$$ \mathbb EXf(X)=\Sigma\cdot\mathbb E\nabla f(X). $$换句话说，
$$ \mathbb EX_i f(X) = \sum_{j=1}^n\Sigma_{ij}\mathbb E\frac{\partial f}{\partial x_j}(X), \qquad i=1,\dots,n. \tag{7.7} $$ 查看学习笔记：Lemma 7.2.4 完整证明这个推广将在 Exercise 7.6 中证明。
设 $X\sim N(0,\Sigma^X)$、$Y\sim N(0,\Sigma^Y)$ 独立，并定义 $Z(u)$ 如 (7.8)。对二阶可微函数 $f:\mathbb R^n\to\mathbb R$，
$$ \frac{d}{du}\mathbb Ef(Z(u)) = \frac12 \sum_{i,j=1}^n (\Sigma^X_{ij}-\Sigma^Y_{ij}) \mathbb E \frac{\partial^2f}{\partial x_i\partial x_j}(Z(u)). \tag{7.9} $$ 查看学习笔记：Lemma 7.2.5 完整证明由 chain rule，
$$ \begin{aligned} \frac d{du}\mathbb Ef(Z(u)) &= \sum_{i=1}^n \mathbb E \frac{\partial f}{\partial x_i}(Z(u)) \frac{dZ_i}{du}\\ &= \frac12 \sum_{i=1}^n \mathbb E \frac{\partial f}{\partial x_i}(Z(u)) \left( \frac{X_i}{\sqrt u} - \frac{Y_i}{\sqrt{1-u}} \right), \end{aligned} \tag{7.10} $$其中第二步使用了 (7.8)。把这个和分成两部分，先计算包含 $X_i$ 的项。为此，条件化在 $Y$ 上，并写成
$$ \sum_{i=1}^n \frac1{\sqrt u} \mathbb EX_i \frac{\partial f}{\partial x_i}(Z(u)) = \sum_{i=1}^n \frac1{\sqrt u} \mathbb EX_i g_i(X), \tag{7.11} $$其中
$$ g_i(X)= \frac{\partial f}{\partial x_i} \left(\sqrt u X+\sqrt{1-u}Y\right). $$对 $X$ 应用多元高斯分部积分（Lemma 7.2.4）。由 (7.7)，
$$ \begin{aligned} \mathbb EX_i g_i(X) &= \sum_{j=1}^n \Sigma^X_{ij} \mathbb E\frac{\partial g_i}{\partial x_j}(X)\\ &= \sum_{j=1}^n \Sigma^X_{ij} \mathbb E \frac{\partial^2 f}{\partial x_i\partial x_j} \left(\sqrt u X+\sqrt{1-u}Y\right) \sqrt u. \end{aligned} $$代入 (7.11)，得到
$$ \sum_{i=1}^n \frac1{\sqrt u} \mathbb EX_i \frac{\partial f}{\partial x_i}(Z(u)) = \sum_{i,j=1}^n \Sigma^X_{ij} \mathbb E \frac{\partial^2 f}{\partial x_i\partial x_j}(Z(u)). $$再对 $Y$ 取期望，即解除对 $Y$ 的条件化。对 (7.10) 中包含 $Y_i$ 的另一项做完全类似的计算，并合并两部分，就得到 (7.9)。
7.2.2 Slepian 不等式的证明
设 $X,Y$ 是 $\mathbb R^n$ 中均值为 $0$ 的高斯随机向量，满足同方差和增量支配条件。若二阶可微函数 $f$ 满足对所有 $i\ne j$，
$$ \frac{\partial^2 f}{\partial x_i\partial x_j}\ge0, $$则 $\mathbb Ef(X)\ge\mathbb Ef(Y)$。
查看学习笔记：Lemma 7.2.6 完整证明这些假设意味着 $X$ 与 $Y$ 的协方差矩阵 $\Sigma^X,\Sigma^Y$ 满足
$$ \Sigma^X_{ii}=\Sigma^Y_{ii}, \qquad \Sigma^X_{ij}\ge\Sigma^Y_{ij}, \qquad i,j=1,\ldots,n. $$确实，展开 $\mathbb E(X_i-X_j)^2$ 与 $\mathbb E(Y_i-Y_j)^2$，再用对角方差相等即可得到非对角协方差的比较。我们可以假设 $X$ 与 $Y$ 独立。应用 Lemma 7.2.5，并使用上面的协方差比较以及 $\partial^2 f/(\partial x_i\partial x_j)\ge0$，得到
$$ \frac d{du}\mathbb Ef(Z(u))\ge0. $$因此 $\mathbb Ef(Z(u))$ 随 $u$ 增加。于是
$$ \mathbb Ef(X)=\mathbb Ef(Z(1)) \ge \mathbb Ef(Z(0))=\mathbb Ef(Y). $$设 $X,Y$ 是 Lemma 7.2.6 中的两个高斯随机向量。则对任意 $\tau\ge0$，
$$ \mathbb P\{\max_i X_i\ge \tau\} \le \mathbb P\{\max_i Y_i\ge \tau\}, $$从而
$$ \mathbb E\max_i X_i\le \mathbb E\max_i Y_i. $$ 查看学习笔记：Theorem 7.2.7 完整证明令 $h:\mathbb R\to[0,1]$ 是一个二阶可微、非增函数，用来近似 interval $(-\infty,\tau)$ 的 indicator 函数：
$$ h(x)\approx\mathbf 1_{(-\infty,\tau)}. $$
定义 $f:\mathbb R^n\to\mathbb R$ 为
$$ f(x)=h(x_1)\cdots h(x_n). $$则 $f(x)$ 近似 indicator 函数
$$ f(x)\approx\mathbf 1_{\{\max_i x_i\lt \tau\}}. $$为了应用 Lemma 7.2.6，需要检查二阶混合偏导的符号。对 $i\ne j$，
$$ \frac{\partial^2 f}{\partial x_i\partial x_j} =h'(x_i)h'(x_j)\prod_{k\notin\{i,j\}}h(x_k)\ge0. $$这里前两个因子都是非正的，其余因子非负，所以乘积非负。由 Lemma 7.2.6，
$$ \mathbb Ef(X)\ge \mathbb Ef(Y). $$取平滑近似极限，得到
$$ \mathbb P\{\max_{i\le n}X_i\lt \tau\} \ge \mathbb P\{\max_{i\le n}Y_i\lt \tau\}. $$这证明了随机支配。期望比较由 Exercise 1.15(b) 中的积分尾公式得到。
查看学习笔记：从随机支配推出期望比较7.2.3 Sudakov-Fernique 与 Gordon inequalities
Slepian 不等式对 (7.3) 中的过程 $(X_t)$ 和 $(Y_t)$ 有两个假设：方差相等，以及增量被支配。现在去掉方差相等的假设，仍然能得到 (7.5)。
设 $(X_t)_{t\in T}$ 与 $(Y_t)_{t\in T}$ 是均值为 $0$ 的高斯过程。若对所有 $t,s\in T$，
$$ \mathbb E(X_t-X_s)^2\le\mathbb E(Y_t-Y_s)^2, $$则
$$ \mathbb E\sup_{t\in T}X_t \le \mathbb E\sup_{t\in T}Y_t. $$ 查看学习笔记：Theorem 7.2.8 完整证明像 Theorem 7.2.7 中证明 Slepian 不等式那样，只需处理 $\mathbb R^n$ 中的高斯随机向量 $X,Y$。仍从高斯插值 Lemma 7.2.5 推出结论。但这一次，不取近似 $\{\max_i x_i\lt \tau\}$ 的 indicator 函数，而是取近似 $\max_i x_i$ 的函数。
为此，令 $\beta\gt 0$，定义软最大值
$$ f(x)=\frac1\beta\log\sum_{i=1}^n e^{\beta x_i}. \tag{7.12} $$直接检查可知
$$ f(x)\to\max_{i\le n}x_i \qquad\text{as }\beta\to\infty. $$把 $f(x)$ 代入高斯插值公式 (7.9) 并化简，可得
$$ \frac d{du}\mathbb Ef(Z(u))\le0, \qquad u\in[0,1]. $$这个计算需要仔细展开，见 Exercise 7.7。于是 $\mathbb Ef(Z(u))$ 随 $u$ 增加而不增。令 $u=0,1$，得到 $\mathbb Ef(X)\le\mathbb Ef(Y)$；再令 $\beta\to\infty$，就得到 Sudakov-Fernique 不等式。
查看学习笔记：软最大值的极限与导数计算有些应用需要随机过程的极小极大界。例如由 (4.14)，若 $A$ 是元素独立且服从 $N(0,1)$ 的 $m\times n$ 高斯矩阵，则其最小奇异值可写为
$$ s_n(A) = \min_{u\in S^{n-1}}\|Au\|_2 = \min_{u\in S^{n-1}}\max_{v\in S^{m-1}}X_{uv}, $$
其中 $X_{uv}=\langle Au,v\rangle$ 是正态随机变量。处理这类问题的一个方便工具是 Gordon 不等式，它把 Slepian 和 Sudakov-Fernique 推广到 min-max setting。
设 $(X_{ut})_{u\in U,t\in T}$ 与 $(Y_{ut})_{u\in U,t\in T}$ 是在 $U\times T$ 上索引的两个均值为 $0$ 的高斯过程。若对所有 $u,t,s$，
$$ \mathbb E(X_{ut}-X_{us})^2 \le \mathbb E(Y_{ut}-Y_{us})^2, $$并且对所有 $u\ne v$ 与所有 $t,s$，
$$ \mathbb E(X_{ut}-X_{vs})^2 \ge \mathbb E(Y_{ut}-Y_{vs})^2, $$则对任意 $\tau\ge0$，
$$ \mathbb P\left\{\inf_{u\in U}\sup_{t\in T}X_{ut}\ge\tau\right\} \le \mathbb P\left\{\inf_{u\in U}\sup_{t\in T}Y_{ut}\ge\tau\right\}, $$从而相应的期望也满足同向比较。
查看学习笔记：Gordon 不等式的证明入口可以先在额外相等方差假设下自己证明 Gordon 不等式（Exercise 7.9）。也可以尝试高斯版本的 Talagrand 收缩原理（Exercise 7.8）。
7.3 应用：高斯矩阵的尖锐界
把刚证明的高斯比较不等式用到随机矩阵上。Section 4.6 中，我们研究了具有独立次高斯行的 $m\times n$ 随机矩阵 $A$，并用 $\varepsilon$-net argument 得到
$$ \mathbb E\|A\|\le \sqrt m+C\sqrt n, $$
其中 $C$ 是常数（见 Exercise 4.41）。现在用 Sudakov-Fernique 不等式，把高斯随机矩阵的这个界改进到尖锐常数 $C=1$。
设 $A$ 是 $m\times n$ 矩阵，元素独立且服从 $N(0,1)$。那么
$$ \mathbb E\|A\|\le\sqrt m+\sqrt n. $$ 查看学习笔记：Theorem 7.3.1 完整证明由 (4.9)，把 $A$ 的范数写成高斯过程的上确界：
$$ \|A\| = \max_{u\in S^{n-1},v\in S^{m-1}}\langle Au,v\rangle = \max_{(u,v)\in T}X_{uv}, $$其中 $T=S^{n-1}\times S^{m-1}$，并且
$$ X_{uv}:=\langle Au,v\rangle\sim N(0,1). $$为了使用 Sudakov-Fernique 比较不等式（Theorem 7.2.8），先计算过程 $(X_{uv})$ 的增量。对任意 $(u,v),(w,z)\in T$，
$$ \begin{aligned} \mathbb E(X_{uv}-X_{wz})^2 &= \mathbb E\left(\langle Au,v\rangle-\langle Aw,z\rangle\right)^2\\ &= \mathbb E\left( \sum_{i,j}A_{ij}(u_jv_i-w_jz_i) \right)^2\\ &= \sum_{i,j}(u_jv_i-w_jz_i)^2 \qquad\text{by independence, mean }0,\text{ 方差 }1\\ &= \|uv^{\mathsf T}-wz^{\mathsf T}\|_F^2\\ &\le \|u-w\|_2^2+\|v-z\|_2^2, \end{aligned} $$最后一步见 Exercise 7.10。
定义一个增量更简单的高斯过程：
$$ Y_{uv}:=\langle g,u\rangle+\langle h,v\rangle,\qquad (u,v)\in T, $$其中 $g\sim N(0,I_n)$，$h\sim N(0,I_m)$，且二者独立。这个过程的增量为
$$ \begin{aligned} \mathbb E(Y_{uv}-Y_{wz})^2 &= \mathbb E\left(\langle g,u-w\rangle+\langle h,v-z\rangle\right)^2\\ &= \mathbb E\langle g,u-w\rangle^2 + \mathbb E\langle h,v-z\rangle^2\\ &= \|u-w\|_2^2+\|v-z\|_2^2. \end{aligned} $$比较两个过程的增量，得到
$$ \mathbb E(X_{uv}-X_{wz})^2 \le \mathbb E(Y_{uv}-Y_{wz})^2 \quad\text{for all }(u,v),(w,z)\in T. $$由 Sudakov-Fernique 不等式（Theorem 7.2.8），
$$ \begin{aligned} \mathbb E\|A\| &= \mathbb E\sup_{(u,v)\in T}X_{uv} \le \mathbb E\sup_{(u,v)\in T}Y_{uv}\\ &= \mathbb E\sup_{u\in S^{n-1}}\langle g,u\rangle + \mathbb E\sup_{v\in S^{m-1}}\langle h,v\rangle\\ &= \mathbb E\|g\|_2+\mathbb E\|h\|_2\\ &\le \left(\mathbb E\|g\|_2^2\right)^{1/2} + \left(\mathbb E\|h\|_2^2\right)^{1/2}\\ &= \sqrt n+\sqrt m. \end{aligned} $$ 查看学习笔记：秩一 Frobenius 距离计算Theorem 7.3.1 只给出期望界，但可以用第 5.2 节的集中工具把它升级成高概率界。
在 Theorem 7.3.1 的假设下，对所有 $t\ge0$，
$$ \mathbb P\{\|A\|\ge\sqrt m+\sqrt n+t\} \le 2\exp(-ct^2). $$ 查看学习笔记：Corollary 7.3.2 完整证明把期望界（Theorem 7.3.1）与高斯集中（Theorem 5.2.3）结合。把 $A$ 通过拼接行视为 $\mathbb R^{m\times n}$ 中的长向量，则 $A\sim N(0,I_{mn})$。考虑函数
$$ f(A):=\|A\|. $$由于算子范数被 Frobenius 范数控制，而 Frobenius 范数正是 $\mathbb R^{m\times n}$ 上的欧氏范数，函数 $f$ 是 Lipschitz 函数，且 Lipschitz 范数至多为 $1$。因此 Theorem 5.2.3 给出
$$ \mathbb P\{\|A\|\ge\mathbb E\|A\|+t\} \le 2\exp(-ct^2). $$再代入 Theorem 7.3.1 对 $\mathbb E\|A\|$ 的界，证明完成。
查看学习笔记：为什么 $A\mapsto\|A\|$ 是 1-Lipschitz现在可以尝试 Exercise 7.11：证明对称高斯矩阵满足 $\mathbb E\|A\|\le2\sqrt n$。还可以做 Exercise 7.13：证明 $m\times n$ 高斯矩阵 $A$ 的最小奇异值满足
$$ \mathbb Es_n(A)\ge \sqrt m-\sqrt n. $$
7.4 Sudakov 不等式
回到任意指标集 $T$ 上的一般均值为零高斯过程 $(X_t)_{t\in T}$。如 Remark 7.1.7 所述，增量
$$ d(t,s)=\|X_t-X_s\|_{L^2}. \tag{7.13} $$
在 $T$ 上定义一个度量，称为典范度量。这个度量决定协方差函数 $\Sigma(t,s)$，而协方差函数又决定过程 $(X_t)_{t\in T}$ 的分布（回忆 Remark 7.1.10）。因此原则上，只要理解度量空间 $(T,d)$ 的几何，就能回答关于该高斯过程分布的问题；换句话说，可以通过几何研究概率。
这里有一个重要的具体问题：如何用 $(T,d)$ 的几何估计
$$ \mathbb E\sup_{t\in T}X_t? \tag{7.14} $$
这是一个困难问题，本章先开始研究，第 8 章继续深入。
先用度量熵给出 (7.14) 的下界。回忆 Section 4.2：对任意 $\varepsilon\gt 0$，覆盖数
$$ \mathcal N(T,d,\varepsilon) $$
是 $T$ 在度量 $d$ 下的最小 $\varepsilon$-net 基数，等价地说，是覆盖 $T$ 所需半径为 $\varepsilon$ 的闭球的最小数量。覆盖数的对数 $\log_2\mathcal N(T,d,\varepsilon)$ 称为 $T$ 的度量熵。
设 $(X_t)_{t\in T}$ 是均值为 $0$ 的高斯过程，$d$ 为其典范度量。那么对任意 $\varepsilon\ge0$，
$$ \mathbb E\sup_{t\in T}X_t \ge c\varepsilon\sqrt{\log\mathcal N(T,d,\varepsilon)}. $$ 查看学习笔记：Theorem 7.4.1 完整证明从 Sudakov-Fernique 比较不等式（Theorem 7.2.8）推出该结果。先假设
$$ \mathcal N(T,d,\varepsilon)=:N $$有限；无限情形留给 Exercise 7.14。令 $\mathcal N$ 是 $T$ 的 maximal $\varepsilon$-separated 子集。由 Lemma 4.2.6，$\mathcal N$ 是 $T$ 的 $\varepsilon$-net，因此
$$ |\mathcal N|\ge N. $$把过程限制到 $\mathcal N$ 上，可见只需证明
$$ \mathbb E\sup_{t\in\mathcal N}X_t \ge c\varepsilon\sqrt{\log N}. $$将 $(X_t)_{t\in\mathcal N}$ 与更简单的高斯过程 $(Y_t)_{t\in\mathcal N}$ 比较，其中
$$ Y_t=\frac{\varepsilon}{\sqrt2}g_t $$且 $g_t$ 是独立 $N(0,1)$ 随机变量。为了使用 Sudakov-Fernique，比较两个过程的增量。若 $t\ne s$ 且 $t,s\in\mathcal N$，由 $\varepsilon$-separated 的定义，
$$ \mathbb E(X_t-X_s)^2=d(t,s)^2\ge\varepsilon^2, $$而
$$ \mathbb E(Y_t-Y_s)^2 = \frac{\varepsilon^2}{2}\mathbb E(g_t-g_s)^2 = \varepsilon^2, $$这里用了 $g_t-g_s\sim N(0,2)$。于是
$$ \mathbb E(X_t-X_s)^2 \ge \mathbb E(Y_t-Y_s)^2 \quad\text{for all }t,s\in\mathcal N. $$应用 Theorem 7.2.8，得到
$$ \mathbb E\sup_{t\in\mathcal N}X_t \ge \mathbb E\sup_{t\in\mathcal N}Y_t = \frac{\varepsilon}{\sqrt2} \mathbb E\max_{t\in\mathcal N}g_t \ge c\varepsilon\sqrt{\log N}. $$最后一步用了 $N$ 个 i.i.d. $N(0,1)$ 随机变量的期望最大值至少为 $c\sqrt{\log N}$；见 Exercise 2.38(b)。
7.4.1 $\mathbb R^n$ 中覆盖数的应用
Sudakov 不等式可用来控制任意集合 $T\subset\mathbb R^n$ 的覆盖数。
设 $T\subset\mathbb R^n$。对任意 $\varepsilon\gt 0$，
$$ \mathbb E\sup_{t\in T}\langle g,t\rangle \ge c\varepsilon\sqrt{\log\mathcal N(T,\varepsilon)}. $$ 查看学习笔记：Corollary 7.4.2 完整证明考虑典范高斯过程 $X_t:=\langle g,t\rangle$，其中 $g\sim N(0,I_n)$。如 Section 7.1.2 所述，这个过程的典范距离就是 $\mathbb R^n$ 中的欧氏距离：
$$ d(t,s)=\|X_t-X_s\|_{L^2}=\|t-s\|_2. $$因此结论直接由 Sudakov 不等式（Theorem 7.4.1）推出。
Exercise 8.5 会证明 Corollary 7.4.2 只差一个对数因子就是尖锐的：
$$ \mathbb E\sup_{t\in T}\langle g,t\rangle \le C\log(n)\,\varepsilon\sqrt{\log\mathcal N(T,\varepsilon)}. $$
作为 Sudakov 不等式的快速应用，粗略重推 Corollary 0.0.3 中关于 $\mathbb R^n$ 中多面体的覆盖数界。
设 $P\subset\mathbb R^n$ 是有 $N$ 个顶点的多胞体，且包含在欧氏单位球中。那么对所有 $\varepsilon\gt 0$，
$$ \mathcal N(P,\varepsilon)\le N^{C/\varepsilon^2}. $$ 查看学习笔记：Corollary 7.4.3 完整证明设 $x_1,\ldots,x_N$ 是 $P$ 的 vertices。则
$$ \mathbb E\sup_{t\in P}\langle g,t\rangle \le \mathbb E\sup_{i\le N}\langle g,x_i\rangle \le C\sqrt{\log N}. \tag{7.15} $$第一个界来自最大值原理（Exercise 1.4）：因为 $P$ 位于其 vertices 的凸包中，对每个固定 $g$，线性函数 $t\mapsto\langle g,t\rangle$ 在某个 vertex 处达到最大值。第二个界来自最大值不等式 (2.22)，因为 $\langle g,x_i\rangle\sim N(0,\|x_i\|_2^2)$ 且 $\|x_i\|_2\le1$。
把 (7.15) 代入 Corollary 7.4.2，并整理，即得
$$ \mathcal N(P,\varepsilon)\le N^{C/\varepsilon^2}. $$7.5 高斯宽度
Section 7.4.1 中，我们看到一个和任意集合 $T\subset\mathbb R^n$ 相关的重要量：典范高斯过程在 $T$ 上的大小。它在高维概率中频繁出现，所以给它命名，并看看它的基本性质。
集合 $T\subset\mathbb R^n$ 的高斯宽度定义为
$$ w(T)=\mathbb E\sup_{x\in T}\langle g,x\rangle, \qquad g\sim N(0,I_n). $$高斯宽度可视为集合 $T\subset\mathbb R^n$ 的一个基本几何量，类似体积或表面积。
(a) Finiteness：$w(T)$ 有限当且仅当 $T$ 有界。
(b) Invariance：对任意 orthogonal 矩阵 $U$ 和任意 vector $y$，有 $w(UT+y)=w(T)$。
(c) 凸包：$w(\operatorname{conv}(T))=w(T)$。
(d) Minkowski 加法与缩放：对任意 $T,S\subset\mathbb R^n$ 和 $a\in\mathbb R$，
$$ w(T+S)=w(T)+w(S), \qquad w(aT)=|a|w(T). $$(e) Symmetry：
$$ w(T)=\frac12 w(T-T) = \frac12\mathbb E\sup_{x,y\in T}\langle g,x-y\rangle, $$(f) 宽度与直径：
$$ \frac1{\sqrt{2\pi}}\operatorname{diam}(T) \le w(T) \le \frac{\sqrt n}{2}\operatorname{diam}(T). $$(g) Linear maps：对任意 $m\times n$ 矩阵 $A$，有 $w(AT)\le\|A\|w(T)$。
查看学习笔记：Proposition 7.5.2 完整证明这里只证明 (f)，其余性质留给 Exercise 7.15。
对下界，固定任意 $x,y\in T$。由于 $x-y$ 与 $y-x$ 都属于 $T-T$，由性质 (e)，
$$ \begin{aligned} w(T) &\ge \frac12\mathbb E\max\left(\langle x-y,g\rangle,\langle y-x,g\rangle\right)\\ &= \frac12\mathbb E|\langle x-y,g\rangle| = \frac12\sqrt{\frac2\pi}\,\|x-y\|_2. \end{aligned} $$最后一个等号成立，是因为 $\langle x-y,g\rangle\sim N(0,\|x-y\|_2^2)$ 且 $\mathbb E|X|=\sqrt{2/\pi}$ 对 $X\sim N(0,1)$ 成立。对所有 $x,y\in T$ 取上确界，得到下界。
对 (f) 中的上界，再次使用性质 (e)：
$$ \begin{aligned} w(T) &= \frac12\mathbb E\sup_{x,y\in T}\langle g,x-y\rangle\\ &\le \frac12\mathbb E\sup_{x,y\in T}\|g\|_2\|x-y\|_2\\ &\le \frac12\mathbb E\|g\|_2\cdot\operatorname{diam}(T). \end{aligned} $$又因为 $\mathbb E\|g\|_2\le(\mathbb E\|g\|_2^2)^{1/2}=\sqrt n$，上界得证。
Proposition 7.5.2(f) 中高斯宽度与直径的上下界都是最优的，不能去掉相差的 $O(\sqrt n)$ 因子；Exercise 7.16 给出达到两端的例子。因此直径不是描述高斯宽度的精细几何量。
查看学习笔记：Exercise 7.16 证明7.5.1 宽度的几何意义
高斯宽度有很好的几何意义：它描述集合 $T\subset\mathbb R^n$ 在随机方向上看起来有多宽。方向 $\theta\in S^{n-1}$ 上的宽度是包含 $T$ 的最小板状区域（两条垂直于 $\theta$ 的平行超平面之间区域）的宽度，见 Figure 7.3，它可写为 $\sup_{x,y\in T}\langle\theta,x-y\rangle$。如果对所有单位方向 $\theta$ 平均，就得到
$$ \mathbb E\sup_{x,y\in T}\langle\theta,x-y\rangle = \mathbb E\sup_{z\in T-T}\langle\theta,z\rangle. \tag{7.16} $$
集合 $T\subset\mathbb R^n$ 的球面宽度定义为
$$ w_s(T)=\mathbb E\sup_{x\in T}\langle\theta,x\rangle, \qquad \theta\sim\operatorname{Unif}(S^{n-1}). $$高斯宽度和球面宽度的唯一区别，是平均所用的随机向量不同：$g\sim N(0,I_n)$ 与 $\theta\sim\operatorname{Unif}(S^{n-1})$。二者都旋转不变，但 $g$ 的长度约为 $\sqrt n$ 倍的 $\theta$。因此得到下面结论。
高斯宽度大约是 $\sqrt n$ 倍的球面宽度：
$$ \left(\sqrt n-\frac C{\sqrt n}\right)w_s(T) \le w(T) \le \sqrt n\,w_s(T). $$ 查看学习笔记：Lemma 7.5.5 完整证明把高斯向量 $g$ 写成长度和方向的乘积：
$$ g=r\theta, \qquad r=\|g\|_2,\quad \theta=\frac{g}{\|g\|_2}. $$由 Exercise 3.22，$\theta\sim\operatorname{Unif}(S^{n-1})$，且 $\theta$ 与 $r$ 独立。因此
$$ \begin{aligned} w(T) &= \mathbb E\sup_{x\in T}\langle r\theta,x\rangle\\ &= \mathbb E[r]\cdot \mathbb E\sup_{x\in T}\langle\theta,x\rangle\\ &= \mathbb E\|g\|_2\cdot w_s(T). \end{aligned} $$最后使用范数集中（见 Exercise 3.2）：
$$ \sqrt n-\frac C{\sqrt n} \le \mathbb E\|g\|_2 \le \sqrt n. $$代入即可得到结论。
7.5.2 例子
欧氏球和球面的高斯宽度为
$$ w(S^{n-1})=w(B_2^n)=\mathbb E\|g\|_2 =\sqrt n\pm \frac C{\sqrt n}. \tag{7.17} $$对应的球面宽度与 $1$ 同阶。
立方体 $B_\infty^n=[-1,1]^n$ 的高斯宽度为
$$ w(B_\infty^n)=\mathbb E\|g\|_1 =\sqrt{\frac2\pi}\,n. \tag{7.18} $$cross-polytope $B_1^n$ 的高斯宽度满足
$$ w(B_1^n)=\mathbb E\|g\|_\infty \asymp \sqrt{\log n}. \tag{7.19} $$有限点集 $T$ 满足
$$ w(T)\le C\sqrt{\log|T|}\operatorname{diam}(T). $$ 查看学习笔记：有限点集高斯宽度通过重新缩放，可假设 $\operatorname{diam}(T)=1/2$；通过平移，可假设 $T$ 位于单位欧氏球中。于是对每个 $x\in T$，$\langle g,x\rangle$ 是均值为零高斯随机变量，且方差至多为 $1$。用最大值不等式 (2.22)，
$$ w(T) = \mathbb E\sup_{x\in T}\langle g,x\rangle \le C\sqrt{\log|T|}. $$恢复缩放，就得到 $w(T)\le C\sqrt{\log|T|}\operatorname{diam}(T)$。
作为练习，可以做 Exercise 7.17：一次性计算任意 $\ell^p$ 球的高斯宽度，从而同时覆盖欧氏球（$p=2$）、立方体（$p=\infty$）和 cross-polytope（$p=1$）。也可以做 Exercises 7.18-7.19，计算算子范数至多为 $1$ 的 $n\times n$ 矩阵集合的高斯宽度。
从高斯宽度看，立方体 $B_\infty^n$ 的大小接近其外接欧氏球 $\sqrt n B_2^n$；而 cross-polytope $B_1^n$ 的大小更接近其内接欧氏球 $(1/\sqrt n)B_2^n$。直观上，立方体有 $2^n$ 个顶点，宽度由庞大的主体贡献；cross-polytope 只有 $2n$ 个尖点，单个尖点很长但总体宽度仍只有 $\sqrt{\log n}$ 量级。
7.5.3 高斯复杂度与有效维数
高斯宽度 $w(T)$ 有几个有用的近亲。通常我们取 $\langle g,t\rangle$ 的期望最大值，但有时 $L^1$ 或 $L^2$ averages 更方便：
$$ w(T)=\mathbb E\sup_{x\in T}\langle g,x\rangle, \qquad \gamma(T)=\mathbb E\sup_{x\in T}|\langle g,x\rangle|, \qquad h(T)=\left(\mathbb E\sup_{x\in T}\langle g,x\rangle^2\right)^{1/2}. $$
这里 $\gamma(T)$ 称为 $T$ 的高斯复杂度。显然
$$ w(T)\le \gamma(T)\le h(T), $$
反向控制也基本成立。
对任意有界集合 $T\subset\mathbb R^n$：
(a) $\gamma(T-T)=2w(T)$。
(b) 对任意 $y\in T$，$h(T)\asymp\gamma(T)\asymp w(T)+\|y\|_2$。特别地，若 $0\in T$，则
$$ h(T)\asymp\gamma(T)\asymp w(T). $$ 查看学习笔记：Lemma 7.5.11 完整证明(a) 由 Proposition 7.5.2(e) 得到，因为 $T-T$ 关于原点对称。
(b) 只证明 $h(T)\asymp\gamma(T)$，而等价式 $\gamma(T)\asymp w(T)+\|y\|_2$ 留给 Exercise 7.20。显然 $\gamma(T)\le h(T)$。
反过来，考虑函数
$$ z\mapsto \sup_{x\in T}|\langle z,x\rangle| $$定义在 $\mathbb R^n$ 上。它的 Lipschitz 范数至多为 radius
$$ r(T):=\sup_{x\in T}\|x\|_2. $$由高斯集中 (5.5)，
$$ \left\| \sup_{x\in T}|\langle g,x\rangle|-\gamma(T) \right\|_{\psi_2} \lesssim r(T). $$于是由三角不等式和 Proposition 2.6.6(ii)，
$$ \begin{aligned} h(T) &= \left\| \sup_{x\in T}|\langle g,x\rangle| \right\|_{L^2}\\ &\lesssim \left\| \sup_{x\in T}|\langle g,x\rangle| \right\|_{\psi_2}\\ &\lesssim \gamma(T)+r(T) \lesssim \gamma(T). \end{aligned} $$最后一步用了事实 $\gamma(T)\gtrsim r(T)$；这来自 (b) 的第二部分，只需对 $y\in T$ 取上确界。
高斯宽度还帮助定义一个稳健的维数概念。集合 $T\subset\mathbb R^n$ 的普通线性代数维数，也就是包含它的最小仿射空间的维数，会因 $T$ 的微小扰动而大幅变化。下面是更稳健的替代品。
有界集合 $T\subset\mathbb R^n$ 的有效维数定义为
$$ d(T)= \frac{h(T-T)^2}{\operatorname{diam}(T)^2} \asymp \frac{w(T)^2}{\operatorname{diam}(T)^2}. $$它总是被线性代数维数控制：
$$ d(T)\le \dim(T), $$
且当 $T$ 是某个子空间中的欧氏球时取等号；见 Exercise 7.21。与普通维数不同，有效维数是稳定的：$T$ 的小扰动只会轻微改变其宽度和直径。
为了练习有效维数，可以计算椭球的有效维数（Exercise 7.23），并控制一般有限集的有效维数（Exercise 7.22）。
7.6 应用：集合的随机投影
如果把集合 $T\subset\mathbb R^n$ 投影到一个随机的 $m$ 维子空间（在 Grassmannian $G_{n,m}$ 中均匀选择），会发生什么？实践中，$T$ 可以是数据集，$P$ 可以看成一种降维方法，比如 Johnson-Lindenstrauss lemma。我们关心投影后的集合 $PT$ 的大小，也就是直径。
对有限集 $T$，Johnson-Lindenstrauss lemma（Theorem 5.3.1）说明，当 $m\gtrsim\log|T|$ 时，随机投影 $P$ 基本上像一个缩放：它把 $T$ 中所有点对距离约缩小为 $\sqrt{m/n}$ 倍。因此特别有
$$ \operatorname{diam}(PT)\approx \sqrt{\frac mn}\operatorname{diam}(T). \tag{7.20} $$
但如果 $T$ 的基数过大或为无限集，(7.20) 可能失败。例如，如果 $T=B_2^n$ 是欧氏球，没有任何投影能真正缩小它的大小：
$$ \dim(PT)=\dim(T). \tag{7.21} $$
那么一般集合 $T$ 会怎样？下一个结果说明，随机投影会按 (7.20) 缩小 $T$，但不能把它缩到球面宽度 $w_s(T)$ 以下。
设 $T\subset\mathbb R^n$ 有界，$P$ 是到随机 $m$ 维子空间 $E\sim\operatorname{Unif}(G_{n,m})$ 的正交投影。那么
$$ \mathbb E\operatorname{diam}(PT) \asymp w_s(T)+\sqrt{\frac mn}\operatorname{diam}(T). $$ 查看学习笔记：Theorem 7.6.1 完整证明这里只证明上界，下界留给 Exercise 7.26。
步骤 1：改变模型。 像 Proposition 5.3.2 的证明那样改变视角。随机子空间 $E\subset\mathbb R^n$ 可以通过把某个固定子空间，例如 $\mathbb R^m$，随机旋转得到。与其固定 $T$ 并随机旋转 $\mathbb R^m$，不如固定 $E=\mathbb R^m$ 并随机旋转 $T$。若 $U\sim\operatorname{Unif}(O(n))$ 是随机正交矩阵，则向量 $x\in T$ 的随机旋转为 $Ux$。把 $Ux$ 投影到 $E=\mathbb R^m$ 等价于保留前 $m$ 个坐标，即 $Qx$，其中 $Q$ 是由 $U$ 的前 $m$ 行组成的 $m\times n$ 矩阵。因此可以用 $Q$ 代替 $P$。
步骤 2：逼近。 不失一般性，设 $\operatorname{diam}(T)\le1$。需要控制
$$ \operatorname{diam}(QT) = \sup_{x\in T-T}\|Qx\|_2 = \sup_{x\in T-T}\max_{z\in S^{m-1}}\langle Qx,z\rangle. $$像 Theorem 4.4.3 的证明一样使用 $\varepsilon$-net argument。取 $S^{m-1}$ 的一个 $1/2$-net $\mathcal N$，由 Corollary 4.2.11 可使
$$ |\mathcal N|\le5^m. $$用 net 替换球面上的上确界，会付出因子 $2$：
$$ \operatorname{diam}(QT) \le 2\max_{z\in\mathcal N} \sup_{x\in T-T}\langle Q^{\mathsf T}z,x\rangle. \tag{7.22} $$见 Exercise 4.35。计划是：先对固定 $z\in\mathcal N$ 控制
$$ \sup_{x\in T-T}\langle Q^{\mathsf T}z,x\rangle, \tag{7.23} $$再对所有 $z$ 做并集界。
步骤 3：集中。 固定 $z\in\mathcal N$。由构造，$Q^{\mathsf T}z$ 均匀分布在球面上：
$$ Q^{\mathsf T}z\sim\operatorname{Unif}(S^{n-1}), $$这个事实在 Exercise 7.24 中仔细验证。于是 (7.23) 的期望可写成球面宽度：
$$ \mathbb E\sup_{x\in T-T}\langle Q^{\mathsf T}z,x\rangle = w_s(T-T) = 2w_s(T), $$最后一个等号是 Proposition 7.5.2(e) 的 spherical version。
为了检查 (7.23) 围绕其均值集中，使用球面上的集中不等式（Theorem 5.1.3，更具体地说 (5.30)）。由于假设 $\operatorname{diam}(T)\le1$，函数
$$ z\mapsto\sup_{x\in T-T}\langle z,x\rangle $$在球面上的 Lipschitz 范数至多为 $1$。于是 (5.30) 给出
$$ \mathbb P\left\{ \sup_{x\in T-T}\langle Q^{\mathsf T}z,x\rangle \ge 2w_s(T)+t \right\} \le 2\exp(-cnt^2). $$步骤 4：并集界。 对 $z\in\mathcal N$ 使用并集界，解除固定 $z$：
$$ \mathbb P\left\{ \max_{z\in\mathcal N} \sup_{x\in T-T}\langle Q^{\mathsf T}z,x\rangle \ge 2w_s(T)+t \right\} \le |\mathcal N|\cdot2\exp(-cnt^2). \tag{7.24} $$回忆 $|\mathcal N|\le5^m$。取 $t=Cs\sqrt{m/n}$，并令绝对常数 $C$ 足够大，则 (7.24) 中概率对任意 $s\ge1$ 都至多为 $2e^{-ms^2}$。结合 (7.24) 与 (7.22)，得到
$$ \mathbb P\left\{ \frac12\operatorname{diam}(QT) \ge 2w_s(T)+Cs\sqrt{\frac mn} \right\} \le 2e^{-ms^2}, \qquad s\ge1. $$由此可用积分尾公式（Lemma 1.6.1）控制 $\mathbb E\operatorname{diam}(QT)$；这一步留给读者检查。恢复一般 $\operatorname{diam}(T)$ 的缩放，即得上界。
查看学习笔记：为什么可归一化 $\operatorname{diam}(T)\le1$ 查看学习笔记：为什么 $Q^{\mathsf T}z$ 均匀分布在球面 查看学习笔记：球面函数的 Lipschitz 范数 查看学习笔记：由尾界推出期望界从 Theorem 7.6.1 可以得到更多直观。因为两个正项之和与它们的最大值等价（只差因子 $2$），所以可写成
$$ \operatorname{diam}(PT) \asymp \max\left[ w_s(T), \sqrt{\frac mn}\operatorname{diam}(T) \right]. $$找相变 point，就是让两项相等并解出 $m$：
$$ m= \frac{(\sqrt n\,w_s(T))^2}{\operatorname{diam}(T)^2} \asymp \frac{w(T)^2}{\operatorname{diam}(T)^2} \asymp d(T), $$这里用了 Lemma 7.5.5 和有效维数 $d(T)$ 的定义（Definition 7.5.12）。所以结论是：当 $m\ge d(T)$ 时，随机投影大致按 $\sqrt{m/n}$ 缩小；一旦 $m$ 降到有效维数 $d(T)$ 以下，缩小停止，直径停在球面宽度 $w_s(T)$ 附近，见 Figure 7.5。这是因为 $\operatorname{conv}(PT)$ 看起来像半径 $w_s(T)$ 的球；Section 9.7.2 会看到这一点。
借助更多工具，我们将在 Section 9.2.2 中改进 Theorem 7.6.1，去掉 $\sqrt{m/n}$ 前面的常数损失。
7.7 Notes
Slepian 不等式（Theorem 7.2.2）最初归功于 D. Slepian [304, 305]；现代证明可见例如 [210, Corollary 3.12]、[11, Section 2.2]、[330, Section 6.1]、[169]、[180]。
Sudakov-Fernique 不等式（Theorem 7.2.8）归功于 V. N. Sudakov [309, 310] 和 X. Fernique [124]。我们在 Section 7.2 中对 Slepian 和 Sudakov-Fernique inequalities 的证明，基于 J.-P. Kahane [180] 的方法以及 S. Chatterjee 的 smoothing argument（见 [11, Section 2.2]），并遵循 [330, Section 6.1]。
比较不等式与随机矩阵 theory 的相关性由 S. Szarek 注意到。Section 7.3 中的应用可从 Y. Gordon [140] 的工作推出。我们在那里的叙述遵循 [94, Section II.c] 的论证，该论证也在 [340, Section 5.3.1] 中复现。
Sudakov 不等式（Theorem 7.4.1）最初由 V. N. Sudakov 证明。我们的叙述遵循 [210, Theorem 3.18]；另见 [21, Section 4.2] 中通过 duality 给出的另一种证明。
Section 7.5 中引入的高斯宽度起源于几何泛函分析和渐近凸几何 [21, 246]。从 [290] 开始，人们认识到高斯宽度在信号处理和高维统计学中的作用。Remark 7.5.10 中讨论的 Milman 的 “hyperbolic sketch” 来自 [241]；更多相关内容见 [21] 的前言和 [23]。
Section 7.5.3 中引入的有效维数在文献中有若干变体，包括凸锥的 statistical dimension [228, 18, 267]。
Theorem 7.6.1 关于集合随机投影直径的结果归功于 V. Milman [245]；另见 [21, Proposition 5.7.1]。
Talagrand 收缩原理（Exercise 7.3）可见 [210, Corollary 3.17]，那里还有一个更一般的结果，允许上确界外作用凸递增函数。
Exercise 7.3 改编自 [330, Exercise 7.4]。Exercise 7.8 中高斯收缩不等式的更一般版本可见 [210, Corollary 3.17]。
Gordon 不等式（Theorem 7.2.9）及其扩展可见 [140, 141, 144, 180]。Exercise 7.11 关于对称高斯矩阵的范数，以及 Exercise 7.13(a) 关于高斯矩阵的最小奇异值，来自 [94, Section II.c]。
Exercise 7.18 引入 nuclear 范数，它是 Schatten 范数的一个例子；Schatten 范数是矩阵奇异值的 $\ell^p$ 范数。特殊情形包括 nuclear 范数（$p=1$）、Frobenius 范数（$p=2$）和算子范数（$p=\infty$）。对偶性可自然推广到所有 Schatten 范数，并可由 von Neumann trace inequality 推出。
Exercises
设 $(X_t)$ 是随机过程。
(a) 假设过程包含零随机变量 $0$。把协方差函数 $\Sigma(t,s)=\mathbb E X_tX_s$ 用度量 $d(t,s)=\|X_t-X_s\|_{L^2}$ 表示出来。
(b) 在过程对取负封闭，即 $X_t$ 在过程中就有 $-X_t$ 也在过程中时，做同样的表示。
(c) 构造例子说明：如果没有这些额外假设，通常不能由增量恢复协方差。
查看学习笔记：Exercise 7.1 证明令 $X_1(t),\ldots,X_N(t)$ 是独立、均值为 $0$ 的随机过程，均由 $t\in T$ 索引。令 $\varepsilon_i$ 为独立 Rademacher 随机变量。证明
$$ \frac12\mathbb E\sup_{t\in T} \left|\sum_{i=1}^N\varepsilon_iX_i(t)\right| \le \mathbb E\sup_{t\in T} \left|\sum_{i=1}^NX_i(t)\right| \le 2\mathbb E\sup_{t\in T} \left|\sum_{i=1}^N\varepsilon_iX_i(t)\right|. $$ 查看学习笔记：Exercise 7.2 证明令 $T\subset\mathbb R^n$ 有界，令 $\varphi_i:\mathbb R\to\mathbb R$ 为收缩映射，即 Lipschitz 常数不超过 $1$。证明
$$ \mathbb E\sup_{t\in T}\sum_i\varepsilon_i\varphi_i(t_i) \le \mathbb E\sup_{t\in T}\sum_i\varepsilon_i t_i. \tag{7.25} $$(a) 先证明 $n=2$ 的一步不等式：对 $T\subset\mathbb R^2$ 与收缩 $\varphi$，有
$$ \sup_T(t_1+\varphi(t_2))+\sup_T(t_1-\varphi(t_2)) \le \sup_T(t_1+t_2)+\sup_T(t_1-t_2). $$(b) 对 $n$ 做归纳。
查看学习笔记：Exercise 7.3 证明把 Exercise 7.3 推广到一般 Lipschitz 函数 $\varphi_i:\mathbb R\to\mathbb R$，其中 Lipschitz 常数不必都小于等于 $1$。
查看学习笔记：Exercise 7.4 证明把 Example 7.1.3 中 $N$ 步随机游走写成典范高斯过程 (7.2) 在某个集合 $T\subset\mathbb R^N$ 上的限制，其中 $Z_i\sim N(0,1)$。
查看学习笔记：Exercise 7.5 证明证明 Lemma 7.2.4。
查看学习笔记：Exercise 7.6 证明在 Sudakov-Fernique 不等式的证明中，令 $Z(u)=\sqrt u\,X+\sqrt{1-u}\,Y$，并令
$$ f(x)=\frac1\beta\log\sum_i e^{\beta x_i}. $$验证 $\frac d{du}\mathbb E f(Z(u))\le0$，步骤如下。
(a) 证明
$$ \partial_i f(x)= \frac{e^{\beta x_i}}{\sum_k e^{\beta x_k}} =:p_i(x), \qquad \partial_{ij}^2f(x)=\beta(\delta_{ij}p_i(x)-p_i(x)p_j(x)). $$(b) 用高斯插值公式 (7.9) 化简得到
$$ \frac d{du}\mathbb Ef(Z(u)) = \frac\beta4\sum_{i\ne j} \bigl[ \mathbb E(X_i-X_j)^2-\mathbb E(Y_i-Y_j)^2 \bigr] \mathbb E p_i(Z(u))p_j(Z(u)). $$(c) 在 Sudakov-Fernique 的假设下说明该表达式非正。
查看学习笔记：Exercise 7.7 证明令 $T\subset\mathbb R^n$ 有界，令 $g_i$ 为独立标准高斯，令 $\varphi_i$ 为收缩映射。用 Sudakov-Fernique 不等式证明
$$ \mathbb E\sup_{t\in T}\sum_i g_i\varphi_i(t_i) \le \mathbb E\sup_{t\in T}\sum_i g_i t_i. $$ 查看学习笔记：Exercise 7.8 证明在额外假设
$$ \mathbb E X_{ut}^2=\mathbb E Y_{ut}^2 \qquad\text{for all }u,t $$下，证明 Theorem 7.2.9。这个同方差假设可以去掉，但本题不要求证明去掉后的版本。
查看学习笔记：Exercise 7.9 证明证明：对 $u,w\in S^{n-1}$ 与 $v,z\in S^{m-1}$，有
$$ \|uv^{\mathsf T}-wz^{\mathsf T}\|_F^2 \le \|u-w\|_2^2+\|v-z\|_2^2. $$ 查看学习笔记：Exercise 7.10 证明令 $A$ 是 $n\times n$ 高斯对称矩阵，上三角元素独立，其中对角线元素服从 $N(0,2)$，非对角线元素服从 $N(0,1)$。
(a) 证明 $\mathbb E\|A\|\le2\sqrt n$。
(b) 证明尾界
$$ \mathbb P\{\|A\|\ge2\sqrt n+t\}\le2\exp(-ct^2). $$ 查看学习笔记：Exercise 7.11 证明令 $g\sim N(0,I_n)$。证明函数
$$ f(n)=\mathbb E\|g\|_2-\sqrt n $$在 $n\ge C$ 时单调递增。
查看学习笔记：Exercise 7.12 证明令 $A$ 为 $m\times n$ 高斯随机矩阵，且 $m\ge n\ge C$。用 Gordon 不等式证明：
(a) $\mathbb E s_n(A)\ge\sqrt m-\sqrt n$。
(b) 对所有 $t\ge0$，
$$ \mathbb P\{s_n(A)\le\sqrt m-\sqrt n-t\} \le 2\exp(-ct^2). $$ 查看学习笔记：Exercise 7.13 证明若 $(T,d)$ 不是 relatively compact，即存在 $\varepsilon\gt 0$ 使得 $\mathcal N(T,d,\varepsilon)=\infty$，证明均值为零的高斯过程满足
$$ \mathbb E\sup_{t\in T}X_t=\infty. $$ 查看学习笔记：Exercise 7.14 证明证明 Proposition 7.5.2 中的性质 (a)-(d) 与 (g)。
查看学习笔记：Exercise 7.15 证明构造例子说明 Proposition 7.5.2(f) 中高斯宽度与直径的上下界在任意维数 $n$ 下都可达到常数因子精度。
查看学习笔记：Exercise 7.16 证明令 $1\le p\le\infty$，并令 $B_p^n$ 为 $\mathbb R^n$ 中的 unit $\ell^p$ 球。证明
$$ w(B_p^n)\asymp \begin{cases} \sqrt{p'}\,n^{1/p'}, & p'\le\log n,\\ \sqrt{\log n}, & p'\ge\log n, \end{cases} $$其中 $p'$ 是 $p$ 的共轭指数。
查看学习笔记：Exercise 7.17 证明对矩阵 $A$，定义 nuclear 范数为奇异值之和：
$$ \|A\|_*=\sum_i s_i(A). $$(a) 证明 nuclear 范数是算子范数的对偶范数：
$$ \|A\|_*=\max\{\langle A,B\rangle:\|B\|\le1\}. $$(b) 推出 nuclear 范数确实是一个范数。
查看学习笔记：Exercise 7.18 证明令 $T=\{B:\|B\|\le1\}$ 为所有 $n\times n$ 矩阵中算子范数至多为 $1$ 的集合。证明
$$ w(T)\asymp n^{3/2}. $$ 查看学习笔记：Exercise 7.19 证明设 $T\subset\mathbb R^n$ 有界，并取 $y\in T$。证明
$$ \gamma(T)\asymp w(T)+\|y\|_2. $$ 查看学习笔记：Exercise 7.20 证明若 $T$ 是有限集合，证明
$$ d(T)\le C\log|T|. $$ 查看学习笔记：Exercise 7.22 证明考虑 ellipsoid $A(B_2^n)$。
(a) 证明 $w(A(B_2^n))\asymp\|A\|_F$。
(b) 证明
$$ d(A(B_2^n))=r(A^{\mathsf T}A)=s(A), $$其中 $d$ 是有效维数，$r$ 是有效秩，$s$ 是稳定秩。
查看学习笔记：Exercise 7.23 证明令 $z\in S^{m-1}$ 固定。令 $U$ 在正交群 $O(n)$ 上服从 Haar 分布，并令 $B$ 为 $U$ 的前 $m$ 列。验证 $Bz$ 均匀分布在 $S^{n-1}$ 上。
查看学习笔记：Exercise 7.24 证明令 $G$ 为 $m\times n$ i.i.d. 高斯矩阵。证明对任意有界 $T\subset\mathbb R^n$，
$$ \mathbb E\operatorname{diam}(GT) \asymp w(T)+\sqrt m\,\operatorname{diam}(T). $$ 查看学习笔记：Exercise 7.25 证明证明 Theorem 7.6.1 的下界：
$$ \mathbb E\operatorname{diam}(PT) \ge c\left[ w_s(T)+\sqrt{\frac mn}\operatorname{diam}(T) \right]. $$ 查看学习笔记：Exercise 7.26 证明令 $A$ 为一个大的 $n\times k$ 矩阵。
(a) 若 $P$ 是到随机 $m$ 维子空间的正交投影，证明
$$ \mathbb E\|PA\| \asymp \frac1{\sqrt n}\|A\|_F+\sqrt{\frac mn}\|A\|. $$(b) 若 $G$ 是 $m\times n$ i.i.d. 高斯矩阵，证明
$$ \mathbb E\|GA\| \asymp \|A\|_F+\sqrt m\,\|A\|. $$ 查看学习笔记：Exercise 7.27 证明