论文标题
熵正规化最佳运输的域分解
Domain decomposition for entropy regularized optimal transport
论文作者
论文摘要
我们研究Benamou的域分解算法，以在熵正规化设置中进行最佳运输。关键观察结果是，在非常温和的假设下，正则化变体会收敛到全球最佳溶液。我们证明了算法相对于kullback-leibler发散的线性收敛，并用数值示例说明了（可能非常慢的）速率。 关于足够的几何结构的问题（例如图像之间的瓦斯汀距离），我们期望会更快地收敛。然后，我们讨论了计算有效实现的重要方面，例如自适应稀疏性，粗到定义的方案和并行化，为解决大型最佳运输问题的方式铺平了道路。我们证明了用于计算2D图像之间的Wasserstein-2距离的有效数值性能，并观察到，即使没有并行化，域的分解也与在运行时，内存和解决方案质量方面相比，与应用sindhorn算法的单一有效实现相比。
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.
