Sinkhorn 距离:最优输运距离的高速计算
本文介绍了 Cuturi 的 Sinkhorn 距离的新分析方法,表明这种算法能够近似地在线性时间内计算出一般上的最优输运距离,同时提出了相应的一种新的贪心坐标下降算法 Greenkhorn,并通过数值模拟表明 Greenkhorn 在实践中比经典的 Sinkhorn 算法显著优越。
May, 2017
使用最优传输距离(OT)和尤其是熵正则化 OT 距离作为机器学习和数据科学中的一种评估度量越来越普遍。本研究主要针对在线 Sinkhorn 算法进行改进和优化,提出了改进的收敛性分析和压缩技术结合的在线 Sinkhorn 算法,通过实证实验和理论证明验证了方法的有效性和性能。
Oct, 2023
本文研究了满足等式和不等式约束条件下的熵正则化的最优输运问题,并提出了一种基于 Sinkhorn 算法的对应解法。通过理论保证,我们首先得出在解决问题时通过熵正则化所带来的近似误差随着参数增加而指数级减小。此外,通过描述具有李雅普诺夫函数的优化过程,我们证明了 Sinkhorn 算法在对偶空间中具有亚线性一阶收敛速度。为了在弱熵正则化下实现快速、高阶收敛,我们通过动态正则化调度和二阶加速技术来改进 Sinkhorn 算法。总体而言,本文将熵最优输运的最近理论和数值进展与约束情况相结合,使从业者能够在复杂场景中得到近似的输运计划。
Mar, 2024
本文介绍了一种新的计算 Sinkhorn 距离的方法,该方法结合了 Nyström 方法和 Sinkhorn Scaling,具有显著的计算效率,适用于海量数据。
Dec, 2018
本文提出两种有效的对数线性时间逼近方法来计算熵正则化最优输运问题,并提出了一种结合图神经网络和增强 Sinkhorn 的图输运网络,并实验证明它在节点数量方面具有对数线性的规模,并在图距离回归方面优于以前的模型 48%。
Jul, 2021
通过引入早停止和牛顿类型子程序,Sinkhorn-Newton-Sparse(SNS)算法提供了超指数收敛,并且在实际情况下收敛速度比 Sinkhorn 算法快几个数量级,包括离散密度的经验分布之间的最优输运和计算 Wasserstein W1,W2 距离。
Jan, 2024
本文提出了一种基于标准 Sinkhorn 更新和紧缩函数的交替迭代算法,以实现不平衡输运的熵正则化,同时证明其在所有情况下的线性收敛性,并在此基础上定义了满足几何公理的伪距离,即不平衡 Sinkhorn 散度,为正测度全空间提供了一种支持不平衡输运的新方法。
Oct, 2019
本文提出了一种新型的最优熵输运问题,解决了在一般拓扑空间的非负有限 Radon 测度类中的问题,其中,最小化线性输运功能和两个凸熵功能的和,并讨论了对数熵输运问题,介绍了一种度量空间中的新 Hellinger-Kantorovich 距离,该距离具有很强的几何分析能力。
Aug, 2015
本研究分析了逼近两个离散分布之间的一般最优运输(OT)距离的两种算法,并证明了复杂度界限,其中一种基于 Sinkhorn 算法,另一种基于 Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) 算法。与先前的最优界限相比,我们的算法具有更好的复杂度界限,更好地依赖于 ε,同时可用于各种正则项。
Feb, 2018