Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances

2013/06/04 by Marco Cuturi · 30 citations
Mathematics · #stat.ML

paper · pdf

published as Advances in Neural Information Processing Systems 26, pages 2292--2300, 2013

arxiv created 2013/06/04 · arxiv updated 2014/03/25

Abstract

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.

Cited by

• Do We Really Need Multimodal Emotion Language Models Larger Than 1B Parameters?
• Linear Independent Component Analysis via Optimal Transport
• A Standardized Framework For Evaluating Gene Expression Generative Models
• Joint Geometric-Chemical Distance for Protein Surfaces
• A data- and compute-efficient chest X-ray foundation model beyond aggressive scaling
• Schrödinger bridges with jumps for time series generation
• Improving Topic Modeling by Distilling Soft Labels from Language Models
• cuRegOT: A GPU-Accelerated Solver for Entropic-Regularized Optimal Transport
• Decision-centric fairness: Evaluation and optimization for resource allocation problems
• CellxPert: Inference-Time MCMC Steering of a Multi-Omics Single-Cell Foundation Model for In-Silico Perturbation
• Benchmarking virtual cell models for in-the-wild perturbation response
• Mesh Denoising
• Semantic-Aligned Learning with Collaborative Refinement for Unsupervised VI-ReID
• Entropic continuity bounds for conditional covariances with applications to Schr" odinger and Sinkhorn bridges
• ReLU integral probability metric and its applications
• MapPFN: Learning Causal Perturbation Maps in Context
• You Need Better Attention Priors
• Multi-Period Martingale Optimal Transport: Classical Theory, Neural Acceleration, and Financial Applications
• ATLAS: Learning to Recommend Across Unseen Domains
• One Knob to Rule Them All: A Unified Optimal Transport View of Cold-Start Active Learning
• Flow Matching Ergodic Coverage
• UG-UMRE: Uncertainty-Guided Modality Augmentation and Distributional Calibration for Unified Multimodal Relation Extraction
• Multimodal Alignment Through Joint Kernel Entropic Gromov--Wasserstein Optimal Transport
• Computing Optimal Transport Plans via Min-Max Gradient Flows
• Quantum Doubly Stochastic Transformers
• Moment Sum-of-Squares Hierarchy for Gromov Wasserstein: Continuous Extensions and Sample Complexity
• SG-Reg: Generalizable and Efficient Scene Graph Registration
• Teach Me How to Denoise: A Universal Framework for Denoising Multi-modal Recommender Systems via Guided Calibration
• MusFlow: Multimodal Music Generation via Conditional Flow Matching
• Convergence of the fully discrete JKO scheme

Related

• Online Sinkhorn: Optimal Transport distances from sample streams
• Faster Sinkhorn's Algorithm with Small Treewidth
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Regularized Optimal Transport and the Rot Mover's Distance
• Numerical Methods for Large-Scale Optimal Transport