• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
View/Open
OTEL.pdf (6.433Mb)
Date
2020-05
Publisher city
Paris
Publisher
Cahier de recherche CEREMADE
Link to item file
https://hal.archives-ouvertes.fr/hal-02563022
Dewey
Analyse
Sujet
Entropic regularization; Sinkhorn Algorithm; Optimal transport; Convex optimization
URI
https://basepub.dauphine.fr/handle/123456789/20879
Collections
  • CEREMADE : Publications
Metadata
Show full item record
Author
Benamou, Jean-David
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Martinet, Mélanie
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Type
Document de travail / Working paper
Item number of pages
49
Abstract (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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.