A fast algorithm for matrix balancing
Knight, Philip and Ruiz, Daniel (2013) A fast algorithm for matrix balancing. IMA Journal of Numerical Analysis, 33 (3). pp. 1029-1047. ISSN 0272-4979
![]()
|
PDF (A fast algorithm for matrix balancing)
fastbalance.pdf Preprint Download (223kB)| Preview |
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 Sinkhorn-Knopp. In this paper we derive new algorithms based on inner-outer iteration schemes. We show that Sinkhorn-Knopp 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.
Creators(s): |
Knight, Philip ![]() | Item type: | Article |
---|---|
ID code: | 42589 |
Keywords: | matrix balancing , quadratic convergence , diagonal scaling, Sinkhorn-Knopp algorithm, doubly stochastic matrix, conjugate gradient iteration, Mathematics, Mathematics(all) |
Subjects: | Science > Mathematics |
Department: | Faculty of Science > Mathematics and Statistics |
Depositing user: | Pure Administrator |
Date deposited: | 16 Jan 2013 11:30 |
Last modified: | 05 Mar 2021 04:10 |
URI: | https://strathprints.strath.ac.uk/id/eprint/42589 |
Export data: |