Lifted Assignment 问题的 Sinkhorn 算法
基于路斯选择公理的广泛类选择和排名模型,包括布拉德利 - 特里 - 路斯和普拉克特 - 路斯模型,我们证明相关的最大似然估计问题等同于具有目标行列和的经典矩阵平衡问题。这种观点打开了两个看似无关的研究领域之间的门槛,并使我们能够将选择建模文献中的现有算法统一为 Sinkhorn 的矩阵平衡算法的特殊实例或类比。我们从这些联系中获得启发,并解决了关于 Sinkhorn 算法的重要开放问题。我们首先证明了对于非负矩阵,只要矩阵平衡问题存在有限解,Sinkhorn 算法在全局上是线性收敛的。我们用数据构造的双部分图将这种全局收敛速率以代数连通性的形式刻画出来。接下来,我们还推导了尖锐的渐近线性收敛速率,这推广了 Knight(2008)的经典结果,但使用了更明确的分析方法来利用内在的正交结构。据我们所知,这是 Sinkhorn 算法在一般非负矩阵和正边缘情况下的第一个定量线性收敛结果。我们在本文中建立的矩阵平衡和选择建模之间的联系可以有助于在两个方向上进一步传递思想和有趣的结果。
Sep, 2023
通过将 Kullback-Leibler divergence 应用于 mirror map 和目标函数中,我们发现 Sinkhorn 算法是增量 / 随机镜像下降的一种特例。该发现使我们能够提出一种新方法,扩展了 Sinkhorn 算法超出两个约束。
Sep, 2019
通过引入早停止和牛顿类型子程序,Sinkhorn-Newton-Sparse(SNS)算法提供了超指数收敛,并且在实际情况下收敛速度比 Sinkhorn 算法快几个数量级,包括离散密度的经验分布之间的最优输运和计算 Wasserstein W1,W2 距离。
Jan, 2024
本研究提出了一种新颖的策略以有效地近似两个离散度量之间的 Sinkhorn 距离。通过直接将可忽略的双重解的组件设置为该值,我们建议通过筛选这些组件来进入 Sinkhorn 问题。这基于 Sinkhorn 分歧问题的新增双重的新公式和该问题的 KKT 最优性条件,其可从该问题中识别可筛选的双重组件,从而确保了可证明的近似。在包括规则化最优输送的复杂任务中,我们展示了 Screenkhorn 的效率,例如维数约简和领域适应。
Jun, 2019
通过在非负矩阵 $A$ 内找到对角矩阵 $D_1,~D_2$,可以得到 $D_1AD_2$ 是双重随机的 Sinkhorn 定理,这篇文章评述了 70 多年来的矩阵缩放,重点关注围绕该问题及其解决方案的数学领域以及扩展至矩阵代数之间的正态映射,几乎不包含任何不普遍的未发表结果。
Sep, 2016
我们提供两种算法的理论分析,这两种算法可以解决两个离散概率测度之间的规则化最优输运问题,我们证明了一种名为绿角(Greenkhorn)算法的贪心版本可以改进到 O˜(n²ε ^-2),这种算法可以在实践中击败 Sinkhorn 算法,基于这个理论我们提出了新的算法。
Jan, 2019
机器学习中的熵正则最优传输问题可以通过 Sinkhorn 算法进行求解,而该研究介绍了 Sinkhorn 算法的连续时间模拟以及其在噪声和偏差容忍性方面的改进,同时与机器学习和数学领域中其他动态方法提供了统一的视角。
Nov, 2023
本文介绍了 Cuturi 的 Sinkhorn 距离的新分析方法,表明这种算法能够近似地在线性时间内计算出一般上的最优输运距离,同时提出了相应的一种新的贪心坐标下降算法 Greenkhorn,并通过数值模拟表明 Greenkhorn 在实践中比经典的 Sinkhorn 算法显著优越。
May, 2017
我们提出了一种新的算法 APDAMD 来解决原子最优输运问题,并证明了算法的复杂度界限与加速变种的 Sinkhorn 算法和 Greenkhorn 算法,在实践中均具有较高的效率。
Jun, 2019
通过将变形参数趋向于正无穷,最优分配问题的解可以由最大熵问题的解趋向得出,从而可以应用最大熵算法来求解最优分配问题。其中 Sinkhorn 算法导致了一种可并行化的方法,可用作处理大规模密集最优分配问题的预处理。此并行预处理允许删除不属于最优排列的条目,从而导致减少内存要求的可解实例。
Apr, 2011