A Parallel Method for Earth Mover’s Distance
A Parallel Method for Earth Mover’s Distance
复制标题
DOI：
10.1007/s10915-017-0529-1
复制
发表时间：
2018-04
影响因子：
2.5
通讯作者：
Wuchen Li;Ernest K. Ryu;S. Osher;W. Yin;W. Gangbo
中科院分区：
文献类型：
--
作者：
Wuchen Li;Ernest K. Ryu;S. Osher;W. Yin;W. Gangbo
我们提出了一种新的算法来近似地球移动器的距离（EMD）。我们的主要思想是由最优运输理论，其中EMD可以重新制定为一个familiartype最小化的动机。我们使用正则化，它为我们提供了这种类型问题的唯一解决方案。新的正则化的最小化是非常类似的问题，已经解决了在压缩传感和图像处理领域，其中有几个快速的方法。在本文中，我们采用了原-对偶算法设计有，它使用非常简单的更新，在每次迭代，收敛速度非常快。提供了几个数值例子。
We propose a new algorithm to approximate the Earth Mover’s distance (EMD). Our main idea is motivated by the theory of optimal transport, in which EMD can be reformulated as a familiartype minimization. We use a regularization which gives us a unique solution for thistype problem. The new regularized minimization is very similar to problems which have been solved in the fields of compressed sensing and image processing, where several fast methods are available. In this paper, we adopt a primal-dual algorithm designed there, which uses very simple updates at each iteration and is shown to converge very rapidly. Several numerical examples are provided.