论文标题
更快的不平衡最佳运输：翻译不变式的sindhorn和1-D Frank-Wolfe
Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe
论文作者
论文摘要
不平衡的最佳运输（UOT）扩展了最佳运输（OT），以考虑质量变化以比较分布。这对于使OT在ML应用中取得成功至关重要，从而使其对数据归一化和异常值具有鲁棒性。基线算法是sndhorn，但其收敛速度的UOT可能比OT慢得多。在这项工作中，我们确定了这种缺陷的原因，即缺乏迭代元素的全局归一化，这等效地对应于双重电位的翻译。我们的第一个贡献利用了这一想法来开发一种可证明加速的sindhorn算法（含有的“翻译不变的sindhorn”），以将计算差距与OT弥合。我们的第二个贡献集中在1-D UOT上，并提出了一种应用于这种翻译不变的配方的Frank-Wolfe求解器。每个步骤的线性甲骨文等于解决1-D OT问题，导致每次迭代的线性时间复杂性。我们的最后贡献将此方法扩展到了1D测量的UOT Barycenter的计算。数值模拟展示了这三种方法带来的收敛速度提高。
Unbalanced optimal transport (UOT) extends optimal transport (OT) to take into account mass variations to compare distributions. This is crucial to make OT successful in ML applications, making it robust to data normalization and outliers. The baseline algorithm is Sinkhorn, but its convergence speed might be significantly slower for UOT than for OT. In this work, we identify the cause for this deficiency, namely the lack of a global normalization of the iterates, which equivalently corresponds to a translation of the dual OT potentials. Our first contribution leverages this idea to develop a provably accelerated Sinkhorn algorithm (coined 'translation invariant Sinkhorn') for UOT, bridging the computational gap with OT. Our second contribution focusses on 1-D UOT and proposes a Frank-Wolfe solver applied to this translation invariant formulation. The linear oracle of each steps amounts to solving a 1-D OT problems, resulting in a linear time complexity per iteration. Our last contribution extends this method to the computation of UOT barycenter of 1-D measures. Numerical simulations showcase the convergence speed improvement brought by these three approaches.
