Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07071.4
URN: urn:nbn:de:0030-drops-10735
URL: https://drops.dagstuhl.de/opus/volltexte/2007/1073/
Knight, Philip A. ; Ruiz, Daniel
A Fast Algorithm for Matrix Balancing
| pdf-format: |
|
Abstract
As long as a square nonnegative matrix A contains sufficient nonzero elements, then the matrix can be balanced, that is we can find a diagonal scaling of A that is doubly stochastic. A number of algorithms have been proposed to achieve the balancing, the most well known of these being the Sinkhorn-Knopp algorithm. In this paper we derive new algorithms based on inner-outer iterationschemes. We show that the Sinkhorn-Knopp algorithm belongs to this family, but other members can converge much more quickly. In particular, we show that while stationary iterative methods offer little or no improvement in many cases, a scheme using a preconditioned conjugate gradient method as the inner
iteration can give quadratic convergence at low cost.
BibTeX - Entry
@InProceedings{knight_et_al:DagSemProc.07071.4,
author = {Knight, Philip A. and Ruiz, Daniel},
title = {{A Fast Algorithm for Matrix Balancing}},
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/1073},
URN = {urn:nbn:de:0030-drops-10735},
doi = {10.4230/DagSemProc.07071.4},
annote = {Keywords: Matrix balancing, Sinkhorn-Knopp algorithm, doubly stochastic matrix, conjugate gradient iteration}
}
| Keywords: | Matrix balancing, Sinkhorn-Knopp algorithm, doubly stochastic matrix, conjugate gradient iteration | |
| Seminar: | 07071 - Web Information Retrieval and Linear Algebra Algorithms | |
| Issue date: | 2007 | |
| Date of publication: | 28.06.2007 |
