论文标题
配对成本有效，精确的多边缘最佳运输
Efficient and Exact Multimarginal Optimal Transport with Pairwise Costs
论文作者
论文摘要
在本文中，我们以成对成本解决了多边缘最佳运输（MMOT）的数值解决方案。 MMOT作为经典两界最佳运输的自然扩展，具有许多重要的应用，包括图像处理，密度功能理论和机器学习，但缺乏有效且精确的数值方法。流行的熵调查方法可能会遭受数值不稳定和模糊的问题。受到Jacobs和Léger引入的来回方法的启发，我们研究了成对成本的MMOT问题。首先，此类问题具有图形表示，我们证明具有树表示的等效MMOT问题。其次，我们引入了一种Noval算法来通过基于梯度的双重公式的方法在根树上求解MMOT。最后，我们获得了可用于无正规化应用程序的准确解决方案。
In this paper, we address the numerical solution to the multimarginal optimal transport (MMOT) with pairwise costs. MMOT, as a natural extension from the classical two-marginal optimal transport, has many important applications including image processing, density functional theory and machine learning, but yet lacks efficient and exact numerical methods. The popular entropy-regularized method may suffer numerical instability and blurring issues. Inspired by the back-and-forth method introduced by Jacobs and Léger, we investigate MMOT problems with pairwise costs. First, such problems have a graphical representation and we prove equivalent MMOT problems that have a tree representation. Second, we introduce a noval algorithm to solve MMOT on a rooted tree, by gradient based method on the dual formulation. Last, we obtain accurate solutions which can be used for the regularization-free applications.
