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

Jialin Liu, Wotao Yin, Wuchen Li, Yat Tin Chow

Submitted:

Overview

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 ground metric.

(Find an optimal transport between two densities rho0 and rho1.) 
(Find an optimal transport between two densities rho0 and rho1.)

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.

(Figure 1. Multilevel optimal flows (ground metric is p=1 norm)) 
(Figure 1. Multilevel optimal flows (ground metric is p=1 norm))
(Figure 2. Multilevel optimal dual variables (ground metric is p=1 norm)) 
(Figure 2. Multilevel optimal dual variables (ground metric is p=1 norm))

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

J. Liu, W. Yin, W. Li, Y.T. Chow, Multilevel optimal transport: a fast approximation of Wasserstein-1 distances, UCLA CAM Report 18-54, 2018.


« Back