Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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) - Draft Version
Available under License ["licenses_description_unspecified" not defined].

Download (197Kb) | 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.

    Item type: Article
    ID code: 19685
    Keywords: matrix balancing, Sinkhorn-Knopp algorithm, PageRank, doubly stochastic matrix, Probabilities. Mathematical statistics, Analysis
    Subjects: Science > Mathematics > Probabilities. Mathematical statistics
    Department: Faculty of Science > Mathematics and Statistics
    Related URLs:
      Depositing user: Strathprints Administrator
      Date Deposited: 07 Jun 2010 11:21
      Last modified: 05 Sep 2014 13:43
      URI: http://strathprints.strath.ac.uk/id/eprint/19685

      Actions (login required)

      View Item

      Fulltext Downloads: