M. Henry: Primal-dual formulation of the optimal transport problem using divergence-free vector field decomposition
Abstract: In this work, we focus on the image interpolation problem and the numerical resolution of the L2-optimal transport problem, for which few numerical methods have been developed so far. Benamou and Brenier place the problem in the context of fluid mechanics by adding a time dimension, leading to a new formulation. We propose to work directly in the space of constraints for the functional to minimize. Indeed, existing algorithms require a projection onto the divergence-free constraint at each iteration, which amounts to solving a 3D Poisson equation for 2D images. The fact that the functional is strictly convex in the set of constraints, which we will prove, motivates our approach. To work in this space, defined by a divergence-free and regularity constraint on the density and the velocity fields, and boundary conditions, we use the Helmholtz-Hodge decomposition. This leads to a new formulation of the problem, which in 1D + time, is equivalent to the resolution of a minimal surface equation on every level set of the potential, equipped with appropriate Dirichlet boundary conditions. Another approach to handle the new formulation is to use a first order primal dual algorithm for convex problems developed by Chambolle and Pock, which can be easily adapted to the minimization of our functional. The Chambolle-Pock method leads to fast implementations and can be easily sped up on parallel architectures. Therefore our method provides an algorithm, simple to implement on imaging problems and faster than state-of-the-art.