Generalized Unnormalized Optimal Transport and its fast algorithms

Abstract

We introduce fast algorithms for generalized unnormalized optimal transport. To handle densities with different total mass, we consider a dynamic model, which mixes the $L^p$ optimal transport with $L^p$ distance. For $p=1$, we derive the corresponding $L^1$ generalized unnormalized Kantorovich formula. We further show that the problem becomes a simple $L^1$ minimization which is solved efficiently by a primal-dual algorithm. For $p=2$, we derive the $L^2$ generalized unnormalized Kantorovich formula, a new unnormalized Monge problem and the corresponding Monge-Ampère 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.

References in corpus (7)

• Wasserstein GAN
• Generalized Wasserstein distance and its application to transport equations with source
• Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures
• Unnormalized Optimal Transport
• Algorithm for Hamilton-Jacobi equations in density space via a generalized Hopf formula
• Seismic Inversion and the Data Normalization for Optimal Transport
• Hopf-Cole transformation via generalized Schrödinger bridge problem

Cited by in corpus (3)

• Computational Mean-field information dynamics associated with Reaction diffusion equations
• High order spatial discretization for variational time implicit schemes: Wasserstein gradient flows and reaction-diffusion systems
• A Fast Proximal Gradient Method and Convergence Analysis for Dynamic Mean Field Planning