Multilevel Optimal Transport: a Fast Approximation of Wasserstein-1 distances

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\times 512$, 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.

References in corpus (8)

• Learning with a Wasserstein Loss
• Optimal Transport with Proximal Splitting
• On the regularization of Wasserstein GANs
• A Sparse Multi-Scale Algorithm for Dense Optimal Transport
• An efficient linear programming method for Optimal Transportation
• DOTmark - A Benchmark for Discrete Optimal Transport
• On the Computation of Kantorovich-Wasserstein Distances between 2D-Histograms by Uncapacitated Minimum Cost Flows
• Semi-discrete optimal transport - the case p=1

Cited by in corpus (3)

• Tracking collective cell motion by topological data analysis
• Optimal Transport: Fast Probabilistic Approximation with Exact Solvers
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes