Abstract
In this short note we propose a new approach for the design and analysis of randomized gossip algorithms which can be used to solve the average consensus problem. We show how that Randomized Block Kaczmarz (RBK) method - a method for solving linear systems - works as gossip algorithm when applied to a special system encoding the underlying network. The famous pairwise gossip algorithm arises as a special case. Subsequently, we reveal a hidden duality of randomized gossip algorithms, with the dual iterative process maintaining a set of numbers attached to the edges as opposed to nodes of the network. We prove that RBK obtains a superlinear speedup in the size of the block, and demonstrate this effect through experiments.
Original language | English (US) |
---|---|
Title of host publication | 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 440-444 |
Number of pages | 5 |
ISBN (Electronic) | 9781509045457 |
DOIs | |
State | Published - Apr 19 2017 |
Event | 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Washington, United States Duration: Dec 7 2016 → Dec 9 2016 |
Publication series
Name | 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings |
---|
Other
Other | 2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 |
---|---|
Country/Territory | United States |
City | Washington |
Period | 12/7/16 → 12/9/16 |
Bibliographical note
Publisher Copyright:© 2016 IEEE.
Keywords
- Average Consensus Problem
- Linear Systems
- Networks
- Randomized Block Kaczmarz
- Randomized Gossip Algorithms
ASJC Scopus subject areas
- Signal Processing
- Computer Networks and Communications