A fast approach to optimal transport: the back-and-forth method
- PDF / 1,368,711 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 143 Views
Numerische Mathematik
A fast approach to optimal transport: the back-and-forth method Matt Jacobs1 · Flavien Léger1 Received: 29 July 2019 / Revised: 1 May 2020 / Accepted: 21 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We present a method to efficiently solve the optimal transportation problem for a general class of strictly convex costs. Given two probability measures supported on a discrete grid with n points we compute the optimal transport map between them in O(n log(n)) operations and O(n) storage space. Our approach allows us to solve optimal transportation problems on spatial grids as large as 4096 × 4096 and 384 × 384 × 384 in a matter of minutes. Mathematics Subject Classification 65K10 · 49M29 · 49N15
1 Introduction The optimal transportation problem was first introduced by Monge in 1781, to find the most cost-efficient way to transport mass from a set of sources to a set of sinks. The theory was modernized and revolutionized by Kantorovich in 1942, who found a key link between optimal transport and linear programming. In recent years, there has been an explosion of interest in optimal transport thanks in part to the discovery of deep connections between the quadratic-cost optimal transport problem and a diverse class of partial differential equations (PDEs) arising in statistical mechanics and fluid mechanics ([3,6,7,17,21] to name just a few of the most prominent results). In addition, optimal transport has become popular in data science (particularly machine learning and image processing), where it provides a very natural way to compare and interpolate probability distributions [1,14].
M.J. and F.L. are supported by AFOSR MURI FA9550-18-1-0502 and ONR N00014-12-1- 0838. M.J. is also supported by NSF DMS-1118971, DARPA FA8750-18-2-0066, and ONR N00014-18-1-2527.
B
Matt Jacobs [email protected] Flavien Léger [email protected]
1
Department of Mathematics, UCLA, Los Angeles 90095, CA, USA
123
M. Jacobs, F. Léger
In this work, we are interested in computing the optimal transport problem for large-scale applications that arise in image processing and in numerical methods for solving PDEs (in both two and three dimensions). For these applications, one needs to accurately compute the optimal transport map on enormous computational domains (millions of grid points or pixels). Up to now, computing the optimal map has been a notoriously difficult task. To the best of our knowledge, all previously known methods for solving the optimal transport problem either do not scale linearly with respect to the problem size [3,5], cannot provide an accurate computation of the optimal map [10], or are only applicable to a limited class of probability densities [4]. Our goal in this paper is to remedy the current situation and provide an efficient and accurate algorithm for computing optimal transport maps. To that end, we introduce a new method for solving optimal transport problems: the back-and-forth method. Given two probability densities μ and ν discretized on a
Data Loading...
