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

arXiv: https://arxiv.org/abs/1810.00118 · HTML: https://mlsanity.com/paper/1810.00118/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2018.

## Built on by (most cited first, 4 of 4)

- [A scalable deep learning approach for solving high-dimensional dynamic optimal transport](https://mlsanity.com/paper/2205.07521/) (2022)
- [Accelerated nonlinear primal-dual hybrid gradient methods with applications to supervised machine learning](https://mlsanity.com/paper/2109.12222/) (2021)
- [HopTrack: A Real-time Multi-Object Tracking System for Embedded Devices](https://mlsanity.com/paper/2411.00608/) (2024)
- [Hierarchical topological clustering](https://mlsanity.com/paper/2601.00892/) (2025)

## Abstract (arXiv)

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.