# Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jul 2015.

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

- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Wasserstein Barycenter-based Model Fusion and Linear Mode Connectivity of Neural Networks](https://mlsanity.com/paper/2210.06671/) (2022)
- [Estimating Barycenters of Distributions with Neural Optimal Transport](https://mlsanity.com/paper/2402.03828/) (2024)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [Variational Wasserstein Barycenters with c-Cyclical Monotonicity](https://mlsanity.com/paper/2110.11707/) (2021)
- [Differentially Private Post-Processing for Fair Regression](https://mlsanity.com/paper/2405.04034/) (2024)
- [Tangential Wasserstein Projections](https://mlsanity.com/paper/2207.14727/) (2022)
- [Continual Learning of Generative Models with Limited Data: From Wasserstein-1 Barycenter to Adaptive Coalescence](https://mlsanity.com/paper/2101.09225/) (2021)
- [Distribution Mismatch Correction for Improved Robustness in Deep Neural Networks](https://mlsanity.com/paper/2110.01955/) (2021)
- [Multi-Output Distributional Fairness via Post-Processing](https://mlsanity.com/paper/2409.00553/) (2024)
- [A Spectral-Grassmann Wasserstein metric for operator representations of dynamical systems](https://mlsanity.com/paper/2509.24920/) (2025)
- [Spectral Clustering for Discrete Distributions](https://mlsanity.com/paper/2401.13913/) (2024)
- [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)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)
- [Optimal Transport Features for Morphometric Population Analysis](https://mlsanity.com/paper/2208.05891/) (2022)
- [Estimation of the Sample Frechet Mean: A Convolutional Neural Network Approach](https://mlsanity.com/paper/2210.07401/) (2022)
- [Fused Gromov-Wasserstein Variance Decomposition with Linear Optimal Transport](https://mlsanity.com/paper/2411.10204/) (2024)
- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

Wasserstein barycenters correspond to optimal solutions of transportation problems for several marginals, and as such have a wide range of applications ranging from economics to statistics and computer science. When the marginal probability measures are absolutely continuous (or vanish on small sets) the theory of Wasserstein barycenters is well-developed (see the seminal paper [1]). However, exact continuous computation of Wasserstein barycenters in this setting is tractable in only a small number of specialized cases. Moreover, in many applications data is given as a set of probability measures with finite support. In this paper, we develop theoretical results for Wasserstein barycenters in this discrete setting. Our results rely heavily on polyhedral theory which is possible due to the discrete structure of the marginals. Our results closely mirror those in the continuous case with a few exceptions. In this discrete setting we establish that Wasserstein barycenters must also be discrete measures and there is always a barycenter which is provably sparse. Moreover, for each Wasserstein barycenter there exists a non-mass-splitting optimal transport to each of the discrete marginals. Such non-mass-splitting transports do not generally exist between two discrete measures unless special mass balance conditions hold. This makes Wasserstein barycenters in this discrete setting special in this regard. We illustrate the results of our discrete barycenter theory with a proof-of-concept computation for a hypothetical transportation problem with multiple marginals: distributing a fixed set of goods when the demand can take on different distributional shapes characterized by the discrete marginal distributions. A Wasserstein barycenter, in this case, represents an optimal distribution of inventory facilities which minimize the squared distance/transportation cost totaled over all demands.