⚡ electrical engineering

Random features for Grassmannian kernel approximation with bounded rank-one projections

本文提出了一种利用有界秩一投影的可扩展随机特征框架，用以高效近似旋转不变的格拉斯曼核（Grassmannian kernels），从而克服经典方法在处理大规模子空间数据集时极高的计算与内存成本。

原作者： Rémi Delogne, Laurent Jacques

发布于 2026-08-06

📖 1 分钟阅读☕ 轻松阅读

原作者： Rémi Delogne, Laurent Jacques

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试教一台计算机识别物体，比如某种特定的犬种或某种类型的汽车。通常情况下，我们会向计算机输入单张照片。但如果物体的样子会根据角度、光照或时间的不同而发生变化呢？与其将每一张照片都视为一个独立的、孤立的点，不如将这一组照片看作一个整体的“形状”或“云团”往往更加聪明。在数学世界中，这个云团被称为子空间（subspace）。它就像是在一个巨大的三维房间（甚至是一个拥有数百个维度的房间）里漂浮着的一张平坦的纸。当我们拥有成千上万个这样的漂浮平面时，我们需要一种方法来衡量两个平面之间的相似性。它们是平行的吗？还是以一个尖锐的角度相交？

为了实现这一点，数学家们使用了一种叫做**核（kernel）的东西。把核想象成一把特殊的尺子，用来测量两个形状之间的“友好度”或相似性。问题在于，当你拥有一个庞大的形状库时，使用传统的尺子会极其缓慢，并且会耗尽你所有的计算机内存。这就像试图通过从头到尾阅读每一本书来比较图书馆里的每一本书；这会耗费无穷的时间。多年来，科学家们一直在寻找一种“捷径”——一种无需进行所有这些繁重的阅读就能快速估计相似性的方法。这就是随机特征（random features）**发挥作用的地方。与其阅读整本书，不如快速随机地扫视几页，然后推测其相似性。这种方法很快，但难点在于如何确保你的快速猜测是准确的，并且不会被奇怪的极端异常值所干扰。

本文介绍了一种巧妙的新方法，可以对这些漂浮的平面（子空间）进行快速的随机“扫视”，以测量它们的相似性。作者 Rémi Delogne 和 Laurent Jacques 提出了一种使用“秩一投影（rank-one projections）”的方法。想象一下，用手电筒照射穿过一个复杂的、多层玻璃雕塑（即子空间），并在墙上投射出它的影子。与其使用一个巨大、昂贵且沉重的强力手电筒（代表旧的、缓慢的方法），他们使用了一个微小、轻便的激光笔。然而，这里有一个陷阱：如果你只使用一个简单的激光笔，阴影有时会变得狂野且难以预测，就像一个闪烁不定的频闪灯。为了解决这个问题，作者为他们的激光笔添加了一个“过滤器”。他们使用一种特殊的数学过滤器，将狂野的影子约束成一种整齐、可预测的模式——要么将其转化为简单的“开/关”信号（类似于二进制代码），要么将其包裹成平滑的、重复的波形。

主要发现是，这些经过过滤的随机激光照射创造了一种新型的“相似性尺子”，它速度极快且占用内存极少，同时仍能高精度地捕捉到形状的真实几何结构。作者展示了，如果你进行足够多次的随机照射（具体来说，是一个与形状大小相关的次数），你的快速估计将与那些缓慢但完美的测量结果几乎完全一致，而且这对于你投掷给它的任何一对形状都成立。他们测试了两种类型的过滤器：一种产生“二进制”代码（仅由 0 和 1 组成），另一种产生“周期性”波形。二进制版本非常紧凑，几乎不占空间；而波形版本则有一个简洁的闭式公式，表现得像一个平滑且可调节的相似性测量仪。

本文还解决了速度问题。即使使用了小型激光笔，为庞大的数据集计算阴影仍然可能很慢。因此，作者借鉴了信号处理中的一个技巧，称为“结构化随机变换（structured random transforms）”。他们没有使用完全随机、混乱的激光，而是使用了一种遵循特定快速模式的激光（基于所谓的“沃尔什-哈达玛变换/Walsh-Hadamard transform”）。这就像是用一个整齐的预设网格取代了混乱的涂鸦；它让计算变得极快，且不会损失精度。

