Distributed Averaging via Lifted Markov Chains

Details Distributed Averaging via Lifted Markov Chains Distributed Averaging via Lifted Markov Chains

2009-08-27

arxiv.org/abs/0908.4073v1

Computer Science

Information Theory

Scientific paper

Motivated by applications of distributed linear estimation, distributed control and distributed optimization, we consider the question of designing linear iterative algorithms for computing the average of numbers in a network. Specifically, our interest is in designing such an algorithm with the fastest rate of convergence given the topological constraints of the network. As the main result of this paper, we design an algorithm with the fastest possible rate of convergence using a non-reversible Markov chain on the given network graph. We construct such a Markov chain by transforming the standard Markov chain, which is obtained using the Metropolis-Hastings method. We call this novel transformation pseudo-lifting. We apply our method to graphs with geometry, or graphs with doubling dimension. Specifically, the convergence time of our algorithm (equivalently, the mixing time of our Markov chain) is proportional to the diameter of the network graph and hence optimal. As a byproduct, our result provides the fastest mixing Markov chain given the network topological constraints, and should naturally find their applications in the context of distributed optimization, estimation and control.

Affiliated with

Also associated with

No associations

Rating

Distributed Averaging via Lifted Markov Chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributed Averaging via Lifted Markov Chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Averaging via Lifted Markov Chains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-412334