Details

Autor(en) / Beteiligte

• Liao, Qichen
• Wang, Zihao
• Chen, Jing
• Bai, Bo
• Jin, Shi
• Wu, Hao

Titel

Fast Sinkhorn II: Collinear Triangular Matrix and Linear Time Accurate Computation of Optimal Transport

Ist Teil von

• Journal of scientific computing, 2024, Vol.98 (1), p.1, Article 1

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2024

Link zum Volltext

Quelle

SpringerLink (Online service)

Beschreibungen/Notizen

• In our previous work (Liao et al. in Commun Math Sci, 2022), 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.