Sinkhorn Distances: Lightspeed Computation of Optimal Transport

By Marco Cuturi. 2013

5,608 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Mathematical Optimization, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

  1. Medhi Bennis
  2. Jihong Park
  3. Francis R. Bach
  4. Martin Jaggi
  5. Sebastian U. Stich
  6. David A. Sontag
  7. Merouane Debbah
  8. Simon Lacoste-Julien

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Dacheng Tao
  3. Trevor Darrell
  4. Xiaogang Wang
  5. Ming-Hsuan Yang
  6. Jitendra Malik
  7. Andrew Zisserman
  8. Andrea Vedaldi

In Mathematical Optimization

  1. Mohammad Rostami
  2. Soheil Kolouri
  3. Martin Jaggi
  4. Simon Lacoste-Julien
  5. G. Peyr'e
  6. François-Pierre Paty
  7. De-chuan Zhan
  8. Han-Jia Ye

In Signal Processing

  1. Yoshua Bengio
  2. Bernhard Schölkopf
  3. Kyunghyun Cho
  4. Dong Yu
  5. Ruslan Salakhutdinov
  6. Neil Zeghidour
  7. Jesse Engel
  8. Li Deng

Citations in the corpus