License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-10735
URL: http://drops.dagstuhl.de/opus/volltexte/2007/1073/
Go to the corresponding Portal


Knight, Philip A. ; Ruiz, Daniel

A Fast Algorithm for Matrix Balancing

pdf-format:
Document 1.pdf (516 KB)


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 iteration schemes. 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:DSP:2007:1073,
  author =	{Philip A. Knight and Daniel Ruiz},
  title =	{A Fast Algorithm for Matrix Balancing},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  year =	{2007},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  number =	{07071},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1073},
  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


DROPS-Home | Fulltext Search | Imprint Published by LZI