SinkSLOT Speeds Up Optimal Transport for Large Datasets

Entropic Optimal Transport (EOT) is a powerful tool for comparing probability distributions, offering a computationally feasible approximation to exact optimal transport. However, the widely used Sinkhorn-Knopp algorithm faces two main challenges: its quadratic computational complexity ($O(N^2)$ per iteration) limits its application to very large datasets, and its use of an independent coupling as a reference measure can lead to assigning mass to high-cost transport edges. A new method called SinkSLOT (Sinkhorn via Sparse Lifted Optimal Transport) has been proposed to overcome these limitations. SinkSLOT introduces the concept of an expected sliced lifted transport plan, which naturally sparsifies the Gibbs kernel using a non-independent prior coupling. This approach significantly reduces the computational burden. The researchers prove that SinkSLOT converges and that each sparse Sinkhorn iteration costs only $O(LN)$, where $L$ is the number of slices, making it much more efficient for large datasets. Furthermore, the resulting objective is a divergence that does not require debiasing. Experimental results on synthetic benchmarks demonstrate that SinkSLOT provides substantial speedups compared to existing dense and sparse EOT methods, and its applicability is shown in a gradient flow experiment.