Dec, 2018

基于 Nystrom 方法的高度可扩展 Sinkhorn 距离

PDF
TL;DR本文介绍了一种新的计算 Sinkhorn 距离的方法，该方法结合了 Nyström 方法和 Sinkhorn Scaling，具有显著的计算效率，适用于海量数据。
sinkhorn distancewasserstein distancemachine learningnyström methodsinkhorn scaling
发现论文，激发创造
  • 稀疏牛顿迭代加速 Sinkhorn 算法

    通过引入早停止和牛顿类型子程序，Sinkhorn-Newton-Sparse（SNS）算法提供了超指数收敛，并且在实际情况下收敛速度比 Sinkhorn 算法快几个数量级，包括离散密度的经验分布之间的最优输运和计算 Wasserstein W1，W2 距离。

    Jan, 2024

  • 在线压缩 Sinkhorn

    使用最优传输距离（OT）和尤其是熵正则化 OT 距离作为机器学习和数据科学中的一种评估度量越来越普遍。本研究主要针对在线 Sinkhorn 算法进行改进和优化，提出了改进的收敛性分析和压缩技术结合的在线 Sinkhorn 算法，通过实证实验和理论证明验证了方法的有效性和性能。

    Oct, 2023

  • Sinkhorn 距离：最优输运距离的高速计算

    本文提出了一种新的最优传输距离家族，从最大熵的角度看待运输问题。在传统最优传输问题上加入熵正则化项，通过 Sinkhorn-Knopp 的矩阵缩放算法计算新的距离，显著提高了性能。

    Jun, 2013

  • 使用 Wasserstein 距离的 Sinkhorn 逼近的微分特性

    应用最优输运及熵正则化计算 Wasserstein 距离中的 Sinkhorn 近似算法的梯度，可以提高学习和优化问题的效率，同时通过高阶平滑性，也可以提供统计保证。

    May, 2018

  • 利用 Sinkhorn 散度实现更快的 Wasserstein 距离估计

    本研究提出使用 Sinkhorn 散度来估计平方 Wasserstein 距离，其允许更高的正则化水平，从而导致改进的计算复杂度界限和实际的强加速。

    Jun, 2020

  • 通过 Sinkhorn 迭代的近线性时间逼近算法优化输运问题

    本文介绍了 Cuturi 的 Sinkhorn 距离的新分析方法，表明这种算法能够近似地在线性时间内计算出一般上的最优输运距离，同时提出了相应的一种新的贪心坐标下降算法 Greenkhorn，并通过数值模拟表明 Greenkhorn 在实践中比经典的 Sinkhorn 算法显著优越。

    May, 2017

  • 一种用于约束优化传输问题的 Sinkhorn 类型算法

    本文研究了满足等式和不等式约束条件下的熵正则化的最优输运问题，并提出了一种基于 Sinkhorn 算法的对应解法。通过理论保证，我们首先得出在解决问题时通过熵正则化所带来的近似误差随着参数增加而指数级减小。此外，通过描述具有李雅普诺夫函数的优化过程，我们证明了 Sinkhorn 算法在对偶空间中具有亚线性一阶收敛速度。为了在弱熵正则化下实现快速、高阶收敛，我们通过动态正则化调度和二阶加速技术来改进 Sinkhorn 算法。总体而言，本文将熵最优输运的最近理论和数值进展与约束情况相结合，使从业者能够在复杂场景中得到近似的输运计划。

    Mar, 2024

  • Sinkhorn Flow: Sinkhorn 算法的连续时间框架解读与推广

    机器学习中的熵正则最优传输问题可以通过 Sinkhorn 算法进行求解，而该研究介绍了 Sinkhorn 算法的连续时间模拟以及其在噪声和偏差容忍性方面的改进，同时与机器学习和数学领域中其他动态方法提供了统一的视角。

    Nov, 2023

  • 熵正则传输问题的稳定稀疏缩放算法

    本文介绍了一种改进的算法，用于解决在处理大数据集时标准 Scaling algorithm 所遇到的一些数字限制问题，其中包括使用 log-domain stabilized formulation、epsilon-scaling heuristic、精简核心的一些问题，并给出了一些数值例子来说明改进算法的效率和多功能性。

    Oct, 2016

  • 基于放松约束的最优输运筛选 Sinkhorn 算法

    本研究提出了一种新颖的策略以有效地近似两个离散度量之间的 Sinkhorn 距离。通过直接将可忽略的双重解的组件设置为该值，我们建议通过筛选这些组件来进入 Sinkhorn 问题。这基于 Sinkhorn 分歧问题的新增双重的新公式和该问题的 KKT 最优性条件，其可从该问题中识别可筛选的双重组件，从而确保了可证明的近似。在包括规则化最优输送的复杂任务中，我们展示了 Screenkhorn 的效率，例如维数约简和领域适应。

    Jun, 2019