Sinkhorn Distances: Lightspeed Computation of Optimal Transport
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 maximumentropy 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.
The paper studies variants of the Earth Mover's 
      distance (EMD) with either a constraint on the entropy or a penalty term 
      in the objective linear in the entropy. When there is a bound on the 
      entropy, the objective turns out to be a distance metric but the paper 
      does not show how to compute it efficiently. The other variant is not a 
      distance metric but the paper shows that the optimal transportation is the 
      unique stochastic matrix obtained by scaling rows and columns of the 
      matrix with entries exp(-lambda*m_{i,j}) where m_{i,j} is the 
      distance/transportation cost between i and j and lambda is the coefficient 
      of the entropy term in the objective. This stochastic matrix can be 
      approximated by Sinkhorn-Knopp's algorithm. The paper makes an interesting 
      observation about a variant of EMD that might be efficiently approximated. 
      However, the comparison with EMD in the paper is not fair, since the 
      authors insist on EMD being computed exactly while the variant being 
      studied is only approximated without any statement on the convergence rate 
      of the algorithm. It is conceivable that for the random vectors tested in 
      the paper, the algorithm converges quickly but it might be slow for 
      pathological vectors. It is also not clear if comparing with EMD on just 
      the original pixel space is the right comparison when the previous work 
      cited by the paper computed EMD in the gradient orientation histograms 
      (SIFT features) as well as the pixel space. The authors might also want to 
      compare the results with previous work using variants/approximations of 
      EMD such as Kristen Grauman, Trevor Darrell. Approximate 
      Correspondences in High Dimensions. NIPS 2006. The pyramid match 
      approach above is inspired by ideas from work on approximating EMD e.g. 
      Indyk, P., and Thaper, N. 2003. Fast Image Retrieval via Embeddings. 
      The paper is generally well written but the authors might want to 
      include a statement of the Sinkhorn-Knopp's theorem, a description of the 
      algorithm using formula rather than Matlab code, and some statement on the 
      convergence rate of the algorithm. ============================ 
      Rebuttal comments: there are many ways to speed up EMD 
      computation, one such approach is to use coarser distances as taken by 
      Pele and Werman already cited in the paper (round so that distances can 
      only be 1,2,3). I am not sure if there are publicly available 
      implementations taking advantage of the small weight range even though 
      this is an area with a lot of theoretical results such as Gabow, 
      Harold N., and Robert E. Tarjan. "Faster scaling algorithms for network 
      problems." SIAM Journal on Computing 18.5 (1989): 1013-1036. It 
      would be interesting to compare to that approach in terms of speed and 
      retrieval accuracy.