Preprint 110/2020

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)
Pages: 10
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.

02.03.2021, 10:32