# On Robust Wasserstein Barycenter: The Model and Algorithm

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 38 references that are in the map.
- First posted on arXiv 25 Dec 2023.

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

- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm](https://mlsanity.com/paper/2002.04783/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Analysis](https://mlsanity.com/paper/2111.01361/) (2021)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Coresets for Clustering in Excluded-minor Graphs and Beyond](https://mlsanity.com/paper/2004.07718/) (2020)
- [Hardness results for Multimarginal Optimal Transport problems](https://mlsanity.com/paper/2012.05398/) (2020)
- [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018)
- [Improved Complexity Bounds in Wasserstein Barycenter Problem](https://mlsanity.com/paper/2010.04677/) (2020)
- [A Novel Sequential Coreset Method for Gradient Descent Algorithms](https://mlsanity.com/paper/2112.02504/) (2021)
- [Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems](https://mlsanity.com/paper/2107.00068/) (2021)
- [Coresets for Wasserstein Distributionally Robust Optimization Problems](https://mlsanity.com/paper/2210.04260/) (2022)
- [Near-optimal Coresets for Robust Clustering](https://mlsanity.com/paper/2210.10394/) (2022)
- [A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment](https://mlsanity.com/paper/2209.02905/) (2022)
- [On Geometric Prototype And Applications](https://mlsanity.com/paper/1804.09655/) (2018)

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

- [Robust Barycenter Estimation using Semi-Unbalanced Neural Optimal Transport](https://mlsanity.com/paper/2410.03974/) (2024)

## Abstract (arXiv)

The Wasserstein barycenter problem is to compute the average of m given probability measures, which has been widely studied in many different areas; however, real-world data sets are often noisy and huge, which impedes its applications in practice. Hence, in this paper, we focus on improving the computational efficiency of two types of robust Wasserstein barycenter problem (RWB): fixed-support RWB (fixed-RWB) and free-support RWB (free-RWB); actually, the former is a subroutine of the latter. Firstly, we improve efficiency through model reducing; we reduce RWB as an augmented Wasserstein barycenter problem, which works for both fixed-RWB and free-RWB. Especially, fixed-RWB can be computed within widetildeO(fracmn2ε_+) time by using an off-the-shelf solver, where ε_+ is the pre-specified additive error and n is the size of locations of input measures. Then, for free-RWB, we leverage a quality guaranteed data compression technique, coreset, to accelerate computation by reducing the data set size m. It shows that running algorithms on the coreset is enough instead of on the original data set. Next, by combining the model reducing and coreset techniques above, we propose an algorithm for free-RWB by updating the weights and locations alternatively. Finally, our experiments demonstrate the efficiency of our techniques.