Dimensionality Reduction

从高维到低维

上几讲反复出现一个隐喻：要在不丢失重要信息的前提下，把庞大的数据「压缩」成更小的对象。Sketching 把流压缩成 $O(\log n)$ 大小的数据结构，Hashing 把无穷字符串空间压缩成 $O(n)$ 个桶。本讲继续这条主线，但压缩的对象换成了几何点——我们有一堆 $\R^d$ 中的高维向量，希望在低维空间里找到「替身」，使得任意两点之间的距离几乎不变。

为什么需要这件事？数据科学里的几乎所有实际向量都是高维的：一张 $1000 \times 1000$ 的图像是 $10^6$ 维向量；一段文本的 TF-IDF^[1] 表示动辄数万维；蛋白质序列的特征向量也常常上千维。直接在这些维度上做最近邻搜索、聚类、回归，会撞上一个臭名昭著的现象——维度的诅咒（Curse of Dimensionality）：

• 距离的「分辨率」消失。在高维球面上，任意两点的距离都集中在某个固定值附近，导致「最近邻」和「最远邻」几乎一样远。
• 算法复杂度爆炸。$k$-d tree、Voronoi 图等低维利器在维度 $d \gtrsim \log n$ 时全部失效，时间或空间退化为 $n^{\Omega(d)}$。

下图直观展示第一条诅咒：左图是不同维度下「两两距离 / 平均距离」的分布，维度越高，分布越集中在 $1$ 附近——所有点几乎彼此等距；右图是「最远与最近距离之差」相对平均距离的对比度，随维度迅速衰减到接近 $0$。当对比度趋于零，「谁是最近邻」便失去了意义。

降维就是与这一诅咒正面对抗的武器。本讲的核心问题是：至少需要多少维才能保住所有 $\binom{n}{2}$ 对距离？ 答案出乎意料——只需 $O(\log n)$ 维，而且对任意 $d$ 都成立。这就是 1984 年由 Johnson 与 Lindenstrauss 证明的奇妙定理。沿着这条线索，我们还会看到：

• 高维 Hamming 空间里的近似最近邻；
• 局部敏感哈希（LSH）——把 JL 的思想推广到「哈希值碰撞」的语言；
• 比朴素 JL 更快的 Fast JL 变换；
• 把降维从点集推广到整个子空间的子空间嵌入（OSE），以及它在大规模线性回归中的应用。

度量嵌入与降维问题

度量嵌入

给定两个度量空间 $(X, d_X)$ 和 $(Y, d_Y)$，度量嵌入（Metric Embedding）是一个映射 $\phi\colon X \to Y$，它将 $X$ 中的点搬到 $Y$ 中。嵌入的「质量」由失真（Distortion）刻画：若存在 $\alpha \ge 1$ 使得对所有 $\bm{x}_1, \bm{x}_2 \in X$，

$$\frac{1}{\alpha} d_X(\bm{x}_1, \bm{x}_2) \le d_Y(\phi(\bm{x}_1), \phi(\bm{x}_2)) \le \alpha \cdot d_X(\bm{x}_1, \bm{x}_2)$$

则称 $\phi$ 是一个 $\alpha$-失真嵌入。$\alpha = 1$ 即等距嵌入；$\alpha$ 越接近 $1$，嵌入越「保距」。

降维问题

把 $X$ 换成高维欧氏空间 $\R^d$，$Y$ 换成低维欧氏空间 $\R^k$，再要求嵌入只对给定的 $n$ 个点（而非整个空间）保距，就得到降维问题：

降维（Dimension Reduction）

• 输入：$n$ 个点 $\bm{x}_1, \dots, \bm{x}_n \in \R^d$，误差 $0 < \varepsilon < 1$。
• 输出：$n$ 个点 $\bm{y}_1, \dots, \bm{y}_n \in \R^k$，满足 $\forall 1 \le i, j \le n$：

$$(1 - \varepsilon)\|\bm{x}_i - \bm{x}_j\| \le \|\bm{y}_i - \bm{y}_j\| \le (1 + \varepsilon)\|\bm{x}_i - \bm{x}_j\|$$

三个核心问题：

• $k$ 能做多小？理想情况下 $k \ll d$。
• 用什么范数 $\|\cdot\|$？最常见是 $\ell_2$ 范数（欧氏距离）。
• 嵌入是否能「高效」构造？

一个动机：$k$-means 聚类

为什么我们关心降维？因为下游算法（聚类、回归、近邻搜索）的时间通常与维数 $d$ 成正比甚至更高次。以 $k$-means 为例：

$k$-means

给定数据 $X = \{\bm{x}_1, \dots, \bm{x}_n\} \subset \R^d$ 和聚类个数 $k$，找出中心 $\bm{y}_1, \dots, \bm{y}_k \in \R^d$ 最小化：

$$\sum_{i \in [n]} \min_{j \in [k]} \|\bm{x}_i - \bm{y}_j\|_2^2$$

固定一个划分 $\mathcal{P} = (\mathcal{P}_1, \dots, \mathcal{P}_k)$，最优中心就是各簇的质心，目标可写成簇内两两平方距离之和：

$$\min_{k\text{-parts } \mathcal{P}} \sum_{j \in [k]} \frac{1}{|\mathcal{P}_j|} \sum_{i \ne i' \in \mathcal{P}_j} \|\bm{x}_i - \bm{x}_{i'}\|_2^2$$

如果降维矩阵 $\bm{\Pi}$ 能把所有两两距离保持在 $(1 \pm \varepsilon)$ 倍内，那么 $k$-means 在低维点 $\bm{\Pi} \bm{x}_i$ 上得到的最优划分，与原数据上的最优划分相差最多 $(1 \pm \varepsilon)^2$ 因子，并且后续的所有计算只在 $\R^k$ 而非 $\R^d$ 中进行，速度可以快出数量级。

Johnson-Lindenstrauss 定理

降维的故事真正的起点是下面这个 1984 年的定理。

Johnson-Lindenstrauss 定理（1984）

$\forall 0 < \varepsilon < 1$，对 $\R^d$ 中任意 $n$ 点构成的集合 $S$，存在矩阵 $\bm{A} \in \R^{k \times d}$，其中 $k = O(\varepsilon^{-2} \log n)$，使得

$$\forall \bm{x}, \bm{y} \in S\colon \quad (1 - \varepsilon)\|\bm{x} - \bm{y}\|_2^2 \le \|\bm{A}\bm{x} - \bm{A}\bm{y}\|_2^2 \le (1 + \varepsilon)\|\bm{x} - \bm{y}\|_2^2$$

"In Euclidean space, it is always possible to embed a set of $n$ points in arbitrary dimension to $O(\log n)$ dimension with constant distortion."
「在欧氏空间中，任意 $n$ 个点的集合都可以被嵌入到 $O(\log n)$ 维的空间中，并且失真是常数级别的。」

最反直觉的是 $k$ 与原维度 $d$ 完全无关——无论原数据是 $10^3$ 维还是 $10^9$ 维，只要点数还是 $n$，目标维度都只是 $O(\log n)$。

三种构造

定理的证明使用概率方法：随机抽取一个矩阵 $\bm{A}$，证明它以高概率满足要求，因而至少存在一个满足要求的 $\bm{A}$。具体的「随机抽取」有三种经典构造：

概率方法到底是什么？

它不是某个具体算法，而是一种存在性证明技巧：要证「存在某个对象具有性质 $P$」，我们设计一个随机过程随机抽出一个对象，并证明它具有性质 $P$ 的概率 $> 0$（通常证「概率 $\to 1$」更强）。因为概率 $> 0$ 意味着至少有一个样本点对应的对象满足 $P$，所以这种对象存在。

一旦失败概率被压到非常小（比如 $1/n$），「以高概率」这件事本身就有算法意义：随机抽一次就能用，失败时再抽一次即可。

构造	$\bm{A}_{ij}$ 的分布	提出者
均匀随机 $k$ 维子空间投影	$\bm{A}$ 的 $k$ 行是 $\R^d$ 中一组均匀随机正交单位向量	Johnson-Lindenstrauss; Dasgupta-Gupta
独立高斯	$\bm{A}_{ij} \sim \mathcal{N}(0, 1/k)$ i.i.d.	Indyk-Motwani
独立 $\pm 1$	$\bm{A}_{ij} \in \{-1/\sqrt{k}, +1/\sqrt{k}\}$ 等概率 i.i.d.	Achlioptas

三种构造的失败概率都形如 $O(1/n)$，我们将主要分析「高斯构造」。

范数保持归约

直接证明「所有 $\binom{n}{2}$ 对距离都被保持」很难。一个标准技巧是联合界归约：

注意 $\bm{A}(\bm{x} - \bm{y})$ 是一个向量，因此「$\|\bm{A}\bm{x} - \bm{A}\bm{y}\|_2^2 \in (1 \pm \varepsilon)\|\bm{x} - \bm{y}\|_2^2$」等价于「对单位向量 $\bm{u} = (\bm{x} - \bm{y})/\|\bm{x} - \bm{y}\|$，有 $\|\bm{A}\bm{u}\|_2^2 \in 1 \pm \varepsilon$」。于是只需证明：

范数保持引理

对任意单位向量 $\bm{u} \in \R^d$：

$$\Pr\bigl[\bigl|\|\bm{A}\bm{u}\|_2^2 - 1\bigr| > \varepsilon\bigr] < \frac{1}{n^3}$$

一旦有了这个，对 $\binom{n}{2} = O(n^2)$ 对点向量 $\bm{x} - \bm{y}$ 做联合界：所有差向量都被良好保持的概率 $\ge 1 - O(n^2) \cdot 1/n^3 = 1 - O(1/n)$。

下图把这步归约拆成两半：左边——任意一对点 $\bm{x}, \bm{y}$ 的差归一化后只是单位球面上的一个方向，所以要管的方向至多 $\binom{n}{2}$ 个；右边——单个方向的失败概率被引理压到 $1/n^3$ 这么小，即便对 $\binom{n}{2} \approx n^2/2$ 个方向做联合界，总失败也只有 $O(1/n)$。正是「$1/n^3$ 足够小」让联合界撑得住。

至此，降维问题被压缩为一个一维的问题：分析 $\|\bm{A}\bm{u}\|_2^2$ 对固定单位向量 $\bm{u}$ 的分布。

高斯构造的证明

设 $\bm{A} \in \R^{k \times d}$，每个元素 $\bm{A}_{ij} \sim \mathcal{N}(0, 1/k)$ 独立同分布。

期望计算

$\bm{A}\bm{u}$ 是 $k$ 维向量，第 $i$ 个分量为

$$(\bm{A}\bm{u})_i = \sum_{j=1}^d \bm{A}_{ij} u_j$$

由「独立高斯之和仍是高斯」^[2]的性质，$\mathcal{N}(\mu_1, \sigma_1^2) + \mathcal{N}(\mu_2, \sigma_2^2) \to \mathcal{N}(\mu_1 + \mu_2, \sigma_1^2 + \sigma_2^2)$，所以

$$(\bm{A}\bm{u})_i \sim \mathcal{N}\left(0,\ \frac{\sum_{j=1}^d u_j^2}{k}\right) = \mathcal{N}\left(0, \frac{1}{k}\right)$$

最后一步用了 $\bm{u}$ 是单位向量，$\|\bm{u}\|_2^2 = 1$。最终所有 $\bm{u}$ 的「方向信息」消失了，结果只与 $\bm{u}$ 的长度有关。这正是高斯分布的球对称性在起作用。即 $(\bm{A} \bm{u})_i$ 独立同分布于 $\mathcal{N}(0, 1/k)$。

由 $\mathbb{E}[Z^2] = \mathrm{Var}(Z) + \mathbb{E}[Z]^2$，我们有 $\mathbb{E}[(\bm{A}\bm{u})_i^2] = \mathrm{Var}((\bm{A}\bm{u})_i) = 1/k$，从而

$$\mathbb{E}\bigl[\|\bm{A}\bm{u}\|_2^2\bigr] = \sum_{i=1}^k \mathbb{E}[(\bm{A}\bm{u})_i^2] = k \cdot \frac{1}{k} = 1$$

期望已经对了（即无偏）。接下来要证 $\|\bm{A}\bm{u}\|_2^2$ 不会偏离 $1$ 太远。

$\chi^2$ 集中度

令 $Y_i = (\bm{A}\bm{u})_i$，则 $Y_i \sim \mathcal{N}(0, 1/k)$ i.i.d.。改用「标准化」的变量 $X_i = \sqrt{k} \cdot Y_i \sim \mathcal{N}(0, 1)$ i.i.d.，则

$$\|\bm{A}\bm{u}\|_2^2 = \sum_{i=1}^k Y_i^2 = \frac{1}{k} \sum_{i=1}^k X_i^2$$

事件 $\bigl|\|\bm{A}\bm{u}\|_2^2 - 1\bigr| > \varepsilon$ 等价于 $\bigl|\sum_i X_i^2 - k\bigr| > \varepsilon k$。而 $\sum_i X_i^2$ 服从自由度为 $k$ 的 $\chi^2$ 分布（$k$ 个独立标准高斯平方和的标准名称，期望 $= k$）。我们需要的是它的集中不等式——刻画 $\sum_i X_i^2$ 偏离自己期望 $k$ 的概率有多小。

下图画出 $\frac{1}{k}\sum_i X_i^2$（也就是 $\|\bm{A}\bm{u}\|_2^2$）的概率密度：$k = 1$ 时分布极宽，随 $k$ 增大迅速向期望 $1$ 收拢成尖峰。这正是「目标维度越高、范数越稳」的来源——只要 $k$ 取得够大，$\|\bm{A}\bm{u}\|_2^2$ 就以压倒性概率落在 $1 \pm \varepsilon$ 之内。

$\chi^2$ 分布的 Chernoff 界

设 $X_1, \dots, X_k \sim \mathcal{N}(0, 1)$ 独立，则

$$\begin{aligned} \Pr\left[\sum_{i=1}^k X_i^2 > (1 + \varepsilon) k\right] &< \e^{-\varepsilon^2 k / 8} \\ \Pr\left[\sum_{i=1}^k X_i^2 < (1 - \varepsilon) k\right] &< \e^{-\varepsilon^2 k / 8} \end{aligned}$$

注意这与上一讲对 Bernoulli 之和的 Chernoff 界形式一致：偏离 $\varepsilon$ 倍期望的概率指数级压缩。但底层随机变量从 $\{0,1\}$ 变成了高斯平方，证明也需要相应地改造。

证明（上尾，下尾对称）

对任意 $\lambda > 0$：

$$\Pr\left[\sum_i X_i^2 > (1 + \varepsilon) k\right] = \Pr\left[\e^{\lambda \sum_i X_i^2} > \e^{\lambda(1+\varepsilon)k}\right] \le \e^{-\lambda(1+\varepsilon)k} \cdot \prod_{i=1}^k \mathbb{E}[\e^{\lambda X_i^2}]$$

