The Sinkhorn-Knopp Algorithm:Convergence and Applications

Author Philip A. Knight



PDF
Thumbnail PDF

File

DagSemProc.07071.16.pdf
  • Filesize: 0.49 MB
  • 18 pages

Document Identifiers

Author Details

Philip A. Knight

Cite AsGet BibTex

Philip A. Knight. The Sinkhorn-Knopp Algorithm:Convergence and Applications. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07071.16

Abstract

As long as a square nonnegative matrix $A$ contains sufficient nonzero elements, the Sinkhorn-Knopp algorithm can be used to balance the matrix, that is, to find a diagonal scaling of $A$ that is doubly stochastic. We relate balancing to problems in traffic flow and describe how balancing algorithms can be used to give a two sided measure of nodes in a graph. We show that with an appropriate modification, 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

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail