Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport
| hal.structure.identifier | Modélisation et simulation de la propagation des ondes fondées sur des mesures expérimentales pour caractériser des milieux géophysiques et héliophysiques et concevoir des objets complexes [MAKUTU] | |
| dc.contributor.author | THIBAULT, Alexis | |
| hal.structure.identifier | Laboratoire de Mathématiques d'Orsay [LMO] | |
| dc.contributor.author | CHIZAT, Lénaïc | |
| hal.structure.identifier | Institut de Mathématiques de Toulouse UMR5219 [IMT] | |
| hal.structure.identifier | Institut National des Sciences Appliquées - Toulouse [INSA Toulouse] | |
| dc.contributor.author | DOSSAL, Charles | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | PAPADAKIS, Nicolas | |
| dc.date.accessioned | 2024-04-04T02:46:35Z | |
| dc.date.available | 2024-04-04T02:46:35Z | |
| dc.date.issued | 2021 | |
| dc.identifier.issn | 1999-4893 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191566 | |
| dc.description.abstractEn | This article describes a set of methods 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). We first proposed to rely on regularized nonlinear acceleration schemes. In practice, such approaches lead to fast algorithms, but their global convergence is not ensured. Hence, we next proposed a new algorithm with convergence guarantees. The idea is to overrelax the Bregman projection operators, allowing for faster convergence. We proposed a simple method for establishing global convergence by ensuring the decrease of a Lyapunov function at each step. An adaptive choice of the overrelaxation parameter based on the Lyapunov function was constructed. We also suggested a heuristic to choose a suitable asymptotic overrelaxation parameter, based on a local convergence analysis. Our numerical experiments showed a gain in convergence speed by an order of magnitude in certain regimes. | |
| dc.description.sponsorship | Generalized Optimal Transport Models for Image processing - ANR-16-CE33-0010 | |
| dc.language.iso | en | |
| dc.publisher | MDPI | |
| dc.title.en | Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.3390/a14050143 | |
| dc.subject.hal | Statistiques [stat]/Machine Learning [stat.ML] | |
| bordeaux.journal | Algorithms | |
| bordeaux.volume | 14 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 5 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-03212175 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-03212175v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Algorithms&rft.date=2021&rft.volume=14&rft.issue=5&rft.eissn=1999-4893&rft.issn=1999-4893&rft.au=THIBAULT,%20Alexis&CHIZAT,%20L%C3%A9na%C3%AFc&DOSSAL,%20Charles&PAPADAKIS,%20Nicolas&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||