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 (https://doi.org/10.1093/imanum/drs019)

[thumbnail of A fast algorithm for matrix balancing]
Preview
 PDF. Filename: 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.

ORCID iDs

Knight, Philip ORCID logoORCID: https://orcid.org/0000-0001-9511-5692 and Ruiz, Daniel;
  • Item type:Article
    ID code:42589
    Dates:
    Date
    Event
    2013
    Published
    26 October 2012
    Published Online
    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:20 Jan 2023 02:15
    URI:https://strathprints.strath.ac.uk/id/eprint/42589
CORE (COnnecting REpositories)