Logo

Capacity Constrained Entropic Optimal Transport, Sinkhorn Saturated Domain Out-Summation and Vanishing Temperature 103

16a09fab818e74e97474976af81aa5b5bbd1366f

Speaker

Jean-David Benamou, INRIA-Paris, France

Time

2020.05.15 16:00-17:00

Venue

Online—ZOOM APP

ZOOM Info

Conference ID: 919-1023-6903
PIN Code: 769610

Abstract

I will first briefly review the classical Kantorovich formulation of Optimal Transport, Entropic Optimal Transport and Sinkhorn Algorithm.

I will then present a new method to reduce the computational cost of the Entropic Optimal Transport in the vanishing temperature (ε) limit. As in [Schmitzer, 2016], the method relies on a Sinkhorn continuation “ε-scaling” approach; but instead of truncating out the small values of the Kernel, we rely on the exact “out-summation” of saturated domains for a modified constrained Entropic Optimal problem. The constraint depends on an additional parameter λ. In pratice λ = ε also vanishes and the constraint disappear. Using [Berman, 2017], the convergence the (ε, λ) continuation method based on this modified problem is established. We then show that the saturated domain can be over estimated from the previous larger (ε, λ). On the saturated zone the solution is constant and known and the domain can be “out-summed” (removed) from Sinkhorn algorithm. The computational and cost and memory foot print is shown to be linear thanks again to an estimate given by [Berman, 2017]. This is confirmed on 1-D numerical experiments.

Bio

Jean-David Benamou is a Senior Researcher at INRIA-Paris France. He is currently the Head of the MOKAPLAN research group focusing in particular on numerical methods and applications in Optimal Transportation. His fields of expertise are Optimal Transportation, Linear Wave Propagation / High Frequency models / Geometric Optics, Calculus of Variation, Non-Smooth Optimization, Numerical Analysis and computer implementation of Numerical Methods.

Sponsors

Video