The Sinkhorn-Knopp algorithm: Convergence and applications. (English) Zbl 1166.15301
Summary: As long as a square nonnegative matrix \(A\) contains sufficient nonzero elements, then the Sinkhorn-Knopp algorithm [R. Sinkhorn and P. Knopp, Pac. J. Math. 21, 343–348 (1967; Zbl 0152.01403)] can be used to balance the matrix, that is, to find a diagonal scaling of \(A\) that is doubly stochastic. It is known that the convergence is linear, and an upper bound has been given for the rate of convergence for positive matrices.
In this paper, we give an explicit expression for the rate of convergence for fully indecomposable matrices. We describe how balancing algorithms can be used to give a measure of web page significance. We compare the measure with some well known alternatives, including PageRank. We show that, with an appropriate modification, the Sinkhorn-Knopp algorithm is a natural candidate for computing the measure on enormous data sets.
In this paper, we give an explicit expression for the rate of convergence for fully indecomposable matrices. We describe how balancing algorithms can be used to give a measure of web page significance. We compare the measure with some well known alternatives, including PageRank. We show that, with an appropriate modification, the Sinkhorn-Knopp algorithm is a natural candidate for computing the measure on enormous data sets.
MSC:
15B48 | Positive matrices and their generalizations; cones of matrices |
15B51 | Stochastic matrices |
65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
65F35 | Numerical computation of matrix norms, conditioning, scaling |