Tight bounds on the convergence rate of generalized ratio consensus algorithms

01/31/2019
by   Balázs Gerencsér, et al.
0

The problems discussed in this paper are motivated by the ratio consensus problem formulated and solved in the context of the push-sum algorithm proposed in Kempe et al. (2003), and extended in Bénézit et al. (2010) under the name weighted gossip algorithm. We consider a strictly stationary, ergodic, sequentially primitive sequence of p × p random matrices with non-negative entries (A_n), n > 1. Let x, w ∈ R^p denote a pair of initial vectors, such that w > 0, w ≠ 0. Our objective is to study the asymptotic properties of the ratios e_i^ A_n A_n-1... A_1 x/ e_i^ A_n A_n-1... A_1 w, i=1,...,p, where e_i is the unit vector with a single 1 in its i-th coordinate. The main results of the paper provide upper bounds for the almost sure exponential convergence rate in terms of the spectral gap associated with (A_n). It will be shown that these upper bounds are sharp. In the final section of the paper we present a variety of connections between the spectral gap of (A_n) and the Birkhoff contraction coefficient of the product A_n ... A_1. Our results complement previous results of Picci and Taylor (2013), and Tahbaz-Salehi and Jadbabaie (2010).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset