提出新方法加速最优传输计算，兼顾速度与精度。
SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport
- 用切片提升传输计划稀疏化核，替代传统独立耦合
- 每轮迭代仅需O(LN)复杂度，比标准方法快数倍
- 适合大规模数据集，尤其适合需要高效距离度量的场景
熵正则最优传输（EOT）可作为精确最优传输的计算可行近似。但标准Sinkhorn-Knopp算法存在两大局限：其一，对于含$N$个点的离散测度，每轮迭代需$O(N^2)$运算，限制了在大规模数据集（如$N\geq10^4$）上的应用；其二，使用独立耦合作为正则化参考，导致中等正则强度下会将质量分配至高成本传输边。本文提出SinkSLOT，通过引入期望切片提升传输计划作为非独立先验耦合，自然实现吉布斯核的稀疏化，同时解决上述两个问题。理论证明：1）SinkSLOT收敛；2）使用$L$个切片时，每轮稀疏Sinkhorn迭代仅需$O(LN)$；3）所得目标为无需去偏的散度。合成基准实验显示，相比现有密集与稀疏EOT方法，SinkSLOT实现显著加速。还通过梯度流实验验证了该散度的应用可行性。代码已公开于https://github.com/cai4cai/SinkSLOT。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。