May, 2019

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

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

    本文提出更快的算法来近似计算两个离散概率分布之间的最优传输距离（如移动距离），同时提供对其的简要介绍和优化，通过将最优传输归约为规范化优化问题，该问题可以在近似线性时间内解决，处理了 linear programs 等问题。

    Oct, 2018

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

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

    Feb, 2018

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

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

    Apr, 2013

  • 逆最优输运

    该论文提出了一种通过噪声数据推断未知成本的方法，利用了前向最优传输问题和随机数生成方法作为基础，探讨了其在国际迁移流问题上的应用和不确定性量化。

    May, 2019

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

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

    Aug, 2019

  • 从 Knothe 的输运到 Brenier 的映射及最优输运的连续化方法

    本文介绍了一种基于 Knothe-Rosenblatt 置换的转换方法，该方法可用于解决具有二次代价的 Monge-Kantorovich 质量输运问题，详细介绍了优化输运问题的数值解法。

    Oct, 2008

  • 神经最优传输

    该研究介绍了一种基于神经网络的算法，用于计算强和弱输运成本的最优输运图和计划，并证明了神经网络是概率分布之间传输计划的通用逼近器。通过在玩具示例和非成对图像翻译上评估我们的最优输运算法的性能。

    Jan, 2022

  • 圆上 Monge 成本的快速运输优化

    研究采用局部优化运输计划的理论进行解决图像处理的问题。得到所有局部最优输运计划都与移动呈共轭关系的结论，并验证了局部最优输运计划的费用是以移动参数的凸函数。提出了一种算法可以近似优化费用，当所有质量是 1/M 的整数倍时，该算法可以在 O (NlogM) 操作中实现准确解决方案。

    Feb, 2009

  • 二次正则化最优输运

    研究正则化问题的对偶问题，提出了用高斯 - 塞德尔方法和半光滑拟牛顿方法解决的方案，实验证明这两种方法在小正则化参数下表现良好。

    Mar, 2019

  • 一种新型用于动态最优运输问题的跳跃正交链表

    离散动态最优运输问题的解法，通过使用新的算法结构 2D Skip Orthogonal List 以及动态树技术，在高复杂度和动态数据结构之间找到了平衡，从而实现在数据点变化时高效更新最优运输方案。

    Oct, 2023