论文标题
快速sindhorn II：共线三角矩阵和线性时间准确计算最佳运输
Fast Sinkhorn II: Collinear Triangular Matrix and Linear Time Accurate Computation of Optimal Transport
论文作者
论文摘要
在我们以前的工作[Arxiv：2202.10042]中，通过利用核心矩阵的特殊结构，将Sink Horn迭代的复杂性从$ O（N^2）$降低到最佳$ O（N）$。在本文中，我们通过定义和利用下部三角形矩阵（L-Colt矩阵）和上电线三角矩阵（U-Colt矩阵）的特性来探讨内核矩阵的特殊结构。我们证明（1）l/u-colt矩阵向量乘法可以在$ o（n）$ aperations中进行； （2）在Hadamard产品和基质缩放下，两个矩阵系列都关闭。这些属性有助于减轻降低不精确的近端方法（IPOT）复杂性的两个关键困难，并使我们能够将迭代次数显着减少到$ O（n）$。这产生了快速sndhorn II（FS-2）算法，以精确计算具有低算法复杂性和快速收敛性的最佳运输。提出了数值实验，以显示我们方法的有效性和效率。
In our previous work [arXiv:2202.10042], the complexity of Sinkhorn iteration is reduced from $O(N^2)$ to the optimal $O(N)$ by leveraging the special structure of the kernel matrix. In this paper, we explore the special structure of kernel matrices by defining and utilizing the properties of the Lower-ColLinear Triangular Matrix (L-CoLT matrix) and Upper-ColLinear Triangular Matrix (U-CoLT matrix). We prove that (1) L/U-CoLT matrix-vector multiplications can be carried out in $O(N)$ operations; (2) both families of matrices are closed under the Hadamard product and matrix scaling. These properties help to alleviate two key difficulties for reducing the complexity of the Inexact Proximal point method (IPOT), and allow us to significantly reduce the number of iterations to $O(N)$. This yields the Fast Sinkhorn II (FS-2) algorithm for accurate computation of optimal transport with low algorithm complexity and fast convergence. Numerical experiments are presented to show the effectiveness and efficiency of our approach.
