Built independently by an author, for readers. Read the story and support ChapterPal
ChapterPal Logo
Log inSign up

keyword

multimarginal Sinkhorn algorithms

Multimarginal Sinkhorn algorithms are iterative computational methods used to approximate solutions to multimarginal optimal transport problems involving three or more probability distributions through entropic regularization. By adding an entropy penalty to the optimal transport objective, these algorithms transform a computationally prohibitive high-dimensional linear program into an entropic tensor scaling problem. They operate by generalizing the classical two-marginal Sinkhorn-Knopp matrix balancing procedure to higher-order tensors, repeatedly updating scaling vectors across each marginal dimension in an alternating fashion until all prescribed marginal constraints are satisfied. This approach significantly reduces computational complexity compared to standard linear programming and interior-point solvers, enabling scalable and parallelizable computation for complex tasks such as multi-dataset alignment, density functional theory, and Wasserstein barycenter estimation.

1 item

On the Complexity of Approximating Multimarginal Optimal Transport

On the Complexity of Approximating Multimarginal Optimal Transport

Tianyi Lin, Nhat Ho, Marco Cuturi, Michael I. Jordan

OrganizationsENSAE ParisGoogleUniversity of CaliforniaUniversity of Texas at Austin

Why you should read this

Establishes the computational limits of discrete multimarginal optimal transport and introduces near-linear time Sinkhorn-based algorithms with rigorous complexity bounds that scale efficiently to multiple probability distributions.

We study the complexity of approximating the multimarginal optimal transport (MOT) distance, a generalization of the classical optimal transport distance, considered here between m discrete probability distributions supported each on n support points. First, we show that the standard linear programming (LP) representation of the MOT problem is not a minimum-cost flow problem when m ≥ 3. This negative result implies that some combinatorial algorithms, e.g., network simplex method, are not suitable for approximating the MOT problem, while the worst-case complexity bound for the deterministic interior-point algorithm remains a quantity of Õ(n^{3m}). We then propose two simple and deterministic algorithms for approximating the MOT problem. The first algorithm, which we refer to as multimarginal Sinkhorn algorithm, is a provably efficient multimarginal generalization of the Sinkhorn algorithm. We show that it achieves a complexity bound of Õ(m^{3}n^{m}ε^{−2}) for a tolerance ε ∈ (0, 1). This provides a first near-linear time complexity bound guarantee for approximating the MOT problem and matches the best known complexity bound for the Sinkhorn algorithm in the classical OT setting when m = 2. The second algorithm, which we refer to as accelerated multimarginal Sinkhorn algorithm, achieves the acceleration by incorporating an estimate sequence and the complexity bound is Õ(m^{3}n^{m+1/3}ε^{−4/3}). This bound is better than that of the first algorithm in terms of 1/ε, and accelerated alternating minimization algorithm (Tupitsa et al., 2020) in terms of n. Finally, we compare our new algorithms with the commercial LP solver GUROBI. Preliminary results on synthetic data and real images demonstrate the effectiveness and efficiency of our algorithms.

Added

2026-09-26