Generalized Unnormalized Optimal Transport and its fast algorithms

We introduce fast algorithms for generalized unnormalized optimal transport. To handle densities with different total mass, we consider a dynamic model, which mixes the Lp optimal transport with Lp distance. For p=1, we derive the corresponding L1 generalized unnormalized Kantorovich formula. We further show that the problem becomes a simple L1 minimization which is solved efficiently by a primal-dual algorithm. For p=2, we derive the L2 generalized unnormalized Kantorovich formula, a new unnormalized Monge problem and the corresponding Monge-Amp`ere equation. Furthermore, we introduce a new unconstrained optimization formulation of the problem. The associated gradient flow is essentially related to an elliptic equation which can be solved efficiently. Here the proposed gradient descent procedure together with the Nesterov acceleration involves the Hamilton-Jacobi equation which arises from the KKT conditions. Several numerical examples are presented to illustrate the effectiveness of the proposed algorithms.