Solving Discrete (Semi) Unbalanced Optimal Transport with Equivalent Transformation Mechanism and KKT-Multiplier Regularization

Semi-Unbalanced Optimal Transport (SemiUOT) shows great promise in matching two discrete probability measures by relaxing one of the marginal constraints. Previous SemiUOT solvers often incorporate an entropy regularization term, inevitably resulting in inaccurate matching solutions. To address this issue, we propose an Equivalent Transformation Mechanism (ETM) approach to determine the marginal probability distributions of SemiUOT with KL divergence. Furthermore, we validate the generalization capability of ETM by exploiting the marginal probability distributions of Unbalanced Optimal Transport (UOT). ETM is able to determine the exact marginal probabilities of both SemiUOT and UOT, based on which we can transform the SemiUOT/UOT into classic Optimal Transport (OT) problem. Moreover, we propose a KKT-Multiplier regularization term combined with Multiplier Regularized Optimal Transport (MROT) to achieve more accurate matching results. We conduct extensive experiments to demonstrate the effectiveness of our proposed methods in addressing SemiUOT and UOT problems 2 .