A Fast Algorithm for Matrix Balancing

Authors Philip A. Knight, Daniel Ruiz



PDF
Thumbnail PDF

File

DagSemProc.07071.4.pdf
  • Filesize: 0.5 MB
  • 18 pages

Document Identifiers

Author Details

Philip A. Knight
Daniel Ruiz

Cite AsGet BibTex

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)
https://doi.org/10.4230/DagSemProc.07071.4

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.
Keywords
  • Matrix balancing
  • Sinkhorn-Knopp algorithm
  • doubly stochastic matrix
  • conjugate gradient iteration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail