Fast Unbalanced Optimal Transport on a Tree

Abstract

This study examines the time complexities of the unbalanced optimal transport problems from an algorithmic perspective for the first time. We reveal which problems in unbalanced optimal transport can/cannot be solved efficiently. Specifically, we prove that the Kantorovich Rubinstein distance and optimal partial transport in the Euclidean metric cannot be computed in strongly subquadratic time under the strong exponential time hypothesis. Then, we propose an algorithm that solves a more general unbalanced optimal transport problem exactly in quasi-linear time on a tree metric. The proposed algorithm processes a tree with one million nodes in less than one second. Our analysis forms a foundation for the theoretical study of unbalanced optimal transport algorithms and opens the door to the applications of unbalanced optimal transport to million-scale datasets.

arXiv commentAccepted to NeurIPS 2020

References in corpus (11)

• Recurrent Models of Visual Attention
• Learning with a Wasserstein Loss
• Generalized Wasserstein distance and its application to transport equations with source
• Imaging with Kantorovich-Rubinstein discrepancy
• Probabilistic Polynomials and Hamming Nearest Neighbors
• Sliced Wasserstein Kernel for Persistence Diagrams
• A new optimal transport distance on the space of finite Radon measures
• Progressive Wasserstein Barycenters of Persistence Diagrams
• Large Scale computation of Means and Clusters for Persistence Diagrams using Optimal Transport
• On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces