Computing the quadratic transportation metric (also called the
$2$-Wasserstein distance or root mean square distance) between two point
clouds, or, more generally, two discrete distributions, is a fundamental
problem in machine learning, statistics, computer graphics, and theoretical
computer science. A long line of work has culminated in a sophisticated
geometric algorithm due to Agarwal and Sharathkumar in 2014, which runs in time
$\tilde{O}(n^{3/2})$, where $n$ is the number of points. However, obtaining
faster algorithms has proven difficult since the $2$-Wasserstein distance is
known to have poor sketching and embedding properties, which limits the
effectiveness of geometric approaches. In this paper, we give an extremely
simple deterministic algorithm with $\tilde{O}(n)$ runtime by using a
completely different approach based on entropic regularization, approximate
Sinkhorn scaling, and low-rank approximations of Gaussian kernel matrices. We
give explicit dependence of our algorithm on the dimension and precision of the
approximation.

该研究提出了一种基于熵正则化、近似 Sinkhorn 缩放和高斯核矩阵低秩逼近的算法，用于计算两个点云或离散分布之间的二次输运度量（也称为 2-Wasserstein 距离或均方根距离），其复杂度为 O (n)。