Knight, Philip A.
The Sinkhorn-Knopp Algorithm:Convergence and Applications
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.
BibTeX - Entry
@InProceedings{knight:DagSemProc.07071.16,
author = {Knight, Philip A.},
title = {{The Sinkhorn-Knopp Algorithm:Convergence and Applications}},
booktitle = {Web Information Retrieval and Linear Algebra Algorithms},
pages = {1--18},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2007},
volume = {7071},
editor = {Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2007/1064},
URN = {urn:nbn:de:0030-drops-10644},
doi = {10.4230/DagSemProc.07071.16},
annote = {Keywords: Matrix balancing, Sinkhorn-Knopp algorithm, PageRank, doubly stochastic matrix}
}
|
Keywords: |
|
Matrix balancing, Sinkhorn-Knopp algorithm, PageRank, doubly stochastic matrix |
|
Seminar: |
|
07071 - Web Information Retrieval and Linear Algebra Algorithms
|
|
Issue date: |
|
2007 |
|
Date of publication: |
|
28.06.2007 |
28.06.2007