第一步是 Markov 不等式的指数化（把 $\Pr[Y > a]$ 转成 $\Pr[\e^{\lambda Y} > \e^{\lambda a}] \le \mathbb{E}[\e^{\lambda Y}] / \e^{\lambda a}$），$\mathbb{E}[\e^{\lambda Y}]$ 就是 $Y$ 的矩生成函数（MGF）——能把高阶矩信息编码进一个解析函数。第二步用了独立性：和的 MGF 是各项 MGF 的乘积。

对单个标准高斯 $X \sim \mathcal{N}(0, 1)$ 的矩生成函数（取于 $X^2$ 上）：

$$\mathbb{E}[\e^{\lambda X^2}] = \int_{-\infty}^{\infty} \frac{1}{\sqrt{2\pi}} \e^{-x^2/2} \e^{\lambda x^2} \d x = \frac{1}{\sqrt{1 - 2\lambda}}, \quad \lambda < \frac{1}{2}$$

直接对积分指数 $-x^2/2 + \lambda x^2 = -(1 - 2\lambda)x^2 / 2$ 做高斯归一化即可得到上式。

代回去：

$$\Pr\left[\sum_i X_i^2 > (1 + \varepsilon) k\right] \le \frac{\e^{-\lambda(1+\varepsilon)k}}{(1 - 2\lambda)^{k/2}}$$

取 $\lambda = \varepsilon / 4$（保证 $\lambda < 1/4 < 1/2$）。利用 $1 - 2\lambda \ge \e^{-2\lambda - 2\lambda^2}$（小 $\lambda$ 泰勒展开），

$$\frac{1}{(1 - 2\lambda)^{k/2}} \le \e^{(\lambda + \lambda^2) k} = \e^{(\varepsilon/4 + \varepsilon^2/16)k}$$

因此

$$\Pr[\cdot] \le \e^{-(\varepsilon/4)(1+\varepsilon)k + (\varepsilon/4 + \varepsilon^2/16)k} = \e^{-\varepsilon^2 k / 8 + O(\varepsilon^3 k)}$$

对 $0 < \varepsilon < 1$ 主导项是 $-\varepsilon^2 k / 8$，得到结论。下尾对 $-X^2$ 做同样的指数化论证，对称。

选取 $k$

由 $\chi^2$ 集中不等式，

$$\Pr\bigl[\bigl|\|\bm{A}\bm{u}\|_2^2 - 1\bigr| > \varepsilon\bigr] \le 2 \e^{-\varepsilon^2 k / 8}$$

要使这个概率 $< 1/n^3$，取

$$k = \frac{8 \cdot 3 \ln n}{\varepsilon^2} = O\bigl(\varepsilon^{-2} \log n\bigr)$$

即可。这正是 JL 定理中的 $k$。结合范数保持归约和联合界，我们证明了 JL 定理对高斯构造成立。

子空间投影构造

把 $\bm{A}$ 取为「均匀随机 $k$ 维子空间上的正交投影」，再乘上放缩因子 $\sqrt{d / k}$——这是 JL 定理最早的构造。它与高斯构造给出形式相同的尾界（同阶的 $k$），但思路是几何而非代数。理解这两条路殊途同归的原因，比单纯走一遍计算更有价值。

几何直觉与放缩因子

把单位向量 $\bm{u}$ 投影到一个随机 $k$ 维子空间，得到一个 $k$ 维向量。它的长度平均会缩小：直观地，长度的 $k/d$ 落在了被「保留」的子空间里，剩下 $(d - k)/d$ 被「丢掉」了。因此放缩 $\sqrt{d / k}$ 把期望拉回到 $1$：

$$\bm{A}\bm{u} = \sqrt{\frac{d}{k}} \cdot \operatorname{Proj}_S(\bm{u}), \qquad \mathbb{E}\bigl[\|\bm{A}\bm{u}\|_2^2\bigr] = 1$$

与高斯构造的对比：

构造	几何描述
高斯	随机选 $k$ 个不一定正交的高斯方向，把向量投过去
子空间投影	随机选一个真正的 $k$ 维正交子空间，把向量正交投过去，再放大 $\sqrt{d/k}$

旋转不变性把问题翻过来

直接分析「固定向量 + 随机正交矩阵」不容易，但有一个非常优雅的对偶视角。考虑两个分布：

视角 A	视角 B
固定单位向量 $\bm{u}$，对随机 $k$ 维子空间 $S$ 求 $\|\operatorname{Proj}_S(\bm{u})\|$	固定 $k$ 维子空间 $S_0$（取前 $k$ 个坐标的子空间），对均匀随机单位向量 $\bm{Y} \in \mathbb{S}^{d-1}$ 求 $\|\operatorname{Proj}_{S_0}(\bm{Y})\|$

等价性

两个分布相同。核心理由：内积在旋转下不变。把视角 A 中的随机子空间 $S$ 想成「先固定 $S_0$、再让一个均匀随机正交矩阵 $\bm{Q}$ 把 $S_0$ 转过去」，则 $\operatorname{Proj}_S(\bm{u}) = \bm{Q} \operatorname{Proj}_{S_0}(\bm{Q}^\intercal \bm{u})$，而 $\bm{Q}^\intercal \bm{u}$ 在 $\bm{Q}$ 均匀随机时即均匀单位向量。

因此 $\|\bm{A}\bm{u}\|^2$（视角 A 配上放缩）与

$$\frac{d}{k} \cdot \sum_{i=1}^k Y_i^2, \qquad \bm{Y} = (Y_1, \dots, Y_d) \text{ 是 } \mathbb{S}^{d-1} \text{ 上的均匀单位向量}$$

同分布。问题从「分析正交矩阵」转到「分析均匀单位向量的前 $k$ 个分量」。

下图对照这两个视角：左边固定向量 $\bm{u}$、让 $k$ 维子空间随机转动；右边固定子空间、让单位向量 $\bm{Y}$ 随机转动。由于内积在旋转下不变，两者给出完全相同的投影长度分布——这正是把「随机子空间」难题翻译成「随机单位向量的前 $k$ 个坐标」的依据。

均匀单位向量的高斯生成

如何在 $\mathbb{S}^{d-1}$ 上均匀采样？最优雅的办法借助高斯的球对称性：

1. 抽 $\bm{X} = (X_1, \dots, X_d)$，每个 $X_i \sim \mathcal{N}(0, 1)$ 独立；
2. 令 $\bm{Y} = \bm{X} / \|\bm{X}\|$。

理由是标准多维高斯的密度函数

$$p(\bm{x}) = \prod_{i=1}^d \frac{1}{\sqrt{2\pi}} \e^{-x_i^2/2} = (2\pi)^{-d/2} \e^{-\|\bm{x}\|_2^2/2}$$

仅依赖于 $\|\bm{x}\|$ 而与方向无关——这就是「球对称」。把这样一个球对称随机向量除以其范数，得到的方向自然在球面上均匀。

归约到独立 $\chi^2$ 之和

由上一步，

$$\sum_{i=1}^k Y_i^2 = \frac{\sum_{i=1}^k X_i^2}{\sum_{i=1}^d X_i^2}$$

要证明

$$\Pr\left[\sum_{i=1}^k Y_i^2 > (1 + \varepsilon) \cdot \frac{k}{d}\right] < \frac{1}{2 n^3}$$

即 $\Pr\left[\sum_{i=1}^k X_i^2 > (1 + \varepsilon)\cdot \dfrac{k}{d} \cdot \sum_{i=1}^d X_i^2\right] < \dfrac{1}{2 n^3}$。

把比例移到一边、合并同类项：

$$\Pr\left[(d - (1 + \varepsilon)k) \sum_{i=1}^k X_i^2 - (1 + \varepsilon)k \sum_{i=k+1}^d X_i^2 > 0\right] < \frac{1}{2 n^3}$$

这是两个独立 $\chi^2$ 之差的尾概率，可以用与高斯构造完全相同的指数化 + MGF 技巧处理。

上尾的详细推导

对任意 $\lambda > 0$，把事件指数化：

$$\Pr\left[(d - (1 + \varepsilon)k) \sum_{i=1}^k X_i^2 - (1 + \varepsilon)k \sum_{i=k+1}^d X_i^2 > 0\right] = \Pr\left[\e^{\lambda \cdot \text{LHS}} > 1\right] \le \mathbb{E}\left[\e^{\lambda \cdot \text{LHS}}\right]$$

按 $X_1, \dots, X_d$ 相互独立拆开（前 $k$ 项与后 $d-k$ 项是不同分量，仍然独立）：

$$\mathbb{E}\left[\e^{\lambda \cdot \text{LHS}}\right] = \prod_{i=1}^k \mathbb{E}\bigl[\e^{\lambda (d - (1+\varepsilon)k) X_i^2}\bigr] \cdot \prod_{i=k+1}^d \mathbb{E}\bigl[\e^{-\lambda (1+\varepsilon)k X_i^2}\bigr]$$

用 $\mathbb{E}[\e^{s X^2}] = (1 - 2s)^{-1/2}$（$s < 1/2$）：

$$= (1 - 2\lambda(d - (1+\varepsilon)k))^{-k/2} \cdot (1 + 2\lambda (1+\varepsilon)k)^{-(d-k)/2}$$

取 $\lambda = \dfrac{\varepsilon}{4(d - k)}$ 并展开，得到约 $\e^{-\varepsilon^2 k / 8 + O(\varepsilon^3 k)}$ 的上界。对 $\varepsilon \in (0, 1)$ 取 $k = \Theta(\varepsilon^{-2} \log n)$ 即可让该概率 $< 1 / (2 n^3)$。下尾对称。

因此

$$\Pr\left[\sum_{i=1}^k Y_i^2 > (1 + \varepsilon)\frac{k}{d}\right] < \frac{1}{2 n^3},\quad \Pr\left[\sum_{i=1}^k Y_i^2 < (1 - \varepsilon)\frac{k}{d}\right] < \frac{1}{2 n^3}$$

合起来即 $\Pr[\,|\|\bm{A}\bm{u}\|_2^2 - 1| > \varepsilon\,] < 1/n^3$，与高斯构造一致。子空间投影是 JL 定理的「最干净」构造——它和高斯构造给出形式相同的尾界（$\chi^2$ 集中度），但把随机性「藏」到了几何里：随机选子空间 + 球对称的均匀单位向量。

$\pm 1$ 矩阵与 Tug-of-War

高斯条目要采样实数、计算时也要做实数乘法；如果换成简单的 $\pm 1$ 条目，乘法可以退化为符号翻转加加法，硬件实现快得多。这就引出了 Achlioptas 的构造。

与 Count Sketch 的同构

回顾上一讲 Count Sketch 估计 $\|\bm{x}\|_2^2$ 的「Tug-of-War」版本：用一组 $\pm 1$ 哈希函数 $\sigma_j$ 给每个元素打符号，再把结果累加。把 $k$ 行符号向量拼起来、除以 $\sqrt{k}$ 做归一，正是 Achlioptas 的随机投影矩阵：

$$\bm{A}_{ij} = \dfrac{r_{ij}}{\sqrt{k}}, \qquad r_{ij} \in \{-1, +1\} \text{ 等概率 i.i.d.}$$

期望仍然无偏

固定单位向量 $\bm{u} \in \R^d$。第 $i$ 行作用在 $\bm{u}$ 上得到

$$(\bm{A}\bm{u})_i = \frac{1}{\sqrt{k}} \sum_{j=1}^d r_{ij} u_j = \frac{1}{\sqrt{k}} Y_i, \qquad Y_i = \sum_{j=1}^d r_{ij} u_j$$

于是 $\|\bm{A}\bm{u}\|_2^2 = \dfrac{1}{k} \sum_{i=1}^k Y_i^2$。问题归结为：独立同分布的 $Y_1^2, \dots, Y_k^2$ 的平均值是否集中在 $1$ 附近？

展开 $Y_i^2$：

$$Y_i^2 = \left(\sum_j r_{ij} u_j\right)^2 = \sum_j r_{ij}^2 u_j^2 + \sum_{p \ne q} r_{ip} r_{iq} u_p u_q$$

注意 $r_{ij}^2 = 1$（确定值），而 $\{r_{ip}\}, \{r_{iq}\}$ 独立、均值为 $0$，所以 $\mathbb{E}[r_{ip} r_{iq}] = 0$（$p \ne q$）。因此

$$\mathbb{E}[Y_i^2] = \sum_j u_j^2 = \|\bm{u}\|_2^2 = 1, \quad \mathbb{E}\bigl[\|\bm{A}\bm{u}\|_2^2\bigr] = 1$$

与高斯构造一样，期望已经无偏。剩下要看的就是方差，即 $\|\bm{A}\bm{u}\|_2^2$ 偏离 $1$ 的程度。

方差为 $O(1/k)$：Chebyshev 还不够

下一步是计算 $\mathrm{Var}(Y_i^2) = \mathbb{E}[Y_i^4] - 1$，关键是四阶矩：

$$Y_i^4 = \left(\sum_j r_{ij} u_j\right)^4 = \sum_{a, b, c, d} r_{ia} r_{ib} r_{ic} r_{id} \cdot u_a u_b u_c u_d$$

由 Rademacher 的对称性 $\mathbb{E}[r_{ia} r_{ib} r_{ic} r_{id}]$ 仅在「指标两两配对」时为 $1$，否则为 $0$。配对方式有三种：$(a=b, c=d),\, (a=c, b=d),\, (a=d, b=c)$。仔细数（注意 $a=b=c=d$ 被三种方式共同覆盖），最终

$$\mathbb{E}[Y_i^4] = 3 \sum_{j \ne j'} u_j^2 u_{j'}^2 + \sum_j u_j^4 = 3\bigl(\|\bm{u}\|_2^4 - \sum_j u_j^4\bigr) + \sum_j u_j^4 = 3 - 2 \sum_j u_j^4 \le 3$$

所以 $\mathrm{Var}(Y_i^2) \le 2$。各 $Y_i^2$ 独立，故

$$\mathrm{Var}\bigl(\|\bm{A}\bm{u}\|_2^2\bigr) = \frac{1}{k^2} \sum_{i=1}^k \mathrm{Var}(Y_i^2) \le \frac{2}{k} = O\left(\frac{1}{k}\right)$$

Chebyshev 不等式给出

$$\Pr\bigl[\,\bigl|\|\bm{A}\bm{u}\|_2^2 - 1\bigr| \ge \varepsilon\,\bigr] \le \frac{O(1/k)}{\varepsilon^2} = O\left(\frac{1}{k \varepsilon^2}\right)$$

Chebyshev 路线的瓶颈

要让上式 $< 1/n^3$，需要 $k = \Omega(n^3 / \varepsilon^2)$。这比 JL 所需的 $\Theta(\varepsilon^{-2} \log n)$ 大了 $\Theta(n^3 / \log n)$ 倍，维度爆炸。问题在于 Chebyshev 只用到二阶矩，丢掉了 Rademacher 和的指数集中性。

矩比较：拿到与高斯同阶的 $k$

Achlioptas 的关键观察是：Rademacher 加权和 $Y_i = \sum_j r_{ij} u_j$ 与高斯加权和 $\sum_j Z_{ij} u_j \sim \mathcal{N}(0, 1)$ 不仅二阶矩都等于 $1$，而且更进一步——Rademacher 的所有偶数阶矩都被高斯支配。于是可以照搬高斯的 MGF 计算，得到完全同阶的指数级尾界。

矩比较引理

令 $\bm{w} = (1, 1, \dots, 1) \in \R^d$，$\bm{Z} \in \R^d$ 是 i.i.d. $\mathcal{N}(0, 1)$ 向量，$\bm{r} \in \{-1, +1\}^d$ 是 i.i.d. 均匀 Rademacher 向量。对任意 $k \in \N$ 与 $\|\bm{x}\|_2^2 = d$ 的 $\bm{x}$：

$$\mathbb{E}\bigl[\langle \bm{x}, \bm{r} \rangle^{2k}\bigr] \le \mathbb{E}\bigl[\langle \bm{w}, \bm{r} \rangle^{2k}\bigr] \le \mathbb{E}\bigl[\langle \bm{w}, \bm{Z} \rangle^{2k}\bigr]$$

关于归一化：引理把 $\bm{x}$ 归一化到 $\|\bm{x}\|_2^2 = d$（而非 $1$）以保持与「最坏方向 $\bm{w}$」的同尺度比较。要应用到正文中 $\|\bm{u}\|_2 = 1$ 的 $\bm{u}$，代入 $\bm{x} = \sqrt{d} \cdot \bm{u}$ 即可，两边各乘 $d^k$，结论形式不变。

引理由两个不等式串起来，下面分别给出思路。

第一个不等式

$\bm{x}$ 不比 $\bm{w}$ 更「胖」

直观地，$\bm{w} = (1, \dots, 1)$ 是「能量最分散」的方向，对应最坏的 Rademacher 和；任意 $\bm{x}$（同样满足 $\|\bm{x}\|_2^2 = d$）的 Rademacher 和都被它支配。

形式化地，把 $\langle \bm{x}, \bm{r}\rangle^{2k}$ 多项式展开后对所有 $\bm{r}$ 求期望，奇次的项消失，能存活的是「每个指标都出现偶数次」的项。每种存活模式贡献的因子形如 $\prod_j x_j^{2 m_j}$，其中 $\sum_j m_j = k$。在约束 $\sum_j x_j^2 = d$ 下，幂次和不等式说明 $\sum_j x_j^{2 m_j}$ 在 $\bm{x} = \bm{w}$ 处取最大。逐项求和即得不等式。

第二个不等式

Rademacher 的偶数阶矩 ≤ 高斯

由 $\bm{w} = (1, \dots, 1)$，$\langle \bm{w}, \bm{r}\rangle^{2k} = (\sum_i r_i)^{2k}$。多项式展开：

$$\langle \bm{w}, \bm{r}\rangle^{2k} = \sum_{i_1, \dots, i_{2k}} r_{i_1} \cdots r_{i_{2k}}$$

仅当每个指标出现偶数次时期望非零。设某项可记作 $r_{j_1}^{2\ell_1} r_{j_2}^{2\ell_2} \cdots r_{j_m}^{2\ell_m}$（$\sum_p \ell_p = k$），则

$$\mathbb{E}\bigl[r_{j_1}^{2\ell_1} \cdots r_{j_m}^{2\ell_m}\bigr] = 1$$

对应的高斯项：

$$\mathbb{E}\bigl[Z_{j_1}^{2\ell_1} \cdots Z_{j_m}^{2\ell_m}\bigr] = \prod_p \mathbb{E}[Z^{2\ell_p}] = \prod_p \frac{(2\ell_p)!}{\ell_p! \cdot 2^{\ell_p}}$$

由 $(2\ell)! \ge \ell! \cdot 2^\ell$（即 $\dfrac{(2\ell)!}{\ell! \cdot 2^\ell} = (2\ell - 1)!! \ge 1$），每一项的高斯贡献都 $\ge 1$，逐项支配 Rademacher 的贡献。

下图从两个角度看「Rademacher 被高斯支配」：左图是 MGF 层面——$\cosh u \le \e^{u^2/2}$，Rademacher 的矩生成函数被高斯的逐点压住（这正是 sub-Gaussian 的定义，也是稍后 Khintchine 不等式的钥匙）；右图是矩层面——偶数阶矩 $\mathbb{E}[r^{2k}] = 1 \le (2k-1)!! = \mathbb{E}[Z^{2k}]$，逐项被高斯支配。两个角度都指向同一结论：把高斯条目换成 $\pm 1$，集中度不会变差。

借助矩比较，对 Rademacher 版本套用与高斯相同的 MGF 上界（MGF 是偶数阶矩的指数级数，逐项受高斯 MGF 控制），可以得到

$$\Pr\bigl[\,\bigl|\|\bm{A}\bm{u}\|_2^2 - 1\bigr| > \varepsilon\,\bigr] \le 2 \e^{-\Omega(\varepsilon^2 k)}$$

因此 $k = O(\varepsilon^{-2} \log n)$ 即可——与高斯构造完全同阶。Achlioptas 构造在维度上不付任何代价，但在计算时间和硬件实现上都更便宜，因此在工程实践中常被首选。

最近邻搜索

到目前为止，我们已经把 JL 定理证完了三遍——高斯、子空间投影、$\pm 1$ 矩阵，三种构造在维度上完全同阶，区别只在「怎么生成随机性」。有了能把高维数据压到 $O(\log n)$ 维的工具，自然的问题是：这能解决什么问题？

最直接的下游应用是最近邻搜索（Nearest Neighbor Search, NNS）——给定一堆数据点，找出离查询点最近的一个。这是数据库系统、图像检索、机器学习中最普遍的查询模式。但很快我们会发现，光有 JL 不够；高维下的 NNS 还有更深的困难需要克服。

问题定义

最近邻搜索（NNS）

设 $(X, \operatorname{dist})$ 为一个度量空间。

• 数据：$n$ 个点 $\bm{y}_1, \bm{y}_2, \dots, \bm{y}_n \in X$。
• 查询：给一个新点 $\bm{x} \in X$，找到与 $\bm{x}$ 距离最近的 $\bm{y}_i$。

NNS 广泛出现在数据库系统、模式匹配、机器学习、图像处理、生物信息学等领域。

低维下的经典方法

当维度 $d$ 较小时，已经有相当成熟的算法：

• $k$-d tree：递归地按坐标划分平面，二叉树结构，平均 $O(\log n)$ 查询。
• Voronoi 图：将空间预先划分为「每点的最近邻区域」，配合点定位结构做查询。

这些算法的代价随维度指数增长，如 $k$-d tree 在 $d \gtrsim 20$ 时已退化为线性扫描，而 Voronoi 图的复杂度在 $d$ 维下是 $n^{\Theta(d)}$。

维度的诅咒

当 $d \gg \log n$ 时，事情变得棘手：

维度诅咒

人们普遍猜测：在高维下精确求解 NNS 需要超多项式空间或超多项式查询时间（其中一者）。换言之，不存在 $\mathrm{poly}(n, d)$ 时间且 $\mathrm{poly}(n, d)$ 空间的精确 NNS 算法。

证据来自细粒度复杂性理论：精确 NNS 已被归约到强指数时间假设（SETH）等硬度问题。

诅咒之下，唯一的出路就是牺牲一点精度 + 接受一点随机性，这正是接下来要做的事情。

近似最近邻（ANN）

$c$-ANN 与 $(c, r)$-ANN

放宽对「最近」的要求：只要找到一个「近似最近」的点即可。

$c$-ANN 与 $(c, r)$-ANN

$c$-ANN（Approximate Nearest Neighbor）：返回一个 $\bm{y}_i$ 满足

$$\operatorname{dist}(\bm{x}, \bm{y}_i) \le c \cdot \min_{1 \le j \le n} \operatorname{dist}(\bm{x}, \bm{y}_j)$$

$(c, r)$-ANN（Approximate Near Neighbor）：

• 若 $\exists \bm{y}_j,\, \operatorname{dist}(\bm{x}, \bm{y}_j) \le r$，返回某个 $\bm{y}_i$ 满足 $\operatorname{dist}(\bm{x}, \bm{y}_i) \le c \cdot r$；
• 若 $\forall \bm{y}_i,\, \operatorname{dist}(\bm{x}, \bm{y}_i) > c \cdot r$，返回 "no"；
• 否则任意。

$c$-ANN 是「近似比」目标，$(c, r)$-ANN 则把问题卡在某个阈值 $r$ 上，本质上更简单。

从 $(c, r)$ 到 $c$-ANN 的归约

两者之间有一个简洁的归约。先记下数据中两两距离的极值：

$$D_{\min} = \min_{i \ne j} \operatorname{dist}(\bm{y}_i, \bm{y}_j), \quad D_{\max} = \max_{i \ne j} \operatorname{dist}(\bm{y}_i, \bm{y}_j), \quad R = \frac{D_{\max}}{D_{\min}}$$

构造一个公比为 $\sqrt{c}$ 的几何序列

$$r_0 = D_{\min},\quad r_\ell = \sqrt{c} \cdot r_{\ell - 1},\quad \dots,\quad r_L \ge D_{\max}$$

共 $L = \lceil\log_{\sqrt{c}} R\rceil$ 层。换底后 $L = O(\log_c R)$，与 $\log_c R$ 只差常数，下文中我们就统一用 $\log_c R$ 表示这个层数。对每个 $r_\ell$ 各建一份 $(\sqrt{c}, r_\ell)$-ANN 数据结构，查询时对 $\ell$ 做二分搜索。

为什么公比是 $\sqrt{c}$？

这是归约能成立的关键。设真实最近距离为 $D^* = \min_j \operatorname{dist}(\bm{x}, \bm{y}_j)$（$D^* \ge D_{\min} = r_0$），则存在唯一的 $\ell \ge 1$ 满足 $r_{\ell - 1} < D^* \le r_\ell$（当 $D^* = D_{\min}$ 时取 $\ell = 1$），即

$$\frac{r_\ell}{\sqrt{c}} < D^* \le r_\ell$$

此时 $(\sqrt{c}, r_\ell)$-ANN 返回的点 $\bm{y}_i$ 满足 $\operatorname{dist}(\bm{x}, \bm{y}_i) \le \sqrt{c} \cdot r_\ell$。$c$-ANN 的目标是 $\operatorname{dist}(\bm{x}, \bm{y}_i) \le c \cdot D^*$，而

$$\sqrt{c} \cdot r_\ell \le \sqrt{c} \cdot \sqrt{c} \cdot D^* = c \cdot D^* \quad\checkmark$$

若公比改成 $c$，则 $D^*$ 最低可达 $r_\ell / c$，目标变成 $\sqrt{c} \cdot r_\ell \le c \cdot D^* = r_\ell$。但 $\sqrt{c} > 1$，不等式不成立——近似比就保不住。

本质：内层算法的近似比（$\sqrt{c}$）必须「覆盖」外层离散化引入的误差（公比 $\sqrt{c}$），二者相乘恰好得到外层目标近似比 $c$。

下图把这条几何阶梯画出来（取 $c = 4$，故公比 $\sqrt c = 2$）：距离轴上 $r_0, r_1, \dots$ 按 $\sqrt c$ 等比排开，真实最近距离 $D^*$ 落在某一级 $(r_{\ell-1}, r_\ell]$；该级的 $(\sqrt c, r_\ell)$-ANN 保证返回点距离 $\le \sqrt c\, r_\ell$，而 $r_\ell < \sqrt c\, D^*$，两个 $\sqrt c$ 相乘恰好把返回点压进 $c\,D^*$ 之内——这正是公比取 $\sqrt c$ 的原因。

归约结论

若 $(\sqrt{c}, r)$-ANN 能以 $s$ 空间、$t$ 时间求解，则 $c$-ANN 可以以 $O(s \log_c R)$ 空间、$O(t \log \log_c R)$ 时间求解。其中 $\log \log_c R$ 来自对 $L$ 层做二分查找。

从而只需把精力放在 $(c, r)$-ANN 上，距离参数 $r$ 是「已知的」。

Hamming 空间上的降维与 ANN

归约把我们送到了 $(c, r)$-ANN——半径已知的近邻查询。但怎么解这个子问题？JL 的欧氏构造在这里不直接适用（Hamming 距离不是 $\ell_2$），需要专门为 $\{0, 1\}^d$ 设计的降维。

接下来在一个具体度量空间——$\{0, 1\}^d$ 上的 Hamming 距离（两向量不同坐标的数量）——上构造 $(c, r)$-ANN 算法。Hamming 空间是文本匹配、序列比较、稀疏特征比较的常用模型，本身也是高维问题最棘手的代表。

高维下的暴力算法困境

数据是 $n$ 个 Hamming 向量 $\bm{y}_1, \dots, \bm{y}_n \in \{0, 1\}^d$，$d \gg \log n$。如果允许预处理空间 $O(2^d)$，可以对每个查询点直接表查；但 $2^d$ 是天文数字。如何用 $\mathrm{poly}(n, d)$ 空间解 $(c, r)$-ANN？

策略：先做降维——用一个随机矩阵 $\bm{A}$ 把 Hamming 向量从 $d$ 维压到 $k = O(\log n)$ 维，使得「近的点降维后还是近」「远的点降维后还是远」。然后在低维空间里做暴力表查——$2^k$ 已经是多项式。

Boolean 矩阵降维

随机抽取 $k \times d$ 的 Boolean 矩阵 $\bm{A}$，每个元素 $\bm{A}_{ij} \sim \operatorname{Bernoulli}(p)$ i.i.d.（$p$ 待定）。映射

$$\bm{z}_i = \bm{A}\bm{y}_i \pmod 2 \in \{0, 1\}^k$$

所有乘法和加法都在 $\mathrm{GF}(2)$ 上做。预处理时把每个 $\bm{y}_i$ 周围 Hamming 半径为 $s$ 的球内所有点 $\bm{u}$ 当作键、存入字典并指向 $\bm{y}_i$；查询时把 $\bm{x}$ 降到 $\bm{A}\bm{x}$，在字典中查表。

单坐标的碰撞概率

降维成立的核心是下面的公式，它把碰撞概率显式地写成 Hamming 距离的函数：

