  The Wasserstein metric is broadly used in optimal transport for comparing two
probabilistic distributions, with successful applications in various fields
such as machine learning, signal processing, seismic inversion, etc.
Nevertheless, the high computational complexity is an obstacle for its
practical applications. The Sinkhorn algorithm, one of the main methods in
computing the Wasserstein metric, solves an entropy regularized minimizing
problem, which allows arbitrary approximations to the Wasserstein metric with
O(N^2) computational cost. However, higher accuracy of its numerical
approximation requires more Sinkhorn iterations with repeated matrix-vector
multiplications, which is still unaffordable. In this work, we propose an
efficient implementation of the Sinkhorn algorithm to calculate the
Wasserstein-1 metric with O(N) computational cost, which achieves the optimal
theoretical complexity. By utilizing the special structure of Sinkhorn's
kernel, the repeated matrix-vector multiplications can be implemented with O(N)
times multiplications and additions, using the Qin Jiushao or Horner's method
for efficient polynomial evaluation, leading to an efficient algorithm without
losing accuracy. In addition, the log-domain stabilization technique, used to
stabilize the iterative procedure, can also be applied in this algorithm. Our
numerical experiments show that the newly developed algorithm is one to three
orders of magnitude faster than the original Sinkhorn algorithm.
