A numerical algorithm with linear complexity for Multi-marginal Optimal Transport with L¹ Cost

Numerically solving multi-marginal optimal transport (MMOT) problems is computationally prohibitive, even for moderate-scale instances involving l4 marginals with support sizes of N1000. The cost in MMOT is represented as a tensor with Nˡ 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 O (Nˡ) or beyond. In this paper, inspired by our previous work Comm. \ Math. \ Sci. , 20 (2022), pp. 2053 - 2057, 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¹ cost, achieving a miraculous reduction in the computational cost of the entropy regularized solution to 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.