Sinkhorn Distances: Lightspeed Computation of Optimal Transport

TLDR

Optimal transport distances are fundamental for comparing probability measures and feature histograms, but their computation via linear programming becomes prohibitive when support size or dimensionality exceeds a few hundred. We propose a new family of optimal transport distances that view transport problems from a maximum‑entropy perspective. By adding an entropic regularization term, the optimal transport problem becomes a distance computable via Sinkhorn’s matrix‑scaling algorithm, yielding several orders of magnitude speedup over traditional solvers. On MNIST classification, the regularized distance outperforms classic optimal transport distances.

Abstract

Optimal transport distances are a fundamental family of distances for probability measures and histograms of features. Despite their appealing theoretical properties, excellent performance in retrieval tasks and intuitive formulation, their computation involves the resolution of a linear program whose cost can quickly become prohibitive whenever the size of the support of these measures or the histograms' dimension exceeds a few hundred. We propose in this work a new family of optimal transport distances that look at transport problems from a maximum-entropy perspective. We smooth the classic optimal transport problem with an entropic regularization term, and show that the resulting optimum is also a distance which can be computed through Sinkhorn's matrix scaling algorithm at a speed that is several orders of magnitude faster than that of transport solvers. We also show that this regularized distance improves upon classic optimal transport distances on the MNIST classification problem.