Loading [MathJax]/jax/output/HTML-CSS/config.js
Online First
A Numerical Algorithm with Linear Complexity for Multi-Marginal Optimal Transport with $L^1$ Cost
Chunhui Chen, Jing Chen, Baojia Luo, Shi Jin and Hao Wu

CSIAM Trans. Appl. Math. DOI: 10.4208/csiam-am.SO-2024-0025

Publication Date : 2025-06-24

  • Abstract

Numerically solving multi-marginal optimal transport (MMOT) problems is computationally prohibitive, even for moderate-scale instances involving $l≥4$ marginals with support sizes of $N ≥ 1000.$ The cost in MMOT is represented as a tensor with $N^l$ elements. Even accessing each element once incurs a significant computational burden. In fact, many algorithms require direct computation of tensor-vector products, leading to a computational complexity of $\mathcal{O}(N^l)$ or beyond. In this paper, inspired by our previous work [Comm. Math. Sci., 20, 2022], we observe that the costly tensor-vector products in the Sinkhorn Algorithm can be computed with a recursive process by separating summations and dynamic programming. Based on this idea, we propose a fast tensor-vector product algorithm to solve the MMOT problem with $L^1$ cost, achieving a miraculous reduction in the computational cost of the entropy regularized solution to $\mathcal{O}(N).$ Numerical experiment results confirm such high performance of this novel method which can be several orders of magnitude faster than the original Sinkhorn algorithm.

  • Copyright

COPYRIGHT: © Global Science Press