The Sinkhorn-Knopp algorithm: convergence and applications

Research output: Contribution to journalArticle

68 Citations (Scopus)

Abstract

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.
LanguageEnglish
Pages261-275
Number of pages15
JournalSIAM Journal on Matrix Analysis and Applications
Volume30
Issue number1
Early online date5 Mar 2008
DOIs
Publication statusPublished - 2008

Fingerprint

Rate of Convergence
Positive Matrices
PageRank
Nonnegative Matrices
Square matrix
Balancing
Scaling
Sufficient
Upper bound
Computing
Alternatives

Keywords

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

Cite this

@article{119d8cd3ca884b95b46d5cfbb4dd7d17,
title = "The Sinkhorn-Knopp algorithm: convergence and applications",
abstract = "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.",
keywords = "matrix balancing, Sinkhorn-Knopp algorithm, PageRank, doubly stochastic matrix",
author = "P.A. Knight",
year = "2008",
doi = "10.1137/060659624",
language = "English",
volume = "30",
pages = "261--275",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "1",

}

The Sinkhorn-Knopp algorithm : convergence and applications. / Knight, P.A.

In: SIAM Journal on Matrix Analysis and Applications, Vol. 30, No. 1, 2008, p. 261-275.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The Sinkhorn-Knopp algorithm

T2 - SIAM Journal on Matrix Analysis and Applications

AU - Knight, P.A.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - matrix balancing

KW - Sinkhorn-Knopp algorithm

KW - PageRank

KW - doubly stochastic matrix

U2 - 10.1137/060659624

DO - 10.1137/060659624

M3 - Article

VL - 30

SP - 261

EP - 275

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 1

ER -