Javascript must be enabled

Matthew Jacobs : A fast approach to optimal transport: the back-and-forth method

Given two probability measures and a transportation cost, the optimal transport problem asks to find the most cost efficient way to transport one measure to the other. Since its introduction in 1781 by Gaspard Monge, the optimal transport problem has found applications in logistics, economics, physics, PDEs, and more recently data science. However, despite sustained attention from the numerics community, solving optimal transport problems has been a notoriously difficult task. In this talk I will introduce the back-and-forth method, a new algorithm to efficiently solve the optimal transportation problem for a general class of strictly convex transportation costs. Given two probability measures supported on a discrete grid with n points, the method computes the optimal map in O(n log(n)) operations using O(n) storage space. As a result, the method can compute highly accurate solutions to optimal transportation problems on spatial grids as large as 4096 x 4096 and 384 x 384 x 384 in a matter of minutes. If time permits, I will demonstrate an extension of the algorithm to the simulation of a class of gradient flows. This talk is joint work with Flavien Leger.

Please select playlist name from following

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.


Comments Disabled For This Video