This paper studies the Partial Optimal Transport (POT) problem between two unbalanced measures with at most $n$ supports and its applications in various AI tasks such as color transfer or domain adaptation. There is hence the need for fast approximations of POT with increasingly large problem sizes in arising applications. We first theoretically and experimentally investigate the infeasibility of the state-of-the-art Sinkhorn algorithm for POT due to its incompatible rounding procedure, which consequently degrades its qualitative performance in real world applications like point-cloud registration. To this end, we propose a novel rounding algorithm for POT, and then provide a feasible Sinkhorn procedure with a revised computation complexity of $\mathcal{\widetilde O}(n^2/\varepsilon^4)$. Our rounding algorithm also permits the development of two first-order methods to approximate the POT problem. The first algorithm, Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD), finds an $\varepsilon$-approximate solution to the POT problem in $\mathcal{\widetilde O}(n^{2.5}/\varepsilon)$, which is better in $\varepsilon$ than revised Sinkhorn. The second method, Dual Extrapolation, achieves the computation complexity of $\mathcal{\widetilde O}(n^2/\varepsilon)$, thereby being the best in the literature. We further demonstrate the flexibility of POT compared to standard OT as well as the practicality of our algorithms on real applications where two marginal distributions are unbalanced.

本文研究了两个非平衡度量之间的部分最优输运（Partial Optimal Transport，POT）问题及其在颜色转移或领域适应等各种人工智能任务中的应用。我们首先通过理论和实验证明了现有的Sinkhorn算法在POT问题上的不可行性，进而提出了一种新的POT算法来解决这一问题，并且提供了几种近似POT问题的一阶方法，其中包括了近似解在ε范围内的Adaptive Primal-Dual Accelerated Gradient Descent（APDAGD）算法以及具有最佳计算复杂度的Dual Extrapolation算法。同时，我们还展示了POT相比标准OT的灵活性以及我们算法在两个非平衡边缘分布的实际应用中的实用性。

关于部分最优输运: 修正Sinkhorn和高效梯度方法的不可行性