A Fast Approach to Optimal Transport: The Back-and-forth Method

Wednesday, November 11, 2020 - 1:40pm - 2:25pm
Matthew Jacobs (University of California, Los Angeles)
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 large scale optimal transportation problems.

This talk is joint work with Flavien Leger.