Domain decomposition for entropic unbalanced optimal transport
针对大规模熵非平衡最优传输问题，提出一种带自适应步长的域分解算法，保证全局收敛，并在GPU上高效实现，实验证明其有效性。
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.