DocumentCode :
3693356
Title :
Randomized gossip algorithms for solving Laplacian systems
Author :
Anastasios Zouzias;Nikolaos M. Freris
Author_Institution :
Department of Mathematical and Computational Sciences at IBM-Research Zü
fYear :
2015
fDate :
7/1/2015 12:00:00 AM
Firstpage :
1920
Lastpage :
1925
Abstract :
We consider the problem of solving a Laplacian system of equations Lx = b in a distributed fashion, where L is the Laplacian of the communication graph. Solving Laplacian systems arises in a number of applications including consensus, distributed control, clock synchronization, localization and calculating effective resistances, to name a few. We leverage our analysis on a randomized variant of Kaczmarz´s algorithm to propose a distributed asynchronous gossip algorithm with expected exponential convergence. We quantify the convergence rate depending solely on properties of the network topology, and further propose an accelerated version that scales favorably for larger networks. Our approach naturally extends to least-squares estimation of general linear systems where each row/column is assigned to nodes of a given network. Last but not least, we show that average consensus is a special case in our framework.
Keywords :
"Laplace equations","Computational modeling","Convergence","Algorithm design and analysis","Synchronization","Linear systems","Analytical models"
Publisher :
ieee
Conference_Titel :
Control Conference (ECC), 2015 European
Type :
conf
DOI :
10.1109/ECC.2015.7330819
Filename :
7330819
Link To Document :
بازگشت