论文标题
无需为Sinkhorn算法提供快速傅立叶变换增强
Nonequispaced Fast Fourier Transform Boost for the Sinkhorn Algorithm
论文作者
论文摘要
这项贡献具有对Sinkhorn算法的加速计算，该算法通过使用无需使用的快速傅立叶变换（NFFT）来近似于Wasserstein的运输距离。提出的算法允许通过不超过$ \ MATHCAL O（N \ log n）$操作来近似Wasserstein距离，以提供〜$ n $点支持的概率度量。此外，提出的方法避免了表征矩阵的昂贵分配。通过这种数值加速度，到目前为止，无法实现的概率度量可以达到运输距离。使用合成和真实数据的数值实验肯定了计算优势和优越性。
This contribution features an accelerated computation of the Sinkhorn's algorithm, which approximates the Wasserstein transportation distance, by employing nonequispaced fast Fourier transforms (NFFT). The algorithm proposed allows approximations of the Wasserstein distance by involving not more than $\mathcal O(n\log n)$ operations for probability measures supported by~$n$ points. Furthermore, the proposed method avoids expensive allocations of the characterizing matrices. With this numerical acceleration, the transportation distance is accessible to probability measures out of reach so far. Numerical experiments using synthetic and real data affirm the computational advantage and superiority.
