🔢 mathematics

Nyström Approximation on Manifolds

本文提出了一种无坐标的黎曼 Nyström 近似，利用 Haar–Grassmann 投影在流形上高效构建低秩切空间算子，从而在保持正定性和精度的同时实现更快的随机牛顿型优化方法。

原作者： Hantao Nie, Bin Gao, Andi Han, Pratik Jawanpuria, Bamdev Mishra, Zaiwen Wen

发布于 2026-05-15

📖 1 分钟阅读🧠 深度阅读

原作者： Hantao Nie, Bin Gao, Andi Han, Pratik Jawanpuria, Bamdev Mishra, Zaiwen Wen

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

想象你正在尝试穿越一片复杂、弯曲的地形，比如地球表面或蜿蜒的山脉。在数学和机器学习中，这片地形被称为流形。为了在这片地形上做出决策——例如寻找最低点（优化）或理解地形的形状（分析）——你需要观察脚下那片“平坦”的地面。这片平坦的地面被称为切空间。

问题在于，在高维数据（如医学图像或复杂信号）中，这片平坦地面极其巨大。计算在其上移动的精确规则，就像试图阅读图书馆的每一页以找到某一句特定的话。这既耗时又耗费内存。

本文介绍了一种巧妙的捷径，称为黎曼 Nyström 近似。以下是其工作原理，辅以简单的类比：

1. 问题：“完整图书馆”与“摘要”

想象你拥有一张庞大而复杂的城市地图（切空间上的算子）。为了规划完美的路线，你通常需要以高清分辨率研究整张地图。但这张地图太大，导致你的计算机在尝试将其全部载入内存时崩溃。

作者指出：“我们不需要整张地图。我们只需要一个能保留最重要特征的摘要。”

2. 解决方案：“采样草图”

本文提出了一种通过仅观察地图的一小部分随机样本来创建该摘要的方法。

旧方法：在平坦、简单的数学（欧几里得空间）中，你可能只需随机选取坐标（例如随机选取街道地址）来推测布局。
新方法（本文）：由于我们处于弯曲表面上，无法直接选取“坐标”，因为表面没有固定的网格。相反，作者发明了一种**“哈尔–格拉斯曼草图化”**方法。
- 类比：想象你被蒙住双眼站在一个弯曲的山丘上。与其基于一个不存在的固定指南针来猜测北方，不如随机旋转并选择一个方向。数学保证无论你怎么旋转，你的随机选择在统计上都是公平的，并能完美代表整座山丘。这是“无坐标”的，意味着它不依赖于特定的地图网格。

3. 魔法技巧：“运输”草图

当你在弯曲表面上向前迈一步时，脚下的地面方向会发生变化。通常，你必须丢弃旧的摘要，并在新位置从头开始构建全新的摘要。这很慢。

作者表明，你可以将旧的摘要**“运输”**到新位置。

类比：想象你在一张柔韧的橡胶片上绘制了一幅房间的草图。如果你将这块橡胶移动到一个看起来相似的新房间，你可以拉伸并滑动橡胶以适应新房间，而无需重画所有内容。本文证明，如果你正确地移动“随机样本”（使用所谓的等距向量传输），统计规则依然成立。这节省了巨大的计算能力。

4. 结果：更快的优化

作者利用这一捷径构建了一种牛顿型方法。

目标：尽可能快地找到山谷底部（最佳解）。
方法：与其计算整个山谷的精确陡峭程度（这很慢），他们只计算所选随机样本的陡峭程度。
结果：他们在数学上证明了这种“采样”路径几乎与“精确”路径一样好，但速度快得多。

5. 现实世界测试

该团队在两种特定类型的弯曲地形上测试了这种方法：

SPD 流形：用于分析医学图像（如 MRI 扫描）等数据，其中数据点是必须保持“正定”和“对称”的形状。
格拉斯曼流形：用于诸如在数据集中寻找主方向（主测地线分析）等任务，类似于在一大堆文件中寻找主要趋势。

发现：

