A fast algorithm for matrix balancing
A fast algorithm for matrix balancing
复制标题
DOI：
10.1093/imanum/drs019
复制
发表时间：
2013-07-01
影响因子：
2.1
通讯作者：
Ruiz, Daniel
中科院分区：
文献类型：
--
作者：
Knight, Philip A.;Ruiz, Daniel
只要一个正方形非负矩阵A有全支集，那么它就可以是平衡的，也就是说，我们可以找到一个行和列和等于1的对角标度。已经提出了许多算法来实现平衡，其中最著名的是Sinkhorn-Knopp。在本文中，我们推导出新的算法的基础上的内外迭代计划。我们表明，Sinkhorn-Knopp属于这个家庭，但其他成员可以收敛得更快。特别是，我们表明，虽然固定的迭代方法提供很少或没有改善，在许多情况下，一个计划使用预处理共轭梯度法作为内部迭代收敛在低得多的成本（在矩阵向量产品方面）的广泛的矩阵，并成功的情况下，辛霍恩-克诺普算法失败。
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.