  Computing the optimal transport distance between statistical distributions is
a fundamental task in machine learning. One remarkable recent advancement is
entropic regularization and the Sinkhorn algorithm, which utilizes only matrix
scaling and guarantees an approximated solution with near-linear runtime.
Despite the success of the Sinkhorn algorithm, its runtime may still be slow
due to the potentially large number of iterations needed for convergence. To
achieve possibly super-exponential convergence, we present
Sinkhorn-Newton-Sparse (SNS), an extension to the Sinkhorn algorithm, by
introducing early stopping for the matrix scaling steps and a second stage
featuring a Newton-type subroutine. Adopting the variational viewpoint that the
Sinkhorn algorithm maximizes a concave Lyapunov potential, we offer the insight
that the Hessian matrix of the potential function is approximately sparse.
Sparsification of the Hessian results in a fast $O(n^2)$ per-iteration
complexity, the same as the Sinkhorn algorithm. In terms of total iteration
count, we observe that the SNS algorithm converges orders of magnitude faster
across a wide range of practical cases, including optimal transportation
between empirical distributions and calculating the Wasserstein $W_1, W_2$
distance of discretized densities. The empirical performance is corroborated by
a rigorous bound on the approximate sparsity of the Hessian matrix.
