arXiv:2012.12562 Abstract | arXiv Analytics

arXiv:2012.12562 [math.OC]Abstract References Reviews Resources

A note on overrelaxation in the Sinkhorn algorithm

Tobias Lehmann, Max-K. von Renesse, Alexander Sambale, André Uschmajew

Published 2020-12-23Version 1

We derive an a-priori parameter range for overrelaxation of the Sinkhorn algorithm, which guarantees global convergence and a strictly faster asymptotic local convergence. Guided by the spectral analysis of the linearized problem we pursue a zero cost procedure to choose a near optimal relaxation parameter.

Comments: 8 pages, 1 figure

Categories: math.OC, cs.NA, math.NA, math.ST, stat.TH

Subjects: 65D18, 49Q22

Keywords: sinkhorn algorithm, overrelaxation, strictly faster asymptotic local convergence, optimal relaxation parameter, zero cost procedure

Related articles: Most relevant | Search more

arXiv:2208.03120 [math.OC] (Published 2022-08-05)

Accelerating the Sinkhorn algorithm for sparse multi-marginal optimal transport by fast Fourier transforms

Fatima Antarou Ba, Michael Quellmalz

arXiv:2207.02977 [math.OC] (Published 2022-07-06)

Convergence of the Sinkhorn algorithm when the Schrödinger problem has no solution

Aymeric Baradat, Elias Ventre

arXiv:2410.14104 [math.OC] (Published 2024-10-18)