Contractions for consensus processes

J. Liu; A. S. Morse; B. D.O. Anderson; C. Yu

doi:10.1109/CDC.2011.6160989

Contractions for consensus processes

J. Liu^*, A. S. Morse, B. D.O. Anderson, C. Yu

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

17 Citations (Scopus)

Abstract

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 S₁, S ₂S₁, S₃S₂S₁, ⋯ 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.

Original language	English
Title of host publication	2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1974-1979
Number of pages	6
ISBN (Print)	9781612848006
DOIs	https://doi.org/10.1109/CDC.2011.6160989
Publication status	Published - 2011
Event	2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 - Orlando, FL, United States Duration: 12 Dec 2011 → 15 Dec 2011

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
Country/Territory	United States
City	Orlando, FL
Period	12/12/11 → 15/12/11

Access to Document

10.1109/CDC.2011.6160989

Cite this

Liu, J., Morse, A. S., Anderson, B. D. O., & Yu, C. (2011). Contractions for consensus processes. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 (pp. 1974-1979). Article 6160989 (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2011.6160989

@inproceedings{daf72a486b164fe88e3224a1b6f69b61,

title = "Contractions for consensus processes",

abstract = "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.",

author = "J. Liu and Morse, {A. S.} and Anderson, {B. D.O.} and C. Yu",

year = "2011",

doi = "10.1109/CDC.2011.6160989",

language = "English",

isbn = "9781612848006",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1974--1979",

booktitle = "2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011",

address = "United States",

note = "2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011 ; Conference date: 12-12-2011 Through 15-12-2011",

}

Liu, J, Morse, AS, Anderson, BDO & Yu, C 2011, Contractions for consensus processes. in 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011., 6160989, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 1974-1979, 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011, Orlando, FL, United States, 12/12/11. https://doi.org/10.1109/CDC.2011.6160989

Contractions for consensus processes. / Liu, J.; Morse, A. S.; Anderson, B. D.O. et al.
2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011. Institute of Electrical and Electronics Engineers Inc., 2011. p. 1974-1979 6160989 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 - http://www.scopus.com/inward/record.url?scp=84860651162&partnerID=8YFLogxK

U2 - 10.1109/CDC.2011.6160989

DO - 10.1109/CDC.2011.6160989

M3 - Conference contribution

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 -

Contractions for consensus processes

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this