Optimal transport with proximal splitting

in collaboration with N. Papadakis and G. Peyré



All details can be found in our paper Optimal transport with proximal splitting. Multi-dimensional Matlab code for computing continuous optimal trnasport, including fast divergence projection operator by FFT, is available at . See also the ANR project TOMMI for additional results.

Optimal transport is a well developed mathematical theory that defines a family of metrics between probability distributions. These metrics measure the amplitude of an optimal displacement according to a so-called ground cost defined on the space supporting the distributions. The resulting distance is sometimes referred to as the Wasserstein distance in the case of Lp ground costs. The geometric nature of optimal transportation, as well as the ability to compute optimal displacements between densities, make this theory progressively mainstream in several applicative fields such as economic modeling and image processing. However, the numerical resolution of the optimal transportation problem raises several challenges. This article is focused on the computation of geodesics for the optimal transport metric associated to the L2 cost. It reviews and extends the approach pioneered by Benamou and Brenier from the perspective of proximal operator splitting in convex optimization. This shows the simplicity and efficiency of this method, which can easily be extended beyond the setting of optimal transport by considering various convex cost functions.

Move your mouse on the pictures to animate (slow connection be patient)

Finding the way out is a convex programming problem !!! The two movies on the right illustrate the impact of the incompressible constraint (numerical experiments of N. Papadakis).

Our first contribution is to show how the method initially proposed is a specific instance of the Douglas-Rachford algorithm. This allows one to use several variations on the initial method, by changing the values of the two relaxation parameters. Our second contribution is the introduction of a staggered grid discretization which is the canonical way to enforce incompressibility constraints. We show how this discretization fits into our proximal splitting methodology by introducing an interpolation operator and either making use of auxiliary variables or primal-dual methods.

Optimal transport of a translated density by different dynamic cost functions depending on the β parameter (computations of N. Papadakis).


Our last contribution includes an exploration of several variations on the original convex transportation objective, the one proposed in, and a specially varying penalization which can be interpreted as replacing the L2 ground cost by a geodesic distance on a Riemannian manifold.

Effects of different dynamical cost functions on real images : interpolation between Gaspard Monge and Leonid Kantorovich (computations of N. Papadakis).