Sinkhorn Distances and Entropic Regularized Optimal Transport

Sinkhorn Distances and Entropic Regularized Optimal Transport is a scalable optimal transport framework introduced by Cuturi (2013) that replaces the unregularized O(d^3 log d) network-simplex linear program d_M(r, c) = min_{P in U(r, c)} <P, M> over the transport polytope U(r, c) = {P in R_+^{d x d} : P 1_d = r, P^T 1_d = c} with the strictly convex entropic-regularized Dual-Sinkhorn problem d_M^lambda(r, c) = <P^lambda, M> where P^lambda = argmin_{P in U(r, c)} {<P, M> - (1/lambda) h(P)} and h(P) = -sum_{i,j} P_{ij} log P_{ij} is the Shannon entropy (Equations 2-3). By strict convexity and KKT optimality (Lemma 2), the unique optimal coupling has the diagonal-scaling form P^lambda = diag(u) K diag(v) of the Gibbs kernel K_{ij} = exp(-lambda M_{ij}), which is computed at linear convergence rate via the Sinkhorn-Knopp alternating row- and column-normalization iteration u <- r ./ (K v), v <- c ./ (K^T u) using vectorized matrix-vector multiplications in O(d^2) operations per iteration (Algorithm 1).