Dual Methods for Optimal Transport

1 Dual Methods for Optimal Transport Quentin M´erigot Geometric Science of Information 2013, Paris August 28, 2013 LJK / CNRS / Universit´e de Grenoble 2 Computational optimal transport For αi, βj = 1: Hungarian algorithm linear programming General αi, βj: Bertsekas’ auction algorithm αi βj 2 Computational optimal transport For αi, βj = 1: Hungarian algorithm linear programming General αi, βj: Bertsekas’ auction algorithm αi βj Source and target with density: Benamou-Brenier ’00 Loeper-Rapetti ’05 Angenent-Haker-Tannenbaum ’03 Benamou-Froese-Oberman ’12 2 Computational optimal transport For αi, βj = 1: Hungarian algorithm linear programming General αi, βj: Bertsekas’ auction algorithm αi βj Source with density, finite target: Aurenhammer, Hoffmann, Aronov ’98 Oliker-Prussner ’89 Caffarelli-Kochengin-Oliker ’04 Kitagawa ’12 Source and target with density: Benamou-Brenier ’00 Loeper-Rapetti ’05 Angenent-Haker-Tannenbaum ’03 Benamou-Froese-Oberman ’12 3 Optimal transport: Monge’s problem µ = probability measure on X ν = prob. measure on finite Y Monge problem: Tc(µ, ν) := min{Cc(T); T#µ = ν} y with density, X = manifold = y