🔢 mathematics

FINOM: Fast Sinkhorn on Non-uniform Meshes

本文介绍了 FINOM，这是一种线性复杂度的算法，它通过利用新发现的准共线结构，借助“划分索引”将非均匀网格上 Wasserstein-1 距离计算的每迭代复杂度从 $O(N^2)$ 降低到 $O(N)$ ，从而加速该计算。

原作者： Qihao Cheng, Qichen Liao, Hao Wu, Shuai Yang

发布于 2026-05-27

📖 1 分钟阅读🧠 深度阅读

原作者： Qihao Cheng, Qichen Liao, Hao Wu, Shuai Yang

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

想象你是一名物流经理，试图将一堆沙子从一个地点运到另一个地点。你有一个源堆（“供给”）和一个目标堆（“需求”）。你的目标是以最高效的方式移动沙子，使总行驶距离最小化。在数学和数据科学领域，这被称为最优传输。

本文介绍了一种名为FINOM（非均匀网格上的快速 Sinkhorn 算法）的新工具，用于比以往更快地解决这一问题，尤其是在“沙子”分布不均匀的情况下。

以下是该问题及其解决方案的分解，使用了简单的类比：

1. 问题：“网格”与“不均匀的沙子”

为了在计算机上解决这个数学问题，我们通常会在沙子所在的区域铺设一个网格（就像方格纸）。

均匀网格（旧方法）： 想象一个完美的均匀网格，就像棋盘。每个方格大小相同。过去，研究人员发现了一个巧妙的捷径（一种“快速 Sinkhorn"算法），可以在这些完美网格上解决沙子移动问题。这就像拥有一台魔法计算器，能在几秒钟内完成计算。
非均匀网格（现实世界）： 在现实生活中，事物并不完美。有时你在一个地方有一大堆沙子，而在另一个地方几乎没有任何沙子。为了高效，你可能会使用一种网格，在沙堆附近方格极小（以提高精度），而在空旷区域方格巨大（以节省空间）。这就是非均匀网格。
瓶颈： 旧的“魔法计算器”（快速 Sinkhorn）仅适用于完美的棋盘网格。当科学家试图将其用于这些不均匀的、现实世界的网格时，数学计算就会失效。他们不得不退回到缓慢的暴力计算方法，这需要非常长的时间（想象计算每一粒沙子与每一粒其他沙子之间的距离）。

2. 创新：“划分索引”

本文的作者问道：“我们能否让这台魔法计算器在不均匀的网格上工作？”

他们发现了一种方法，可以将混乱、不均匀的网格切割成两个整洁、易于管理的部分。他们发明了一个名为**“划分索引”**的概念。

类比： 想象你有一长排身高各异、摇摇晃晃的人。你想整理他们。与其试图一次性整理整排人，不如为每个人找到一个特定的“切割点”。
- 对于左边的人，你将他们分组到一个数学表现良好的区块中（就像楼梯一样）。
- 对于右边的人，你也做同样的处理。
“准共线”秘密： 即使网格不均匀，一旦他们使用这个“划分索引”将其分割，他们就发现每一半都隐藏着一个模式。它并非完全笔直，但它是“几乎笔直”的（准共线）。这种模式允许计算机使用动态规划技巧。

这里的动态规划是什么？
把它想象成爬楼梯。如果你想知道整个楼梯有多少级台阶，你不必每次都从底部重新数每一级台阶。你只需数出第一段楼梯的台阶数，然后加上下一段的台阶数，依此类推。你利用之前的答案来获得下一个答案。

旧方法： 每次都从头开始数每一级台阶（慢： $O(N^2)$ ）。
FINOM 方法： 利用之前的计数直接跳到下一步（快： $O(N)$ ）。

3. 结果：FINOM

通过使用“划分索引”将问题分割，然后应用“楼梯”计数技巧，作者创建了FINOM。

速度： 他们声称 FINOM 具有线性复杂度。用通俗的话说，如果你将数据量加倍，所需时间仅加倍。旧方法是“二次”的，意味着如果你将数据量加倍，所需时间将变为四倍（甚至更糟）。
准确性： 他们并没有为了速度而作弊。他们证明了 FINOM 给出的答案与缓慢但准确的方法完全相同。它只是更快地到达那里。
规模： 他们在具有随机、混乱网格的 1D（线）和 2D（平面）问题上测试了这一点。
- 在 1D 中，速度快了数百倍。
- 在 2D 中，速度快了数千倍（对于大型问题，加速比超过 10,000 倍）。

4. 为什么这很重要（根据论文）

论文特别指出，这对于数据分布不均匀的领域非常有用，例如：

计算流体动力学： 模拟空气或水的流动（你需要在机翼或管道附近获得高细节，而在空旷空间中只需低细节）。
金融： 建模金融风险，其中极端事件罕见但至关重要。

总结

本文提出了FINOM，这是一种新算法，就像是为计算如何在非均匀网格上移动概率分布（如沙子）安装了“涡轮增压器”。

问题： 进行这种数学运算的快速方法仅适用于完美、均匀的网格。现实世界的网格是混乱的。
解决方案： 他们发明了一个“划分索引”，将混乱的网格切割成两部分，这两部分表现得就像在完美网格上一样。
回报： 这使得计算机能够使用“楼梯”捷径（动态规划）来解决数学问题。
结果： 该解决方案的准确性与缓慢的方法一样，但运行速度快数千倍，使得在非均匀网格上进行复杂模拟首次变得切实可行。

技术摘要：FINOM——非均匀网格上的快速 Sinkhorn 算法

问题陈述

本文解决了在非均匀网格上定义的两个离散概率测度之间计算 Wasserstein-1 距离的计算挑战。虽然最优传输（OT）问题在流体力学、金融和机器学习等应用中至关重要，但在非均匀网格上高效求解该问题仍然困难。

