A note on overrelaxation in the Sinkhorn algorithm

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.

MoreLess

Year of publication:	2021
Authors:	Lehmann, Tobias ; von Renesse, Max-K. ; Sambale, Alexander ; Uschmajew, André
Published in:	Optimization Letters. - Berlin, Heidelberg : Springer, ISSN 1862-4480. - Vol. 16.2021, 8, p. 2209-2220
Publisher:	Berlin, Heidelberg : Springer
Subject:	Sinkhorn algorithm \| Matrix scaling \| Overrelaxation \| Optimal transport

More details

Type of publication:	Article
Type of publication (narrower categories):	Article
Language:	English
Other identifiers:	10.1007/s11590-021-01830-0 [DOI]
Source:	EconStor

Persistent link: https://www.econbiz.de/10014501397