Well-Posedness and Efficient Algorithms for Inverse Optimal Transport with Bregman Regularization
Provides theoretical foundations and a practical algorithm for inverse optimal transport, benefiting researchers in optimal transport and related fields.
This work establishes well-posedness (existence, uniqueness, stability) for inverse optimal transport with Bregman regularization and proposes an efficient block coordinate descent algorithm with linear convergence, validated on synthetic and real-world data.
This work analyzes the inverse optimal transport (IOT) problem under Bregman regularization. We establish well-posedness results, including existence, uniqueness (up to equivalence classes of solutions), and stability, under several structural assumptions on the cost matrix. On the computational side, we investigate the existence of solutions to the optimization problem with general constraints on the cost matrix and provide a sufficient condition guaranteeing existence. In addition, we propose an inexact block coordinate descent (BCD) method for the problem with a strongly convex penalty term. In particular, when the penalty is quadratic, the subproblems admit a diagonal Hessian structure, which enables highly efficient element-wise Newton updates. We establish a linear convergence rate for the algorithm and demonstrate its practical performance through numerical experiments, including the validation of stability bounds, the investigation of regularization effects, and the application to a marriage matching dataset.