随机投影

随机投影 (Random Projection) 是一种利用随机矩阵将高维数据映射到低维子空间的高效降维方法。其核心理论基础是 Johnson–Lindenstrauss 引理，该引理保证：在适当的概率下，随机投影能够近似保持原始高维数据点之间的成对欧氏距离。与主成分分析 (PCA) 等确定性方法相比，随机投影具有计算成本低、无需观察全部数据即可操作、且能良好适应流式数据场景等优势，因而在机器学习、信号处理、近似最近邻搜索和信息检索等领域得到了广泛的应用。

数学原理与 Johnson–Lindenstrauss 引理

设原始数据 $\mathbf{X} \in \mathbb{R}^{n \times d}$ 包含 $n$ 个 $d$ 维样本点（通常 $d$ 非常大）。随机投影的目标是构造一个随机矩阵 $\mathbf{R} \in \mathbb{R}^{d \times k}$（$k \ll d$），使得投影后的低维表示 $\tilde{\mathbf{X}} = \mathbf{X} \mathbf{R} \in \mathbb{R}^{n \times k}$ 以高概率近似保持 $\mathbf{X}$ 中点之间的欧氏距离结构。

Johnson–Lindenstrauss 引理（1984）是这一方法的理论支柱。设 $\epsilon \in (0, 1)$ 为失真参数，$n$ 为样本点数，则存在一个从 $\mathbb{R}^d$ 到 $\mathbb{R}^k$ 的线性映射 $f$，使得对所有 $\mathbf{u}, \mathbf{v} \in S$（$|S| = n$），有

其中 $k = O(\epsilon^{-2} \log n)$。这一结果的关键洞察在于：目标维度 $k$ 仅依赖于样本数量的对数，而与原始维度 $d$ 完全无关——这意味着即使数据位于数百万维的空间中，只要将其投影到 $O(\log n)$ 维的低维空间，距离结构就能被高概率保持。这一结论在直觉上十分惊人：它意味着高维空间中的点集本质上具有比表观维度低得多的内在维度。

常见的随机投影矩阵构造

随机投影的核心在于 $\mathbf{R}$ 的分布选择。不同的构造方式在计算效率、理论保证和实际表现上各有侧重。常用的构造方式有以下三种。

高斯随机投影

$\mathbf{R}$ 的每个元素独立同分布于标准正态分布 $r_{ij} \sim \mathcal{N}(0, 1)$，然后对投影结果进行缩放 $1/\sqrt{k}$。高斯投影是理论性质最清晰的方案，因为正态分布的正交不变性使其几乎等距地作用于所有方向。实际使用中，高斯投影的 Johnson–Lindenstrauss 性质可以直接从正态分布的集中不等式推出，证明最为直观。

稀疏随机投影

Achlioptas（2001）提出了一种计算上更高效的构造：以概率 $1/6$ 取 $\sqrt{3}$，以概率 $1/6$ 取 $-\sqrt{3}$，以概率 $2/3$ 取 $0$，即

矩阵的稀疏性（约 $2/3$ 为零）大幅降低了投影的计算开销：与高斯投影的 $O(dk)$ 相比，稀疏投影的期望计算时间为 $O(dk/3)$，在极稀疏情形下可通过特殊数据结构进一步加速。

非常稀疏投影

Li, Hastie 和 Church（2006）推广了上述方法，引入参数 $s$ 来控制稀疏程度：以概率 $1/(2s)$ 取 $\sqrt{s}$，以概率 $1/(2s)$ 取 $-\sqrt{s}$，以概率 $1 - 1/s$ 取 $0$。当 $s \to \infty$ 时矩阵趋向于超稀疏，能在保持 Johnson–Lindenstrauss 保证的同时进一步降低计算成本。

与 PCA 的比较

PCA 和随机投影尽管都用于降维，但两者的哲学和适用场景截然不同。PCA 选择数据方差最大的方向（主成分），是一种数据依赖的、最优的低秩逼近。然而，PCA 需要对协方差矩阵进行奇异值分解（SVD），计算复杂度为 $O(\min(d^2 n, d n^2))$，当 $d$ 极大时（例如文本词袋数据，$d$ 可达数百万）不可行。此外，PCA 是批处理算法，增量更新并非直接支持。

随机投影则是数据无关的——投影矩阵完全由随机性决定，无需观察数据即可生成。这使得它特别适合分布式和流式环境：投影过程本身只是一个简单的矩阵乘法，时间仅为 $O(n d k)$，且极易并行化。但代价是投影后的维度 $k$ 可能存在冗余，且无法像 PCA 那样对方差进行最优集中。在实际应用中，一种常见的策略是先使用随机投影将数据快速降至中等维度（如 $k = 1000$），再用 PCA 进行精细压缩（如 $k' = 50$）。这种两阶段方法兼具随机投影的速度和 PCA 的最优性。

在近似最近邻搜索中的应用

随机投影的一个重要实用场景是局部敏感哈希 (Locality-Sensitive Hashing, LSH)。具体来说，可以利用随机投影的符号（$\operatorname{sgn}(\mathbf{x} \mathbf{R})$）来构造哈希函数：如果两个点在投影后的符号向量一致，则它们极有可能是近邻。这种方法的理论保证依赖于随机投影的距离保持性质：若原始距离小，则投影后方向相近，符号冲突的概率低，从而同一哈希桶中的点更可能具有较小的距离。在 Web 文档去重、图像检索和推荐系统中，这一技术被广泛用于处理亿级数据集上的快速近似近邻搜索任务。

总结

随机投影提供了一种简洁而优雅的降维框架，它在数学上的简洁性——基于 Johnson–Lindenstrauss 引理——和计算上的高效性使其成为高维数据分析的利器。与 PCA 等确定性方法互为补充，随机投影在数据维度极高、计算资源有限或数据以流式到达的场景下尤其具有不可替代的价值。近年来，随着深度学习嵌入向量维度的持续增长（如 BERT 的 768 维乃至更大的视觉模型特征），随机投影作为高效的索引和检索预处理步骤，正获得越来越广泛的学术和工业关注。