Fast Computation of Wasserstein Barycenters
Fast Computation of Wasserstein Barycenters
复制标题
DOI：
--
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Marco Cuturi;A. Doucet
中科院分区：
文献类型：
--
作者：
Marco Cuturi;A. Doucet
我们提出了新的算法来计算一组经验概率措施下的最佳运输度量的平均值。这个平均值，称为瓦瑟斯坦重心，是最小化其到该集合中每个元素的瓦瑟斯坦距离之和的度量。我们提出了两个原始算法来计算Wasserstein重心，建立在次梯度法。然而，这些算法的直接实现成本太高，因为它需要重复解决大型原始和对偶最优运输问题来计算次梯度。扩展Cuturi（2013）的工作，我们建议使用熵正则化器平滑Wasserstein重心定义中使用的Wasserstein距离，并在这样做时恢复严格凸目标，其梯度可以使用矩阵缩放算法以相当便宜的计算成本计算。我们使用这些算法来可视化一个大家庭的图像，并解决了约束聚类问题。
We present new algorithms to compute the mean of a set of empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter, is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We propose two original algorithms to compute Wasserstein barycenters that build upon the subgradient method. A direct implementation of these algorithms is, however, too costly because it would require the repeated resolution of large primal and dual optimal transport problems to compute subgradients. Extending the work of Cuturi (2013), we propose to smooth the Wasserstein distance used in the definition of Wasserstein barycenters with an entropic regularizer and recover in doing so a strictly convex objective whose gradients can be computed for a considerably cheaper computational cost using matrix scaling algorithms. We use these algorithms to visualize a large family of images and to solve a constrained clustering problem.