# Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances

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

## Key facts

- Cited by 2,316 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2013.

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

- [Emerging Properties in Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.14294/) (2021)
- [VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning](https://mlsanity.com/paper/2105.04906/) (2021)
- [Improving and generalizing flow-based generative models with minibatch optimal transport](https://mlsanity.com/paper/2302.00482/) (2023)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [MusicLM: Generating Music From Text](https://mlsanity.com/paper/2301.11325/) (2023)
- [Multisample Flow Matching: Straightening Flows with Minibatch Couplings](https://mlsanity.com/paper/2304.14772/) (2023)
- [Unified Scaling Laws for Routed Language Models](https://mlsanity.com/paper/2202.01169/) (2022)
- [A Large-Scale Study on Unsupervised Spatiotemporal Representation Learning](https://mlsanity.com/paper/2104.14558/) (2021)
- [Dual Diffusion Implicit Bridges for Image-to-Image Translation](https://mlsanity.com/paper/2203.08382/) (2022)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Word Alignment by Fine-tuning Embeddings on Parallel Corpora](https://mlsanity.com/paper/2101.08231/) (2021)
- [Reinforcement Learning with Prototypical Representations](https://mlsanity.com/paper/2102.11271/) (2021)
- [OTA: Optimal Transport Assignment for Object Detection](https://mlsanity.com/paper/2103.14259/) (2021)
- [A Unified Objective for Novel Class Discovery](https://mlsanity.com/paper/2108.08536/) (2021)
- [Multi-Granularity Cross-modal Alignment for Generalized Medical Visual Representation Learning](https://mlsanity.com/paper/2210.06044/) (2022)
- [Diffusion Schr"odinger Bridge Matching](https://mlsanity.com/paper/2303.16852/) (2023)
- [CoFiNet: Reliable Coarse-to-fine Correspondences for Robust Point Cloud Registration](https://mlsanity.com/paper/2110.14076/) (2021)
- [Optimal Transport Aggregation for Visual Place Recognition](https://mlsanity.com/paper/2311.15937/) (2023)
- [Efficient Self-supervised Vision Transformers for Representation Learning](https://mlsanity.com/paper/2106.09785/) (2021)
- [An optimal control perspective on diffusion-based generative modeling](https://mlsanity.com/paper/2211.01364/) (2022)
- [Fine-Tuning of Continuous-Time Diffusion Models as Entropy-Regularized Control](https://mlsanity.com/paper/2402.15194/) (2024)
- [Solving Schr"odinger Bridges via Maximum Likelihood](https://mlsanity.com/paper/2106.02081/) (2021)
- [Rethinking Semantic Segmentation: A Prototype View](https://mlsanity.com/paper/2203.15102/) (2022)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [Contrastive Masked Autoencoders are Stronger Vision Learners](https://mlsanity.com/paper/2207.13532/) (2022)
- [Learning Target Candidate Association to Keep Track of What Not to Track](https://mlsanity.com/paper/2103.16556/) (2021)
- [QuadTree Attention for Vision Transformers](https://mlsanity.com/paper/2201.02767/) (2022)
- [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023)
- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Equivariance with Learned Canonicalization Functions](https://mlsanity.com/paper/2211.06489/) (2022)

## Abstract (arXiv)

Optimal transportation distances are a fundamental family of parameterized distances for histograms. Despite their appealing theoretical properties, excellent performance in retrieval tasks and intuitive formulation, their computation involves the resolution of a linear program whose cost is prohibitive whenever the histograms' dimension exceeds a few hundreds. We propose in this work a new family of optimal transportation distances that look at transportation problems from a maximum-entropy perspective. We smooth the classical optimal transportation problem with an entropic regularization term, and show that the resulting optimum is also a distance which can be computed through Sinkhorn-Knopp's matrix scaling algorithm at a speed that is several orders of magnitude faster than that of transportation solvers. We also report improved performance over classical optimal transportation distances on the MNIST benchmark problem.