HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport Problems

doi:10.1109/TPAMI.2025.3564353

2025-08-01

DOI：10.1109/TPAMI.2025.3564353

原文链接

原文求助

摘要

En 中文

本文提出了一种高效的HOT算法，用于求解有限支撑集的最优运输（OT）问题。我们特别关注在支撑集位于$\mathbb {R}^{2}$且地面距离由$L_{2}^{2}$范数计算的情况下，HOT算法的高效实现。具体而言，我们设计了一种Halpern加速算法来求解离散OT问题的等效简化模型。此外，我们推导出一种新颖的方法，用于在HOT算法中以线性时间复杂度求解涉及的线性方程组。因此，我们可以获得具有$M$个支撑集的最优运输问题的$\varepsilon$-近似解，计算复杂度为$O(M^{1.5}/\varepsilon )$次浮点运算，这显著提高了已知最佳的计算复杂度。我们进一步提出了一种高效的过程，基于简化模型的解来恢复原始OT问题的最优运输计划，从而克服了简化OT模型在需要运输计划的应用中的局限性。我们在PyTorch中实现了HOT算法，大量的数值结果表明，与现有的求解OT问题的最先进算法相比，HOT算法具有优越的性能。

Keyword:

Optimal transport

Kantorovich-Wasserstein distance

Halpern iteration

acceleration

computational complexity