Sinkhorn Algorithm for Sequentially Composed Optimal Transports

Sinkhorn算法是事实上的最优传输近似算法标准，已被应用于多种领域，包括图像处理和自然语言处理。理论上，其收敛性的证明基于矩阵缩放问题中Sinkhorn-Knopp算法的收敛性，而Altschuler等人证明了其最坏情况下的时间复杂度接近线性。最近，Watanabe和Isobe提出了顺序组合最优传输作为最优传输的层次扩展。在本文中，我们提出了一种高效的近似算法，即用于顺序组合最优传输的Sinkhorn算法，针对其熵正则化进行了优化。此外，我们对Sinkhorn算法进行了理论分析，具体包括：(i) 关于Hilbert伪度量的指数收敛到最优解；(ii) 对单一顺序组合情况下的最坏情况复杂度分析。

该论文旨在为顺序组合最优传输问题提供一个高效的近似算法，并分析其理论性质。这是一个相对较新的问题，因为它扩展了传统的最优传输问题，引入了层次结构。

论文的关键思路是将Sinkhorn算法应用于顺序组合最优传输的熵正则化问题。与传统最优传输问题不同，顺序组合最优传输考虑了多个步骤的传输过程，从而增加了问题的复杂性。论文不仅提出了算法，还提供了理论分析，证明了算法在Hilbert伪度量下的指数收敛性和最坏情况下的时间复杂度。

1. 提出了针对顺序组合最优传输的Sinkhorn算法，这是对传统Sinkhorn算法的一个重要扩展。 2. 通过理论分析证明了算法的指数收敛性和最坏情况下的时间复杂度。 3. 实验设计包括了对不同数据集的测试，展示了算法的有效性和效率。 4. 论文提供了开源代码，方便其他研究人员复现和进一步研究。 5. 指出了一些未来的研究方向，如多层顺序组合最优传输的优化方法。

1. Altschuler et al., 'Near-Linear Time Approximation Algorithms for Optimal Transport via Sinkhorn Iteration' (2017) 2. Cuturi, 'Sinkhorn Distances: Lightspeed Computation of Optimal Transport' (2013) 3. Watanabe and Isobe, 'Sequentially Composed Optimal Transports' (2022) 4. Peyré and Cuturi, 'Computational Optimal Transport' (2019)