Fast Computation of Wasserstein Barycenters

Marco Cuturi, Arnaud Doucet
; Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):685-693, 2014.

Abstract

We present new algorithms to compute the mean of a set of N empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter \citepagueh2011barycenters,rabin2012, is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We argue through a simple example that Wasserstein barycenters have appealing properties that differentiate them from other barycenters proposed recently, which all build on kernel smoothing and/or Bregman divergences. Two original algorithms are proposed that require the repeated computation of primal and dual optimal solutions of transport problems. However direct implementation of these algorithms is too costly as optimal transports are notoriously computationally expensive. Extending the work of \citetcuturi2013sinkhorn, we smooth both the primal and dual of the optimal transport problem to recover fast approximations of the primal and dual optimal solutions. We apply these algorithms to the visualization of perturbed images and to a clustering problem.

Cite this Paper


BibTeX
@InProceedings{pmlr-v32-cuturi14, title = {Fast Computation of Wasserstein Barycenters}, author = {Marco Cuturi and Arnaud Doucet}, pages = {685--693}, year = {2014}, editor = {Eric P. Xing and Tony Jebara}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/cuturi14.pdf}, url = {http://proceedings.mlr.press/v32/cuturi14.html}, abstract = {We present new algorithms to compute the mean of a set of N empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter \citepagueh2011barycenters,rabin2012, is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We argue through a simple example that Wasserstein barycenters have appealing properties that differentiate them from other barycenters proposed recently, which all build on kernel smoothing and/or Bregman divergences. Two original algorithms are proposed that require the repeated computation of primal and dual optimal solutions of transport problems. However direct implementation of these algorithms is too costly as optimal transports are notoriously computationally expensive. Extending the work of \citetcuturi2013sinkhorn, we smooth both the primal and dual of the optimal transport problem to recover fast approximations of the primal and dual optimal solutions. We apply these algorithms to the visualization of perturbed images and to a clustering problem.} }
Endnote
%0 Conference Paper %T Fast Computation of Wasserstein Barycenters %A Marco Cuturi %A Arnaud Doucet %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-cuturi14 %I PMLR %J Proceedings of Machine Learning Research %P 685--693 %U http://proceedings.mlr.press %V 32 %N 2 %W PMLR %X We present new algorithms to compute the mean of a set of N empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter \citepagueh2011barycenters,rabin2012, is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We argue through a simple example that Wasserstein barycenters have appealing properties that differentiate them from other barycenters proposed recently, which all build on kernel smoothing and/or Bregman divergences. Two original algorithms are proposed that require the repeated computation of primal and dual optimal solutions of transport problems. However direct implementation of these algorithms is too costly as optimal transports are notoriously computationally expensive. Extending the work of \citetcuturi2013sinkhorn, we smooth both the primal and dual of the optimal transport problem to recover fast approximations of the primal and dual optimal solutions. We apply these algorithms to the visualization of perturbed images and to a clustering problem.
RIS
TY - CPAPER TI - Fast Computation of Wasserstein Barycenters AU - Marco Cuturi AU - Arnaud Doucet BT - Proceedings of the 31st International Conference on Machine Learning PY - 2014/01/27 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-cuturi14 PB - PMLR SP - 685 DP - PMLR EP - 693 L1 - http://proceedings.mlr.press/v32/cuturi14.pdf UR - http://proceedings.mlr.press/v32/cuturi14.html AB - We present new algorithms to compute the mean of a set of N empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter \citepagueh2011barycenters,rabin2012, is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We argue through a simple example that Wasserstein barycenters have appealing properties that differentiate them from other barycenters proposed recently, which all build on kernel smoothing and/or Bregman divergences. Two original algorithms are proposed that require the repeated computation of primal and dual optimal solutions of transport problems. However direct implementation of these algorithms is too costly as optimal transports are notoriously computationally expensive. Extending the work of \citetcuturi2013sinkhorn, we smooth both the primal and dual of the optimal transport problem to recover fast approximations of the primal and dual optimal solutions. We apply these algorithms to the visualization of perturbed images and to a clustering problem. ER -
APA
Cuturi, M. & Doucet, A.. (2014). Fast Computation of Wasserstein Barycenters. Proceedings of the 31st International Conference on Machine Learning, in PMLR 32(2):685-693

Related Material