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

Alejandro D. Dominguez-Garcia; Christoforos N. Hadjicostis

doi:10.1109/CDC.2014.7039890

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

Alejandro D. Dominguez-Garcia, Christoforos N. Hadjicostis

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

Abstract

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.

Original language	English (US)
Title of host publication	53rd IEEE Conference on Decision and Control,CDC 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3240-3245
Number of pages	6
Edition	February
ISBN (Electronic)	9781479977468
DOIs	https://doi.org/10.1109/CDC.2014.7039890
State	Published - 2014
Event	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States Duration: Dec 15 2014 → Dec 17 2014

Publication series

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

Other

Other	2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Country/Territory	United States
City	Los Angeles
Period	12/15/14 → 12/17/14

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Online availability

10.1109/CDC.2014.7039890

Library availability

Discover UIUC Full Text

Cite this

Dominguez-Garcia, A. D., & Hadjicostis, C. N. (2014). Convergence rate of a distributed algorithm for matrix scaling to doubly stochastic form. In 53rd IEEE Conference on Decision and Control,CDC 2014 (February ed., pp. 3240-3245). [7039890] (Proceedings of the IEEE Conference on Decision and Control; Vol. 2015-February, No. February). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2014.7039890

Convergence rate of a distributed algorithm for matrix scaling to doubly stochastic form. / Dominguez-Garcia, Alejandro D.; Hadjicostis, Christoforos N.

53rd IEEE Conference on Decision and Control,CDC 2014. February. ed. Institute of Electrical and Electronics Engineers Inc., 2014. p. 3240-3245 7039890 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2015-February, No. February).

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

Dominguez-Garcia, AD & Hadjicostis, CN 2014, Convergence rate of a distributed algorithm for matrix scaling to doubly stochastic form. in 53rd IEEE Conference on Decision and Control,CDC 2014. February edn, 7039890, Proceedings of the IEEE Conference on Decision and Control, no. February, vol. 2015-February, Institute of Electrical and Electronics Engineers Inc., pp. 3240-3245, 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014, Los Angeles, United States, 12/15/14. https://doi.org/10.1109/CDC.2014.7039890

Dominguez-Garcia AD, Hadjicostis CN. Convergence rate of a distributed algorithm for matrix scaling to doubly stochastic form. In 53rd IEEE Conference on Decision and Control,CDC 2014. February ed. Institute of Electrical and Electronics Engineers Inc. 2014. p. 3240-3245. 7039890. (Proceedings of the IEEE Conference on Decision and Control; February). https://doi.org/10.1109/CDC.2014.7039890

Dominguez-Garcia, Alejandro D. ; Hadjicostis, Christoforos N. / Convergence rate of a distributed algorithm for matrix scaling to doubly stochastic form. 53rd IEEE Conference on Decision and Control,CDC 2014. February. ed. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 3240-3245 (Proceedings of the IEEE Conference on Decision and Control; February).

@inproceedings{08b0c9a59dfb40cb956c4f0eb40267ae,

title = "Convergence rate of a distributed algorithm for matrix scaling to doubly stochastic form",

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

author = "Dominguez-Garcia, {Alejandro D.} and Hadjicostis, {Christoforos N.}",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 ; Conference date: 15-12-2014 Through 17-12-2014",

year = "2014",

doi = "10.1109/CDC.2014.7039890",

language = "English (US)",

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

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

number = "February",

pages = "3240--3245",

booktitle = "53rd IEEE Conference on Decision and Control,CDC 2014",

address = "United States",

edition = "February",

}

TY - GEN

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

AU - Dominguez-Garcia, Alejandro D.

AU - Hadjicostis, Christoforos N.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84988288850&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988288850&partnerID=8YFLogxK

U2 - 10.1109/CDC.2014.7039890

DO - 10.1109/CDC.2014.7039890

M3 - Conference contribution

AN - SCOPUS:84988288850

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 3240

EP - 3245

BT - 53rd IEEE Conference on Decision and Control,CDC 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014

Y2 - 15 December 2014 through 17 December 2014

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this