DROPS

Document

A Fast Algorithm for Matrix Balancing

Authors: Philip A. Knight and Daniel Ruiz

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)

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.

Cite as

Philip A. Knight and Daniel Ruiz. A Fast Algorithm for Matrix Balancing. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.07071.4},
  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}
}

Document

DOI: 10.4230/DagSemProc.07071.16

The Sinkhorn-Knopp Algorithm:Convergence and Applications

Authors: Philip A. Knight

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)

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

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.07071.16},
  URN =		{urn:nbn:de:0030-drops-10644},
  doi =		{10.4230/DagSemProc.07071.16},
  annote =	{Keywords: Matrix balancing, Sinkhorn-Knopp algorithm, PageRank, doubly stochastic matrix}
}

Search Results

Documents authored by Knight, Philip A.

A Fast Algorithm for Matrix Balancing

Abstract

Cite as

The Sinkhorn-Knopp Algorithm:Convergence and Applications

Abstract

Cite as

Thanks for your feedback!

Could not send message