The Sinkhorn-Knopp Algorithm:Convergence and Applications

Knight, Philip A.

doi:10.4230/DagSemProc.07071.16

Document

The Sinkhorn-Knopp Algorithm:Convergence and Applications

Author Philip A. Knight

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 7071
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2007-06-28

PDF

File

PDF

DagSemProc.07071.16.pdf

Filesize: 0.49 MB
18 pages

Document Identifiers

DOI: 10.4230/DagSemProc.07071.16
URN: urn:nbn:de:0030-drops-10644

Subject Classification

Keywords

Matrix balancing
Sinkhorn-Knopp algorithm
PageRank
doubly stochastic matrix

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Philip A. Knight

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail