论文标题
通过加速交替的最小化多重边缘最佳运输
Multimarginal Optimal Transport by Accelerated Alternating Minimization
论文作者
论文摘要
我们考虑了多边缘最佳运输，其中包括特定情况下的瓦斯坦·巴里卡特问题。在此问题中，必须在$ m $概率的措施之间找到最佳的耦合，这等于找到订单$ m $的张量。我们提出了一种基于加速交替的最小化的加速方法，并估计其复杂性，以找到问题的近似解决方案。我们将熵正则化和足够小的正则化参数使用，并将加速交替的最小化应用于双重问题。一种新型的原始偶二分析用于重建近似最佳的耦合张量。对于问题参数的某些制度，我们的算法比最先进的方法表现出更好的计算复杂性。
We consider a multimarginal optimal transport, which includes as a particular case the Wasserstein barycenter problem. In this problem one has to find an optimal coupling between $m$ probability measures, which amounts to finding a tensor of the order $m$. We propose an accelerated method based on accelerated alternating minimization and estimate its complexity to find the approximate solution to the problem. We use entropic regularization with sufficiently small regularization parameter and apply accelerated alternating minimization to the dual problem. A novel primal-dual analysis is used to reconstruct the approximately optimal coupling tensor. Our algorithm exhibits a better computational complexity than the state-of-the-art methods for some regimes of the problem parameters.