单坐标碰撞概率

对任意 $\bm{x}, \bm{y} \in \{0, 1\}^d$，固定行 $i$：

$$\Pr[(\bm{A}\bm{x})_i \ne (\bm{A}\bm{y})_i] = \frac{1}{2}\bigl(1 - (1 - 2p)^{\operatorname{dist}(\bm{x}, \bm{y})}\bigr)$$

直接对 $\bm{A}_{i,\cdot}$ 是 $\operatorname{Bernoulli}(p)$ 向量做计算不容易看清楚结构。下面用一个等价生成技巧把概率结构展开。

等价生成

假设 $p \le 1/2$。我们把 $\bm{A}_{ij} \sim \operatorname{Bernoulli}(p)$ 的采样拆成两个独立步骤：先决定坐标是否「活跃」、再在活跃坐标上掷公平硬币。

1. 每个 $j \in [d]$ 以概率 $2p$ 独立加入「活跃集」$D \subseteq [d]$；
2. 对 $j \in D$，独立采样 $\bm{A}_{ij} \in \{0, 1\}$ 均匀；
3. 对 $j \notin D$，置 $\bm{A}_{ij} = 0$。

验证：单个 $\bm{A}_{ij}$ 取 $1$ 的概率 $= \Pr[j \in D] \cdot (1/2) = 2p \cdot 1/2 = p$，与 $\operatorname{Bernoulli}(p)$ 一致——这就是「活跃概率取 $2p$」的来源。$p \le 1/2$ 保证 $2p \le 1$ 是合法概率（下面选取的 $p$ 会满足这一条件）。

为什么要这么生成？因为它把概率结构「拆开」：进入活跃集 $D$ 之后才掷硬币，而硬币是公平的——这正是后面分析所需要的良好结构。

记 $D' = \{j\colon x_j \ne y_j\}$ 为 $\bm{x}, \bm{y}$ 不同的坐标集（$|D'| = \operatorname{dist}(\bm{x}, \bm{y})$）。注意 $\bm{A}_{i, \cdot}$ 中所有 $j \notin D'$ 的位置上 $x_j = y_j$，对差 $(\bm{A}\bm{x})_i - (\bm{A}\bm{y})_i$ 没有贡献。所以

$$(\bm{A}\bm{x})_i \ne (\bm{A}\bm{y})_i \iff \bigoplus_{j \in D'} \bm{A}_{ij}\cdot(x_j - y_j) \equiv 1 \pmod 2 \iff \bigoplus_{j \in D'} \bm{A}_{ij} = 1$$

最后一步用了 $j \in D'$ 时 $x_j - y_j \equiv 1 \pmod 2$。于是分两种情形：

情形	$D \cap D'$	$\bigoplus_{j \in D'} \bm{A}_{ij}$ 的分布	$\Pr[\text{为 } 1]$
活跃集错过差异	$D \cap D' = \empty$	所有 $\bm{A}_{ij} = 0$，XOR 恒 $= 0$	$0$
活跃集命中差异	$D \cap D' \ne \empty$	$\ge 1$ 个独立公平硬币的 XOR	$1/2$

综合：

