An efficient numerical algorithm for the L2 optimal transport problem with periodic densities

Abstract

We present an extension of the numerical method of Loeper and Rapetti (2005, Numerical solution of the Monge–Ampère equation by a Newton's algorithm. C.R. Acad. Sci. Paris, I, 319–324) for the Monge–Ampère equation to non-uniform target densities and adopt it to solve the optimal transport problem with quadratic cost. The method employs a damped Newton algorithm to solve the Monge–Ampère equation. We show that the algorithm converges for sufficiently large damping coefficients, for the case where the source and target densities are sufficiently smooth, periodic and bounded away from zero. At each Newton iteration, we solve a non-constant coefficient linear partial differential equation. To improve the efficiency of the procedure, we use an analytically preconditioned fast Fourier transform method coupled with GMRES (Strain, J. (1994) Fast spectrally-accurate solution of variable-coefficients elliptic problems. Proc. Amer. Math. Sci., 122, 843–850) to solve this equation, as opposed to a more straightforward approach based on a second-order finite-difference discretization combined with biconjugate gradient used in the original LOEPER and RAPETTI paper. Finally, we present some numerical experiments in image processing to demonstrate the efficiency of the method.