Jun Kitagawa : A damped Newton algorithm for semi-discrete optimal transport

Posted by Youngjoon Hong , part of the Analysis and Applied Mathematics Seminar.

At

March 6, 2017, 4 p.m.

In

SEO 636

Abstract

We consider a damped Newton algorithm to calculate the transport map of semi-discrete optimal transport problems, where the initial measure is absolutely continuous while the target measure is discrete. For costs satisfying standard conditions arising in the regularity theory of optimal transport, and initial measures with Hölder continuous density and support satisfying some mild connectivity conditions, we show this algorithm enjoys global linear and local superlinear convergence. A key ingredient in the proof comes from PDE theory, and involves Loeper’s geometric interpretation of the Ma-Trudinger-Wang conditions. This is joint work with Quentin Mérigot and Boris Thibert.