Show simple item record

dc.contributor.authorThibault, Alexis
dc.contributor.authorChizat, Lénaïc
dc.contributor.authorDossal, Charles
dc.contributor.authorPapadakis, Nicolas
dc.date.accessioned2020-02-03T14:32:18Z
dc.date.available2020-02-03T14:32:18Z
dc.date.issued2017
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20514
dc.language.isoenen
dc.subjectSinkhorn-Knopp Algorithmen
dc.subject.ddc621.3en
dc.titleOverrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transporten
dc.typeCommunication / Conférence
dc.description.abstractenThis article describes a method for quickly computing the solution to the regularized optimal transport problem. It generalizes and improves upon the widely-used iterative Bregman projections algorithm (or Sinkhorn-Knopp algorithm). The idea is to overrelax the Bregman projection operators, allowing for faster convergence. In practice this corresponds to elevating the diagonal scaling factors to a given power, at each step of the algorithm. We propose a simple method for establishing global convergence by ensuring the decrease of a Lyapunov function at each step. An adaptive choice of overrelaxation parameter based on the Lyapunov function is constructed. We also suggest a heuristic to choose a suitable asymptotic overrelaxation parameter, based on a local convergence analysis. Our numerical experiments show a gain in convergence speed by an order of magnitude in certain regimes.en
dc.relation.ispartofdate2017
dc.subject.ddclabelTraitement du signalen
dc.relation.conftitleNIPS'17 Workshop on Optimal Transport & Machine Learningen
dc.relation.confdate2017-12
dc.relation.confcityLong Beachen
dc.relation.confcountryUnited Statesen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-02-03T14:17:45Z
hal.person.labIds91477
hal.person.labIds60
hal.person.labIds1954
hal.person.labIds27730


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record