Picture of a black hole

Strathclyde Open Access research that creates ripples...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of research papers by University of Strathclyde researchers, including by Strathclyde physicists involved in observing gravitational waves and black hole mergers as part of the Laser Interferometer Gravitational-Wave Observatory (LIGO) - but also other internationally significant research from the Department of Physics. Discover why Strathclyde's physics research is making ripples...

Strathprints also exposes world leading research from the Faculties of Science, Engineering, Humanities & Social Sciences, and from the Strathclyde Business School.

Discover more...

The Sinkhorn-Knopp algorithm : convergence and applications

Knight, P.A. (2008) The Sinkhorn-Knopp algorithm : convergence and applications. SIAM Journal on Matrix Analysis and Applications, 30 (1). pp. 261-275. ISSN 0895-4798

[img]
Preview
PDF (THE SINKHORN-KNOPP ALGORITHM: CONVERGENCE AND APPLICATIONS)
skapp.pdf - Preprint
License: Unspecified

Download (202kB) | Preview

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.