Fast Computation of Wasserstein Barycenters

作者: Arnaud Doucet , Marco Cuturi

DOI:

关键词:

摘要: We present new algorithms to compute the mean of a set empirical probability measures under optimal transport metric. This mean, known as Wasserstein barycenter, is measure that minimizes sum its distances each element in set. propose two original barycenters build upon subgradient method. A direct implementation these is, however, too costly because it would require repeated resolution large primal and dual problems subgradients. Extending work Cuturi (2013), we smooth distance used definition with an entropic regularizer recover doing so strictly convex objective whose gradients can be computed for considerably cheaper computational cost using matrix scaling algorithms. use visualize family images solve constrained clustering problem.

参考文章(33)
Leonidas Guibas, Adrian Butscher, Justin Solomon, Raif Rustamov, Wasserstein Propagation for Semi-Supervised Learning international conference on machine learning. pp. 306- 314 ,(2014)
Shun-ichi Amari, Hiroshi Nagaoka, Methods of information geometry ,(2000)
Julien Rabin, Gabriel Peyré, Julie Delon, Marc Bernot, Wasserstein Barycenter and Its Application to Texture Mixing Lecture Notes in Computer Science. ,vol. 6667, pp. 435- 446 ,(2012) , 10.1007/978-3-642-24785-9_37
John Tsitsiklis, Dimitris Bertsimas, Introduction to linear optimization ,(1997)
Martial Agueh, Guillaume Carlier, Barycenters in the Wasserstein Space Siam Journal on Mathematical Analysis. ,vol. 43, pp. 904- 924 ,(2011) , 10.1137/100805741
Takafumi Kanamori, Taiji Suzuki, Masashi Sugiyama, Statistical analysis of kernel-based least-squares density-ratio estimation Machine Learning. ,vol. 86, pp. 335- 367 ,(2012) , 10.1007/S10994-011-5266-3
Amir Beck, Marc Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization Operations Research Letters. ,vol. 31, pp. 167- 175 ,(2003) , 10.1016/S0167-6377(02)00231-6
Takafumi Kanamori, Taiji Suzuki, Masashi Sugiyama, $f$ -Divergence Estimation and Two-Sample Homogeneity Test Under Semiparametric Density-Ratio Models IEEE Transactions on Information Theory. ,vol. 58, pp. 708- 720 ,(2012) , 10.1109/TIT.2011.2163380
Michael K. Ng, A note on constrained k-means algorithms Pattern Recognition. ,vol. 33, pp. 515- 519 ,(2000) , 10.1016/S0031-3203(99)00057-6
Robert J. McCann, Existence and uniqueness of monotone measure-preserving maps Duke Mathematical Journal. ,vol. 80, pp. 309- 323 ,(1995) , 10.1215/S0012-7094-95-08013-2