Consensus propagation

被引：140

作者：

Moallemi, Ciamac C. ^{[1
]}

Van Roy, Benjamin

机构：

[1] Stanford Univ, Dept Elect Engn, Stanford, CA 94305 USA

[2] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2006年 / 52卷 / 11期

基金：

美国国家科学基金会;

关键词：

belief propagation; distributed averaging; distributed consensus; distributed signal processing; Gaussian Markov random fields; max-product algorithm; message-passing algorithms; min-sum algorithm; sum-product algorithm;

D O I：

10.1109/TIT.2006.883539

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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

引用

页码：4753 / 4766

页数：14

共 38 条

[21] Madden S, 2002, FOURTH IEEE WORKSHOP ON MOBILE COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS, P49, DOI 10.1109/MCSA.2002.1017485
[22] Moallemi C. C., 2004, ADV NEURAL INFORM PR, V16
[23] MOALLEMI CC, 2006, CONVERGENCE MINSUM M
[24] Montresor A, 2004, 2004 INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND NETWORKS, PROCEEDINGS, P19
[25] MOOIJ JM, 2005, SUFFICIENT CONDITION
[26] MOSKAOYAMA D, 2005, INFORM DISSEMINATION
[27] The capacity of low-density parity-check codes under message-passing decoding
Richardson, TJ
Urbanke, RL
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2001, 47 (02) : 599 - 618
[28] Bounding fastest mixing
Roch, S
[J]. ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2005, 10 : 282 - 296
[29] An analysis of belief propagation on the turbo decoding graph with Gaussian densities
Rusmevichientong, P
Van Poy, B
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2001, 47 (02) : 745 - 765
[30] Saligrama V., 2005, ASYNCHRONOUS DISTRIB

← 1 2 3 4 →