175. A splitting method for computing Wasserstein Barycenters
Invited abstract in session WF-3: Splitting algorithms, stream Variational analysis: theory and algorithms.
Wednesday, 16:20 - 18:00Room: M:J
Authors (first author is the speaker)
| 1. | Welington de Oliveira
|
| CMA, Mines Paris PSL | |
| 2. | Daniel Mimouni
|
| IFP Energies Nouvelles | |
| 3. | Malisani Paul
|
| IFP Energies Nouvelles | |
| 4. | Jiamin Zhu
|
| IFP Energies Nouvelles |
Abstract
The Wasserstein barycenter (WB) is an important tool for summarizing sets of probability measures. It finds applications in applied probability, clustering, image processing, etc. When the measures' supports are finite, computing a (balanced) WB can be done by solving a linear optimization problem whose dimensions generally exceed standard solvers' capabilities. In the more general setting where measures have different total masses, we propose a convex nonsmooth optimization formulation for the so-called unbalanced WB problem. Due to their colossal dimensions, we introduce a decomposition scheme based on the Douglas-Rachford splitting method that can be applied to both balanced and unbalanced WB problem variants. Our algorithm, which has the interesting interpretation of being built upon averaging marginals, operates a series of simple (and exact) projections that can be parallelized and even randomized, making it suitable for large-scale datasets.
Keywords
- Convex and non-smooth optimization
- Optimization for learning and data analysis
Status: accepted
Back to the list of papers