研究人员提出SinkSLOT算法，大幅提升最优传输计算效率，适用于大规模数据集。
SinkSLOT解决了Sinkhorn-Knopp算法在大规模数据集上的计算瓶颈问题。该算法通过引入期望切片提升传输计划，将每次迭代复杂度从O(N²)降至O(LN)。实验表明，SinkSLOT在合成基准测试中显著优于现有密集和稀疏EOT方法。代码已在GitHub开源。
SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport
Entropic optimal transport (EOT) has been shown to offer a computationally tractable approximation to exact optimal transport. However, the standard Sinkhorn-Knopp algorithm has two main limitations. First, given discrete measures with $N$ points, each iteration requires $O(N^2)$ operations, which restricts its use on large-scale datasets (e.g. $N\geq10^4$). Second, it uses the independent coupling as a reference measure for regularisation. This assigns mass to high-cost transport edges at moderate regularisation strengths. We propose SinkSLOT, which addresses both limitations by putting forth the expected sliced lifted transport plan as a natural way to sparsify the Gibbs kernel with a non-independent prior coupling. We prove that: 1) SinkSLOT converges; 2) with $L$ slices, each resulting sparse Sinkhorn iteration costs $O(LN)$; and 3) the resulting objective is a divergence requiring no debiasing. Experiments on synthetic benchmarks show that SinkSLOT delivers substantial speedups over state-of-the-art dense and sparse EOT methods. We also demonstrate the applicability of the proposed divergence in a gradient flow experiment. The code is publicly available at https://github.com/cai4cai/SinkSLOT.