论文标题
加速sindhorn算法，以通过快速傅立叶变换稀疏的多核心最佳运输
Accelerating the Sinkhorn algorithm for sparse multi-marginal optimal transport by fast Fourier transforms
论文作者
论文摘要
我们考虑通过sindhorn算法的离散多 - 边界最佳运输（MOT）的数值解。通常，sndhorn算法相对于边缘数量，尺寸遭受了维数的诅咒。如果MOT成本函数根据树或圆形将其复杂性在边际测量的数量中是线性。在这种情况下，我们通过非均匀快速傅立叶方法在凹痕算法中所需的径向内核加快卷积。带有树结构成本功能的提议加速的沉没算法的每个步骤的复杂性为$ \ MATHCAL O（k n）$，而不是经典的$ \ Mathcal O（K n^2）$（k n^2）$用于直接矩阵矢量操作，其中$ k $是Marginals和Marginals量的数量，并且是$ n $ n $ n $ n $ n。如果圆形结构成本函数，复杂性从$ \ Mathcal O（k n^3）$转化为$ \ Mathcal O（k n^2）$。数值实验证实了这一点。
We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or circle, its complexity is linear in the number of marginal measures. In this case, we speed up the convolution with the radial kernel required in the Sinkhorn algorithm by non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of $\mathcal O(K N)$ instead of the classical $\mathcal O(K N^2)$ for straightforward matrix-vector operations, where $K$ is the number of marginals and each marginal measure is supported on at most $N$ points. In case of a circle-structured cost function, the complexity improves from $\mathcal O(K N^3)$ to $\mathcal O(K N^2)$. This is confirmed by numerical experiments.
