# Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm

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

## Key facts

- Cited by 29 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 12 Feb 2020.

## Built on by (most cited first, 29 of 29)

- [Automatic Text Evaluation through the Lens of Wasserstein Barycenters](https://mlsanity.com/paper/2108.12463/) (2021)
- [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Revisiting Sliced Wasserstein on Images: From Vectorization to Convolution](https://mlsanity.com/paper/2204.01188/) (2022)
- [Hierarchical Sliced Wasserstein Distance](https://mlsanity.com/paper/2209.13570/) (2022)
- [Amortized Projection Optimization for Sliced Wasserstein Generative Models](https://mlsanity.com/paper/2203.13417/) (2022)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Integrating Efficient Optimal Transport and Functional Maps For Unsupervised Shape Correspondence Learning](https://mlsanity.com/paper/2403.01781/) (2024)
- [Global-Local Regularization Via Distributional Robustness](https://mlsanity.com/paper/2203.00553/) (2022)
- [Markovian Sliced Wasserstein Distances: Beyond Independent Projections](https://mlsanity.com/paper/2301.03749/) (2023)
- [Fixed Support Tree-Sliced Wasserstein Barycenter](https://mlsanity.com/paper/2109.03431/) (2021)
- [Projection Robust Wasserstein Barycenters](https://mlsanity.com/paper/2102.03390/) (2021)
- [Variational Wasserstein Barycenters with c-Cyclical Monotonicity](https://mlsanity.com/paper/2110.11707/) (2021)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Wasserstein Geodesic Generator for Conditional Distributions](https://mlsanity.com/paper/2308.10145/) (2023)
- [Structure-Aware E(3)-Invariant Molecular Conformer Aggregation Networks](https://mlsanity.com/paper/2402.01975/) (2024)
- [Relative Translation Invariant Wasserstein Distance](https://mlsanity.com/paper/2409.02416/) (2024)
- [On Label Shift in Domain Adaptation via Wasserstein Distance](https://mlsanity.com/paper/2110.15520/) (2021)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems](https://mlsanity.com/paper/2411.01115/) (2024)
- [Generalized Wasserstein Flow Matching: Transport Plans, Everywhere, All at Once](https://mlsanity.com/paper/2605.08424/) (2026)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)
- [Efficient Forecasting of Large Scale Hierarchical Time Series via Multilevel Clustering](https://mlsanity.com/paper/2205.14104/) (2022)
- [Liouville PDE-based sliced-Wasserstein flow](https://mlsanity.com/paper/2505.17204/) (2025)
- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

We study the fixed-support Wasserstein barycenter problem (FS-WBP), which consists in computing the Wasserstein barycenter of m discrete probability measures supported on a finite metric space of size n. We show first that the constraint matrix arising from the standard linear programming (LP) representation of the FS-WBP is textitnot totally unimodular when m ≥ 3 and n ≥ 3. This result resolves an open question pertaining to the relationship between the FS-WBP and the minimum-cost flow (MCF) problem since it proves that the FS-WBP in the standard LP form is not an MCF problem when m ≥ 3 and n ≥ 3. We also develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP, with a complexity bound of tildeO(mn7/3varepsilon-4/3), where varepsilon ∈ (0, 1) is the desired tolerance. This complexity bound is better than the best known complexity bound of tildeO(mn2varepsilon-2) for the IBP algorithm in terms of varepsilon, and that of tildeO(mn5/2varepsilon-1) from accelerated alternating minimization algorithm or accelerated primal-dual adaptive gradient algorithm in terms of n. Finally, we conduct extensive experiments with both synthetic data and real images and demonstrate the favorable performance of the textscFastIBP algorithm in practice.