  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.
