
Capacity Constrained Entropic Optimal Transport, Sinkhorn Saturated Domain Out-Summation and Vanishing Temperature
Benamou, Jean-David; Martinet, Mélanie (2020-05), Capacity Constrained Entropic Optimal Transport, Sinkhorn Saturated Domain Out-Summation and Vanishing Temperature. https://basepub.dauphine.fr/handle/123456789/20879
Voir/Ouvrir
Type
Document de travail / Working paperLien vers un document non conservé dans cette base
https://hal.archives-ouvertes.fr/hal-02563022Date
2020-05Éditeur
Cahier de recherche CEREMADE
Ville d’édition
Paris
Pages
49
Métadonnées
Afficher la notice complèteAuteur(s)
Benamou, Jean-DavidCEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Martinet, Mélanie
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Résumé (EN)
We propose 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 of 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 almost linear thanks again to an estimate given by [Berman, 2017]. This is confirmed on 1-D numerical experiments.Mots-clés
Entropic regularization; Sinkhorn Algorithm; Optimal transport; Convex optimizationPublications associées
Affichage des éléments liés par titre et auteur.
-
Benamou, Jean-David; Ijzerman, Wilbert; Rukhaia, Giorgi (2020) Article accepté pour publication ou publié
-
Benamou, Jean-David; Cotter, Colin; Malamut, Hugo (2023) Document de travail / Working paper
-
Benamou, Jean-David; Carlier, Guillaume; Nenna, Luca (2019) Article accepté pour publication ou publié
-
Benamou, Jean-David; Gallouët, Thomas; Vialard, François-Xavier (2019) Article accepté pour publication ou publié
-
Benamou, Jean-David (2021) Article accepté pour publication ou publié