期刊
SIAM JOURNAL ON SCIENTIFIC COMPUTING
卷 43, 期 1, 页码 A193-A220出版社
SIAM PUBLICATIONS
DOI: 10.1137/18M1219813
关键词
multilevel algorithms; optimal transport; Wasserstein-1 distance; primal-dual algorithm
资金
- AFOSR MURI [FA9550-18-1-0502]
- ONR [N000141712162]
- NSF [DMS-1720237]
The paper proposes a fast algorithm for calculating the Wasserstein-1 distance, based on multilevel primal-dual algorithms, and demonstrates its computational speed through numerical examples and complexity analysis. The proposed algorithm provides solutions within 0.2 to 1.5 seconds on a single CPU for commonly used image examples of size 512 x 512, which is much faster than state-of-the-art algorithms.
We propose a fast algorithm for the calculation of the Wasserstein-1 distance, which is a particular type of optimal transport distance with transport cost homogeneous of degree one. Our algorithm is built on multilevel primal-dual algorithms. Several numerical examples and a complexity analysis are provided to demonstrate its computational speed. On some commonly used image examples of size 512 x 512, the proposed algorithm gives solutions within 0.2 similar to 1.5 seconds on a single CPU, which is much faster than the state-of-the-art algorithms.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据