在实验中，作者在名为 ETH-80 的图像数据集上测试了这些方法，该数据集包含 80 种不同物体（如苹果、汽车和牛）的照片，这些照片是从许多不同角度拍摄的。他们将这些图像组转化为了前文提到的“漂浮平面”。当他们尝试使用这些新随机特征进行物体分类时，结果令人印象深刻。他们实现了极高的准确率——通常能达到与缓慢、完美的方法相当的表现——同时仅使用了极小部分的内存和时间。例如，在一次测试中，他们将数据表示量减少到了原始大小的仅 5%，却依然获得了出色的结果。他们方法的结构化快速版本甚至更快，在原本传统方法需要数分钟的时间内，它仅需数秒即可完成运行。

作者谨慎地指出，虽然他们的方法在速度和效率上有了巨大提升，但它所逼近的是一个与旧有的标准“相似性尺子”略有不同的工具。二进制版本创造了一种新的、有效的尺子，但目前还没有简单的公式；而波形版本则创造了一种可以根据他们称为“频率”的设置来调整以模拟不同现有尺子的尺子。他们在数学上证明了这些近似方法是可靠的，且误差是受控的，这意味着即使在处理海量数据时，你也可以信任这些结果。最终，这项工作表明，我们并不需要携带沉重、缓慢的工具来理解数据的形状；一种轻量级、智能且随机的方法同样可以胜任，这为在比以往更大、更复杂的数据集上进行机器学习开辟了大门。

技术摘要：具有有界秩一投影的 Grassmannian 核近似随机特征

问题陈述

在许多监督和无监督学习任务中，数据类或簇在自然状态下是由高维空间中的低维子空间而非单个欧几里得点来表示的。这使得在 Grassmann 流形 $\mathcal{G}(k, n)$ （即 $\mathbb{R}^n$ 中所有 $k$ 维子空间的集合）上进行操作成为必要。虽然核机器（如 SVM）可以使用正定核（如投影核或 Binet–Cauchy 核）在这些数据上进行有效学习，但它们面临着扩展性差的问题。标准的核方法需要构建并存储一个 $N \times N$ 的 Gram 矩阵，导致 $O(N^2)$ 的内存和计算成本，这对于大规模数据集来说是难以承受的。

现有的通过随机特征近似 Grassmannian 核的尝试面临两个主要局限：

稠密随机投影： 通过将正交投影映射到稠密高斯矩阵来嵌入子空间，每个特征需要 $O(n^2)$ 的存储和计算，这在处理高维数据时是不切实际的。
无界秩一投影 (ROP)： 虽然 ROPs 基于二次测量 $a^\top P b$ 的计算成本较低（每个特征 $O(kn)$），但它们表现出重尾分布（sub-Weibull）。这导致收敛速度缓慢，无法在整个 Grassmann 流形上实现随特征数量线性缩放的均匀近似保证。

方法论

作者提出了一类结合了秩一投影 (ROP) 与有界非线性变换的随机特征映射家族，以实现可扩展且均匀的核近似。

1. 秩一投影 (ROP)

对于由正交基 $U$ 表示的子空间 $P \in \mathcal{G}(k, n)$ （其中 $P = UU^\top$ ），该方法使用 $m$ 个独立的秩一二次测量来探测子空间：
$\psi_{\text{rop}}(U) = \left( a_i^\top P b_i \right)_{i=1}^m$
其中 $a_i, b_i \sim \text{i.i.d. } \mathcal{N}(0, I_n)$ 。这使得每个特征的计算成本降低至 $O(kn) $，存储也降低至$ O(kn) $（通过对$ U^\top a_i $和$ U^\top b_i$ 进行分解）。

2. 有界非线性变换

为了抑制无界 ROPs 的重尾分布并确保均匀收敛，作者将 $\psi_{\text{rop}}$ 与有界非线性函数 $g(\cdot)$ 复合：
$\psi_g(U) = g(\psi_{\text{rop}}(U))$
研究分析了两种特定的变换：

二值特征： 使用符号函数， $g(\lambda) = \text{sign}(\lambda)$ 。这产生了二值随机特征 $\psi_\pm \in \{\pm 1\}^m$ ，实现了紧凑的 1-bit 存储和快速位运算。
周期性特征： 使用复指数函数， $g(\lambda) = \exp(i\omega \lambda)$ 。这产生了周期性随机特征 $\psi_\circ$ ，类似于随机傅里叶特征（Random Fourier Features）。

3. 结构化投影

为了进一步降低计算复杂度，作者使用基于快速 Walsh-Hadamard 变换与随机对角符号矩阵组合的结构化随机矩阵（受 Choromanski 等人 2016 年的研究启发）替换了稠密高斯探测向量。这将在保持统计特性的同时，将计算复杂度从 $O(kmn) $降低到$ O(km \log n)$。

核心贡献

理论保证

