André Uschmajew (University of Augsburg)

Title: Accelerating operator Sinkhorn iteration with overrelaxation
Abstract: The operator scaling problem is a generalization of the famous matrix scaling problem and admits several important applications. The operator Sinkhorn iteration (OSI) is an iterative algorithm for finding a solution. In the talk we will introduce the basic convergence theory of this method based on the Hilbert metric on positive definite matrices. In addition, we propose accelerated versions of OSI using overrelaxation and investigate their convergence properties. In particular, the local convergence analysis allows to determine the asymptotically optimal relaxation parameter based on Young's classic SOR theorem. For a geodesic version of overrelaxation we also obtain a global convergence result in a specific range of relaxation parameters. Numerical experiments demonstrate that the accelerated methods outperform the original OSI in certain applications.