## Multilevel Optimal Transport: a Fast Approximation of Wasserstein-1 distancesJialin Liu, Wotao Yin, Wuchen Li, Yat Tin Chow Submitted: ## OverviewWe 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 ground metric.
Our algorithm is built on multilevel primal-dual algorithms. Coarser levels are easier to compute and their solutions are great initial solutions to the next finer levels.
Several numerical examples and 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.5 seconds on a single CPU, which is much faster than the state-of-the-art algorithms. ## Citation
« Back |