稀疏牛顿迭代加速 Sinkhorn 算法
本文介绍了一种新的计算 Sinkhorn 距离的方法,该方法结合了 Nyström 方法和 Sinkhorn Scaling,具有显著的计算效率,适用于海量数据。
Dec, 2018
本文研究了满足等式和不等式约束条件下的熵正则化的最优输运问题,并提出了一种基于 Sinkhorn 算法的对应解法。通过理论保证,我们首先得出在解决问题时通过熵正则化所带来的近似误差随着参数增加而指数级减小。此外,通过描述具有李雅普诺夫函数的优化过程,我们证明了 Sinkhorn 算法在对偶空间中具有亚线性一阶收敛速度。为了在弱熵正则化下实现快速、高阶收敛,我们通过动态正则化调度和二阶加速技术来改进 Sinkhorn 算法。总体而言,本文将熵最优输运的最近理论和数值进展与约束情况相结合,使从业者能够在复杂场景中得到近似的输运计划。
Mar, 2024
使用最优传输距离(OT)和尤其是熵正则化 OT 距离作为机器学习和数据科学中的一种评估度量越来越普遍。本研究主要针对在线 Sinkhorn 算法进行改进和优化,提出了改进的收敛性分析和压缩技术结合的在线 Sinkhorn 算法,通过实证实验和理论证明验证了方法的有效性和性能。
Oct, 2023
本文提出了一种新的最优传输距离家族,从最大熵的角度看待运输问题。在传统最优传输问题上加入熵正则化项,通过 Sinkhorn-Knopp 的矩阵缩放算法计算新的距离,显著提高了性能。
Jun, 2013
本文提出了一种新的重要性稀疏化方法,称为 Spar-Sink,用于高效地近似熵正则化的最优输运和不平衡最优输运解决方案。实验证明,Spar-Sink 在估计误差和速度方面优于主流竞争对手,并可以有效地估计和可视化心脏周期。
Jun, 2023
通过将 Kullback-Leibler divergence 应用于 mirror map 和目标函数中,我们发现 Sinkhorn 算法是增量 / 随机镜像下降的一种特例。该发现使我们能够提出一种新方法,扩展了 Sinkhorn 算法超出两个约束。
Sep, 2019
本文介绍了一种改进的算法,用于解决在处理大数据集时标准 Scaling algorithm 所遇到的一些数字限制问题,其中包括使用 log-domain stabilized formulation、epsilon-scaling heuristic、精简核心的一些问题,并给出了一些数值例子来说明改进算法的效率和多功能性。
Oct, 2016
本研究提出了一种基于 Nesterov 的平滑技术的新算法,通过近似 Log-Sum-Exp 函数来平滑 Kantorovich 势的非平滑 c-transform,并将此平滑后的 Kantorovich 泛函应用于快速的 FISTA 算法以提高计算效率和精确度。实验结果表明,该方法相较于 Sinkhorn 算法在相同参数下具有更快的收敛速度和更高的准确性。
Apr, 2021
机器学习中的熵正则最优传输问题可以通过 Sinkhorn 算法进行求解,而该研究介绍了 Sinkhorn 算法的连续时间模拟以及其在噪声和偏差容忍性方面的改进,同时与机器学习和数学领域中其他动态方法提供了统一的视角。
Nov, 2023
本文提出使用低秩近似的 ground costs 方法来提高 Sinkhorn divergences 计算效率,并将该方法应用于训练 OT-GAN 模型。
Jun, 2020