A note on overrelaxation in the Sinkhorn algorithm

Tobias Lehmann, Max von Renesse, Alexander Sambale, and André Uschmajew

Contact the author: Please use for correspondence this email.
Submission date: 23. Dec. 2020 (revised version: December 2021)
Pages: 11
Bibtex
Download full preprint: PDF (513 kB)
Link to arXiv: See the arXiv entry of this preprint.

Abstract:
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.