  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.
