Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 5 Pith papers
-
Notes on Wasserstein distance and wormholes
Defines Boltzmann-Wasserstein distance on quantum theories via optimal W2 transport of Boltzmann-weighted spectra, equates it to thermal correlators, and constructs a Schwinger-Keldysh wormhole saddle that reproduces ...
-
Hausdorff and Wasserstein metrics on graphs and other structured data
Defines Hausdorff-style and Wasserstein-style metrics on C-sets, proving the latter are convex relaxations of the former and computable as linear programs.
-
pop-cosmos: Disentangling galaxy properties from observables using data-driven approaches
A beta-VAE analysis of pop-cosmos models finds that five latent dimensions capture the rest-frame optical SED, corresponding to stellar mass, recent star formation, dust, and two gas ionization states.
-
AURA: Adaptive Uncertainty-aware Refinement for LLM-as-a-Judge Auditing
AURA is an adaptive uncertainty-aware refinement method for auditing LLM-as-a-judge pairwise decisions that learns human-consistency signals through selective human verification on uncertain cases.
-
A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits
Applies optimal transport to bound OOD generalization error in Transformers via Lipschitz continuity and TC^0 circuit depth lower bounds for Dyck-k backtracking, supported by evaluations on 54 configurations.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.