MMAug, 2019

带储存费用的半离散最优输运的牛顿算法

PDF
TL;DR本文介绍和证明了一种阻尼牛顿算法的收敛性，以近似解决存储费用、硬容量约束下的半离散最优输运问题，并探讨了其在队列罚函数问题、数据聚类等方面的应用，是第一种基于数值方法并具有收敛性的解决该变体问题的算法，同时不需要任何关于源测度支集的连通性假设并提出相关的拉格尔细胞稳定性结果，所有结果均附带定量的速率分析和数值例子。
newton algorithmoptimal transport problemstorage feeshard capacity constraintsdata clustering
发现论文，激发创造
  • $L_2$ 三维半离散最优输运的数值算法

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

    Sep, 2014

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

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

    May, 2019

  • 通过加速梯度下降实现高效最优传输算法

    本研究提出了一种基于 Nesterov 的平滑技术的新算法，通过近似 Log-Sum-Exp 函数来平滑 Kantorovich 势的非平滑 c-transform，并将此平滑后的 Kantorovich 泛函应用于快速的 FISTA 算法以提高计算效率和精确度。实验结果表明，该方法相较于 Sinkhorn 算法在相同参数下具有更快的收敛速度和更高的准确性。

    Apr, 2021

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

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

    Apr, 2020

  • 张量最优输运、测度集之间的距离与张量缩放

    研究了 $d>2$ 离散测度的最优输运问题，提出了有熵正则化项的线性规划方案，并引入了 Sinkhorn 扩展算法，并给出了严格凸函数部分最小化算法的变形，得到其收敛速度的几何估计。

    May, 2020

  • 带有近端分裂的最优输运

    本文回顾了使用一阶凸优化方法来解决 Benamou 和 Brenier 最初提出的离散动态最优输运问题的方法，介绍了适用于计算基于均匀空间网格上定义的分布之间的 $L^2$ 最优输运测地线的交错网格离散化方法，展示了如何使用近端分裂方法来解决结果导致的大规模凸优化问题。同时，还介绍了如何考虑更一般的成本函数，以及如何扩展该方法以在 Riemann 流形上执行最优输运。

    Apr, 2013

  • 一种用于稠密最优传输的稀疏多尺度算法

    提供了一个与连续的最优传输类比的框架，以便于在本地验证离散传输计划的全局最优性，从而构建一种通过考虑一系列稀疏问题来解决大规模密集问题的算法，进而可以与分层多尺度方案相结合，明显减少了运行时间和内存要求。

    Oct, 2015

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

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

    Feb, 2018

  • 基于核的优化输运的专用半光滑牛顿法

    核密度估计方法在处理高维度的可行域问题方面比线性规划方法在统计效率上更加高效，但由于使用了大量迭代计算，使得该方法对于样本数量的扩展性较差。为了提高该方法在大样本情况下的可伸缩性，本文提出了一种基于核密度估计的非光滑定点模型，并通过专门的半光滑牛顿方法来高效地求解该模型，证明了该方法具有全局收敛速度 O (1/√k) 和在标准正则性条件下的局部二次收敛速度，并在合成数据集和真实数据集上显示了相对于使用短步内点法的显著加速。

    Oct, 2023

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

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

    Feb, 2018