论文证明了这些有界随机特征的经验内积是特定、定义良好的旋转不变 Grassmannian 核的无偏估计量。至关重要的是，作者证明了在固定维度 $k$ 的所有子空间上的均匀近似界限。

样本复杂度： 他们表明，$m = O(kn) $个随机特征（在对数因子范围内）足以控制整个流形的均匀近似误差。这与$ n $的线性关系以及与子空间维度$ k$ 的线性关系，相比于无界 ROPs 的 $O((kn)^2)$ 要求，是一个显著的改进。
二值核 ( $\kappa_\pm$ )： 二值特征的期望核被证明是正定的且具有旋转不变性。虽然对于一般 $k$ 不存在闭式解，但它可以半显式地表征为：
$\kappa_\pm(U, V) = 1 - \frac{2}{\pi} \mathbb{E}[\angle(P g, Q g)]$
其中 $g \sim \mathcal{N}(0, I_n)$ 且 $\angle(\cdot, \cdot)$ 是向量间的夹角。对于 $k=1$ ，推导出了闭式解 $(1 - 2\theta/\pi)^2$ 。
周期性核 ( $\kappa_\circ$ )： 周期性特征的期望核具有取决于主角度 $\{\theta_j\}_{j=1}^k$ ${θ_{j}}_{j = 1}^{k}$ 的闭式表达式：
$\kappa_\circ(U, V) = \prod_{j=1}^k (1 + \omega^2 \sin^2 \theta_j)^{-1}$
作者分析了 $\kappa_\circ$ $κ_{\circ}$ 随频率参数 $\omega$ $ω$ 的行为：
- 大 $\omega$ 时： $\kappa_\circ$ 表现得像反 Binet–Cauchy 核（对微小主角度敏感）。
- 小 $\omega$ 时： $\kappa_\circ$ 近似于投影径向基函数 (RBF) 核， $\exp(-\frac{1}{2}\omega^2 \|P-Q\|_F^2)$ 。

计算复杂度

提出的方法提供了显著的效率提升：

内存： 非结构化有界 ROPs 的存储空间为 $m$ 个探测向量的 $O(mn) $。当使用$ m = O(kn) $以确保均匀近似时，总内存复杂度变为$ O(kn^2) $（在文中具体推导为$ O(\delta^{-2}(kn^2)) $）。这与稠密投影所需的$ O(mn^2) $存储（对于均匀近似而言，其规模为$ O(k^3 n^3)$）截然不同。
计算： 非结构化有界 ROPs 的计算复杂度为 $O(kmn) $。当$ m = O(kn) $时，其规模为$ O(k^2 n^2) $。这显著低于与稠密投影方法相关的$ O(k^2 n^3) $复杂度（后者需要$ O(\delta^{-2} k^3 n^3)$）。
存储： 二值特征每个子空间仅需 $O(m)$ 比特。

实验结果

作者通过合成实验和 ETH-80 数据集（来自不同视角的视觉物体图像）验证了其方法。

核近似： 实验确认，有界 ROPs 以比稠密投影更低的计算和内存成本收敛到其目标核。
结构化嵌入： 对结构化 Hadamard-对角草图（sketches）的经验分析表明，使用 $S=3$ 个分块足以近似高斯分布，这验证了使用快速变换的有效性。
分类性能：
- 在超类分类（8 类）和物体分类（80 类）任务中，所提出的随机特征（包括非结构化和结构化）达到了与精确核方法相当的分类准确率，尽管根据具体任务和核的不同，存在一定的权衡。
- 特别是，使用过采样率 $\rho = m/(nk)$ 低至 0.05（原始基数大小的 5%）的结构化嵌入，在获得高准确率的同时，将计算时间降低了数个数量级。例如，在 80 类分类任务中，结构化方法将总运行时间从约 52.9 秒（精确投影核）减少到约 1.9 秒。然而，这种加速也带来了准确率的显著下降，从 98.75%（精确）降至 83.00%（结构化），凸显了在此特定设置下计算效率与分类性能之间的权衡。

重要性与声明

本文声称提供了一种实用且可扩展的经典 Grassmannian 核的替代方案。通过结合秩一投影与有界非线性，作者证明了实现以下目标是可能的：

高精度地恢复 Grassmann 几何结构。
在流形上实现均匀近似保证，且特征数量随内在维度线性缩放。
大幅降低内存和计算需求，使针对大规模、高维数据的基于核的学习变得可行。

这项工作弥合了理论核方法与实际可扩展性之间的鸿沟，提供了一个可以根据随机特征的数量和非线性变换的选择来显式控制近似误差与计算成本之间权衡的框架。