The Sinkhorn-Knopp algorithm: convergence and applications

Research output: Contribution to journalArticlepeer-review

192 Citations (Scopus)
231 Downloads (Pure)


As long as a square nonnegative matrix A contains sufficient nonzero elements, then the Sinkhorn-Knopp algorithm 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 modi. cation, the Sinkhorn-Knopp algorithm is a natural candidate for computing the measure on enormous data sets.
Original languageEnglish
Pages (from-to)261-275
Number of pages15
JournalSIAM Journal on Matrix Analysis and Applications
Issue number1
Early online date5 Mar 2008
Publication statusPublished - 2008


  • matrix balancing
  • Sinkhorn-Knopp algorithm
  • PageRank
  • doubly stochastic matrix


Dive into the research topics of 'The Sinkhorn-Knopp algorithm: convergence and applications'. Together they form a unique fingerprint.

Cite this