# Multiscale Strategies for Computing Optimal Transport

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

## Key facts

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

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

- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (2021)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Large-scale optimal transport map estimation using projection pursuit](https://mlsanity.com/paper/2106.05838/) (2021)
- [Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning](https://mlsanity.com/paper/2204.06645/) (2022)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples](https://mlsanity.com/paper/2103.00394/) (2021)
- [Applications of No-Collision Transportation Maps in Manifold Learning](https://mlsanity.com/paper/2304.00199/) (2023)
- [Improving Approximate Optimal Transport Distances using Quantization](https://mlsanity.com/paper/2102.12731/) (2021)
- [Efficient Transferable Optimal Transport via Min-Sliced Transport Plans](https://mlsanity.com/paper/2511.19741/) (2025)
- [Efficient Optimal Transport Algorithm by Accelerated Gradient descent](https://mlsanity.com/paper/2104.05802/) (2021)
- [Optimal Transport Features for Morphometric Population Analysis](https://mlsanity.com/paper/2208.05891/) (2022)
- [Quantization-based Bounds on the Wasserstein Metric](https://mlsanity.com/paper/2506.00976/) (2025)
- [Fast Log-Domain Sinkhorn Optimal Transport with Warp-Level GPU Reductions](https://mlsanity.com/paper/2605.00837/) (2026)
- [Multiscale Supervised Unbalanced Optimal Transport Flow Matching](https://mlsanity.com/paper/2605.16529/) (2026)
- [Representations from Pretrained Machine-Learning Interatomic Potentials as Coarse Coordinates for Material Generation and Evaluation](https://mlsanity.com/paper/2607.28776/) (2026)
- [Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions](https://mlsanity.com/paper/2609.13010/) (2026)
- [FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport](https://mlsanity.com/paper/2610.02395/) (2026)

## Abstract (arXiv)

This paper presents a multiscale approach to efficiently compute approximate optimal transport plans between point sets. It is particularly well-suited for point sets that are in high-dimensions, but are close to being intrinsically low-dimensional. The approach is based on an adaptive multiscale decomposition of the point sets. The multiscale decomposition yields a sequence of optimal transport problems, that are solved in a top-to-bottom fashion from the coarsest to the finest scale. We provide numerical evidence that this multiscale approach scales approximately linearly, in time and memory, in the number of nodes, instead of quadratically or worse for a direct solution. Empirically, the multiscale approach results in less than one percent relative error in the objective function. Furthermore, the multiscale plans constructed are of interest by themselves as they may be used to introduce novel features and notions of distances between point sets. An analysis of sets of brain MRI based on optimal transport distances illustrates the effectiveness of the proposed method on a real world data set. The application demonstrates that multiscale optimal transport distances have the potential to improve on state-of-the-art metrics currently used in computational anatomy.