# Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters

arXiv: https://arxiv.org/abs/2202.00954 · HTML: https://mlsanity.com/paper/2202.00954/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 51 references that are in the map.
- First posted on arXiv 2 Feb 2022.

## Builds on (most cited first, 30 of 30)

- [Describing Textures in the Wild](https://mlsanity.com/paper/1311.3618/) (2013)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Statistical Aspects of Wasserstein Distances](https://mlsanity.com/paper/1806.05500/) (2018)
- [Scalable Bayes via Barycenter in Wasserstein Space](https://mlsanity.com/paper/1508.05880/) (2015)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [Debiased Sinkhorn barycenters](https://mlsanity.com/paper/2006.02575/) (2020)
- [Continuous Regularized Wasserstein Barycenters](https://mlsanity.com/paper/2008.12534/) (2020)
- [Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support](https://mlsanity.com/paper/1510.00012/) (2015)
- [Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm](https://mlsanity.com/paper/2002.04783/) (2020)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm](https://mlsanity.com/paper/1905.13194/) (2019)
- [Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space](https://mlsanity.com/paper/1910.05954/) (2019)
- [Wasserstein barycenters can be computed in polynomial time in fixed dimension](https://mlsanity.com/paper/2006.08012/) (2020)
- [Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data](https://mlsanity.com/paper/1507.07218/) (2015)
- [Fr'echet Means and Procrustes Analysis in Wasserstein Space](https://mlsanity.com/paper/1701.06876/) (2017)
- [On a linear Gromov-Wasserstein distance](https://mlsanity.com/paper/2112.11964/) (2021)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [A Generative Model for Texture Synthesis based on Optimal Transport between Feature Distributions](https://mlsanity.com/paper/2007.03408/) (2020)
- [The Linearized Hellinger--Kantorovich Distance](https://mlsanity.com/paper/2102.08807/) (2021)
- [Unbalanced Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2103.10854/) (2021)
- [Fixed Support Tree-Sliced Wasserstein Barycenter](https://mlsanity.com/paper/2109.03431/) (2021)
- [Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm](https://mlsanity.com/paper/1710.08234/) (2017)
- [Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem](https://mlsanity.com/paper/1905.12895/) (2019)
- [Improved Complexity Bounds in Wasserstein Barycenter Problem](https://mlsanity.com/paper/2010.04677/) (2020)
- [A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1809.04249/) (2018)
- [Randomised Wasserstein Barycenter Computation: Resampling with Statistical Guarantees](https://mlsanity.com/paper/2012.06397/) (2020)
- [An LP-based, Strongly-Polynomial 2-Approximation Algorithm for Sparse Wasserstein Barycenters](https://mlsanity.com/paper/1704.05491/) (2017)
- [Improved Linear Programs for Discrete Barycenters](https://mlsanity.com/paper/1803.11313/) (2018)
- [A Column Generation Approach to the Discrete Barycenter Problem](https://mlsanity.com/paper/1907.01541/) (2019)

## Abstract (arXiv)

Computationally solving multi-marginal optimal transport (MOT) with squared Euclidean costs for N discrete probability measures has recently attracted considerable attention, in part because of the correspondence of its solutions with Wasserstein-2 barycenters, which have many applications in data science. In general, this problem is NP-hard, calling for practical approximative algorithms. While entropic regularization has been successfully applied to approximate Wasserstein barycenters, this loses the sparsity of the optimal solution, making it difficult to solve the MOT problem directly in practice because of the curse of dimensionality. Thus, for obtaining barycenters, one usually resorts to fixed-support restrictions to a grid, which is, however, prohibitive in higher ambient dimensions d. In this paper, after analyzing the relationship between MOT and barycenters, we present two algorithms to approximate the solution of MOT directly, requiring mainly just N-1 standard two-marginal OT computations. Thus, they are fast, memory-efficient and easy to implement and can be used with any sparse OT solver as a black box. Moreover, they produce sparse solutions and show promising numerical results. We analyze these algorithms theoretically, proving upper and lower bounds for the relative approximation error.