精校翻译
本页覆盖 1.pdf 的 Appetizer 正文、Notes 与 Exercises 0.1-0.9；对应解题提示已放入学习笔记页。
目录
| 原书部分 | 中文说明 | 页码 | 翻译 | 笔记 |
|---|---|---|---|---|
| Appetizer | 用概率方法从凸组合构造确定性几何近似。 | PDF p.1 | 译文 | 笔记 |
| Theorem 0.0.1-0.0.2 | Caratheodory 与近似 Caratheodory；Maurey 经验方法完整展开。 | PDF p.1-3 | 译文 | 证明 |
| 0.0.1 Covering geometric sets | 用近似 Caratheodory 构造覆盖数，并推出高维体积界。 | PDF p.3-5 | 译文 | 证明 |
| Notes | 原书对本篇方法和后续材料的补充说明。 | PDF p.5 | 译文 | 笔记 |
| Exercises 0.1-0.9 | 方差恒等式、概率方法、组合计数与高维体积练习。 | PDF p.5-7 | 译文 | 证明 |
开胃篇：用概率覆盖一个集合
我们先从一个优雅的例子开始：概率推理如何帮助我们处理几何问题。如果你更想直接进入正文，可以跳过这一节。
设 $z_1,\ldots,z_m\in\mathbb R^n$。这些点的一个凸组合，是指形如
$$ \sum_{i=1}^m \lambda_i z_i, \qquad \lambda_i\ge 0,\qquad \sum_{i=1}^m\lambda_i=1 $$
的线性组合。集合 $T\subset\mathbb R^n$ 的凸包，是 $T$ 中任意有限多个点的所有凸组合构成的集合：
$$ \operatorname{conv}(T) = \{\text{$T$ 中有限多个点的凸组合}\}. $$
图 0.1 给出一个直观示例。
在 $\mathbb R^n$ 中，定义一个凸组合所需的点数 $m$ 原本没有先验限制。不过经典的 Caratheodory 定理说明，总可以把点数限制到 $n+1$ 以内。
定理 0.0.1：Caratheodory 定理
集合 $T\subset\mathbb R^n$ 的凸包中的每个点，都可以表示为 $T$ 中至多 $n+1$ 个点的凸组合。
查看学习笔记完整证明这个 $n+1$ 的界是紧的。例如，对一个单纯形来说，确实需要一般位置上的 $n+1$ 个点。可是，如果我们只要求近似表示，而不要求精确表示，会发生什么？答案是：我们可以使用少得多的点，而且所需点数甚至不依赖维度。
定理 0.0.2：近似 Caratheodory 定理
设 $T\subset\mathbb R^n$ 包含在 Euclidean 单位球中。那么，对任意 $x\in\operatorname{conv}(T)$ 和任意 $k\in\mathbb N$，都可以找到 $x_1,\ldots,x_k\in T$，使得
$$ \left\|x-\frac1k\sum_{j=1}^k x_j\right\|_2 \le \frac1{\sqrt k}. $$ 查看学习笔记完整证明这个结论有两个令人意外的地方。第一，点数 $k$ 不依赖维度 $n$。第二，所有凸权重都是相等的，都是 $1/k$。当然，允许 $x_j$ 之间有重复。
定理 0.0.2 的证明：Maurey 经验方法
固定 $x\in\operatorname{conv}(T)$，把它写成某些点 $z_1,\ldots,z_m\in T$ 的凸组合：
$$ x=\sum_{i=1}^m\lambda_i z_i. $$把这个凸组合解释成概率分布：令随机向量 $Z$ 以概率 $\lambda_i$ 取值 $z_i$。由于 $\lambda_i\ge0$ 且总和为 1，这确实定义了一个概率分布。于是
$$ \mathbb E Z = \sum_{i=1}^m\lambda_i z_i =x. $$现在取 $Z_1,\ldots,Z_k$ 为 $Z$ 的独立同分布副本。强大数定律告诉我们样本均值会几乎必然收敛到 $x$。为了得到定量结论，直接计算均方误差：
$$ \mathbb E\left\|x-\frac1k\sum_{j=1}^k Z_j\right\|_2^2 = \frac1{k^2} \mathbb E\left\|\sum_{j=1}^k (Z_j-x)\right\|_2^2. $$由于 $Z_j-x$ 独立且均值为零，和的方差等于方差之和，所以
$$ \mathbb E\left\|x-\frac1k\sum_{j=1}^k Z_j\right\|_2^2 = \frac1{k^2} \sum_{j=1}^k \mathbb E\|Z_j-x\|_2^2. $$又因为 $Z\in T$ 且 $T$ 位于单位球中，
$$ \mathbb E\|Z-\mathbb EZ\|_2^2 = \mathbb E\|Z\|_2^2-\|\mathbb EZ\|_2^2 \le \mathbb E\|Z\|_2^2 \le 1. $$因此
$$ \mathbb E\left\|x-\frac1k\sum_{j=1}^k Z_j\right\|_2^2 \le \frac1k. $$既然平均意义下误差平方不超过 $1/k$，就必然存在某个具体的样本实现，使误差平方也不超过 $1/k$。这个样本实现给出的点 $x_1,\ldots,x_k\in T$ 就满足定理要求。
0.0.1 覆盖几何集合
定理 0.0.2 可以用来覆盖高维中的多面体。设 $P\subset\mathbb R^n$ 是一个给定集合。要用指定半径的球覆盖 $P$，寻找最少球数通常并不容易。图 0.2 中，六个球可以覆盖这个多边形；但五个球不够用是否显然？
近似 Caratheodory 定理可以帮助我们为高维中的多面体找到经济的覆盖。
设 $P\subset\mathbb R^n$ 是一个有 $N$ 个顶点、并包含在 Euclidean 单位球中的 polytope。那么对每个 $k\in\mathbb N$，$P$ 可以由至多 $N^k$ 个半径为 $1/\sqrt k$ 的 Euclidean 球覆盖。
查看学习笔记完整证明证明中的中心集合是
$$ \mathcal N = \left\{ \frac1k\sum_{j=1}^k x_j: x_j\text{ 是 }P\text{ 的顶点} \right\}. $$由于每个点 $x\in P$ 都属于这些顶点集合的凸包，近似 Caratheodory 定理保证 $x$ 距离某个 $\mathcal N$ 中的点不超过 $1/\sqrt k$。而选取 $k$ 个顶点、允许重复，一共有至多 $N^k$ 种方式，所以 $|\mathcal N|\le N^k$。
覆盖技术在许多场景中都有用。第 4.2 节会把覆盖和 packing 联系起来，第 4.3 节会把它和熵、编码联系起来，第 7-8 章还会把它用于随机过程。现在，我们先说明如何用覆盖来研究体积。
你可能记得一些特殊形状的体积公式，例如平行多面体或棱柱。但一般多面体的体积并不容易计算，尤其是在高维空间中。尽管如此，我们有一个简单的上界。
设 $P$ 是一个有 $N$ 个顶点的 polytope，并且包含在 $\mathbb R^n$ 的 Euclidean 单位球 $B$ 中。那么
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left(3\sqrt{\frac{\log N}{n}}\right)^n. \tag{0.2} $$ 查看学习笔记完整证明推论 0.0.3 说明，polytope $P$ 可以由至多 $N^k$ 个半径为 $1/\sqrt k$ 的球覆盖。每个这样的球的体积是 $(1/\sqrt k)^n\operatorname{Vol}(B)$。这是因为在 $n$ 维空间中，若把球的半径放大 $r$ 倍，体积会放大 $r^n$ 倍。
$P$ 的体积不超过覆盖它的这些球的总体积，所以
$$ \operatorname{Vol}(P) \le N^k\left(\frac1{\sqrt k}\right)^n\operatorname{Vol}(B). $$整理得到
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \frac{N^k}{k^{n/2}}. \tag{0.3} $$这个界对每个 $k\in\mathbb N$ 都成立。于是我们想选择使右侧最小的 $k$。对右侧取对数、求导并令导数为零，可得形式上的最优值
$$ k_0=\frac{n}{2\log N}. \tag{0.4} $$若直接把 $k=k_0$ 代入 (0.3)，并化简，就得到
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left(\sqrt{\frac{2e\log N}{n}}\right)^n. $$这个界甚至比定理声称的更强。不过，上面的论证有一个小漏洞：$k$ 必须是整数，而 $k_0$ 不一定是整数。为修正这一点，取 $k=\lceil k_0\rceil$。把这个 $k$ 代回 (0.3)，并使用 $k_0\le k\le k_0+1$，得到
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \frac{N^{k_0+1}}{k_0^{n/2}} \le N\left(\sqrt{\frac{2e\log N}{n}}\right)^n. $$若 $N\le e^{n/9}$，则右侧可由 $\left(3\sqrt{\log(N)/n}\right)^n$ 控制。另一方面，若 $N>e^{n/9}$，则 (0.2) 右侧大于 1；由于 $P\subset B$，这个界显然成立。因此无论哪种情况，定理都成立。
定理 0.0.4 给出一个反直觉结论：顶点数量适中的 polytope 体积极小。如果回忆证明开头关于体积缩放的讨论，可以把界 (0.2) 理解为：$P$ 的体积至多相当于半径为 $3\sqrt{\log(N)/n}$ 的 Euclidean 球的体积，甚至可能更小。因此，如果 $N$ 的增长慢于 $n$ 的指数函数，这个半径会收缩到 0，意味着 $P$ 只占单位球的极小一部分。
本书中还会遇到其他类似的高维惊讶。随着你对高维空间的直觉逐渐增长，这些现象会开始变得自然。
现在轮到你了：请验证定理 0.0.2 证明中用到的方差公式（习题 0.1、0.3），自己给出一个确定性结果的概率证明（习题 0.4），说明 approximate Caratheodory 定理的界基本是紧的（习题 0.5），检查一个非常有用的二项式和估计（习题 0.6，不要跳过），发现另一个高维反直觉现象（习题 0.7-0.8），并改进 polytope 体积上界（习题 0.9）。
本开胃篇的核心信息是：随机性不仅可以描述不确定性，也可以作为构造确定性对象的工具。后续章节会不断复用这种思想。
Exercises
(a) 回忆随机变量 $X$ 的方差满足
$$ \operatorname{Var}(X) = \mathbb{E}(X-\mathbb{E}X)^2 = \mathbb{E}X^2-(\mathbb{E}X)^2. $$我们来证明这个恒等式的高维版本。检查任意随机向量 $Z\in\mathbb{R}^n$ 都满足
$$ \mathbb{E}\|Z-\mathbb{E}Z\|_2^2 = \mathbb{E}\|Z\|_2^2-\|\mathbb{E}Z\|_2^2. $$(b) 设 $Z$ 是 $\mathbb{R}^n$ 中的随机向量，$Z'$ 是 $Z$ 的一个独立副本，即 $Z'$ 与 $Z$ 独立且同分布。检查：
$$ \mathbb{E}\|Z-\mathbb{E}Z\|_2^2 = \frac12\mathbb{E}\|Z-Z'\|_2^2. $$ 查看学习笔记完整证明随机变量 $X$ 的方差有下面的极值性质：
$$ \operatorname{Var}(X) = \min_{a\in\mathbb{R}}\mathbb{E}(X-a)^2. $$我们来证明这个事实的更一般的高维版本。检查：若随机向量 $Z\in\mathbb{R}^n$ 满足 $\mathbb{E}\|Z\|_2^2<\infty$，则
$$ \mathbb{E}\|Z-\mathbb{E}Z\|_2^2 = \min_{a\in\mathbb{R}^n}\mathbb{E}\|Z-a\|_2^2. $$ 查看学习笔记完整证明回忆：独立随机变量之和的方差等于方差之和。现在证明这个恒等式的高维版本。检查：任意独立、均值为零的随机向量 $Z_1,\ldots,Z_k\in\mathbb{R}^n$ 都满足
$$ \mathbb{E}\biggl\|\sum_{j=1}^k Z_j\biggr\|_2^2 = \sum_{j=1}^k \mathbb{E}\|Z_j\|_2^2. $$ 查看学习笔记完整证明设 $x_1,\ldots,x_n$ 是 $\mathbb{R}^n$ 中的向量，且都落在以原点为中心的 Euclidean 单位球内。
(a) 证明：可以给每个向量指定一个符号 $\varepsilon_i\in\{-1,1\}$，使得
$$ \sum_{i=1}^n \varepsilon_i x_i $$落在以原点为中心、半径为 $\sqrt n$ 的 Euclidean 球内。
(b) 解释为什么一般不能把 $\sqrt n$ 这个值再降低。
查看学习笔记完整证明通过例子说明 Theorem 0.0.2 中的界几乎是紧的。具体地，对每个 $n$，找到一个集合 $T\subset\mathbb{R}^n$ 和一个点 $x\in\operatorname{conv}(T)$，使得对 $T$ 中任意 $k$ 个点 $x_1,\ldots,x_k$ 的任意凸组合 $\sum_{j=1}^k\lambda_jx_j$，都有
$$ \biggl\| x-\sum_{j=1}^k\lambda_jx_j \biggr\|_2 \ge \sqrt{\frac1k-\frac1n}. $$固定 $k$ 并令 $n\to\infty$，即可看出 Theorem 0.0.2 在高维中是渐近紧的。
查看学习笔记完整证明证明：对任意整数 $1\le k\le n$，都有
$$ \left(\frac{n}{k}\right)^k \le \binom{n}{k} \le \sum_{j=0}^k \binom{n}{j} \le \left(\frac{en}{k}\right)^k. $$ 查看学习笔记完整证明我们来证明一个反直觉事实：高维球的大部分体积都靠近表面。考虑 $\mathbb{R}^n$ 的 Euclidean 单位球中那些距离球面不超过 $5/n$ 的点；见图 0.3。证明：这些点占单位球体积的 $99\%$ 以上。
设随机向量 $X$ 在 $\mathbb{R}^n$ 的 Euclidean 单位球中均匀分布。证明：
$$ \mathbb{E}\|X\|_2 = \frac{n}{n+1}. $$ 查看学习笔记完整证明把 Theorem 0.0.4 中的 $N$ 改进为 $N/n$。设 $P$ 是一个有 $N\ge n$ 个顶点的 polytope，且包含在 $\mathbb{R}^n$ 的 Euclidean 单位球 $B$ 中。证明：
$$ \frac{\operatorname{Vol}(P)}{\operatorname{Vol}(B)} \le \left( C\sqrt{\frac{\log(eN/n)}{n}} \right)^n, $$其中 $C>0$ 是一个绝对常数。
查看学习笔记完整证明注记
本节展示了概率方法：用随机性构造一个有用对象。Alon 和 Spencer 的书 [17] 给出了概率方法的许多例子，主要来自组合数学。
本节使用的 B. Maurey 经验方法最早发表于 [271]，此后出现了许多应用。B. Carl 曾用它得到 covering number 的界 [76]，正如我们在推论 0.0.3 中所做的那样。
近似 Caratheodory 定理（定理 0.0.2）有一个较弱版本：不要求凸组合中所有权重相等。即使这个较弱版本也并不平凡。它可以不用概率方法证明，而是使用 Frank-Wolfe 算法的一种形式。这是一种确定性的、迭代式的贪婪算法；可参见 [43, Lemma 2.6]。
与 Caratheodory 定理类似，组合几何中的若干其他结果也可以通过允许“近似”而非“精确”来变成维度无关的形式 [10]。
定理 0.0.4 及其在习题 0.9 中的加强最早由 B. Carl 和 A. Pajor [77] 证明。通过考虑随机 polytopes，N. Dafnis、A. Giannopoulos 和 A. Tsolomitis [90] 证明，习题 0.9 中的界在整个有趣范围 $n\le N\le e^n$ 内都是最优的。
后续阅读
继续阅读 第 1 章：分析与概率快速回顾。