# Massively scalable Sinkhorn distances via the Nystr"om method

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2018.

## Built on by (most cited first, 30 of 41)

- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Differentiable Particle Filtering via Entropy-Regularized Optimal Transport](https://mlsanity.com/paper/2102.07850/) (2021)
- [Low Budget Active Learning via Wasserstein Distance: An Integer Programming Approach](https://mlsanity.com/paper/2106.02968/) (2021)
- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [PSD Representations for Effective Probability Models](https://mlsanity.com/paper/2106.16116/) (2021)
- [Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning](https://mlsanity.com/paper/2204.06645/) (2022)
- [Rethinking Initialization of the Sinkhorn Algorithm](https://mlsanity.com/paper/2206.07630/) (2022)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [Deep Networks Provably Classify Data on Curves](https://mlsanity.com/paper/2107.14324/) (2021)
- [Applications of No-Collision Transportation Maps in Manifold Learning](https://mlsanity.com/paper/2304.00199/) (2023)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [Kernel approximation on algebraic varieties](https://mlsanity.com/paper/2106.02755/) (2021)
- [Order Constraints in Optimal Transport](https://mlsanity.com/paper/2110.07275/) (2021)
- [Approximating Optimal Transport via Low-rank and Sparse Factorization](https://mlsanity.com/paper/2111.06546/) (2021)
- [Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR](https://mlsanity.com/paper/2111.11550/) (2021)
- [Provably Efficient Kernelized Q-Learning](https://mlsanity.com/paper/2204.10349/) (2022)
- [Gromov-Wasserstein-like Distances in the Gaussian Mixture Models Space](https://mlsanity.com/paper/2310.11256/) (2023)
- [Geometric Sparse Coding in Wasserstein Space](https://mlsanity.com/paper/2210.12135/) (2022)
- [A Sinkhorn-type Algorithm for Constrained Optimal Transport](https://mlsanity.com/paper/2403.05054/) (2024)
- [Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimization](https://mlsanity.com/paper/2503.22923/) (2025)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [Structured Prediction in Online Learning](https://mlsanity.com/paper/2406.12366/) (2024)

## Abstract (arXiv)

The Sinkhorn "distance", a variant of the Wasserstein distance with entropic regularization, is an increasingly popular tool in machine learning and statistical inference. However, the time and memory requirements of standard algorithms for computing this distance grow quadratically with the size of the data, making them prohibitively expensive on massive data sets. In this work, we show that this challenge is surprisingly easy to circumvent: combining two simple techniques---the Nystr"om method and Sinkhorn scaling---provably yields an accurate approximation of the Sinkhorn distance with significantly lower time and memory requirements than other approaches. We prove our results via new, explicit analyses of the Nystr"om method and of the stability properties of Sinkhorn scaling. We validate our claims experimentally by showing that our approach easily computes Sinkhorn distances on data sets hundreds of times larger than can be handled by other techniques.