期刊
IMA JOURNAL OF NUMERICAL ANALYSIS
卷 33, 期 3, 页码 1029-1047出版社
OXFORD UNIV PRESS
DOI: 10.1093/imanum/drs019
关键词
matrix balancing; Sinkhorn-Knopp algorithm; doubly stochastic matrix; conjugate gradient iteration
资金
- Carnegie Trust for the Universities of Scotland
As long as a square non-negative matrix A has total support then it can be balanced, that is, we can find a diagonal scaling of A that has row and column sums equal to one. 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 converges at much lower cost (in terms of matrix-vector products) for a broad range of matrices; and succeeds in cases where the Sinkhorn-Knopp algorithm fails.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据