# Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support

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

## Key facts

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

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

- [Towards Cross-Tokenizer Distillation: the Universal Logit Distillation Loss for LLMs](https://mlsanity.com/paper/2402.12030/) (2024)
- [Automatic Text Evaluation through the Lens of Wasserstein Barycenters](https://mlsanity.com/paper/2108.12463/) (2021)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Dynamic Multimodal Prototype Learning in Vision-Language Models](https://mlsanity.com/paper/2507.03657/) (2025)
- [Small Transformers Compute Universal Metric Embeddings](https://mlsanity.com/paper/2209.06788/) (2022)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [Nonparametric Iterative Machine Teaching](https://mlsanity.com/paper/2306.03007/) (2023)
- [Projection Robust Wasserstein Barycenters](https://mlsanity.com/paper/2102.03390/) (2021)
- [Linear Optimal Partial Transport Embedding](https://mlsanity.com/paper/2302.03232/) (2023)
- [Variational Wasserstein Barycenters with c-Cyclical Monotonicity](https://mlsanity.com/paper/2110.11707/) (2021)
- [Nonparametric Teaching for Multiple Learners](https://mlsanity.com/paper/2311.10318/) (2023)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [A novel notion of barycenter for probability distributions based on optimal weak mass transport](https://mlsanity.com/paper/2102.13380/) (2021)
- [Fast Topological Clustering with Wasserstein Distance](https://mlsanity.com/paper/2112.00101/) (2021)
- [Clustering Market Regimes using the Wasserstein Distance](https://mlsanity.com/paper/2110.11848/) (2021)
- [Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structures](https://mlsanity.com/paper/2308.09250/) (2023)
- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [Continual Learning of Generative Models with Limited Data: From Wasserstein-1 Barycenter to Adaptive Coalescence](https://mlsanity.com/paper/2101.09225/) (2021)
- [Regularized Optimal Transport Layers for Generalized Global Pooling Operations](https://mlsanity.com/paper/2212.06339/) (2022)
- [Schr"odinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres](https://mlsanity.com/paper/2506.17197/) (2025)
- [Expectation Distance-based Distributional Clustering for Noise-Robustness](https://mlsanity.com/paper/2110.08871/) (2021)
- [Decentralized Entropic Optimal Transport for Distributed Distribution Comparison](https://mlsanity.com/paper/2301.12065/) (2023)
- [Spectral Clustering for Discrete Distributions](https://mlsanity.com/paper/2401.13913/) (2024)
- [Gamifying optimization: a Wasserstein distance-based analysis of human search](https://mlsanity.com/paper/2112.06292/) (2021)
- [Revisiting Global Pooling through the Lens of Optimal Transport](https://mlsanity.com/paper/2201.09191/) (2022)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)
- [An Asynchronous Decentralized Algorithm for Wasserstein Barycenter Problem](https://mlsanity.com/paper/2304.11653/) (2023)
- [Canonical Variates in Wasserstein Metric Space](https://mlsanity.com/paper/2405.15768/) (2024)
- [Explanation of Dynamic Physical Field Predictions using WassersteinGrad: Application to Autoregressive Weather Forecasting](https://mlsanity.com/paper/2604.22580/) (2026)

## Abstract (arXiv)

In a variety of research areas, the weighted bag of vectors and the histogram are widely used descriptors for complex objects. Both can be expressed as discrete distributions. D2-clustering pursues the minimum total within-cluster variation for a set of discrete distributions subject to the Kantorovich-Wasserstein metric. D2-clustering has a severe scalability issue, the bottleneck being the computation of a centroid distribution, called Wasserstein barycenter, that minimizes its sum of squared distances to the cluster members. In this paper, we develop a modified Bregman ADMM approach for computing the approximate discrete Wasserstein barycenter of large clusters. In the case when the support points of the barycenters are unknown and have low cardinality, our method achieves high accuracy empirically at a much reduced computational cost. The strengths and weaknesses of our method and its alternatives are examined through experiments, and we recommend scenarios for their respective usage. Moreover, we develop both serial and parallelized versions of the algorithm. By experimenting with large-scale data, we demonstrate the computational efficiency of the new methods and investigate their convergence properties and numerical stability. The clustering results obtained on several datasets in different domains are highly competitive in comparison with some widely used methods in the corresponding areas.