# A Sparse Multi-Scale Algorithm for Dense Optimal Transport

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2015.

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

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Expected Sliced Transport Plans](https://mlsanity.com/paper/2410.12176/) (2024)
- [Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning](https://mlsanity.com/paper/2204.06645/) (2022)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [Shedding a PAC-Bayesian Light on Adaptive Sliced-Wasserstein Distances](https://mlsanity.com/paper/2206.03230/) (2022)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [Applications of No-Collision Transportation Maps in Manifold Learning](https://mlsanity.com/paper/2304.00199/) (2023)
- [Set Representation Learning with Generalized Sliced-Wasserstein Embeddings](https://mlsanity.com/paper/2103.03892/) (2021)
- [Neural approximation of Wasserstein distance via a universal architecture for symmetric and factorwise group invariant functions](https://mlsanity.com/paper/2308.00273/) (2023)
- [Efficient Transferable Optimal Transport via Min-Sliced Transport Plans](https://mlsanity.com/paper/2511.19741/) (2025)
- [Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems](https://mlsanity.com/paper/2103.12624/) (2021)
- [Learning Ultrametric Trees for Optimal Transport Regression](https://mlsanity.com/paper/2210.12288/) (2022)
- [New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning](https://mlsanity.com/paper/2207.09588/) (2022)
- [Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions](https://mlsanity.com/paper/2609.13010/) (2026)
- [UltraMatch: Transport Path Routing for Ultra-Fast and Memory-Efficient Image Matching](https://mlsanity.com/paper/2609.36980/) (2026)
- [FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport](https://mlsanity.com/paper/2610.02395/) (2026)
- [Exact Optimal Transport by Matching](https://mlsanity.com/paper/2610.04085/) (2026)

## Abstract (arXiv)

Discrete optimal transport solvers do not scale well on dense large problems since they do not explicitly exploit the geometric structure of the cost function. In analogy to continuous optimal transport we provide a framework to verify global optimality of a discrete transport plan locally. This allows construction of an algorithm to solve large dense problems by considering a sequence of sparse problems instead. The algorithm lends itself to being combined with a hierarchical multi-scale scheme. Any existing discrete solver can be used as internal black-box.Several cost functions, including the noisy squared Euclidean distance, are explicitly detailed. We observe a significant reduction of run-time and memory requirements.