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

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

TL;DR

This paper introduces "Fast Sinkhorn II" (FS-2), an algorithm that significantly speeds up the computation of optimal transport (OT) distances. By leveraging a novel matrix structure called "Collinear Triangular Matrices" (COLT), FS-2 achieves linear (O(N)) time complexity for OT calculations, a substantial improvement over existing methods, enabling more efficient analysis of complex data distributions.

What Problem Does This Paper Address?

Optimal Transport (OT) is a powerful framework for comparing probability distributions, with applications spanning machine learning, computer vision, and physics. A key challenge in OT is efficiently computing the Wasserstein distance, especially for high-dimensional data. While the Sinkhorn algorithm offers an approximation, it can be slow and numerically unstable for accurate OT solutions. Previous work (Fast Sinkhorn I) reduced the complexity of the Sinkhorn algorithm to (O(N)) by exploiting the structure of the kernel matrix for the Wasserstein-1 metric. However, applying this to more robust methods like the Inexact Proximal Point method (IPOT), which provides accurate OT solutions, remained difficult due to the (O(N^2)) complexity of essential matrix operations (Hadamard product and scaling) within IPOT. This paper aims to bridge this gap by developing an (O(N)) algorithm for accurate OT computation using IPOT.

Methods

The core innovation of this paper lies in the introduction and utilization of Collinear Triangular Matrices (COLT), specifically Lower-ColLinear Triangular (L-COLT) and Upper-ColLinear Triangular (U-COLT) matrices. The authors demonstrate that:

  • Efficient Matrix Operations: L/U-COLT matrix-vector multiplications can be performed in (O(N)) time, a significant speedup from the standard (O(N^2)). This is achieved by representing these matrices with just two vectors and using dynamic programming-like recurrences.
  • Closure Properties: Crucially, L/U-COLT matrices are shown to be closed under the Hadamard product and matrix scaling. This means that intermediate matrices generated during the IPOT algorithm, which involve these operations, also retain the COLT structure.
  • Representation: Any L/U-COLT matrix can be uniquely represented by its diagonal elements and a "ratio vector," reducing the memory footprint from (O(N^2)) to (O(N)).

These properties allow the authors to adapt the Inexact Proximal Point method (IPOT) to achieve (O(N)) complexity. The Fast Sinkhorn II (FS-2) algorithm integrates these COLT-based optimizations into the IPOT framework, enabling fast and accurate computation of the Wasserstein-1 metric. The paper also extends these concepts to block matrices for handling higher dimensions.

Datasets

Not discussed in the paper. The paper uses synthetic distributions (Gaussian, uniform) and image data for evaluation.

Key Insights and Ideas

  • COLT Matrices as a Key Structure: The identification and exploitation of L/U-COLT matrices is the central insight. Their specific structure allows for dramatic speedups in matrix operations that are bottlenecks in existing OT algorithms.
  • Bridging Accuracy and Speed: FS-2 successfully combines the accuracy of IPOT with the speed of Sinkhorn-like algorithms by making IPOT's core operations efficient. This is a significant step towards practical, high-accuracy OT computations.
  • (O(N)) Representation: Representing complex matrices with just a few vectors is a powerful technique for reducing both computational and memory complexity.
  • Generalization to Higher Dimensions: The extension of COLT matrices to block matrices demonstrates the scalability of the approach for multi-dimensional problems.

Key Results

The paper demonstrates significant improvements in computational speed and accuracy:

  • Computational Complexity: The Fast Sinkhorn II (FS-2) algorithm achieves (O(N)) time complexity for computing the Wasserstein-1 metric, a substantial improvement over the (O(N^2)) complexity of standard IPOT methods.
  • Speedup: Numerical experiments show that FS-2 provides a speedup of two orders of magnitude compared to the IPOT method for 1D Gaussian distributions. For 2D random distributions, the empirical complexity of FS-2 is (O(N^{2.05})) compared to (O(N^{4.98})) for IPOT.
  • Accuracy: FS-2 consistently achieves comparable or better accuracy than FS-1, especially for small regularization parameters where FS-1 struggles. The paper shows FS-2's ability to converge to accurate solutions even when FS-1 fails.
  • Image Matching: In image matching tasks, FS-2 also demonstrates superior performance, achieving faster convergence and lower computational cost while maintaining high accuracy.

Limitations and Future Work

  • Numerical Stability with Zeros: The paper acknowledges a "minor flaw" in the algorithm regarding the computation of (W_1(u, v)) in the last step, which remains (O(N^2)). They mention this was also overlooked in prior work and suggest it will be addressed.
  • Extension to Other Metrics: While the paper focuses on the Wasserstein-1 metric, future work could explore extending the COLT-based approach to other OT metrics.
  • Broader Applications: The authors suggest that the FS-2 algorithm and its underlying principles could be applied to various fields, including machine learning, image processing, and inverse problems, indicating potential for wider impact.

Summary updated

Abstract

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.
BibTeX
@article{liao2024fast,
  author = {Qichen Liao and Zihao Wang and Jing Chen and Bo Bai and Shi Jin and Hao Wu},
  title = {{Fast Sinkhorn II: Collinear Triangular Matrix and Linear Time Accurate Computation of Optimal Transport}},
  journal = {J. Sci. Comput.},
  year = {2024},
  doi = {10.1007/s10915-023-02403-2},
}
Figure