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: March 2021)
Download full preprint: PDF (483 kB)
Link to arXiv: See the arXiv entry of this preprint.
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.