Contractions for consensus processes
J. Liu, A. Stephen Morse, Brian D. O. Anderson, Changbin Brad Yu · 2011
Many distributed control algorithms of current interest can be modeled by linear recursion equations of the form x(t + 1) = M(t)x(t), t ≥ 1 where each M(t) is a real-valued “stochastic” or “doubly stochastic” matrix. Convergence of such recursions often reduces to deciding when the sequence of matrix productsM(1), M(2)M(1), M(3)M(2)M(1), … converges. Certain types of stochastic and doubly stochastic matrices have the property that any sequence of products of such matrices of the form S1, S2S1, S3S2S1, … converges exponentially fast. We explicitly characterize the largest classes of stochastic and doubly stochastic matrices with positive diagonal entries which have these properties. The main goal of this paper is to find a “semi-norm” with respect to which matrices from these “convergability classes” are contractions. For any doubly stochastic matrix S such a semi-norm is identified and is shown to coincide with the second largest singular value of S.