arXiv (Cornell University) · 2020 · 18 citations · 16 references
ComputingComputer ScienceMathematicsAlgorithmsOptimizationTransportAlgorithm AnalysisApproximation AlgorithmsTransportation ProblemsComplexity AnalysisComputational Complexity Of AlgorithmsConvergenceOptimal Transport
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.
16
Sinkhorn Distances: Lightspeed Computation of Optimal Transport
Marco Cuturi · 2013 · 2.2K citations
Optimal Transport for Domain Adaptation
Nicolas Courty, Rémi Flamary, Devis Tuia et al. · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 942 citations · Full text
Computational Optimal Transport
Gabriel Peyré, Marco Cuturi · now publishers, Inc. eBooks · 2019 · 903 citations
Fast and robust Earth Mover's Distances
Ofir Pele, Michael Werman · 2009 · 836 citations