2022/06/17 by Qichen Liao, Zihao Wang, Liao, Qichen +9 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #49M25 #65K10 #Advanced Optimization Algorithms Research #Electromagnetic Scattering and Analysis #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2206.09049
openalex publication_date 2022/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In our previous work [arXiv:2202.10042], the complexity of Sinkhorn iteration is reduced from O(N2) 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.