nips nips2005 nips2005-46 nips2005-46-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Benjamin V. Roy, Ciamac C. Moallemi
Abstract: We propose consensus propagation, an asynchronous distributed protocol for averaging numbers across a network. We establish convergence, characterize the convergence rate for regular graphs, and demonstrate that the protocol exhibits better scaling properties than pairwise averaging, an alternative that has received much recent attention. Consensus propagation can be viewed as a special case of belief propagation, and our results contribute to the belief propagation literature. In particular, beyond singly-connected graphs, there are very few classes of relevant problems for which belief propagation is known to converge. 1
[1] C. C. Moallemi and B. Van Roy. Consensus propagation. Technical report, Management Science & Engineering Deptartment, Stanford University, 2005. URL: http://www. moallemi.com/ciamac/papers/cp-2005.pdf.
[2] L. Xiao, S. Boyd, and S. Lall. A scheme for robust distributed sensor fusion based on average consensus. To appear in the proceedings of IPSN, 2005.
[3] C. C. Moallemi and B. Van Roy. Distributed optimization in adaptive networks. In Advances in Neural Information Processing Systems 16, 2004.
[4] J. N. Tsitsiklis. Problems in Decentralized Decision-Making and Computation. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1984.
[5] D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In ACM Symposium on Theory of Computing, 2004.
[6] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms: Design, analysis and applications. To appear in the proceedings of INFOCOM, 2005.
[7] P. Rusmevichientong and B. Van Roy. An analysis of belief propagation on the turbo decoding graph with Gaussian densities. IEEE Transactions on Information Theory, 47(2):745–765, 2001.
[8] S. Tatikonda and M. I. Jordan. Loopy belief propagation and Gibbs measures. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, 2002.
[9] T. Heskes. On the uniqueness of loopy belief propagation fixed points. Neural Computation, 16(11):2379–2413, 2004.
[10] A. T. Ihler, J. W. Fisher III, and A. S. Willsky. Message errors in belief propagation. In Advances in Neural Information Processing Systems, 2005.
[11] G. Forney, F. Kschischang, and B. Marcus. Iterative decoding of tail-biting trelisses. In Proceedings of the 1998 Information Theory Workshop, 1998.
[12] S. M. Aji, G. B. Horn, and R. J. McEliece. On the convergence of iterative decoding on graphs with a single cycle. In Proceedings of CISS, 1998.
[13] Y. Weiss and W. T. Freeman. Correctness of local probability propagation in graphical models with loops. Neural Computation, 12:1–41, 2000.
[14] M. Bayati, D. Shah, and M. Sharma. Maximum weight matching via max-product belief propagation. preprint, 2005.
[15] V. Saligrama, M. Alanyali, and O. Savas. Asynchronous distributed detection in sensor networks. preprint, 2005.
[16] Y. Weiss and W. T. Freeman. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Neural Computation, 13:2173–2200, 2001.
[17] D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, Belmont, MA, 1997.
[18] S. Boyd, P. Diaconis, J. Sun, and L. Xiao. Fastest mixing Markov chain on a path. submitted to The American Mathematical Monthly, 2003.
[19] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Mixing times for random walks on geometric random graphs. To appear in the proceedings of SIAM ANALCO, 2005.
[20] S. Roch. Bounded fastest mixing. preprint, 2004.