# Dimensionality Reduction for Wasserstein Barycenter

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 71 references that are in the map.
- First posted on arXiv 18 Oct 2021.

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

- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Multilevel Clustering via Wasserstein Means](https://mlsanity.com/paper/1706.03883/) (2017)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [Scalable Bayes via Barycenter in Wasserstein Space](https://mlsanity.com/paper/1508.05880/) (2015)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [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)
- [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)
- [Wasserstein barycenters can be computed in polynomial time in fixed dimension](https://mlsanity.com/paper/2006.08012/) (2020)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data](https://mlsanity.com/paper/1507.07218/) (2015)
- [Subspace Detours: Building Transport Plans that are Optimal on Subspace Projections](https://mlsanity.com/paper/1905.10099/) (2019)
- [Parallel Streaming Wasserstein Barycenters](https://mlsanity.com/paper/1705.07443/) (2017)
- [The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction](https://mlsanity.com/paper/1411.2404/) (2014)
- [On the Computational Complexity of Finding a Sparse Wasserstein Barycenter](https://mlsanity.com/paper/1910.07568/) (2019)

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

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Hierarchical Optimal Transport for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2112.02073/) (2021)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Variational Wasserstein Barycenters with c-Cyclical Monotonicity](https://mlsanity.com/paper/2110.11707/) (2021)
- [To Err Is Human: Systematic Quantification of Errors in Published AI Papers via LLM Analysis](https://mlsanity.com/paper/2512.05925/) (2025)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)
- [Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures](https://mlsanity.com/paper/2506.00165/) (2025)
- [EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset](https://mlsanity.com/paper/2608.16101/) (2026)

## Abstract (arXiv)

The Wasserstein barycenter is a geometric construct which captures the notion of centrality among probability distributions, and which has found many applications in machine learning. However, most algorithms for finding even an approximate barycenter suffer an exponential dependence on the dimension d of the underlying space of the distributions. In order to cope with this "curse of dimensionality," we study dimensionality reduction techniques for the Wasserstein barycenter problem. When the barycenter is restricted to support of size n, we show that randomized dimensionality reduction can be used to map the problem to a space of dimension O(log n) independent of both d and k, and that any solution found in the reduced dimension will have its cost preserved up to arbitrary small error in the original space. We provide matching upper and lower bounds on the size of the reduced dimension, showing that our methods are optimal up to constant factors. We also provide a coreset construction for the Wasserstein barycenter problem that significantly decreases the number of input distributions. The coresets can be used in conjunction with random projections and thus further improve computation time. Lastly, our experimental results validate the speedup provided by dimensionality reduction while maintaining solution quality.