PRUNE AND SPLIT: A SCALABLE APPROACH TO UNBALANCED OPTIMAL TRANSPORT

In this paper, we analyze the T-Sparse Unbalanced Optimal Transport (TSUOT) problem, a variant of the standard Unbalanced Optimal Transport (UOT) problem that enables customizable sparsity, i.e., Pruning of long-range transport arcs, via a tunable parameter $T$. After showing that the TSUOT is well defined for most of the Csiszár divergences, we propose the Main Diagonal Block method, an ad hoc Block Coordinate Descent algorithm for UOT problems. At the core of the method is a structure-aware coordinate partition that, by Splitting the transport variables into suitably chosen blocks, allows for efficient parallel optimization. The interaction between Pruning and Splitting yields dual advantages. On the one hand, Pruning bounds the number of relevant blocks; on the other hand, Splitting decreases the local \Holder constant. These effects combined improve the overall complexity of the method. Experiments on heterogeneous real-world benchmarks show that the proposed approach achieves comparable numerical accuracy to standard UOT baselines while substantially reducing wall-clock computation time, with speedups of up to two orders of magnitude in the tested regimes. These results position the proposed framework as a competitive approach to large-scale UOT computation.