近线性时间内逼近二次传输度量

Oct, 2018

Approximating the Quadratic Transportation Metric in Near-Linear Time

Jason Altschuler, Francis Bach, Alessandro Rudi, Jonathan Weed

TL;DR该研究提出了一种基于熵正则化、近似 Sinkhorn 缩放和高斯核矩阵低秩逼近的算法，用于计算两个点云或离散分布之间的二次输运度量（也称为 2-Wasserstein 距离或均方根距离），其复杂度为 O (n)。

Abstract

Computing the quadratic transportation metric (also called the $2$-Wasserstein distance or root mean square distance) between two point clouds, or, more generally, two discrete distributions, is a fundamental problem in machine learning, statistics, computer graphics, and theoretical c

quadratic transportation metric 2-wasserstein distance entropic regularization approximate sinkhorn scaling low-rank approximations

发现论文，激发创造

子空间鲁棒瓦热斯坦距离

本文针对高维离散量之间的 Wasserstein 距离提出了具有鲁棒性的 “Max-Min” 方案，通过将量投影到一个较低维的子空间来最大化它们之间的距离。此外，我们提出了一种基于熵正则化的算法来解决相关问题，并在实验中显示了其优越性。

Jan, 2019

在低维欧几里得空间全局解决点云的 Gromov-Wasserstein 问题

提出了一种计算低维空间中两组点之间 Gromov-Wasserstein 问题的框架，通过将 Quadratic Assignment Problem (QAP) 重新表述为低维域的优化问题来解决计算复杂度的挑战。该方法适用于具有成千上万个点的大规模问题，可用于找到全局解，并在合成问题和计算生物学中的一个感兴趣的问题上与最先进的方法进行比较。

Jul, 2023

Gromov-Wasserstein 距离的快速梯度计算

我们提出了一种新的方法，通过动态规划技术加速精确梯度计算，将复杂度从立方降低到二次，从而突破了原有的计算瓶颈，可以在总二次时间内获得新的熵解，这几乎是最优复杂度。大量实验证实了我们方法的高效性和有效性。

Apr, 2024

核最大切片 Wasserstein 距离的统计和计算保证

通过找到一种优化非线性映射，将数据降维到一维后计算 Wasserstein 距离，本文提供了 KMS p-Wasserstein 距离的尖锐有限样本保证，并给出了计算 KMS 2-Wasserstein 距离的难度和仿真实验的表现。

May, 2024

可扩展的最近邻搜索用于最优输运

这篇论文介绍一种快速、准确的 Wasserstein-1 距离近邻搜索算法 Flowtree，通过实验表明它比之前的最先进算法快 7.4 倍。

Oct, 2019

反演数据匹配的二次 Wasserstein 度量

本文研究了二次 Wasserstein 距离作为计算逆问题数据差异度量的两个主要作用，并证明了在无限维度的情况下，$W_2$ 距离对反演过程具有平滑效应以及在有限维度的问题中，$W_2$ 距离相比经典的 $L^2$ 和 $H^{-1}$ 距离有更好的优化凸性质。

Nov, 2019

一种新的鲁棒部分 $p$-Wasserstein 比较分布度量

给定一篇研究论文，提取五个关键词来准确表示其主要主题和研究领域，然后用一句简洁的中文句子对论文进行总结。

May, 2024

计算精确瓦瑟斯坦距离的快速近端点方法

开发了一种基于 Inexact Proximal point 方法的算法 (IPOT)，该算法通过将投影用于概率单纯形来近似评估近端算子，以解决精确最优输运问题，并具有具有理论保证和强健的正则化参数选择，同时缓解了数值稳定性问题并避免了应用于生成模型时的收缩问题。此外，基于 IPOT 提出了一种新的算法，用于获得更锐利的 Wasserstein 重心。

Feb, 2018

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

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

Jun, 2020

快速双子梯度优化随机核之间的综合运输距离

一种新的概率核心间距离，综合运输距离的广义 Wasserstein 度量，为 Markov 系统的概率核心之间建立了一种新颖的距离。这种度量技术为一种高效的近似方法奠定了基础，能够用有限集合元素支持的核心替代原始系统的核心。为了方便实际实施，我们提出了一种专门的对偶算法，能够快速高效地构建这些近似核心，而无需计算昂贵的矩阵运算。最后，我们通过几个实例展示了我们方法的实用性，展示了它在实际场景中的效果。这一进展为核心表示的随机系统的简化分析和操作提供了新的可能性。

Dec, 2023