Sinkhorn Distances: Lightspeed Computation of Optimal Transport

Abstract. Optimal transportation distances are a fundamental family of pa-rameterized distances for histograms. Despite their appealing theoretical prop-erties, excellent performance in retrieval tasks and intuitive formulation, their computation involves the resolution of a linear program whose cost is prohibi-tive 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 com-puted through Sinkhorn-Knopp’s…