License: Creative Commons Attribution 4.0 International 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
Go to the corresponding Portal

Knight, Philip A. ; Ruiz, Daniel

A Fast Algorithm for Matrix Balancing

07071.KnightPhilip.Paper.1073.pdf (0.5 MB)


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

  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 =		{},
  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
Collection: 07071 - Web Information Retrieval and Linear Algebra Algorithms
Issue Date: 2007
Date of publication: 28.06.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI