Optimal Transport理论与计算方法

"Computational Optimal Transport 是一个深入探讨概率分布几何比较的数学领域，它在概率论、分析和优化之间架起了一座桥梁。该理论通过将概率分布视为沙堆，来研究如何以最低成本将一个沙堆形状转换成另一个。Gabriel Peyré 和 Marco Cuturi 的论文详细阐述了其理论基础和算法实现，包括最优运输问题、 Kantorovich 放松、双优化问题以及熵正则化等关键概念，并介绍了 Sinkhorn 算法和加速技巧。此外，论文还讨论了半离散最优运输和相关的 c 变换技术。" 本文档详细介绍了计算最优传输的理论和算法基础，旨在解决两个概率分布之间的比较和转换问题。作者首先定义了概率分布的概念，将其比作沙堆，其中的峰值代表可能的观察值出现的位置。最优传输的目标是找到将一个分布转换为另一个分布的最低成本方式，这一过程涉及到 Monge 问题和 Kantorovich 放松。 在理论基础上，文章详细讨论了概率分布的表示（如直方图和测度），以及 Monge 问题，即寻找一对一的映射以最小化成本。接着，Kantorovich 放松引入了更广义的优化框架，允许不完全匹配的情况。文章还讨论了最优传输的度量性质，如其作为概率分布距离的特性，以及与其相关的双优化问题。 算法部分，作者介绍了 Kantorovich 线性规划及其解法，如 C-变换、互补松弛性和运输多面体的顶点。网络单纯形方法和拍卖算法是求解这些优化问题的策略。此外，文章特别关注了熵正则化，这是一种加速计算和稳定优化的技术，其中 Sinkhorn 算法是核心，它能快速迭代得到近似解。为了进一步提高效率，文中提出了各种加速 Sinkhorn 迭代的方法，以及在对数域中进行的正则化双优化和成本估计。 最后，半离散最优运输被介绍，这是一种处理离散分布与连续分布之间运输问题的方法，涉及 c 变换和其变种 ¯c 变换。这些技术扩展了最优传输的应用范围，使其在实际数据处理中更具灵活性和实用性。 这篇论文涵盖了计算最优传输的广泛内容，从基本理论到高效算法，对于理解和应用最优传输理论在机器学习、图像处理和统计学等领域具有重要价值。