Oct, 2018

求解最优输运问题的最优运行时间

PDF
TL;DR本文提出更快的算法来近似计算两个离散概率分布之间的最优传输距离（如移动距离），同时提供对其的简要介绍和优化，通过将最优传输归约为规范化优化问题，该问题可以在近似线性时间内解决，处理了 linear programs 等问题。
optimal transport distanceearth mover's distanceprobability distributionscouplinglinear programs
发现论文，激发创造
  • 一种直接的 $ ilde {O}(1/ε)$ 迭代并行算法，用于最优输运

    本文介绍一种基于原始对偶外推方法的平行一阶算法，通过计算最优传输（包括基于 Wasserstein 距离的计算）来解决机器学习和统计学中常见的问题，具有较强的实际应用价值，并实验验证了优异的性能。

    Jun, 2019

  • 最优输运的图论加法逼近

    本文提出了一种基于 Gabow 和 Tarjan 的图算法的新颖分析，并提供了一个简单的贪婪式迭代算法，其执行时间为 O (n^2*C/δ + nC^2/δ^2)，用于求解概率分布的最优运输问题，在数值不稳定的情况下具有竞争力的执行时间。

    May, 2019

  • 快速求解最优输运问题：往返法

    本研究提出一种迭代方法来高效地解决一类严格凸代价函数的最优运输问题，该方法包括二次和 p 次幂代价函数。我们针对两个定义在离散网格上的概率分布，使用 O (n) 的存储空间和 O (n log (n)) 的操作量计算最优映射，具有近似指数收敛速度。该方法能够在几分钟内解决空间网格大小达到 4096x4096 和 384x384x384 的最优运输问题。

    May, 2019

  • 最优传输：带精确求解器的快速概率逼近

    本文提出了一个基于离散最优输运问题的简单子抽样方案，用于快速随机近似计算最优输运距离。该方案针对完全数据的随机子集操作，可使用任何精确算法作为黑盒后端，包括最先进的求解器和熵惩罚版本。我们给出了其非渐进偏差范围，以针对更高的精度或更短的计算时间进行简化。实验证明，该子抽样方案可以在计算时间大大降低的情况下，获得比精确方法更好的近似效果。

    Feb, 2018

  • 最优输运方案的定量稳定性和误差估计

    本文研究了两个绝对连续测度之间的最优输运问题，提出了半离散和全离散算法，并证明了这两种算法的误差估计及其计算收敛速率。

    Apr, 2020

  • 计算最优传输：加速梯度下降比 Sinkhorn 算法更好的复杂度

    本研究分析了逼近两个离散分布之间的一般最优运输（OT）距离的两种算法，并证明了复杂度界限，其中一种基于 Sinkhorn 算法，另一种基于 Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) 算法。与先前的最优界限相比，我们的算法具有更好的复杂度界限，更好地依赖于 ε，同时可用于各种正则项。

    Feb, 2018

  • $L_2$ 三维半离散最优输运的数值算法

    本文介绍了一种计算两个测度之间 L2 最优传输图的数值算法，其中一个测度源自由分段线性函数（由四面体网格支持）定义的密度 rho，而另一个测度则是 Dirac 质量之和。作者提出了一个实用的算法来计算分段线性密度与 Dirac 质量总和之间的最优传输图。

    Sep, 2014

  • 连续图传输距离

    该论文提出了一种基于图顶点的概率分布最优传输方法，它不仅满足三角不等式，而且具有更好的可扩展性和与连续传输理论的联系，同时提供了一个适用于该方法的时间离散化方法并验证了其有效性。

    Mar, 2016

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

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

    May, 2017

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

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

    Oct, 2018