Knight, P.A. (2008) The SinkhornKnopp algorithm : convergence and applications. SIAM Journal on Matrix Analysis and Applications, 30 (1). pp. 261275. ISSN 08954798

PDF (THE SINKHORNKNOPP ALGORITHM: CONVERGENCE AND APPLICATIONS)
skapp.pdf  Draft Version Available under License Unspecified. Download (202kB)  Preview 
Abstract
As long as a square nonnegative matrix A contains sufficient nonzero elements, then the SinkhornKnopp 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 SinkhornKnopp algorithm is a natural candidate for computing the measure on enormous data sets.
Item type:  Article 

ID code:  19685 
Keywords:  matrix balancing, SinkhornKnopp algorithm, PageRank, doubly stochastic matrix, Probabilities. Mathematical statistics, Analysis 
Subjects:  Science > Mathematics > Probabilities. Mathematical statistics 
Department:  Faculty of Science > Mathematics and Statistics 
Depositing user:  Strathprints Administrator 
Date Deposited:  07 Jun 2010 10:21 
Last modified:  21 May 2015 11:41 
URI:  http://strathprints.strath.ac.uk/id/eprint/19685 
Actions (login required)
View Item 