# Quantization-based Bounds on the Wasserstein Metric

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 37 references that are in the map.
- First posted on arXiv 1 Jun 2025.

## Builds on (most cited first, 16 of 16)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Geometric Dataset Distances via Optimal Transport](https://mlsanity.com/paper/2002.02923/) (2020)
- [Generative Modeling using the Sliced Wasserstein Distance](https://mlsanity.com/paper/1803.11188/) (2018)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019)
- [Multiscale Strategies for Computing Optimal Transport](https://mlsanity.com/paper/1708.02469/) (2017)
- [DOTmark - A Benchmark for Discrete Optimal Transport](https://mlsanity.com/paper/1610.03368/) (2016)
- [Fast and Scalable Optimal Transport for Brain Tractograms](https://mlsanity.com/paper/2107.02010/) (2021)
- [Manifold learning with arbitrary norms](https://mlsanity.com/paper/2012.14172/) (2020)
- [Alignment of Density Maps in Wasserstein Distance](https://mlsanity.com/paper/2305.12310/) (2023)
- [AlignOT: An optimal transport based algorithm for fast 3D alignment with applications to cryogenic electron microscopy density maps](https://mlsanity.com/paper/2210.09361/) (2022)
- [Wasserstein K-Means for Clustering Tomographic Projections](https://mlsanity.com/paper/2010.09989/) (2020)
- [Improving Approximate Optimal Transport Distances using Quantization](https://mlsanity.com/paper/2102.12731/) (2021)

## Abstract (arXiv)

The Wasserstein metric has become increasingly important in many machine learning applications such as generative modeling, image retrieval and domain adaptation. Despite its appeal, it is often too costly to compute. This has motivated approximation methods like entropy-regularized optimal transport, downsampling, and subsampling, which trade accuracy for computational efficiency. In this paper, we consider the challenge of computing efficient approximations to the Wasserstein metric that also serve as strict upper or lower bounds. Focusing on discrete measures on regular grids, our approach involves formulating and exactly solving a Kantorovich problem on a coarse grid using a quantized measure and specially designed cost matrix, followed by an upscaling and correction stage. This is done either in the primal or dual space to obtain valid upper and lower bounds on the Wasserstein metric of the full-resolution inputs. We evaluate our methods on the DOTmark optimal transport images benchmark, demonstrating a 10x-100x speedup compared to entropy-regularized OT while keeping the approximation error below 2%.