论文标题
在不平衡的最佳运输中：sindhorn算法的分析
On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
论文作者
论文摘要
我们为Sinkhorn算法提供了计算复杂性分析，该算法解决了两种可能不同质量的量度不同的熵不平衡的最佳运输（UOT）问题，最多最多$ n $组件。我们表明，找到$ \ varepsilon $ - 对UOT问题的解决方案的复杂性是$ \ widetilde {\ Mathcal {o}}}（n^2/ \ varepsilon）$，这是接近线性的时间。据我们所知，这种复杂性比解决最佳传输（OT）问题的sindhorn算法的复杂性要好，即$ \ wideTilde {\ Mathcal {o}}}（n^2/\ varepsilon^2）$。我们的证明技术基于凹痕更新到熵正规化UOT问题的最佳双重解决方案的几何收敛和原始解决方案的某些属性。这也与近似ot问题的sindhorn算法的复杂性的证明也不同，因为UOT解决方案不必满足边缘约束。
We provide a computational complexity analysis for the Sinkhorn algorithm that solves the entropic regularized Unbalanced Optimal Transport (UOT) problem between two measures of possibly different masses with at most $n$ components. We show that the complexity of the Sinkhorn algorithm for finding an $\varepsilon$-approximate solution to the UOT problem is of order $\widetilde{\mathcal{O}}(n^2/ \varepsilon)$, which is near-linear time. To the best of our knowledge, this complexity is better than the complexity of the Sinkhorn algorithm for solving the Optimal Transport (OT) problem, which is of order $\widetilde{\mathcal{O}}(n^2/\varepsilon^2)$. Our proof technique is based on the geometric convergence of the Sinkhorn updates to the optimal dual solution of the entropic regularized UOT problem and some properties of the primal solution. It is also different from the proof for the complexity of the Sinkhorn algorithm for approximating the OT problem since the UOT solution does not have to meet the marginal constraints.
