2018/09/29 by Jialin Liu, Liu, Jialin, Wotao Yin +5 · 1 citation
Mathematics · Medicine · #Geometric Analysis and Curvature Flows #Markov Chains and Monte Carlo Methods #Advanced Neuroimaging Techniques and Applications
paper · pdf · doi:10.48550/arxiv.1810.00118
We propose a fast algorithm for the calculation of the Wasserstein-1 distance, which is a particular type of optimal transport distance with homogeneous of degree one transport cost. 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×512, the proposed algorithm gives solutions within 0.2∼ 1.5 seconds on a single CPU, which is much faster than the state-of-the-art algorithms.