# Fast Computation of Wasserstein Barycenters

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

## Key facts

- Cited by 216 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2013.

## Built on by (most cited first, 30 of 216)

- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [Differentiable Particle Filtering via Entropy-Regularized Optimal Transport](https://mlsanity.com/paper/2102.07850/) (2021)
- [Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections](https://mlsanity.com/paper/2107.01718/) (2021)
- [Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization](https://mlsanity.com/paper/2102.01752/) (2021)
- [Entropic Neural Optimal Transport via Diffusion Processes](https://mlsanity.com/paper/2211.01156/) (2022)
- [Automatic Text Evaluation through the Lens of Wasserstein Barycenters](https://mlsanity.com/paper/2108.12463/) (2021)
- [A Survey on Optimal Transport for Machine Learning: Theory and Applications](https://mlsanity.com/paper/2106.01963/) (2021)
- [Low Budget Active Learning via Wasserstein Distance: An Integer Programming Approach](https://mlsanity.com/paper/2106.02968/) (2021)
- [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021)
- [Transformed Distribution Matching for Missing Value Imputation](https://mlsanity.com/paper/2302.10363/) (2023)
- [Dataset Distillation via the Wasserstein Metric](https://mlsanity.com/paper/2311.18531/) (2023)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [A Unified Framework for Implicit Sinkhorn Differentiation](https://mlsanity.com/paper/2205.06688/) (2022)
- [Curriculum Reinforcement Learning using Optimal Transport via Gradual Domain Adaptation](https://mlsanity.com/paper/2210.10195/) (2022)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [SurvITE: Learning Heterogeneous Treatment Effects from Time-to-Event Data](https://mlsanity.com/paper/2110.14001/) (2021)
- [Hierarchical Multi-Marginal Optimal Transport for Network Alignment](https://mlsanity.com/paper/2310.04470/) (2023)
- [Heterogeneous manifolds for curvature-aware graph embedding](https://mlsanity.com/paper/2202.01185/) (2022)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformer](https://mlsanity.com/paper/2201.13094/) (2022)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Efficient Gradient Flows in Sliced-Wasserstein Space](https://mlsanity.com/paper/2110.10972/) (2021)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space](https://mlsanity.com/paper/2312.02849/) (2023)
- [Interpreting Unfairness in Graph Neural Networks via Training Node Attribution](https://mlsanity.com/paper/2211.14383/) (2022)
- [Multimarginal generative modeling with stochastic interpolants](https://mlsanity.com/paper/2310.03695/) (2023)
- [Data Valuation and Detections in Federated Learning](https://mlsanity.com/paper/2311.05304/) (2023)
- [DESCN: Deep Entire Space Cross Networks for Individual Treatment Effect Estimation](https://mlsanity.com/paper/2207.09920/) (2022)
- [Monge, Bregman and Occam: Interpretable Optimal Transport in High-Dimensions with Feature-Sparse Maps](https://mlsanity.com/paper/2302.04065/) (2023)

## Abstract (arXiv)

We present new algorithms to compute the mean of a set of empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter, is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We propose two original algorithms to compute Wasserstein barycenters that build upon the subgradient method. A direct implementation of these algorithms is, however, too costly because it would require the repeated resolution of large primal and dual optimal transport problems to compute subgradients. Extending the work of Cuturi (2013), we propose to smooth the Wasserstein distance used in the definition of Wasserstein barycenters with an entropic regularizer and recover in doing so a strictly convex objective whose gradients can be computed for a considerably cheaper computational cost using matrix scaling algorithms. We use these algorithms to visualize a large family of images and to solve a constrained clustering problem.