On Optimal Transport, an elementary introduction and a practical algorithm.

@inproceedings{LevyGM2015,
 abstract = { In this article, I present an introduction to a mathematical theory known as Optimal Transport, that is likely to have important applications for a wide class of problems in scientific computing. I also present the first efficient numerical solution mechanism that computes it in 3D. Optimal Transport is an elegant theory that studies a certain class of optimization problems and gives a natural definition of distances between a very general class of objects (measures). Recent results (due to Brenier, Benamou, Alexandrov, Aurenhammer, Merigot ...) let envision new numerical solution mechanisms that make it possible for the first time to compute it in practice. Similarly to the Fast Fourier Transform that made spectral analysis usable in numerical sciences and engineering, the recent advances that make Optimal Transport computation tractable potentially have a considerable impact on a wide class of applications. This comprises distance measurements, interpolation, 3D morphing/matching, reflector/refractor design, reconstruction of the early state of the universe from observed galaxy clusters, and more generally, new solvers for a certain class of equations. I first give an elementary presentation of some known results on optimal transport and then observe a relation with another problem (optimal sampling). This relation gives simple arguments to study the objective functions that characterize both problems. Based on this observation, I then propose a practical algorithm to compute the optimal transport map between a piecewise linear density and a sum of Dirac masses in 3D. In this semi-discrete setting, Aurenhammer et.al [Aurenhammer et al., 1992] showed that the optimal transport map is determined by the weights of a power diagram. The optimal weights are computed by minimizing a convex objective function with a quasi-Newton method. To evaluate the value and gradient of this objective function, I propose an efficient and robust algorithm, that computes at each iteration the intersection between a power diagram and the tetrahedral mesh that defines the measure µ. The numerical algorithm is experimented and evaluated on several datasets, with up to hundred thousands tetrahedra and one million Dirac masses. I posted an early version of this article on ArXiv [Lévy, 2014a] and published a revised version in e a mathematics journal [Lévy, 2015]. The present version includes new figures and a new introduction to motivate Optimal Transport for practical applications. },
 author = { Levy, Bruno },
 booktitle = { 35th Gocad Meeting - 2015 RING Meeting },
 publisher = { ASGA },
 title = { On Optimal Transport, an elementary introduction and a practical algorithm. },
 year = { 2015 }
}