We propose a simple subsampling scheme for fast randomized approximate
computation of optimal transport distances. This scheme operates on a random
subset of the full data and can use any exact algorithm as a black-box
back-end, including state-of-the-art solvers and entropically penalized
versions. It is based on averaging the exact distances between empirical
measures generated from independent samples from the original measures and can
easily be tuned towards higher accuracy or shorter computation times. To this
end, we give non-asymptotic deviation bounds for its accuracy in the case of
discrete optimal transport problems. In particular, we show that in many
important instances, including images (2D-histograms), the approximation error
is independent of the size of the full problem. We present numerical
experiments that demonstrate that a very good approximation in typical
applications can be obtained in a computation time that is several orders of
magnitude smaller than what is required for exact computation of the full
problem.

本文提出了一个基于离散最优输运问题的简单子抽样方案，用于快速随机近似计算最优输运距离。该方案针对完全数据的随机子集操作，可使用任何精确算法作为黑盒后端，包括最先进的求解器和熵惩罚版本。我们给出了其非渐进偏差范围，以针对更高的精度或更短的计算时间进行简化。实验证明，该子抽样方案可以在计算时间大大降低的情况下，获得比精确方法更好的近似效果。