Domain decomposition for entropy regularized optimal transport
Domain decomposition for entropy regularized optimal transport
复制标题
熵正则化最优传输的域分解
DOI：
--
复制
发表时间：
2020
影响因子：
2.1
通讯作者：
Bernhard Schmitzer
中科院分区：
文献类型：
--
作者：
M. Bonafini;Bernhard Schmitzer
研究了最优输运问题的Benamou区域分解算法。关键的观察结果是，在非常温和的假设下，正则化变量收敛到全局最优解。我们证明了算法关于Kullback-Leibler发散的线性收敛，并用数值例子说明了(潜在的非常慢的)速度。对于具有足够几何结构的问题(如图像之间的Wasserstein距离)，我们预计收敛速度要快得多。然后，我们讨论了计算高效实现的重要方面，如自适应稀疏性、从粗到精的方案和并行化，为数值求解大规模最优运输问题铺平了道路。我们展示了计算2D图像之间的Wasserstein-2距离的有效数值性能，并观察到，即使没有并行化，区域分解在运行时间、内存和解质量方面也比应用Sinkhorn算法的单一有效实现更有利。
We study Benamou’s domain decomposition algorithm for optimal transport in the entropy regularized setting. The key observation is that the regularized variant converges to the globally optimal solution under very mild assumptions. We prove linear convergence of the algorithm with respect to the Kullback–Leibler divergence and illustrate the (potentially very slow) rates with numerical examples. On problems with sufficient geometric structure (such as Wasserstein distances between images) we expect much faster convergence. We then discuss important aspects of a computationally efficient implementation, such as adaptive sparsity, a coarse-to-fine scheme and parallelization, paving the way to numerically solving large-scale optimal transport problems. We demonstrate efficient numerical performance for computing the Wasserstein-2 distance between 2D images and observe that, even without parallelization, domain decomposition compares favorably to applying a single efficient implementation of the Sinkhorn algorithm in terms of runtime, memory and solution quality.
DOI：
10.1007/978-3-642-38267-3_38
发表时间：
2013
期刊：
影响因子：
--
作者：
Schmitzer;C. Schnörr
通讯作者：
C. Schnörr