TY - GEN
T1 - Contractions for consensus processes
AU - Liu, J.
AU - Morse, A. S.
AU - Anderson, B. D.O.
AU - Yu, C.
PY - 2011
Y1 - 2011
N2 - 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, S 2S1, 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.
AB - 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, S 2S1, 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.
UR - https://www.scopus.com/pages/publications/84860651162
U2 - 10.1109/CDC.2011.6160989
DO - 10.1109/CDC.2011.6160989
M3 - Conference contribution
AN - SCOPUS:84860651162
SN - 9781612848006
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 1974
EP - 1979
BT - 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
Y2 - 12 December 2011 through 15 December 2011
ER -