$$\Pr[(\bm{A}\bm{x})_i \ne (\bm{A}\bm{y})_i] = \Pr[D \cap D' \ne \empty] \cdot \frac{1}{2}$$

而 $D \cap D' = \empty$ 当且仅当所有 $j \in D'$ 都未被选入 $D$，概率为 $(1 - 2p)^{|D'|}$。因此

$$\Pr[(\bm{A}\bm{x})_i \ne (\bm{A}\bm{y})_i] = \frac{1}{2}\bigl(1 - (1 - 2p)^{\operatorname{dist}(\bm{x}, \bm{y})}\bigr)$$

选取 $p$ 与阈值 $s$

精妙的选取：取 $p$ 使 $(1 - 2p) = 2^{-1/r}$。代入后碰撞概率简化为 $(1 - 2^{-\operatorname{dist}/r})/2$，把 Hamming 距离的影响压缩成指数衰减：

情形	$\operatorname{dist}/r$ 范围	$\Pr[(\bm{A}\bm{x})_i \ne (\bm{A}\bm{y})_i]$
$\operatorname{dist}(\bm{x}, \bm{y}) \le r$（近）	$\le 1$	$\le (1 - 2^{-1})/2 = 1/4$
$\operatorname{dist}(\bm{x}, \bm{y}) > c r$（远）	$> c$	$> (1 - 2^{-c})/2 = 1/2 - 2^{-(c+1)}$

记示性变量 $X_i = \mathbf{1}[(\bm{A}\bm{x})_i \ne (\bm{A}\bm{y})_i]$，则 $X = \sum_{i=1}^k X_i = \operatorname{dist}(\bm{A}\bm{x}, \bm{A}\bm{y})$，且

$$\mathbb{E}[X] \le \frac{k}{4} \text{（近）}, \qquad \mathbb{E}[X] > \left(\frac{1}{2} - 2^{-(c+1)}\right) k \text{（远）}$$

两段期望被一道恒定间隔 $\Delta = 1/4 - 2^{-(c+1)} > 0$ 隔开。取阈值 $s$ 落在两段期望的中点（设近端期望上界为 $A = k/4$，远端期望下界为 $B = (1/2 - 2^{-(c+1)})k$）：

$$s = \frac{A + B}{2} = \left(\frac{3}{8} - 2^{-(c+2)}\right) k$$

这样近的情形要求 $X$ 上溢 $\ge \Delta k/2$，远的情形要求 $X$ 下溢 $\ge \Delta k/2$——两段都偏离自己的期望至少 $t = (1/8 - 2^{-(c+2)})k$。

Hoeffding 给出集中

Hoeffding 不等式

对 $X = \sum_{i=1}^k X_i$，$X_i \in \{0, 1\}$ 独立（或负相关），任意 $t > 0$：

$$\Pr[X \ge \mathbb{E}[X] + t] \le \exp\left(-\frac{2t^2}{k}\right), \qquad \Pr[X \le \mathbb{E}[X] - t] \le \exp\left(-\frac{2t^2}{k}\right)$$

这是「加性偏差」的指数集中，与上一讲讨论的 Chernoff 乘性偏差形式不同，但常被一并称作 Chernoff-Hoeffding 不等式。

代入 $t = (1/8 - 2^{-(c+2)})k$，$2 t^2/k = \Omega(k)$（$c$ 固定时为常数倍 $k$），所以

$$\begin{aligned} \operatorname{dist}(\bm{x}, \bm{y}) \le r &\implies \Pr\bigl[\operatorname{dist}(\bm{A}\bm{x}, \bm{A}\bm{y}) > s\bigr] < \e^{-\Omega(k)} \\ \operatorname{dist}(\bm{x}, \bm{y}) > c r &\implies \Pr\bigl[\operatorname{dist}(\bm{A}\bm{x}, \bm{A}\bm{y}) \le s\bigr] < \e^{-\Omega(k)} \end{aligned}$$

取 $k = O(\log n)$ 使每个尾概率 $< 1/n^2$，对全部点对做联合界，$(c, r)$-ANN 以高概率正确。

下图把这套机制画在一起（取 $c = 2$）。左图：单坐标碰撞概率随 Hamming 距离指数增长，精选的 $p$ 让「近点」（$\le 1/4$）与「远点」（$> 3/8$）被一道恒定间隔隔开。右图：把 $k = 200$ 个独立坐标累加后，近对的投影距离集中在 $k/4 = 50$、远对集中在 $3k/8 = 75$，两个分布相距 $\Omega(k)$ 几乎不重叠——阈值 $s \approx 62$ 一刀切开，Hoeffding 保证两边都极难越界。

复杂度小结

最终的数据结构：

操作	代价
空间	$O(n \cdot 2^k) = O(n \cdot \mathrm{poly}(n))$（每个 $\bm{y}_i$ 的 $s$-邻域占 $\binom{k}{\le s} \le 2^k$ 个键）
查询时间	$O(k d)$（计算 $\bm{A}\bm{x}$）$+ O(1)$（查表）

空间是 $n$ 的多项式（$k = O(\log n)$ 时 $2^k = \mathrm{poly}(n)$），查询时间是 $O(d \log n)$。维度的诅咒被打破。

局部敏感哈希（LSH）

上一节的 Hamming 算法把「近点降到同桶、远点降到不同桶」当成核心机制。这个机制其实不依赖 Hamming 特殊性——任何度量空间，只要能找到合适的「随机哈希函数」让近的点更容易碰撞，就能玩出相同的把戏。把这个机制抽出来，就是局部敏感哈希。

LSH 把降维 + 桶定位两步合并成一个哈希函数，并明确写出这个哈希函数需要满足的「近/远」条件，从而把整个算法框架推广到任意度量空间。

LSH 的定义

局部敏感哈希（LSH）

设 $(X, \operatorname{dist})$ 为度量空间。一个随机映射 $h\colon X \to U$ 称为 $(r, cr, p, q)$-LSH，若对所有 $x, y \in X$：

$$\begin{aligned} \operatorname{dist}(x, y) \le r &\implies \Pr[h(x) = h(y)] \ge p \\ \operatorname{dist}(x, y) > c \cdot r &\implies \Pr[h(x) = h(y)] \le q \end{aligned}$$

直观地：「近」的点哈希到同一桶的概率高（至少 $p$），「远」的点碰撞概率低（至多 $q$）。要求 $p > q$，「概率间隔」越大越好。

张量化：拉开概率间隔

直接拿一个 LSH 一般不够好——$p$ 可能只比 $q$ 大一点（如 $p = 0.5, q = 0.4$），把它当成「近邻分类器」非常不可靠。

张量化是把概率间隔指数级放大的标准技巧：并联 $k$ 个独立的 LSH 实例，要求全部都同值才算碰撞。

张量化命题

若存在 $(r, cr, p, q)$-LSH $h\colon X \to U$，则存在 $(r, cr, p^k, q^k)$-LSH $g\colon X \to U^k$，其中

$$g(x) = (h_1(x), h_2(x), \dots, h_k(x))$$

$h_1, \dots, h_k$ 是按 $h$ 分布独立抽取的。

一句话证明：$g(x) = g(y)$ 当且仅当所有 $k$ 个独立的 $h_i$ 都给出相同值。

张量化的代价是两个概率都同时缩小。但由于 $p > q$，对数尺度下 $p^k$ 比 $q^k$ 收缩得慢——这是我们想要的不对称效果。

选 $k$ 让远点几乎不碰撞：取 $k = \log_{1/q} n$，则 $q^k = 1/n$。此时

$$p^k = p^{\log_{1/q} n} = n^{-\rho}, \quad \rho := \frac{\log(1/p)}{\log(1/q)} = \frac{\log p}{\log q} \in (0, 1)$$

记 $p^* = p^k = n^{-\rho}$。新的 LSH $g$ 满足：

• 近点碰撞概率 $\ge p^* = n^{-\rho}$（仍是多项式，不会被压到零）；
• 远点碰撞概率 $\le 1/n$（几乎不会和任意一个具体的数据点错碰）。

参数 $\rho$ 越接近 $0$，张量化后近点的碰撞概率越高，最终算法越快。

下图展示张量化 + 多副本如何把「平缓」的碰撞曲线锐化成「近点必中、远点必丢」的 S 形：单个 $h$ 的碰撞概率恰等于相似度（对角虚线）；并联 $k$ 个（$g = h^k$）再跑 $\ell$ 个副本后，曲线在某个相似度阈值附近急剧抬升——$k$ 越大、副本越多，S 形越陡，近点（高相似）几乎必被检索、远点（低相似）几乎必被丢弃。

LSH 数据结构

现在我们有了张量化后的 LSH $g$，怎么用它解 $(c, r)$-ANN？

直觉：把 $n$ 个数据点 $\bm{y}_1, \dots, \bm{y}_n$ 全部用 $g$ 哈希后存入字典 $\langle g(\bm{y}_i), \bm{y}_i\rangle$。查询时对 $\bm{x}$ 算 $g(\bm{x})$，在字典里查所有 $g$-碰撞的点。

• 若 $\exists \bm{y}_s$ 与 $\bm{x}$ 是近邻，它有概率 $\ge p^* = n^{-\rho}$ 与 $\bm{x}$ 碰撞——但 $n^{-\rho}$ 不到 $1$，可能错过。
• 每个远点有概率 $\le 1/n$ 与 $\bm{x}$ 碰撞，期望「假阳性」总数 $\le n \cdot 1/n = 1$，不会被淹没。

真正的问题：近邻可能错过。补救：跑 $\ell$ 个独立的 LSH 副本 $g_1, \dots, g_\ell$，只要任一个让 $\bm{x}$ 与 $\bm{y}_s$ 碰撞就行。错过的概率从 $(1 - p^*)$ 降到 $(1 - p^*)^\ell$。取 $\ell = 1/p^* = n^\rho$ 让它 $\le 1/\e$。

副作用：远点变多了。$\ell$ 个副本每个都可能放假阳性进来——期望坏点数 $\le \ell$。如果坏点把扫描淹没，就找不出真的近邻。补救：扫描时设上限，最多看 $10\ell$ 个候选；由 Markov 不等式，坏点超过 $10\ell$ 的概率 $\le 1/10$。

把上面几条合起来就是 LSH 算法：

flowchart LR
    subgraph DataStruct["数据结构"]
        direction TB
        H1["g₁: 字典 ⟨g₁(y_i), y_i⟩"]
        H2["g₂: 字典 ⟨g₂(y_i), y_i⟩"]
        Hl["g_ℓ: 字典 ⟨g_ℓ(y_i), y_i⟩"]
        H1 -.- H2 -.- Hl
    end

    Q["查询 x"] --> DataStruct
    DataStruct --> R["扫描所有<br/>y_i s.t. ∃j, g_j(x)=g_j(y_i)<br/>≤ 10ℓ 个"]
    R --> A{"是否存在<br/>dist(x,y_i) ≤ cr ？"}
    A -->|是| Yes["返回该 y_i"]
    A -->|否| No["返回 no"]

    classDef data fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef query fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef ans fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    class H1,H2,Hl,DataStruct data
    class Q,R query
    class Yes,No,A ans

具体地：

• 预处理：抽取 i.i.d. 的 $g_1, \dots, g_\ell$，其中 $\ell = 1/p^* = n^\rho$。对每个 $j$ 建一份字典，存储所有 $\langle g_j(\bm{y}_i), \bm{y}_i\rangle$ 键值对。
• 查询 $\bm{x}$：扫描所有与 $\bm{x}$ 在某个 $g_j$ 下哈希相同的点 $\bm{y}_i$（至多扫 $10\ell$ 个，超过则停止）；若遇到 $\operatorname{dist}(\bm{x}, \bm{y}_i) \le c r$ 则返回该 $\bm{y}_i$；否则返回 "no"。

正确性与复杂度分析

正确性（永远正确的情形）：若真实答案是 "no"（所有 $\bm{y}_i$ 都远），算法只可能返回 "no" 或一个被验证为 $\operatorname{dist}(\bm{x}, \bm{y}_i) \le c r$ 的 $\bm{y}_i$——后者不可能发生，所以总是返回 "no"。

错失近邻的两个失败源（当存在 $\bm{y}_s$ 满足 $\operatorname{dist}(\bm{x}, \bm{y}_s) \le r$）：

1. 未被任何 $g_j$ 撞上：$\forall j, g_j(\bm{x}) \ne g_j(\bm{y}_s)$ 的概率 $\le (1 - p^*)^\ell \le 1/\e$（$\ell = 1/p^*$）。
2. 被坏点淹没：超过 $10\ell$ 个远点满足某个 $g_j$ 下与 $\bm{x}$ 碰撞，近邻被「挤出」扫描窗口。期望坏点数 $\le \ell \cdot n \cdot 1/n = \ell$，由 Markov $\Pr[\text{坏点数} > 10\ell] \le 1/10$。

合并：错失概率 $\le 1/\e + 0.1 < 0.5$。

复杂度（用 FKS 完美哈希实现字典）：

• 空间：$O(n \ell) = O(n / p^*) = O(n^{1 + \rho})$。
• 查询时间：$O(\ell \cdot \text{每次 } g_j \text{ 计算}) = O(n^\rho \log n)$。

LSH 主定理

若度量空间 $(X, \operatorname{dist})$ 上存在 $(r, c r, p, q)$-LSH，则 $(c, r)$-ANN 可以用空间 $O(n^{1+\rho})$、查询时间 $O(n^\rho \log n)$ 求解，单侧错误率 $< 0.5$，其中

$$\rho = \frac{\log p}{\log q}$$

$\rho$ 是决定算法效率的唯一参数——找到 $\rho$ 小的 LSH，算法就快。剩下的工作是为每个度量空间设计具体的 LSH。

Hamming 空间的具体 LSH

抽象框架建好了，回头看 Hamming 空间最简单的 LSH 实例：对 $\bm{x} \in \{0, 1\}^d$，

$$h(\bm{x}) = x_i, \quad i \sim \operatorname{Uniform}([d])$$

也就是随机挑一个坐标返回。这个简单的哈希函数为什么能保持距离？因为

$$h(\bm{x}) = h(\bm{y}) \iff x_i = y_i \iff i \notin \{j\colon x_j \ne y_j\}$$

随机选中「相同坐标」的概率正好是「不同坐标数 $/ d$」的余：

$$\Pr[h(\bm{x}) = h(\bm{y})] = 1 - \frac{\operatorname{dist}(\bm{x}, \bm{y})}{d}$$

代入两个区间：

情形	$\operatorname{dist}(\bm{x}, \bm{y})$	碰撞概率
近	$\le r$	$\ge 1 - r/d$
远	$> cr$	$\le 1 - cr/d$

所以 $h$ 是 $(r, cr, 1 - r/d, 1 - cr/d)$-LSH。其 $\rho$ 参数：

$$\rho = \frac{\log(1 - r/d)}{\log(1 - cr/d)} \le \frac{1}{c}$$

最后一步用 $\log(1 - x) \approx -x$ 的小 $x$ 近似（对 $r/d \ll 1$ 严格成立）。代入 LSH 主定理：

Hamming 空间 ANN

Hamming 空间上的 $(c, r)$-ANN 可以以空间 $O(n^{1 + 1/c})$、查询时间 $O(n^{1/c} \log n)$ 求解，单侧错误率 $< 0.5$。

$c$ 越大（近似要求越宽松），$n^{1/c}$ 越小、算法越快——这是「近似换效率」的清晰量化。$c = 2$ 时空间 $O(n^{1.5})$、查询 $O(\sqrt{n} \log n)$，已经远好于线性扫描的 $O(n d)$。

跨学科彩蛋

Dasgupta, Stevens 和 Navlakha（2017）发现，果蝇的嗅觉回路本质上是一个 LSH：50 个嗅觉投影神经元通过稀疏随机连接矩阵映射到 2000 个 Kenyon 细胞，激活其中 5% 形成「气味标签」。相似的气味产生相似的稀疏激活模式，天然的局部敏感性。这说明 LSH 不只是工程方便的产物，也是生物神经回路演化出的算法策略。

Fast Johnson-Lindenstrauss 变换

LSH 解决了一个独立的问题（高维 ANN），现在回到 JL 本身。JL 矩阵 $\bm{A} \in \R^{k \times d}$ 在数值上是稠密的（高斯条目）或 $\pm 1$（Achlioptas），矩阵向量乘 $\bm{A}\bm{x}$ 的时间是 $O(k d) = O(d \log n / \varepsilon^2)$。对每个 $\bm{x}$ 做一次，共 $n$ 个点，总开销 $O(n d \log n / \varepsilon^2)$——当 $d$ 与 $n$ 都很大时仍然吃力。

能否让 JL 本身更快？ Ailon-Chazelle 2006 年给出了答案：把 JL 的「稠密随机矩阵」换成「有快速算法的结构化矩阵 + 随机扰动」的复合，可以把单次降维的时间从 $O(d \log n)$ 压到 $O(d \log d)$。这就是 Fast JL 变换。

本节记号

Fast JL 沿用 $\bm{\Pi} \in \R^{m \times d}$ 的形状（用 $m$ 而非 $k$ 表示目标维度，与 FJLT 文献一致）。本质上 $m$ 与前面 JL 章节的 $k$ 是同一个量；这里换名字是为了避免与 Hadamard 矩阵的指标冲突。

两条加速思路

思路	原理	加速
稀疏构造	$\bm{A}$ 的 $2/3$ 元素为 $0$	常数倍
良结构构造	$\bm{A}$ 由 Hadamard / Fourier 等具有快速算法的矩阵复合	$O(d \log d)$ 总时间

朴素加速：随机采样的失败

最朴素的加速：随机挑 $m$ 个坐标。对 $i \in [m]$，令

$$y_i = x_{j_i} \cdot \sqrt{d/m}, \quad j_i \sim \operatorname{Uniform}([d])$$

无偏：$\mathbb{E}[y_i^2] = \dfrac{1}{d}\sum_j x_j^2 \cdot \dfrac{d}{m} = \dfrac{\|\bm{x}\|_2^2}{m}$，所以 $\mathbb{E}[\|\bm{y}\|_2^2] = \|\bm{x}\|_2^2$。计算时间 $O(m)$。

朴素采样的失败模式

设 $\bm{x} = (\sqrt{d}, 0, 0, \dots)$，能量全部集中在第一个坐标，$\|\bm{x}\|_2^2 = d$。要采到 $j_i = 1$ 的概率只有 $1/d$，绝大多数情况下 $\bm{y}$ 全是零，$\|\bm{y}\|_2^2 = 0 \ne d$。

用方差刻画：$\mathrm{Var}(y_i^2)$ 主项为 $\dfrac{d \|\bm{x}\|_\infty^4}{m^2}$。极端集中向量下 $\|\bm{x}\|_\infty^4 = d^2$，方差正比于 $d^3/m^2$，爆炸。

根因：$\bm{x}$ 的 $\ell_\infty$ 范数越大（能量越集中），采样方差越大。如果能在采样之前预处理 $\bm{x}$，让它变得「均匀」（低 $\ell_\infty$ 范数），就能修复这个问题。

用 Hadamard 矩阵做快速旋转

预处理的工具是 Hadamard 矩阵——一个递归构造的 $\pm 1$ 正交矩阵，存在 $O(d \log d)$ 时间的快速变换。

Hadamard 矩阵

$d = 2^k$ 时，递归定义

$$\bm{H}_1 = (1), \qquad \bm{H}_{2d} = \begin{pmatrix} \bm{H}_d & \bm{H}_d \\ \bm{H}_d & -\bm{H}_d \end{pmatrix}$$

满足 $\bm{H}_d \bm{H}_d^\intercal = d \bm{I}$，即 $\bm{H}_d / \sqrt{d}$ 是正交矩阵。$\bm{H}_d \bm{x}$ 可在 $O(d \log d)$ 时间内计算（快速 Walsh-Hadamard 变换）。

但只用 $\bm{H}$ 还不够：对 $\bm{x} = \bm{e}_1$（标准基），$\bm{H} \bm{e}_1$ 是 $\bm{H}$ 的第一列，等于 $(1, 1, \dots, 1)^\intercal$，确实压低了 $\ell_\infty$。但若 $\bm{x} = (1, 1, \dots, 1)/\sqrt{d}$，$\bm{H} \bm{x}$ 反过来会把能量集中到第一个坐标——具体 $\bm{x}$ 是「坏」的依赖 $\bm{x}$ 本身。

解决方法是先用随机 Rademacher 翻转每个坐标的符号，把所有 $\bm{x}$ 的「坏」程度均匀化：

FJLT（Ailon-Chazelle）

$$\bm{\Pi} = \frac{1}{\sqrt{m}} \bm{S}\bm{H}\bm{D}$$

其中：

• $\bm{D}$：对角线为 i.i.d. Rademacher（$\pm 1$）的 $d \times d$ 对角矩阵；
• $\bm{H}$：$d \times d$ 未归一化 Hadamard 矩阵（$\bm{H}\bm{H}^\intercal = d \bm{I}$）；
• $\bm{S}$：$m \times d$ 采样矩阵，每行随机选一个坐标。

计算时间：$\bm{D}\bm{x}$ 是 $O(d)$ 的逐元素乘法；$\bm{H}(\bm{D}\bm{x})$ 是 $O(d \log d)$ 快速变换；$\bm{S}(\bm{H}\bm{D}\bm{x})$ 是 $O(m)$ 采样。总计 $O(d \log d + m)$，比朴素矩阵乘法 $O(d k)$ 快——当 $k \approx \log n$ 时是数量级提升。

关键引理：$\bm{H}\bm{D}$ 压低 $\ell_\infty$

令 $\bm{z} = \bm{D} \bm{x}$（每个 $x_j$ 独立翻转符号），$\bm{y} = \bm{H} \bm{z}$。则

$$y_i = \sum_j \bm{H}_{ij} \delta_j x_j, \quad \delta_j \in \{-1, +1\} \text{ 独立 Rademacher}$$

由于 $\bm{H}_{ij} \in \{-1, +1\}$ 是确定值，$\varepsilon_j := \bm{H}_{ij} \delta_j$ 仍是 i.i.d. Rademacher。所以 $y_i = \sum_j \varepsilon_j x_j$ 是一个标准的「Rademacher 加权和」，可以用 Khintchine 控制它的尾部。

下图说明为什么非要 $\bm{D}$ 不可（取 $d = 64$）。左图：对一个能量集中的「平坦」向量只做 $\bm{H}$，能量反而被挤成一根尖峰，$\ell_\infty = 1$，随后采样几乎必然采空；右图：先用随机符号 $\bm{D}$ 翻转各坐标、再做 $\bm{H}$，能量被均匀打散，$\ell_\infty$ 降到 $\approx 0.31$，此时再均匀采样才安全。

Khintchine 不等式

对 i.i.d. Rademacher 向量 $\bm{\sigma} \in \{-1, +1\}^d$ 和任意 $\bm{x} \in \R^d$：

$$\Pr[|\langle \bm{\sigma}, \bm{x} \rangle| \ge \lambda] \le 2 \exp\left(-\frac{\lambda^2}{2 \|\bm{x}\|_2^2}\right)$$

即：Rademacher 和的尾部以高斯速率衰减，是 sub-Gaussian 随机变量。

Khintchine 不等式的证明

设 $X = \sum_i \sigma_i x_i$。对任意 $t > 0$，由 Markov 的指数化：

$$\Pr[X \ge \lambda] \le \e^{-t\lambda} \mathbb{E}[\e^{tX}]$$

由独立性：

$$\mathbb{E}[\e^{tX}] = \prod_i \mathbb{E}[\e^{t \sigma_i x_i}] = \prod_i \frac{\e^{-t x_i} + \e^{t x_i}}{2} = \prod_i \cosh(t x_i)$$

由 $\cosh(u) = \sum_{k \ge 0} \dfrac{u^{2k}}{(2k)!}$ 与 $(2k)! \ge k! \cdot 2^k$：

$$\cosh(u) = \sum_{k \ge 0} \frac{u^{2k}}{(2k)!} \le \sum_{k \ge 0} \frac{u^{2k}}{k! \cdot 2^k} = \e^{u^2/2}$$

因此 $\mathbb{E}[\e^{tX}] \le \exp(t^2 \|\bm{x}\|_2^2 / 2)$。取 $t = \lambda / \|\bm{x}\|_2^2$：

$$\Pr[X \ge \lambda] \le \exp\left(t^2 \|\bm{x}\|_2^2/2 - t \lambda\right) = \exp\left(-\frac{\lambda^2}{2 \|\bm{x}\|_2^2}\right)$$

下尾对 $-X$ 对称证明，合并得 $2 \exp(-\lambda^2 / (2\|\bm{x}\|_2^2))$。

对单位向量 $\bm{x}$（$\|\bm{x}\|_2 = 1$），代入 $\lambda = \sqrt{2 \ln(4d/\delta)}$，单个坐标越界的概率：

$$\Pr\bigl[|y_i| \ge \sqrt{2 \ln(4d/\delta)}\bigr] \le 2 \exp\left(-\frac{2 \ln(4d/\delta)}{2}\right) = \frac{2}{4d/\delta} = \frac{\delta}{2 d}$$

（注意 Khintchine 自带的因子 $2$ 与 $4d/\delta$ 中的 $4$ 抵消成 $1/2$。）对所有 $d$ 个坐标做联合界，$\|\bm{y}\|_\infty$ 越界的概率：

$$\Pr\bigl[\|\bm{y}\|_\infty > \sqrt{2 \ln(4d/\delta)}\bigr] \le d \cdot \frac{\delta}{2d} = \frac{\delta}{2}$$

即

$$\Pr\bigl[\|\bm{y}\|_\infty \le \sqrt{2 \ln(4d/\delta)}\bigr] \ge 1 - \delta/2$$

旋转后的 $\bm{y}$ 几乎肯定每个坐标都 $O(\sqrt{\log(d/\delta)})$，能量被均匀打散。

范数保持的最后一步

记上述「$\ell_\infty$ 被控制」事件为 $\mathcal{E}$（概率 $\ge 1 - \delta/2$）。在 $\mathcal{E}$ 上，采样矩阵 $\bm{S}$ 就能安全工作。

注意 $\|\bm{y}\|_2^2 = \|\bm{H}\bm{D}\bm{x}\|_2^2 = d \|\bm{x}\|_2^2 = d$（$\bm{H}\bm{H}^\intercal = d \bm{I}$，$\bm{D}$ 正交）。采样 $\bm{S}$ 在每个 $i \in [m]$ 独立从 $[d]$ 中均匀挑一个坐标 $j_i$，则

$$\|\bm{\Pi} \bm{x}\|_2^2 = \frac{1}{m} \sum_{i=1}^m y_{j_i}^2$$

每项 $y_{j_i}^2$ i.i.d.，均值 $\dfrac{1}{d} \sum_j y_j^2 = 1$，在 $\mathcal{E}$ 上有界于 $2 \ln(4d/\delta)$。对此类 i.i.d. 有界变量套 Chernoff：

有界变量的 Chernoff

设 $W_1, \dots, W_m$ i.i.d.，$W_i \in [0, B]$，$\mu = \mathbb{E}[W_i]$。则

$$\Pr\left[\left|\frac{1}{m}\sum_i W_i - \mu\right| \ge \varepsilon \mu\right] \le 2 \exp\left(-\Omega\left(\frac{\varepsilon^2 \mu m}{B}\right)\right)$$

代入 $W_i = y_{j_i}^2$，$\mu = 1$，$B = 2 \ln(4 d/\delta)$：

$$\Pr\Bigl[\bigl|\|\bm{\Pi} \bm{x}\|_2^2 - 1\bigr| \ge \varepsilon\ \big|\ \mathcal{E}\Bigr] \le 2 \exp\left(-\Omega\left(\frac{\varepsilon^2 m}{\ln(d/\delta)}\right)\right)$$

取 $m = O(\varepsilon^{-2} \log n \cdot \log d)$，并将这步的失败概率与 $\mathcal{E}$ 的失败概率合起来，总失败概率 $\le 1/n^3$。维度比朴素 JL 多了 $\log d$ 倍，但构造时间从 $O(d k)$ 降到了 $O(d \log d)$——绝大多数实际应用里这是双赢。

子空间嵌入（OSE）

迄今为止，我们的降维都对一个有限的点集生效：JL 保 $n$ 个点的两两距离，LSH 保 $n$ 个点的近邻关系。但很多应用场景里，我们要保的不是离散的点，而是整个线性子空间——比如线性回归中，回归参数 $\bm{\beta}$ 可以取整个 $\R^d$，对应的 $\bm{X}\bm{\beta}$ 可以是 $\bm{X}$ 列空间中的任何向量。要把回归问题压缩到低维做，就必须保住这一整族向量的范数。

这就引出了一个更激进的目标：保持整个子空间中所有向量的范数。

记号约定

本节及之后，把降维矩阵改记为 $\bm{\Pi}$、目标维度改记为 $m$（与 OSE 文献惯例一致），这与前面 JL 部分的 $\bm{A}, k$ 是同一回事，只是换了名字。在涉及输入 $\bm{X}$ 或 $\bm{A}$ 的最小二乘/OSE 上下文中，$\bm{\Pi}$ 不会与输入混淆。

从点集到子空间

子空间嵌入

设 $T \subset \R^n$ 是一个 $d$ 维子空间。嵌入 $\bm{\Pi}\colon T \to \R^m$ 称为 $\varepsilon$-子空间嵌入（Subspace Embedding），若

$$\forall \bm{x} \in T,\ \|\bm{\Pi} \bm{x}\|_2^2 = (1 \pm \varepsilon) \|\bm{x}\|_2^2$$

（写成平方形式与 OSE 主流文献一致，也让后面的 Sketch-and-Solve 证明常数更干净。）

这比 JL 强得多——JL 只保证有限多个固定向量被保持，OSE 要求连续无穷多的向量都被保持。

但子空间嵌入也有可能很简单：如果允许「看数据」，可以直接用 $T$ 的一组正交基 $\bm{U}$，令 $\bm{\Pi} = \bm{U}^\intercal$，则 $\|\bm{\Pi} \bm{x}\|_2 = \|\bm{x}\|_2$（精确等距）。问题是计算 $\bm{U}$ 需要做 SVD，时间 $O(n d^2)$——这正是想避免的瓶颈。

数据无关 vs 数据相关

更有挑战的是数据无关（oblivious）的嵌入：希望同一个随机 $\bm{\Pi}$ 对所有子空间都成立。这样在算法层面就完全不用看数据，可以提前生成好。

Oblivious 子空间嵌入（OSE）

随机矩阵 $\bm{\Pi} \in \R^{m \times n}$ 是 $(d, \varepsilon, \delta)$-OSE，若对所有 $\R^n$ 中的 $d$ 维子空间 $T$：

$$\Pr\bigl[\forall \bm{x} \in T,\ \|\bm{\Pi} \bm{x}\|_2^2 = (1 \pm \varepsilon)\|\bm{x}\|_2^2\bigr] \ge 1 - \delta$$

等价表述：对所有 $\bm{A} \in \R^{n \times d}$ 和所有 $\bm{\beta} \in \R^d$，$\|\bm{\Pi} \bm{A} \bm{\beta}\|_2^2 = (1 \pm \varepsilon)\|\bm{A} \bm{\beta}\|_2^2$。

OSE 的设计目标：

• 精度：上述 $1 \pm \varepsilon$。
• 降维：$m \ll n$。
• 快速计算：$\bm{\Pi} \bm{A}$ 的乘积要尽量快算。

OSE 怎么造？ 这是一个独立的问题——后面会用 γ-net 论证说明 JL 矩阵其实自动就是 OSE，还会介绍稀疏的 Count Sketch OSE。在此之前，先看一个 OSE 的标志性应用：大规模线性回归。

OSE 的应用：线性回归

OSE 一个最直接的应用是大规模线性回归。

经典最小二乘

最小二乘

给定数据 $\bm{X} \in \R^{n \times d}$ 和标签 $\bm{y} \in \R^n$，找 $\bm{\beta} \in \R^d$ 使 $\|\bm{X} \bm{\beta} - \bm{y}\|_2$ 最小：

$$\bm{\beta}^{\mathrm{LS}} = (\bm{X}^\intercal \bm{X})^+ \bm{X}^\intercal \bm{y}$$

观察：$\bm{y}$ 可分解为 $\bm{y} = \bm{y}^\parallel + \bm{y}^\perp$，其中 $\bm{y}^\parallel$ 在 $\bm{X}$ 的列空间内、$\bm{y}^\perp$ 与之正交。则

$$\|\bm{X} \bm{\beta} - \bm{y}\|_2^2 = \|\bm{X} \bm{\beta} - \bm{y}^\parallel\|_2^2 + \|\bm{y}^\perp\|_2^2$$

最小化第一项即令 $\bm{X} \bm{\beta} = \bm{y}^\parallel$，标准解通过 SVD 得到，时间 $O(n d^2)$。$n$ 巨大时这是瓶颈。

Sketch-and-Solve

OSE 给出一个干净的近似算法：在草图后的小问题上解最小二乘。

Sketch-and-Solve

令 $\bm{\Pi}$ 是 $\mathrm{span}(\mathrm{cols}(\bm{X}) \cup \{\bm{y}\})$ 上的 $\varepsilon$-OSE。计算

$$\tilde{\bm{\beta}}^{\mathrm{LS}} = \arg\min_{\bm{\beta}} \|\bm{\Pi} \bm{X} \bm{\beta} - \bm{\Pi} \bm{y}\|_2^2$$

则

$$\|\bm{X} \tilde{\bm{\beta}}^{\mathrm{LS}} - \bm{y}\|_2^2 \le \frac{1 + \varepsilon}{1 - \varepsilon} \cdot \|\bm{X} \bm{\beta}^{\mathrm{LS}} - \bm{y}\|_2^2$$

证明（三步夹挤）：

对任意 $\bm{\beta}$，$\bm{X}\bm{\beta} - \bm{y}$ 属于 $\bm{\Pi}$ 嵌入的子空间，OSE 给出 $(1 - \varepsilon)\|\cdot\|^2 \le \|\bm{\Pi} \cdot\|^2 \le (1 + \varepsilon)\|\cdot\|^2$：

$$(1 - \varepsilon)\|\bm{X} \tilde{\bm{\beta}}^{\mathrm{LS}} - \bm{y}\|_2^2 \le \|\bm{\Pi} \bm{X} \tilde{\bm{\beta}}^{\mathrm{LS}} - \bm{\Pi} \bm{y}\|_2^2 \le \|\bm{\Pi} \bm{X} \bm{\beta}^{\mathrm{LS}} - \bm{\Pi} \bm{y}\|_2^2 \le (1 + \varepsilon)\|\bm{X} \bm{\beta}^{\mathrm{LS}} - \bm{y}\|_2^2$$

• 第一、第三步用 OSE；
• 第二步用 $\tilde{\bm{\beta}}^{\mathrm{LS}}$ 是草图问题的最优（所以草图目标值 $\le$ 任何其它 $\bm{\beta}$ 的草图目标值，特别地 $\le$ $\bm{\beta}^{\mathrm{LS}}$ 的）。

代价：$O(m d^2)$（解草图问题，$m \ll n$）$+$ 矩阵乘积 $\bm{\Pi} \bm{X}$ 的时间。

梯度下降的收敛分析

Sketch-and-Solve 只能拿到 $(1 + O(\varepsilon))$ 的近似。要拿到任意精度的近似解，需要用迭代法。最自然的选择是梯度下降——但下面会看到它在原始数据上跑得有多慢，然后用 OSE 把它救回来。

梯度下降

$$\bm{\beta}^{(t+1)} \leftarrow \bm{\beta}^{(t)} - \gamma \nabla f(\bm{\beta}^{(t)})$$

对 $f(\bm{\beta}) = \|\bm{X} \bm{\beta} - \bm{y}\|_2^2$，$\nabla f(\bm{\beta}) = 2 \bm{X}^\intercal (\bm{X} \bm{\beta} - \bm{y})$。取 $\gamma = 1/2$：

$$\bm{\beta}^{(t+1)} = \bm{\beta}^{(t)} + \bm{X}^\intercal \bm{y} - \bm{X}^\intercal \bm{X} \bm{\beta}^{(t)}$$

由最优性条件 $\bm{X}^\intercal \bm{y} = \bm{X}^\intercal \bm{X} \bm{\beta}^{\mathrm{LS}}$，迭代误差

$$\bm{\beta}^{(t+1)} - \bm{\beta}^{\mathrm{LS}} = (\bm{I} - \bm{X}^\intercal \bm{X})(\bm{\beta}^{(t)} - \bm{\beta}^{\mathrm{LS}})$$

接下来要把误差展开到 SVD 基里、看每个方向各自收缩多少。设 $\bm{X} = \bm{U}\bm{\Sigma}\bm{V}^\intercal$，记 $\bm{e}^{(t)} = \bm{V}^\intercal(\bm{\beta}^{(t)} - \bm{\beta}^{\mathrm{LS}})$ 为误差在 $\bm{V}$ 列基里的坐标。则

$$\bm{V}^\intercal(\bm{I} - \bm{X}^\intercal \bm{X})\bm{V} = \bm{I} - \bm{\Sigma}^2$$

是对角矩阵，第 $i$ 个对角元为 $1 - \sigma_i^2$。在 $\bm{V}$ 基里，迭代误差就是逐分量按 $|1 - \sigma_i^2|$ 收缩：$\bm{e}^{(t+1)}_i = (1 - \sigma_i^2) \bm{e}^{(t)}_i$。

我们最终关心 $\|\bm{X}(\bm{\beta}^{(t)} - \bm{\beta}^{\mathrm{LS}})\|_2 = \|\bm{U}\bm{\Sigma}\bm{e}^{(t)}\|_2 = \|\bm{\Sigma}\bm{e}^{(t)}\|_2$（$\bm{U}$ 正交保范数）。两轮之间的比值：

$$\frac{\|\bm{\Sigma}\bm{e}^{(t)}\|_2^2}{\|\bm{\Sigma}\bm{e}^{(t-1)}\|_2^2} = \frac{\sum_i \sigma_i^2 (1 - \sigma_i^2)^2 (\bm{e}^{(t-1)}_i)^2}{\sum_i \sigma_i^2 (\bm{e}^{(t-1)}_i)^2} \le \max_i (1 - \sigma_i^2)^2$$

所以

$$\|\bm{X}(\bm{\beta}^{(t)} - \bm{\beta}^{\mathrm{LS}})\|_2 \le \max_i |1 - \sigma_i^2| \cdot \|\bm{X}(\bm{\beta}^{(t-1)} - \bm{\beta}^{\mathrm{LS}})\|_2$$

每轮误差按 $\max_i |1 - \sigma_i^2|$ 收缩。

关键观察

若 $\bm{X}$ 的所有奇异值都「足够接近」$1$（具体地，$|1 - \sigma_i^2| \le 1/2$，即 $\sigma_i \in [1/\sqrt{2}, \sqrt{3/2}]$），则每轮误差至少减半，$t$ 轮后误差以 $2^{-t}$ 速度缩到任意小：

$$\|\bm{X}(\bm{\beta}^{(t)} - \bm{\beta}^{\mathrm{LS}})\|_2 \le \|\bm{X}(\bm{\beta}^{(0)} - \bm{\beta}^{\mathrm{LS}})\|_2 / 2^t$$

实际数据的奇异值不会自带这个性质，但可以用 OSE「人为」造一个。

利用 OSE 构造预处理子

策略：找一个可逆矩阵 $\bm{R} \in \R^{d \times d}$，使 $\bm{X}\bm{R}$ 的奇异值都接近 $1$，然后在 $\bm{X}\bm{R}$ 上做梯度下降。

设 $\bm{\Pi}$ 是足够小常数 $\varepsilon_0$（如 $\varepsilon_0 \approx 0.2$）的 OSE。计算 $\bm{\Pi}\bm{X}$ 的 SVD：

$$\bm{\Pi}\bm{X} = \bm{U}' \bm{\Sigma}' \bm{V}'^\intercal$$

令 $\bm{R} = \bm{V}' \bm{\Sigma}'^{-1}$。则

观察 1（$\bm{X}\bm{R}$ 的奇异值接近 $1$）：对任意 $\bm{z}$，

$$\bm{\Pi}\bm{X}\bm{R}\bm{z} = (\bm{U}'\bm{\Sigma}'\bm{V}'^\intercal)(\bm{V}'\bm{\Sigma}'^{-1})\bm{z} = \bm{U}'\bm{z}$$

所以 $\|\bm{\Pi}\bm{X}\bm{R}\bm{z}\|_2 = \|\bm{U}'\bm{z}\|_2 = \|\bm{z}\|_2$。OSE 平方形式 $\|\bm{\Pi}\bm{v}\|_2^2 = (1 \pm \varepsilon_0)\|\bm{v}\|_2^2$ 应用到 $\bm{v} = \bm{X}\bm{R}\bm{z}$（属于 $\bm{X}$ 的列空间），开方得

$$\sqrt{1 - \varepsilon_0}\,\|\bm{X}\bm{R}\bm{z}\|_2 \le \|\bm{\Pi}\bm{X}\bm{R}\bm{z}\|_2 = \|\bm{z}\|_2 \le \sqrt{1 + \varepsilon_0}\,\|\bm{X}\bm{R}\bm{z}\|_2$$

即 $\bm{X}\bm{R}$ 的奇异值落在 $\left[\dfrac{1}{\sqrt{1+\varepsilon_0}}, \dfrac{1}{\sqrt{1-\varepsilon_0}}\right]$ 内，平方后 $\sigma_i^2(\bm{X}\bm{R}) \in [1/(1+\varepsilon_0), 1/(1-\varepsilon_0)]$，所以 $|1 - \sigma_i^2| \le \varepsilon_0/(1-\varepsilon_0)$。取 $\varepsilon_0 \le 1/3$ 即可让 $|1 - \sigma_i^2| \le 1/2$ 对所有 $i$ 成立——梯度下降的收缩条件达成。

下图对照预处理前后 $\bm{X}$ 的奇异值平方谱（注意左图是对数轴）：原始 $\bm{X}$ 的奇异值横跨好几个数量级，梯度下降会在「陡」方向震荡、在「平」方向龟速；经预处理子 $\bm{R}$ 校正后，所有 $\sigma_i^2$ 都被「拉平」进收敛带 $|1 - \sigma^2| \le 1/2$，于是每轮误差至少减半。

观察 2（最优化等价性）：$\bm{X}\bm{R}$ 与 $\bm{X}$ 有相同的列空间（$\bm{R}$ 可逆），所以

$$\min_{\bm{\beta}'} \|\bm{X}\bm{R}\bm{\beta}' - \bm{y}\|_2 = \min_{\bm{\beta}} \|\bm{X}\bm{\beta} - \bm{y}\|_2, \quad \bm{\beta} = \bm{R}\bm{\beta}'$$

二者最优解之间通过 $\bm{R}$ 一一对应。

把两个观察拼起来：先用 OSE + SVD 拿到预处理子 $\bm{R}$，在 $\bm{X}\bm{R}$ 上跑梯度下降，每轮误差减半，$T$ 轮后达到 $2^{-T}$ 的相对误差。

总代价：$\bm{\Pi}\bm{X}$ 乘积（视 $\bm{\Pi}$ 类型而定）$+$ $O(m d^2)$ 的 SVD $+$ $T$ 轮 $O(n d + d^2)$ 的梯度（每轮里 $\bm{X}\bm{R}$ 的乘法吸收进 $O(d^2)$ 项）。$T$ 是常数即可达机器精度——这是大规模最小二乘的现代标配。

$\gamma$-net 论证：从 JL 到 OSE

前面把 OSE 当成一个黑箱来用，但还没回答最关键的问题：它怎么造？最自然的想法是直接拿来一个 JL 矩阵。在动手之前，先看清楚有什么困难。

一个表面看上去过不去的鸿沟

JL 矩阵只保证：固定的 $n$ 个向量被 $(1 \pm \varepsilon)$ 保持，证明用了对 $n$ 个对象的 union bound。

OSE 要的是：$d$ 维子空间里所有单位向量都被保持——这是一个不可数无穷的集合。直接做 union bound 显然不可能。

但「不可数无穷」这个直觉有个漏洞：单位球面在度量上是紧致的。任何方向都可以用有限多个「代表方向」近似到任意精度。如果我们能：

1. 找一个有限的「代表集」$N$（叫做 γ-网），网中每个向量都被 JL 保持；
2. 把任意方向写成网中向量的某个线性组合；
3. 用「网上的保持性」推出「整个球面的保持性」；

那么 OSE 就被构造出来了。这正是 γ-net 论证的策略。下图概括了它的两个关键步骤：左边是 $5^d$ 个「代表方向」（γ-网）覆盖整个单位球面，球面上任何方向都能在距离 $\gamma$ 内找到代表；右边是把任意方向 $\bm{x}$ 写成网中向量的几何级数和 $\bm{x} = \bm{x}_1 + \bm{x}_2 + \cdots$，其中 $\|\bm{x}_i\|$ 按 $\gamma^{i-1}$ 几何衰减（图中 $1.00 \to 0.39 \to 0.08$）。

第一步：定义 γ-net

不失一般性，把 $d$ 维子空间用一组正交基同构到 $\R^d$ 本身（这只是换个坐标系）。OSE 要保持的就是 $\mathbb{S}^{d-1}$ 上所有单位向量的范数。在这个同构下，JL 矩阵的形状从原本作用于 $\R^n$ 的 $\bm{\Pi} \in \R^{m \times n}$ 退化为作用于 $\R^d$ 的 $\bm{\Pi} \in \R^{m \times d}$——下面就分析这个简化形式。

γ-net

集合 $N \subset \mathbb{S}^{d-1}$ 称为单位球面的 $\gamma$-网，若

$$\forall \bm{x} \in \mathbb{S}^{d-1},\ \exists \bm{y} \in N\colon \|\bm{x} - \bm{y}\|_2 \le \gamma$$

直观地：网中的点是球面上的「代表」，球面上任何方向都能在 $\gamma$ 距离内被代表。$\gamma$ 越小，网越「密」，代表越精准，但代表数也越多。

第二步：体积论证给出 $|N| \le 5^d$

我们需要一个大小可控的 γ-网。用贪心构造：只要还有方向与 $N$ 中所有点距离 $> \gamma$，就把它加入 $N$；直到所有方向都被 $\gamma$-代表。

终止时观察：

• $N$ 中任意两点距离 $> \gamma$（贪心终止条件）；
• 以 $N$ 中每点为中心、半径 $\gamma/2$ 的球两两不交；
• 这些球都包含在原点处半径 $1 + \gamma/2$ 的球内。

由 $d$ 维球的体积 $V_d(R) = c_d R^d$（$c_d$ 是与维度有关的常数），「不交球的体积之和 $\le$ 大球的体积」给出

$$|N| \cdot c_d (\gamma/2)^d \le c_d (1 + \gamma/2)^d \implies |N| \le \left(\frac{1 + \gamma/2}{\gamma/2}\right)^d = \left(1 + \frac{2}{\gamma}\right)^d$$

特别地，$\gamma = 1/2$ 时 $|N| \le 5^d$。一个仅 $5^d$ 大小的集合代表了整个 $d$ 维球面。

第三步：JL 在网上的保持性

设 $\bm{\Pi}$ 是 $\R^d$ 上的 JL 矩阵，对任何固定向量 $\bm{v}$，

$$\Pr\bigl[\bigl|\|\bm{\Pi}\bm{v}\|_2^2 - 1\bigr| > \varepsilon\bigr] \le \exp(-\Omega(\varepsilon^2 m))$$

对网中 $5^d$ 个向量做 union bound：

$$\Pr\bigl[\exists \bm{y} \in N\colon \bigl|\|\bm{\Pi}\bm{y}\|_2^2 - 1\bigr| > \varepsilon\bigr] \le 5^d \cdot \exp(-\Omega(\varepsilon^2 m))$$

取 $m = \Omega(d / \varepsilon^2)$（远小于无穷），上式 $\le \exp(-\Omega(d))$。

这里就是 OSE 比 JL 「容易」的根本原因

JL 要 $m = O(\varepsilon^{-2} \log n)$ 去抵御 $n$ 个对象的 union bound；OSE 借助 $5^d$ 的网，只需 $m = O(\varepsilon^{-2} d)$。两者结构上是同一种「指数族 + union bound」，只是被绑住的对象数不同。

到这里，我们已经让网中所有方向都被 $(1 \pm \varepsilon)$ 保持。接下来要把它扩展到所有方向。

第四步：几何级数分解

关键想法：把任意 $\bm{x} \in \mathbb{S}^{d-1}$ 表示成

$$\bm{x} = \bm{x}_1 + \bm{x}_2 + \bm{x}_3 + \cdots, \qquad \|\bm{x}_i\|_2 \le \gamma^{i-1}$$

其中每个 $\bm{x}_i$ 都是网中向量的某个标量倍（所以 JL 也按比例保持它的范数）。$\|\bm{x}_i\|_2$ 几何级数衰减保证了求和收敛。

递归构造：

• $i = 1$：在 $N$ 中找 $\bm{y}_1$ 满足 $\|\bm{x} - \bm{y}_1\|_2 \le \gamma$。令 $\bm{x}_1 = \bm{y}_1$。
• $i \ge 2$：记残差 $\bm{r}_{i-1} = \bm{x} - \sum_{k < i} \bm{x}_k$。把它归一化得到单位向量 $\bm{r}_{i-1}/\|\bm{r}_{i-1}\|_2$，在 $N$ 中找 $\bm{y}_i$ 满足

  $$\left\|\frac{\bm{r}_{i-1}}{\|\bm{r}_{i-1}\|_2} - \bm{y}_i\right\|_2 \le \gamma$$

  令 $\bm{x}_i = \|\bm{r}_{i-1}\|_2 \cdot \bm{y}_i$（把网中单位向量放回残差的尺度）。

残差几何递减：

$$\|\bm{r}_i\|_2 = \|\bm{r}_{i-1} - \bm{x}_i\|_2 = \|\bm{r}_{i-1}\|_2 \cdot \left\|\frac{\bm{r}_{i-1}}{\|\bm{r}_{i-1}\|_2} - \bm{y}_i\right\|_2 \le \gamma \cdot \|\bm{r}_{i-1}\|_2$$

归纳：$\|\bm{r}_i\|_2 \le \gamma^i$（因为 $\|\bm{r}_0\|_2 = \|\bm{x}\|_2 = 1$）。

$\bm{x}_i$ 的范数界：由构造 $\|\bm{x}_i\|_2 = \|\bm{r}_{i-1}\|_2 \le \gamma^{i-1}$。

$\bm{x}_i$ 与网的关系：$\bm{x}_i = \|\bm{r}_{i-1}\|_2 \cdot \bm{y}_i$，所以 $\bm{x}_i / \|\bm{x}_i\|_2 = \bm{y}_i \in N$（如果 $\bm{x}_i \ne 0$）。这就保证 JL 对 $\bm{x}_i$ 的范数保持是按比例成立的。

最终 $\bm{x} = \lim_{n \to \infty} (\bm{x} - \bm{r}_n) = \sum_{i \ge 1} \bm{x}_i$（残差几何衰减到 $0$）。

第五步：合成范数保持

我们要的就是 $\|\bm{\Pi}\bm{x}\|_2^2 \approx \|\bm{x}\|_2^2 = 1$。展开：

$$\|\bm{\Pi}\bm{x}\|_2^2 = \left\|\bm{\Pi}\sum_i \bm{x}_i\right\|_2^2 = \sum_i \|\bm{\Pi}\bm{x}_i\|_2^2 + 2 \sum_{i < j} \langle \bm{\Pi}\bm{x}_i, \bm{\Pi}\bm{x}_j \rangle$$

需要分别控制对角项和交叉项。

对角项——JL 已经处理好了。由于 $\bm{x}_i = \|\bm{x}_i\|_2 \cdot \bm{y}_i$，$\bm{y}_i \in N$，JL 在网上的保持性给出 $\|\bm{\Pi}\bm{y}_i\|_2^2 = 1 \pm \varepsilon$，按比例 $\|\bm{\Pi}\bm{x}_i\|_2^2 = (1 \pm \varepsilon)\|\bm{x}_i\|_2^2$。

$$\sum_i \|\bm{\Pi}\bm{x}_i\|_2^2 = \sum_i \|\bm{x}_i\|_2^2 \cdot (1 \pm \varepsilon)$$

交叉项——需要 JL 不仅保持范数，还要保持内积。

内积保持引理

若 JL 对网中向量 $\bm{y}, \bm{y}'$ 与它们的差 $\bm{y} - \bm{y}'$ 都保持范数 $(1 \pm \varepsilon)$，则

$$\langle \bm{\Pi} \bm{y}, \bm{\Pi} \bm{y}' \rangle = \langle \bm{y}, \bm{y}' \rangle \pm O(\varepsilon)$$

证明：由极化恒等式 $\|\bm{a} - \bm{b}\|^2 = \|\bm{a}\|^2 + \|\bm{b}\|^2 - 2 \langle \bm{a}, \bm{b}\rangle$。把它套到 $\bm{a} = \bm{\Pi}\bm{y}, \bm{b} = \bm{\Pi}\bm{y}'$，并用 $\|\bm{\Pi}\bm{y}\|^2, \|\bm{\Pi}\bm{y}'\|^2, \|\bm{\Pi}(\bm{y} - \bm{y}')\|^2$ 都被 $(1 \pm \varepsilon)$ 保持，移项化简即得。

要让 $\bm{y} - \bm{y}'$ 也属于「JL 保持范数」的对象，把网扩张为 $N \cup \{\bm{y} - \bm{y}'\colon \bm{y}, \bm{y}' \in N\}$，大小最多 $|N|^2 \le 25^d$，仍是 $\exp(O(d))$，不改变 $m = O(d/\varepsilon^2)$ 的阶。

把内积保持应用到 $\bm{x}_i, \bm{x}_j$（它们是网中向量的标量倍，所以同样适用）：

$$\langle \bm{\Pi}\bm{x}_i, \bm{\Pi}\bm{x}_j\rangle = \langle \bm{x}_i, \bm{x}_j\rangle \pm O(\varepsilon) \cdot \|\bm{x}_i\|_2 \|\bm{x}_j\|_2$$

合并对角项与交叉项：

$$\|\bm{\Pi}\bm{x}\|_2^2 = \underbrace{\sum_i \|\bm{x}_i\|_2^2 + 2\sum_{i < j} \langle \bm{x}_i, \bm{x}_j\rangle}_{= \|\bm{x}\|_2^2 = 1} + O(\varepsilon) \cdot \left(\sum_i \|\bm{x}_i\|_2^2 + 2\sum_{i < j} \|\bm{x}_i\|_2 \|\bm{x}_j\|_2 \right)$$

后一个括号 $= \left(\sum_i \|\bm{x}_i\|_2\right)^2$。由几何级数 $\sum_i \|\bm{x}_i\|_2 \le \sum_{i \ge 1} \gamma^{i-1} = \dfrac{1}{1-\gamma}$，平方后 $\le \dfrac{1}{(1-\gamma)^2}$；$\gamma = 1/2$ 时上界为 $4 = O(1)$。

所以 $\|\bm{\Pi}\bm{x}\|_2^2 = 1 \pm O(\varepsilon)$。

OSE via JL（结论）

取 $m = \Theta(d/\varepsilon^2)$，则任意 $\R^{m \times d}$ 的 JL 矩阵 $\bm{\Pi}$（如高斯或 Achlioptas $\pm 1$ 构造）对单个固定向量的失败概率 $\le \exp(-\Omega(d))$。与 γ-net 的 $5^d$（含内积保持时 $25^d$）union bound 相乘后，总失败概率仍 $\le \exp(-\Omega(d))$，所以 $\bm{\Pi}$ 自动是任意 $d$ 维子空间的 $O(\varepsilon)$-OSE。

JL vs OSE 的代价对比：

任务	被保持的对象数	所需维度 $m$
JL（点集）	$n$ 个固定向量	$O(\varepsilon^{-2} \log n)$
OSE（子空间）	不可数无穷，但有 $5^d$ 大小的 γ-网	$O(\varepsilon^{-2} d)$

两者结构完全相同（指数集中 $+$ 对数大小的 union bound），只是「对数」里的对象数不同。这就是「OSE 比 JL 容易」的精确含义。

Count Sketch 作为 OSE

γ-net 论证告诉我们「JL 矩阵就是 OSE」。但 JL 是稠密矩阵，$\bm{\Pi} \bm{A}$ 的乘积时间是 $O(m n d)$——对稀疏的 $\bm{A}$（文本特征、网络邻接矩阵等，$\mathrm{nnz}(\bm{A}) \ll n d$）这是巨大浪费。

能否设计一种 OSE，让 $\bm{\Pi} \bm{A}$ 的时间只依赖 $\mathrm{nnz}(\bm{A})$？答案是 Count Sketch——回到那个我们已经熟悉的 ±1 稀疏矩阵。

极致的稀疏

Count Sketch 矩阵

$\bm{\Pi} = \bm{S}\bm{D} \in \R^{m \times n}$，其中：

• $\bm{D}$ 是对角矩阵，对角线为 i.i.d. Rademacher（每个 $\pm 1$）；
• $\bm{S}$ 由哈希函数 $h\colon [n] \to [m]$ 决定，每列恰好一个位置为 $1$（在第 $h(j)$ 行），其余为 $0$。

效果：每个 $\bm{x} \in \R^n$ 的第 $j$ 个坐标被「打上随机符号 $D_{jj}$」后累加进哈希桶 $h(j)$。整个 $\bm{\Pi}$ 每列只有一个非零元，列密度 $1$。

为什么这种稀疏带来速度提升：$\bm{\Pi} \bm{A}$ 的每个非零元 $\bm{A}_{ij}$ 只贡献一次（加到某个桶里），所以总时间是 $O(\mathrm{nnz}(\bm{A}))$，而非 $O(m n)$。对稀疏数据这是数量级提速。

代价：目标维度的二次增长

但稀疏不是免费的午餐。Count Sketch 作为 $d$ 维子空间的 OSE，目标维度

$$m = \Theta\left(\frac{d^2}{\varepsilon^2 \delta}\right)$$

比 JL 的 $O(d / \varepsilon^2)$ 多了一个 $d / \delta$ 倍。但对真正稀疏的输入，$O(\mathrm{nnz}(\bm{A}))$ 的乘积时间完全压倒维度上的劣势。

为什么是 $d^2$ 而非 $d$？直观上：JL 用稠密随机矩阵让每个坐标都参与「扩散」；Count Sketch 只让每个坐标参与一次，扩散能力差，需要更多桶来「容纳」。下面看具体分析为什么 $d^2$ 是正确的阶。

分析的整体策略

设 $\bm{A}$ 已经做过列正交化（不失一般性，把任意 $\bm{A}$ 的列空间用其 SVD 的左奇异向量代替——这只是换基），记为 $\bm{U} \in \R^{n \times d}$，列正交单位向量。

对任意 $\bm{x} \in \mathbb{S}^{d-1}$，令 $\bm{y} = \bm{U} \bm{x}$。我们要证 $\|\bm{\Pi}\bm{y}\|_2^2 = (1 \pm \varepsilon) \|\bm{y}\|_2^2 = 1 \pm \varepsilon$（注意 $\bm{y}$ 也是单位向量，因为 $\bm{U}$ 列正交）。

记 $u_i = \|\bm{U}_{i, *}\|_2^2$ 为 $\bm{U}$ 第 $i$ 行的能量平方（$i = 1, \dots, n$）。由 Cauchy-Schwarz：

$$|y_i|^2 = |\langle \bm{U}_{i, *}, \bm{x}\rangle|^2 \le \|\bm{U}_{i, *}\|_2^2 \cdot \|\bm{x}\|_2^2 = u_i$$

把行按 $u_i$ 降序排列（重排坐标不影响范数），$\bm{y}$ 的前几个坐标可能「重」（$u_1, u_2, \dots$ 较大），后面的「轻」。

把 $\bm{y}$ 切成两段：

• 重头 $\bm{y}_{1:(s-1)}$：前 $s - 1$ 行能量大，每个坐标可能很大；
• 轻尾 $\bm{y}_{s:n}$：剩余 $n - s + 1$ 行能量都被压在 $u_s$ 以下。

阈值 $s$ 怎么选？它应该挑在「重头几乎不影响」与「轻尾足够均匀」的最优分界处。下面三段分析会各自给出 $s$ 与 $m$ 的约束，合并起来得到最优选取——精细的分析最终给出 $m = \Theta(d^2 / (\varepsilon^2 \delta))$，与课件给出的结果一致。

下图概括这套「分而治之」：把 $\bm{U}$ 各行按能量 $u_i$ 降序排列后切成两段——重头（前 $s-1$ 个高能量坐标）要求两两哈希到不同桶（无碰撞，范数被精确保持），轻尾（其余低能量坐标）则散开到各桶、靠桶负载受控来压住方差，两段之间的交叉项再靠 Rademacher 符号相消。三种机制各管一段，正是 $m$ 中 $d^2$ 与 $1/\delta$ 因子的来源。

两段为什么要分开处理

两段被 Count Sketch 哈希后的行为有本质区别，需要不同的工具：

段	失败模式	控制工具
重头 $\bm{y}_{1:(s-1)}$	两个「重」坐标哈希到同一桶（碰撞）会产生大交叉项	无碰撞事件
轻尾 $\bm{y}_{s:n}$	所有「轻」坐标都参与，需要它们的方差控制	桶最大负载（max-load）
重头 $\times$ 轻尾	交叉项需要 Rademacher 让其相消	Rademacher 集中

下面分别说明三段的处理思路。

重头：无碰撞 ⟹ 精确保持

设事件 $\mathcal{E}_B$ 表示重头的 $s - 1$ 个坐标在 $\bm{S}$ 下两两不碰撞——它们各自落入不同的桶。在这个事件上，$\bm{\Pi} \bm{y}_{1:(s-1)}$ 的每一桶最多接收一个重头坐标，连带 Rademacher 符号不变，所以

$$\|\bm{\Pi} \bm{y}_{1:(s-1)}\|_2^2 = \|\bm{y}_{1:(s-1)}\|_2^2 \quad \text{（精确，无误差！）}$$

把 $s - 1$ 个坐标哈希到 $m$ 个桶里不碰撞的概率——「生日问题」类型——大约是 $1 - \binom{s-1}{2}/m$。要这个 $\ge 1 - \delta/3$，需要 $m = \Omega(s^2 / \delta)$。这是 $s^2$ 进入 $m$ 的关键来源。

轻尾：桶最大负载控制方差

记事件 $\mathcal{E}_h$ 表示每个桶 $j \in [m]$ 接收的「轻尾能量」都不超过某个阈值：

$$\max_{j \in [m]} \sum_{\substack{i \ge s \\ h(i) = j}} u_i \le \tau$$

直观上：把轻尾的能量 $\{u_i\}_{i \ge s}$ 当作砝码扔进 $m$ 个桶，没有桶被堆得太重。由 $u_i \le u_s$ 对 $i \ge s$，期望每桶承担 $\sum_{i \ge s} u_i / m \le d/m$（因为 $\sum_i u_i = \|\bm{U}\|_F^2 = d$）。

在 $\mathcal{E}_h$ 上可以证明 $\|\bm{\Pi} \bm{y}_{s:n}\|_2^2 \approx \|\bm{y}_{s:n}\|_2^2$，误差 $\pm O(\varepsilon)$。这一段对 $m$ 提出的约束大致是 $m \gtrsim d/\varepsilon^2$（来自方差与每桶负载 $d/m$ 的比较）。

交叉项：Rademacher 让它消失

最微妙的是交叉项 $\langle \bm{\Pi} \bm{y}_{s:n}, \bm{\Pi} \bm{y}_{1:(s-1)}\rangle$。在 $\mathcal{E}_h, \mathcal{E}_B$ 给定的条件下，Rademacher 符号 $\bm{D}$ 与哈希位置独立。把每个落入与重头同桶的轻尾坐标加上 Rademacher 符号，得到一个 Rademacher 加权和，由类似 Khintchine 的方差控制可以压到 $O(\varepsilon)$。这一段贡献的 $m$ 约束最严格——大致是 $m \gtrsim s \cdot d / (\varepsilon^2 \delta)$，因为有 $s - 1$ 个重头位置每个都要被「保护」不与轻尾的高能量项碰撞。

合成：$s$ 的最优选取

把三段合起来：

$$\bigl|\|\bm{\Pi}\bm{y}\|_2^2 - \|\bm{y}\|_2^2\bigr| = \underbrace{\bigl|\|\bm{\Pi}\bm{y}_{1:(s-1)}\|_2^2 - \|\bm{y}_{1:(s-1)}\|_2^2\bigr|}_{= 0 \text{ on } \mathcal{E}_B} + \underbrace{\bigl|\|\bm{\Pi}\bm{y}_{s:n}\|_2^2 - \|\bm{y}_{s:n}\|_2^2\bigr|}_{\le O(\varepsilon) \text{ on } \mathcal{E}_h} + \underbrace{2|\langle \bm{\Pi}\bm{y}_{s:n}, \bm{\Pi}\bm{y}_{1:(s-1)}\rangle|}_{\le O(\varepsilon)}$$

总误差 $O(\varepsilon)$。三段的失败概率合起来要 $\le \delta$，每段都需要 $m$ 足够大。把这些约束写成只关于 $s$ 与 $m$ 的形式：

段	对 $m$ 的约束
重头无碰撞	$m \gtrsim s^2 / \delta$
轻尾低负载	$m \gtrsim d / \varepsilon^2$
交叉项	$m \gtrsim s \cdot d / (\varepsilon^2 \delta)$

三条约束里，「重头无碰撞」按 $s^2$ 增长，「交叉项」按 $s$ 线性增长——两者反向制衡。一个粗糙的平衡是让 $s^2/\delta = s d/(\varepsilon^2 \delta)$，给出 $s = \Theta(d/\varepsilon^2)$ 量级；精细的分析（详见 Clarkson-Woodruff 等文献）综合各项常数后给出

$$m = \Theta\left(\frac{d^2}{\varepsilon^2 \delta}\right)$$

这就是 Count Sketch OSE 的最终维度——保留了对稀疏输入的速度优势，代价是维度比 JL OSE 多一个 $d / \delta$ 倍。

取舍

Count Sketch 在「列稀疏 $d^2$ 维」和 JL 的「稠密 $d$ 维」之间提供了一个权衡。实际选哪一个：

• $\mathrm{nnz}(\bm{A})$ 远小于 $n d$（稀疏数据）：选 Count Sketch，乘积时间是输入相关的；
• $\bm{A}$ 稠密但 $d$ 很大：选 JL，维度是 $d$ 而非 $d^2$。

现代大规模数据系统常用 Count Sketch 作为 OSE 的「主力」，在稀疏特征矩阵上获得显著加速。

章节小结

本讲沿着「在低维近似保持几何」这条主线，串起了一系列关键工具：

flowchart TD
    JL["JL 定理<br/>k = O(ε⁻² log n)"]
    Gauss["高斯构造<br/>χ² 集中"]
    Sub["子空间投影"]
    Pm["±1 构造<br/>Count Sketch"]
    FJLT["FJLT<br/>Hadamard + Rademacher"]
    NNS["NNS / ANN"]
    LSH["局部敏感哈希"]
    OSE["子空间嵌入 OSE"]
    Reg["大规模线性回归"]
    Net["γ-net 论证"]
    CS_OSE["Count Sketch as OSE"]

    JL --> Gauss
    JL --> Sub
    JL --> Pm
    JL --> FJLT
    JL --> NNS
    NNS --> LSH
    JL --> Net
    Net --> OSE
    OSE --> Reg
    OSE --> CS_OSE
    Pm -.-> CS_OSE

    classDef core fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef construct fill:#e8f5e8,stroke:#2e7d32,stroke-width:2px
    classDef app fill:#fff3e0,stroke:#ef6c00,stroke-width:2px
    classDef tech fill:#f3e5f5,stroke:#4a148c,stroke-width:2px

    class JL,OSE core
    class Gauss,Sub,Pm,FJLT,CS_OSE construct
    class NNS,LSH,Reg app
    class Net tech

几条值得记住的「事实」：

工具	目标维度	构造时间	适用场景
JL（高斯）	$O(\varepsilon^{-2} \log n)$	$O(d k)$	通用降维
Count Sketch（JL）	$O(\varepsilon^{-2} \log n)$	$O(d k)$	$\pm 1$，硬件友好
FJLT	$O(\varepsilon^{-2} \log n \log d)$	$O(d \log d)$	大 $d$
Count Sketch（OSE）	$O(d^2/\varepsilon^2 \delta)$	$O(\mathrm{nnz}(\bm{A}))$	稀疏数据

一个统一的主题：随机的几何嵌入 + 集中不等式 = 高维数据的现代工具。

---

1. 词频-逆文档频率（Term Frequency-Inverse Document Frequency），是文本挖掘中常用的特征表示方法。每个维度对应一个词，值是该词在文本中的频率乘以该词在整个语料库中的逆文档频率（衡量该词的重要性）。TF-IDF 向量通常非常稀疏且高维。词频（TF）：衡量一个词在特定文档中出现的频率，频率越高表明相关性越强。逆文档频率（IDF）：降低在许多文档中频繁出现的词汇（例如 "the" "and"）的权重，并提高稀有词汇的权重。 ↩︎

2. 此外还有线性变换性质：如果 $A_{ij}$ 是独立的 $\mathcal{N}(0, \sigma^2)$，则 $a A_{ij}$ 是 $\mathcal{N}(0, a^2 \sigma^2)$；如果 $X_i$ 是独立的 $\mathcal{N}(\mu_i, \sigma_i^2)$，则 $\sum_i a_i X_i$ 是 $\mathcal{N}(\sum_i a_i \mu_i, \sum_i a_i^2 \sigma_i^2)$。 ↩︎