# Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration

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

## Key facts

- Cited by 223 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2017.

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

- [Multisample Flow Matching: Straightening Flows with Minibatch Couplings](https://mlsanity.com/paper/2304.14772/) (2023)
- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Simulation-free Schr"odinger bridges via score and flow matching](https://mlsanity.com/paper/2307.03672/) (2023)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (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)
- [Understanding DDPM Latent Codes Through Optimal Transport](https://mlsanity.com/paper/2202.07477/) (2022)
- [Improving Mini-batch Optimal Transport via Partial Transportation](https://mlsanity.com/paper/2108.09645/) (2021)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Neural Monge Map estimation and its applications](https://mlsanity.com/paper/2106.03812/) (2021)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Debias Coarsely, Sample Conditionally: Statistical Downscaling through Optimal Transport and Probabilistic Diffusion Models](https://mlsanity.com/paper/2305.15618/) (2023)
- [Sinkhorn Label Allocation: Semi-Supervised Classification via Annealed Self-Training](https://mlsanity.com/paper/2102.08622/) (2021)
- [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021)
- [Optimal Transport for Treatment Effect Estimation](https://mlsanity.com/paper/2310.18286/) (2023)
- [Transformed Distribution Matching for Missing Value Imputation](https://mlsanity.com/paper/2302.10363/) (2023)
- [Trajectory Inference via Mean-field Langevin in Path Space](https://mlsanity.com/paper/2205.07146/) (2022)
- [Meta Optimal Transport](https://mlsanity.com/paper/2206.05262/) (2022)
- [PTaRL: Prototype-based Tabular Representation Learning via Space Calibration](https://mlsanity.com/paper/2407.05364/) (2024)
- [Wasserstein Flow Matching: Generative modeling over families of distributions](https://mlsanity.com/paper/2411.00698/) (2024)
- [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)
- [Towards Compositional Adversarial Robustness: Generalizing Adversarial Training to Composite Semantic Perturbations](https://mlsanity.com/paper/2202.04235/) (2022)
- [Revisiting Sliced Wasserstein on Images: From Vectorization to Convolution](https://mlsanity.com/paper/2204.01188/) (2022)
- [Wasserstein Task Embedding for Measuring Task Similarities](https://mlsanity.com/paper/2208.11726/) (2022)
- [Domain Adaptation for Time-Series Classification to Mitigate Covariate Shift](https://mlsanity.com/paper/2204.03342/) (2022)
- [Hierarchical Sliced Wasserstein Distance](https://mlsanity.com/paper/2209.13570/) (2022)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)

## Abstract (arXiv)

Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi's Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iteration, which also directly suggests a new greedy coordinate descent algorithm, Greenkhorn, with the same theoretical guarantees. Numerical simulations illustrate that Greenkhorn significantly outperforms the classical Sinkhorn algorithm in practice.