Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances

Code

• github.com/thinklab-sjtu/linsatnet
  pytorch★ 82
• github.com/ryanwebster90/OT-texture-synthesis
  none★ 1
• github.com/IntelLabs/Optimized-Implementation-of-Word-Movers-Distance
  none★ 1
• github.com/fwilliams/fml
  pytorch★ 0
• github.com/yrobink/SBCK
  none★ 0
• github.com/locuslab/projected_sinkhorn
  pytorch★ 0
• github.com/nicolasbolle/barycenters
  tf★ 0
• github.com/fwilliams/point-cloud-utils
  none★ 0
• github.com/Godofnothing/optimal_transport_problem
  pytorch★ 0
• github.com/BenoitTran/END
  none★ 0

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.

Tasks

Reproductions