Philip Knight : May 17, 2006

The Sinkhorn-Knopp Algorithm: Convergence and Applications.

Abstract

The Sinkhorn-Knopp algorithm recently celebrated its 70th birthday. As long as a square nonnegative matrix A contains sufficient nonzero elements, then the algorithm finds a diagonal scaling of A that is doubly stochastic (or balanced). Its simplicity has lead to its repeated discovery, and we give a brief history of its use. It is known that the convergence of the Sinkhorn-Knopp algorithm is linear and an upper bound has been given for the rate of convergence for positive matrices. We show how to obtain a sharp bound for the rate of convergence for a much wider class of matrices using some straightforward tools of numerical analysis. We then describe how balancing algorithms can be used to give a ranking of web pages, and show that the Sinkhorn-Knopp algorithm is a natural candidate for enormous data sets.
If we have time, we will also outline a new approach to derive superlinear algorithms for balancing matrices.