On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm

Abstract

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 $\epsilon$-approximate solution to the UOT problem is of order $\tilde{\mathcal{O}}(n^2/\epsilon )$, 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 $\tilde{\mathcal{O}}(n^2/{\epsilon }^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.

References in corpus (8)

• Learning with a Wasserstein Loss
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Scaling Algorithms for Unbalanced Transport Problems
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• Sinkhorn Divergences for Unbalanced Optimal Transport
• Multilevel Clustering via Wasserstein Means
• Spatio-Temporal Alignments: Optimal transport through space and time
• Parallel Unbalanced Optimal Transport Regularization for Large Scale Imaging Problems

Cited by in corpus (9)

• Unbalanced minibatch Optimal Transport; applications to Domain Adaptation
• The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Improving Mini-batch Optimal Transport via Partial Transportation
• On Robust Optimal Transport: Computational Complexity and Barycenter Computation
• Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe
• Optimal Transport for Change Detection on LiDAR Point Clouds
• Topological Node2vec: Enhanced Graph Embedding via Persistent Homology
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity