Convergence rate of a distributed algorithm for matrix scaling to doubly stochastic form

摘要

Motivated by matrix scaling applications and, more recently, distributed averaging previous work has considered settings where the interconnections between components in a distributed system are captured by a strongly connected directed graph (digraph) and each component aims to assign assigning weights on its outgoing edges (based on the weights on its incoming edges) so that the corresponding set of weights forms a doubly stochastic matrix. In particular, it has been shown that the system components can obtain a set of weights that form a doubly stochastic matrix via a variety of distributed algorithms. In this paper, we establish that the convergence rate of one such distributed algorithm is linear with rate between zero and one.