标准的数值方法（如使用熵正则化的 Sinkhorn 算法）通常由于涉及核矩阵 $K$ 的稠密矩阵 - 向量乘法，导致每次迭代的计算复杂度为 $O(N^2)$ 。作者及他人的先前的工作已成功利用核矩阵中的“共线”结构，将 Sinkhorn 算法在均匀网格上的复杂度加速至 $O(N)$ 。然而，这种共线性质在非均匀网格上失效，阻碍了这些快速方法的直接应用。因此，使用非均匀网格（针对集中密度减少网格点数量）所获得的计算节省，往往被 $O(N^2)$ Sinkhorn 迭代的高昂成本所抵消。

方法论

作者提出了FINOM（非均匀网格上的快速 Sinkhorn 算法），这是一种动态规划方法，即使在非均匀网格上，也能将一维问题的线性复杂度恢复为 $O(N)$ ，二维问题恢复为 $O(NM)$。

1. 分割索引与块划分

核心创新在于引入了**“分割索引”** $\zeta(i)$ 。对于排序后的源网格 $x$ 和目标网格 $y$ ， $\zeta(i)$ 标识了 $y$ 中的索引，使得 $y_{\zeta(i)} \le x_i < y_{\zeta(i)+1}$ 。该索引允许将核矩阵 $K$ （其中 $k_{ij} = e^{-|x_i - y_j|/\varepsilon}$ ）划分为两个互补的子块：

下块（ $K_L$ ）： 包含 $j \le \zeta(i)$ 的条目。
上块（ $K_U$ ）： 包含 $j > \zeta(i)$ 的条目。

2. 准共线结构

虽然非均匀网格上的完整核矩阵缺乏均匀网格中严格的共线性，但作者证明了划分后的块 $K_L$ 和 $K_U$ 表现出**“准共线”**性质。具体而言：

在这些块的非零区域内，连续行之间的比率是恒定的（行内恒定比率性质）。
非零条目形成由分割索引决定的“阶梯”模式。

3. 向量表示与动态规划

利用准共线性质，作者证明了 $K_L$ 和 $K_U$ 可以完全由以下要素表示：

比率向量（ $r$ 或 $r'$ ），捕捉恒定的行对行缩放因子。
一组块边缘向量（ $\eta$ 或 $\eta'$ ），捕捉阶梯边界处的唯一值。

这种表示法使得矩阵 - 向量乘法（ $K\psi$ 和 $K^\top\phi$ ）能够进行递归计算。算法不再为每一行计算完整的点积，而是迭代地更新结果：
$p_{i+1} = r_i p_i + \eta_{i+1} \cdot \psi_{i+1}$
这将单次矩阵 - 向量乘法的成本从 $O(N^2)$ 降低到 $O(N)$ 。

4. 向高维扩展

对于二维及更高维的问题，核矩阵分解为 1D 核矩阵的克罗内克积（ $K = K_y \otimes K_x$ ）。作者通过在每个坐标方向上依次应用 1D 快速乘法算法来扩展 FINOM。这保持了相对于网格点总数的线性复杂度（二维为 $O(NM)$）。

主要贡献

快速 Sinkhorn 的推广： 本文将此前仅限于均匀网格的 $O(N)$ 快速 Sinkhorn 算法推广到了非均匀网格的一般情况。
分割索引概念： 引入分割索引，将核矩阵划分为具有准共线结构的块。
线性复杂度算法： 开发了 FINOM，实现了 1D 问题每次迭代 $O(N)$ 的复杂度，2D 问题为 $O(NM)$，同时保持了原始矩阵 - 向量乘法的精确性（不同于近似方法）。
数值验证： 广泛的实验证实，与标准 Sinkhorn 算法相比，FINOM 实现了数个数量级的加速，同时生成的传输计划与标准方法无法区分（差异在机器精度范围内）。

结果

作者在切比雪夫节点和随机非均匀节点上的随机分布中，对 1D 和 2D 问题进行了数值实验。

1D 性能： 随着 $N$ 从 500 增加到 8,000，FINOM 的加速比从约 $10^2$ 到约 $10^3$ 。观察到的缩放比例约为 FINOM 的 $O(N^{1.13})$ ，而标准 Sinkhorn 为 $O(N^{2.58})$ 。
2D 性能： 对于 2D 网格（ $N \times N$ ），加速比迅速增长，在 $160 \times 160$ 的网格上超过 $10^4$ 。观察到的缩放比例约为 FINOM 的 $O(N^{1.74})$ ，而标准 Sinkhorn 为 $O(N^{4.62})$ 。
精度： 在所有测试中，FINOM 与标准 Sinkhorn 算法计算的传输计划之间的差异的 Frobenius 范数（ $\Delta \Gamma$ ）在 $10^{-17}$ 到 $10^{-18}$ 量级，证实了加速并未损害数值精度。

意义与主张

本文主张 FINOM 解决了将最优传输应用于涉及非均匀网格（常见于计算流体力学和金融）的实际问题时的关键瓶颈。通过恢复线性复杂度，该方法使从业者能够利用非均匀网格来减少达到精度所需的网格点数量，而无需承担标准算法 prohibitive 的 $O(N^2)$ 计算成本。

作者强调，他们的方法并非近似；它加速了精确的 Sinkhorn 迭代。他们指出，虽然理论复杂度是线性的，但实验中观察到的指数（例如 $N^{1.13}$ ）略高于 1，这可能是由于实现开销所致，但其增长幅度远小于标准方法的二次或更高阶增长。这项工作为在通用非均匀离散化上实现高效、高精度的最优传输奠定了基础。