Jean-David Benamou

Jean-David Benamou, Brittany D. Froese, Adam M. Oberman

A numerical method for the solution of the elliptic Monge-Ampere Partial Differential Equation, with boundary conditions corresponding to the Optimal Transportation (OT) problem is presented. A local representation of the OT boundary conditions is combined with a finite difference scheme for the Monge-Ampere equation. Newton's method is implemented leading to a fast solver, comparable to solving the Laplace equation on the same grid several times. Theoretical justification for the method is given by a convergence proof in the companion paper (Benamou et al., 2012). In this paper, the algorithm is modified to a simpler compact stencil implementation and details of the implementation are given. Solutions are computed with densities supported on non-convex and disconnected domains. Computational examples demonstrate robust performance on singular solutions and fast computational times.

Jean-David Benamou, Guillaume Carlier, Luca Nenna

Starting from Brenier's relaxed formulation of the incompressible Euler equation in terms of geodesics in the group of measure-preserving diffeomorphisms, we propose a numerical method based on Sinkhorn's algorithm for the entropic regularization of optimal transport. We also make a detailed comparison of this entropic regularization with the so-called Bredinger entropic interpolation problem. Numerical results in dimension one and two illustrate the feasibility of the method.

Jean-David Benamou, Francis Collino, Jean-Marie Mirebeau

We introduce a novel discretization of the Monge-Ampere operator, simultaneously consistent and degenerate elliptic, hence accurate and robust in applications. These properties are achieved by exploiting the arithmetic structure of the discrete domain, assumed to be a two dimensional cartesian grid. The construction of our scheme is simple, but its analysis relies on original tools seldom encountered in numerical analysis, such as the geometry of two dimensional lattices, and an arithmetic structure called the Stern-Brocot tree. Numerical experiments illustrate the method's efficiency.

Jean-David Benamou, Brittany D. Froese, Adam M. Oberman

In this work we present a numerical method for the Optimal Mass Transportation problem. Optimal Mass Transportation (OT) is an active research field in mathematics.It has recently led to significant theoretical results as well as applications in diverse areas. Numerical solution techniques for the OT problem remain underdeveloped. The solution is obtained by solving the second boundary value problem for the MA equation, a fully nonlinear elliptic partial differential equation (PDE). Instead of standard boundary conditions the problem has global state constraints. These are reformulated as a tractable local PDE. We give a proof of convergence of the numerical method, using the theory of viscosity solutions. Details of the implementation and a fast solution method are provided in the companion paper arXiv:1208.4870.

Jean-David Benamou, Vincent Duval

We present an adaptation of the MA-LBR scheme to the Monge-Amp{è}re equation with second boundary value condition, provided the target is a convex set. This yields a fast adaptive method to numerically solve the Optimal Transport problem between two absolutely continuous measures, the second of which has convex support. The proposed numerical method actually captures a specific Brenier solution which is minimal in some sense. We prove the convergence of the method as the grid stepsize vanishes and we show with numerical experiments that it is able to reproduce subtle properties of the Optimal Transport problem.

Jean-David Benamou, Brittany D. Froese

We consider the Monge-Kantorovich optimal transportation problem between two measures, one of which is a weighted sum of Diracs. This problem is traditionally solved using expensive geometric methods. It can also be reformulated as an elliptic partial differential equation known as the Monge-Ampere equation. However, existing numerical methods for this non-linear PDE require the measures to have finite density. We introduce a new formulation that couples the viscosity and Aleksandrov solution definitions and show that it is equivalent to the original problem. Moreover, we describe a local reformulation of the subgradient measure at the Diracs, which makes use of one-sided directional derivatives. This leads to a consistent, monotone discretisation of the equation. Computational results demonstrate the correctness of this scheme when methods designed for conventional viscosity solutions fail.

Jean-David Benamou, Guillaume Carlier, Simone Di Marino et al.

We propose a new viewpoint on variational mean-field games with diffusion and quadratic Hamiltonian. We show the equivalence of such mean-field games with a relative entropy minimization at the level of probabilities on curves. We also address the time-discretization of such problems, establish $Γ$-convergence results as the time step vanishes and propose an efficient algorithm relying on this entropic interpretation as well as on the Sinkhorn scaling algorithm.

Jean-David Benamou, Guillaume Carlier, Luca Nenna

In this paper, we present a numerical method, based on iterative Bregman projections, to solve the optimal transport problem with Coulomb cost. This is related to the strong interaction limit of Density Functional Theory. The first idea is to introduce an entropic regularization of the Kantorovich formulation of the Optimal Transport problem. The regularized problem then corresponds to the projection of a vector on the intersection of the constraints with respect to the Kullback-Leibler distance. Iterative Bregman projections on each marginal constraint are explicit which enables us to approximate the optimal transport plan. We validate the numerical method against analytical test cases.

Jean-David Benamou, Guillaume Carlier, Marco Cuturi et al.

This article details a general numerical framework to approximate so-lutions to linear programs related to optimal transport. The general idea is to introduce an entropic regularization of the initial linear program. This regularized problem corresponds to a Kullback-Leibler Bregman di-vergence projection of a vector (representing some initial joint distribu-tion) on the polytope of constraints. We show that for many problems related to optimal transport, the set of linear constraints can be split in an intersection of a few simple constraints, for which the projections can be computed in closed form. This allows us to make use of iterative Bregman projections (when there are only equality constraints) or more generally Bregman-Dykstra iterations (when inequality constraints are in-volved). We illustrate the usefulness of this approach to several variational problems related to optimal transport: barycenters for the optimal trans-port metric, tomographic reconstruction, multi-marginal optimal trans-port and in particular its application to Brenier's relaxed solutions of in-compressible Euler equations, partial un-balanced optimal transport and optimal transport with capacity constraints.