内存：他们仅使用了传统精确方法所需内存的4% 到 10%。
准确性：尽管使用了如此少的内存，结果却与昂贵的方法几乎完全相同。该“摘要”足够准确，足以正确解决问题。
速度：计算速度显著更快，尤其是在数据量巨大时。

总结

简而言之，本文教导计算机如何通过拍摄地形聪明的随机“快照”来导航复杂、弯曲的数据地形，而不是试图绘制整个地形。它证明这些快照在统计上是可靠的，可以携带到新位置而无需重绘，并允许计算机以更快的速度和更少的内存解决难题，同时不损失准确性。

技术摘要：流形上的黎曼 Nyström 近似

1. 问题陈述

机器学习和信号处理中的许多大规模问题天然地带有流形约束。虽然流形结构能够忠实地建模复杂几何，但切空间上相关的线性代数运算往往成为计算瓶颈，特别是在高维场景中。

具体而言，黎曼流形上的迭代方法通常要求构造一个切空间算子 $H_x: T_xM \to T_xM$ （通常是自伴且半正定的，例如黎曼 Hessian 矩阵），并计算其逆或伪逆。示例包括求解牛顿型优化的线性系统以及在协方差张量上执行主测地线分析（PGA）。显式地构建并求逆这些算子往往代价过高或不可行。现有的技术，如谱截断、多重网格求解器和黎曼拟牛顿法，试图缓解这一问题，但引发了一个疑问：能否构建一种具有可证明误差界的高效近似，同时保留算子的内在几何属性？

2. 方法论

2.1 黎曼 Nyström 近似

作者提出了一种针对 $d$ 维黎曼流形 $(M, g)$ 上自伴半正定（PSD）算子的无坐标黎曼 Nyström 近似。

给定一点 $x \in M$ 和一个算子 $H_x$ ，近似 $\hat{H}_{x, B, \Xi}$ 是利用两个 $\ell$ 维子空间 $B, \Xi \subset T_xM$ （其中 $\ell \leq d$ ）和一个满秩线性映射 $F: B \to \Xi$ 构造的。

草图算子（Sketching Operator）： 定义草图算子 $P_{x, B, \Xi}: T_xM \to T_xM$ 为 $P_{x, B, \Xi}[v] = F \Pi_B [v]$ ，其中 $\Pi_B$ 是到 $B$ 的正交投影。其伴随算子为 $P^*_{x, B, \Xi}[u] = F^* \Pi_\Xi [u]$ 。
近似公式： 黎曼 Nyström 近似定义为：
$\hat{H}_{x, B, \Xi}[u] = \left( H_x P_{x, B, \Xi} (P^*_{x, B, \Xi} H_x P_{x, B, \Xi})^\dagger P^*_{x, B, \Xi} H_x \right)[u]$
其中 $(\cdot)^\dagger$ 表示 Moore–Penrose 伪逆。该公式有效地将线性系统压缩到低维子空间 $B$ 中求解，然后将结果提升回切空间。

2.2 草图条件

为了实现随机误差分析，本文引入了两个草图条件：

高斯草图（Gaussian Sketching）： 类似于欧几里得情形，其中映射 $F$ 在内积上诱导高斯分布。
Haar–Grassmann 草图（Haar–Grassmann Sketching）： 一种新颖的、内在的条件，直接根据几何定义，不依赖于特定的坐标系。它要求：
1. 子空间 $\Xi$ 在 Grassmann 流形 $\text{Gr}(\ell, T_xM)$ 上服从 Haar 均匀分布。
2. $F$ 的极分解中的等距分量在 $B$ 与 $\Xi$ 之间的线性等距集合上服从 Haar 均匀分布。
3. $F$ 的径向因子满足特定的矩界。

该条件被证明是传输兼容的（transport-compatible）：如果草图算子在 $x$ 处满足 Haar–Grassmann 条件，那么通过等距向量传输将其传输到邻近点 $x'$ 后，该条件依然成立。这允许在迭代算法中采用“惰性刷新（lazy refresh）”策略，即传输草图而非在每一步重新生成。

2.3 优化算法

作者提出了一种**随机黎曼 Nyström 立方牛顿（RRNCN）**方法。

黎曼 Hessian 矩阵 $H_x$ 被其 Nyström 近似 $\hat{H}_{x, B, \Xi}$ 替代。
搜索方向通过在子空间 $B$ 中求解简化后的线性系统来计算。
为确保全局收敛，该方法结合了立方正则化，求解如下形式的子问题：
$\min_{v \in B} \left( \langle h, v \rangle_x + \frac{1}{2}\langle J[v], v \rangle_x + \frac{\sigma}{6}\|v\|_x^3 \right)$
其中 $h$ 和 $J$ 分别是草图化的梯度和 Hessian 分量。

3. 主要贡献

内在构造： 开发了一种无坐标的黎曼 Nyström 近似，保留了基本的算子属性，包括半正定性、自伴性以及 Loewner 序单调性。
Haar–Grassmann 草图： 引入了一种几何草图条件，将高斯草图推广到流形上。该条件是内在的、无坐标的，并且与等距向量传输兼容，解决了流形上缺乏规范坐标系的问题。
近似误差界： 建立了算子范数下的谱近似误差界。在 Haar–Grassmann 条件下，期望误差由 $H_x$ 的特征值和草图大小 $\ell$ 的函数界定。具体而言，误差取决于谱的尾部以及算子的“稳定秩”。
传输兼容性： 证明了 Haar–Grassmann 条件在等距向量传输下保持不变，从而使得优化算法中的迭代步骤能够高效地重用草图结构。
优化框架： 提出了一种利用黎曼 Nyström 近似的随机牛顿型方法，并附带了全局复杂度分析（ $O(d/(\ell \epsilon))$ ）以及在强测地凸性下的局部线性收敛速率。

4. 结果

本文通过对对称正定（SPD）流形和 Grassmann 流形上的数值实验验证了所提出的方法。

主测地线分析（PGA）： 在 HDM05 数据集（大小为 $93 \times 93$ $93 \times 93$ 的 SPD 矩阵）上的实验表明，Nyström 近似保留了下游统计性能。
- 准确性： 多类分类准确率（使用逻辑回归、SVM 和 MLP）以及 Hotelling's $T^2$ 统计量在草图大小 $\ell \in \{20, 40, 80\}$ 范围内与精确 PGA 相当。
- 效率： 该方法显著降低了内存使用量，仅需精确算子相关内存增加的 4.30%–9.64%，同时保持了有竞争力的统计质量。
SPD 流形上的优化： 在协方差估计的测地凸优化问题上的实验表明，中间大小的草图（例如 $\ell=80$ ）在近似质量和每迭代计算成本之间提供了最佳权衡，相比精确立方牛顿法，在挂钟时间上实现了更快的收敛。
Grassmann 流形上的传输草图： 在 Grassmann 流形（ $n=20000, p=20$ ）上的实验表明，使用传输草图（每 2–3 次迭代刷新一次）在迭代次数上实现了与完全刷新的 Nyström 方法几乎相同的收敛效果，但通过避免在每一步重新生成草图的成本，显著加快了运行速度。

5. 意义与主张

本文声称将经典的欧几里得 Nyström 理论扩展到了黎曼流形上切空间算子的场景。其主要意义在于提供了一种内在构造的低秩近似技术，保留了几何结构（PSD 属性、自伴性），并在几何上自然的草图条件（Haar–Grassmann）下提供了可证明的近似误差。

作者强调，这种方法允许在不构建完整算子的情况下高效计算切空间算子及其逆，使得高维流形优化和分析（如 PGA）在计算上变得可行。草图条件的传输兼容性被强调为实用迭代算法的关键赋能因素，它在保持理论保证的同时降低了计算开销。这项工作填补了随机线性代数与黎曼优化之间的空白，提供了一种可扩展的替代方案，以取代精确的二阶方法。