Abstract:
Entropic optimal transport has become a popular tool in data analysis and it can be solved efficiently with the celebrated Sinkhorn algorithm, but large scale problems remain challenging. Domain decomposition has been shown to be an efficient strategy on large grids. Unbalanced optimal transport is a versatile generalization of the standard (balanced) optimal transport problem and its entropic variant can also be solved with a generalized Sinkhorn algorithm. However, the domain decomposition algorithm cannot be applied directly to the unbalanced problem since independence of the cell problems is lost. In this article we generalize the domain decomposition algorithm for optimal transport to the unbalanced setting by introducing a new adaptive step size strategy, which allows to ensure the decrement of the global score and prove convergence to the global minimizer. We also provide an efficient GPU implementation of the new algorithm and demonstrate with experiments that domain decomposition is also an efficient strategy for large unbalanced optimal transport problems.
