Multilevel Optimal Transport: a Fast Approximation of Wasserstein-1 distances
arXiv:1810.00118
The paper introduces a multilevel primal‑dual algorithm that rapidly approximates the Wasserstein‑1 distance, achieving solutions for 512×512 images in under a few seconds on a single CPU.
Abstract
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\times512$, the proposed algorithm gives solutions within $0.2\sim 1.5$ seconds on a single CPU, which is much faster than the state-of-the-art algorithms.