Quadratically-Regularized Optimal Transport on Graphs
Quadratically-Regularized Optimal Transport on Graphs
复制标题
图上的二次正则化最优传输
DOI：
10.1137/17m1132665
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
J. Solomon
中科院分区：
文献类型：
--
作者：
Montacer Essid;J. Solomon
最佳运输提供了一种在几何域上的点之间提升距离之间的距离的手段，从而以概率分布表示的信号之间的距离之间的距离。在图上，可以使用运输问题来表达涉及供应与需求相匹配的挑战性任务，而运输费用与最低的运输费用；在离散的语言中，这些成为最低成本的网络流问题。通常需要正则化以确保线性地面距离情况的唯一性并改善优化收敛；最先进的技术在运输矩阵上采用熵正则化。在本文中，我们探索了熵正则化的二次替代方案，以通过图形传输。我们从理论上分析了四次规范化的图传输的行为，表征正则化如何影响小但非正则化的状态中流的结构。我们进一步利用了此问题双重的优雅二阶结构，以得出一种易于实现的牛顿型优化算法。
Optimal transportation provides a means of lifting distances between points on a geometric domain to distances between signals over the domain, expressed as probability distributions. On a graph, transportation problems can be used to express challenging tasks involving matching supply to demand with minimal shipment expense; in discrete language, these become minimum-cost network flow problems. Regularization typically is needed to ensure uniqueness for the linear ground distance case and to improve optimization convergence; state-of-the-art techniques employ entropic regularization on the transportation matrix. In this paper, we explore a quadratic alternative to entropic regularization for transport over a graph. We theoretically analyze the behavior of quadratically-regularized graph transport, characterizing how regularization affects the structure of flows in the regime of small but nonzero regularization. We further exploit elegant second-order structure in the dual of this problem to derive an easily-implemented Newton-type optimization algorithm.