1

Optimizing Reweighted Belief Propagation for
Distributed Likelihood Fusion Problems

arXiv:1801.09281v2 [cs.SY] 7 Feb 2018

Christopher Lindberg, Julien M. Hendrickx, and Henk Wymeersch

Abstract—Belief propagation (BP) is a powerful tool to solve
distributed inference problems, though it is limited by short
cycles in the corresponding factor graph. Such cycles may lead to
incorrect solutions or oscillatory behavior. Only for certain types
of problems are convergence properties understood. We extend
this knowledge by investigating the use of reweighted BP for
distributed likelihood fusion problems, which are characterized
by equality constraints along possibly short cycles. Through a
linear formulation of BP, we are able to analytically derive convergence conditions for certain types of graphs and optimize the
convergence speed. We compare with standard belief consensus
and observe significantly faster convergence.

I. I NTRODUCTION
ELIEF propagation (BP) [1], [2] is a message-passing algorithm for approximate inference on graphs of problems
that arise in many different fields such as statistical physics,
computer vision, artificial intelligence, optimization, behavioral modeling in social networks, and wireless communications [3]–[6]. Examples of applications to wireless communications include detection problems, localization and tracking,
and decoding [7]–[10]. One of the more notable applications is
iterative decoding algorithms for capacity-approaching errorcorrecting codes, including LDPC and turbo codes. Since
BP is a message-passing algorithm, it is also suitable for
solving distributed problems in networks of cooperating nodes.
Examples include distributed cooperative decision making in
cognitive radio [11], distributed cooperative localization and/or
tracking [8], [12], network synchronization [13], distributed
joint source channel decoding [14], and distributed compressed
sensing [15].
While BP generally works well in practice, convergence can
in general not be guaranteed. This phenomenon is especially
apparent on graphs that have cycles with strong interactions,
with extreme case equality constraints, which force variables
to maintain the same value along a cycle in the graph.
An example of such a setting is the distributed likelihood
fusion problem, where nodes in a network must agree on a
global likelihood function, based on locally available, mutually
independent observations. To mitigate the convergence issues

B

Christopher Lindberg is with Zenuity AB, Gothenburg, Sweden. email:
christopher.lindberg@zenuity.com. Julien M. Hendrickx is with ICTEAM Institute/CORE, Université Catholique de Louvain, Louvain-la-Neuve, Belgium.
email: julien.hendrickx@uclouvain.be. Henk Wymeersch is with the Electrical
Engineering Department, Chalmers University of Technology, Gothenburg,
Sweden. email: henkw@chalmers.se. This work was supported, in part, by
the European Research Council under Grant No. 258418 (COOPNET), and by
the DYSCO (dynamical systems, control, and optimization) network, funded
by the Interuniversity Attraction Poles Programme, initiated by the Belgian
Federal Science Policy Office, and by the Concerted Research Action (ARC)
of the French Community of Belgium.

for such problems, one can apply a variation of BP [16]–
[21] or apply methods from the field of distributed consensus
[22], [23]. In the first class, [16], [17] introduced the treereweighted BP (TRW-BP), which optimizes convex combinations of cycle-free graphs (tree-graphs) to represent the
original graph problem, leading to promising performance at
a cost of solving of a high-dimensional optimization problem
over spanning trees. The uniformly reweighted BP (URW-BP)
algorithm [18], [19] is a special case of TRW-BP that involves optimization over one parameter, lending itself well for
implementation in network settings, or where computational
efficiency is prioritized. URW-BP variations were applied to
improve decoding performance of LDPC codes in [20], [21].
In the second class, distributed likelihood fusion is solved
using distributed consensus methods, leading to approaches
commonly termed belief consensus: [22] proposes a distributed
consensus method, whereby the convergence speed depends
on a single scalar parameter, which depends on the maximum
node degree. A fast version of such belief consensus was
proposed in [23] using Metropolis-type weights, which can
be locally computed. However, such consensus methods are
generally slow on tree graphs for which BP works well.
In this paper, we cast URW-BP as a linear system (similar
to the linear BP expressions in [24]), allowing eigen-analysis.
Our contributions are summarized in three parts as follows:
(i) We show that for a certain class of network inference
problems (i.e., likelihood fusion problems) and certain network
topologies (i.e., trees, k-regular graphs, and variations of
the latter), both belief consensus and URW-BP can achieve
convergence to the correct beliefs; (ii) In such cases, we can
analytically optimize the URW-BP parameter to maximize the
convergence rate, outperforming belief consensus; (iii) As a
side-result, we recover a new way to prove the finite-time
convergence of BP on trees.
The remainder of the paper is organized as follows: In
Section II we formalize the distributed likelihood fusion
problem. Section III introduces the algorithms which are used
to solve the problem. Section IV deals with the tools we
use to analyze the convergence behavior of these algorithms.
In Section V, we present the convergence analysis of the
algorithms on tree graphs and k-regular graphs respectively. In
Section VI we present results from numerical simulations, and
some discussion of those. We conclude the paper in Section
VII.
Notation
We use boldface lowercase letters x for column vectors, and
boldface uppercase letters X for matrices. In particular, I M

2

denotes an M ×M identity matrix, OM denotes an M ×M all
zero matrix, 1 is the all one vector of appropriate size, and 0
is the all zero vector of appropriate size. Sets are described by
calligraphic letters X and the cardinality of a set is denoted
by |X |. The transpose of a vector is denoted by [·]T . The
indicator function
P of a statement P is written as I{P} ∈ {0, 1}.
We denote by ∼xi f (x) the summation over all elements in
x, except xi .
II. P ROBLEM F ORMULATION
We consider a network consisting of N connected nodes
which we model by an undirected graph G = (V, E), where
V is the set of nodes and E is the set of edges connecting
the nodes. Associated with the graph G is the adjacency
matrix A with entries Aij = I{(i,j)∈E} , the degree matrix
D = diag(A1), and the Laplacian matrix L = D − A. For
later use, let µ1 , . . . , µN be the eigenvalues of A sorted such
that |µ1 | ≥ |µ2 | ≥ · · · ≥ |µN |. We consider three types of
graphs:
(i) Tree-graphs: The set of edges E connects all the vertices
(nodes) in V such that there are no cycles. Nodes connected to exactly one node are called leaves.
(ii) k-regular graphs: All nodes are connected to exactly k
other nodes.
(iii) General connected graphs: There is no constraint on the
edge set, provided the graph is connected.
The aim of the network is to determine the posterior distribution over a variable θ given independent local observations
yn , at each node n. Hence, each node has access to a local
likelihood function p(yn |θ) where the likelihood functions are
conditionally independent given θ, and it is also assumed that
each node knows the prior distribution p(θ). The posterior
distribution can be factorized as
p(θ|y1 , . . . , yN ) ∝ p(θ)

N
Y

m=1

or equivalently in the log-domain as

log p(θ|y1 , . . . , yN ) ∝ log p(θ) +

p(ym |θ),

N
X

m=1

log p(ym |θ).

rule specified by the algorithm. Let the initial state of the
consensus algorithm of node n be its local likelihood function,
(0)
i.e., xn (θ) = log p(yn |θ). The network updating dynamics
are described by
x(ℓ) (θ) = W x(ℓ−1) (θ),

(3)

where W is an appropriately chosen matrix, with Wnm = 0
when (m, n) ∈
/ E. Examples include Metropolis weighting,
where weighting is decided by all nodes determining its
outgoing weights and self-weight by


{|Nn | , |Nm |} + 1) (n, m) ∈ E
1/ (max
P
(4)
Wnm = 1 − u∈Nn Wnu
m=n


0
otherwise.

or uniform-weight consensus, where


(n, m) ∈ E
ξ
Wnm = 1 − ξ |Nn | m = n


0
otherwise.

(5)

If ξ is chosen as 0 < ξ < 1/ maxm |Nm | , then W in either
(4) or (5) is a doubly stochastic matrix with one
√ eigenvalue 1
(with corresponding normalized eigenvector 1/ N ), while all
other eigenvalues are strictly smaller than 1 in absolute value.
Hence, the convergence rate of belief consensus is determined
by the second largest eigenvalue of W . Moreover, it can be
shown that for any node n
lim

ℓ→∞

x(ℓ)
n (θ)

N
N
1 X
1 X (0)
x (θ) =
log p(ym |θ),
=
N m=1 m
N m=1

(6)

from which after multiplication with N , adding log p(θ) and
taking exponentials, p(θ|y) can be determined at each node.

(1)
B. Uniformly Reweighted Belief Propagation Consensus

(2)

We assume that θ is a discrete random variable that can only
take on K distinct values.

When expressing (1) as a factor graph, we obtain a graph
with a star topology, irrespective of the network graph. This
is shown in Fig. 1: Fig. 1–(a) shows a network graph and
Fig. 1–(b) shows the corresponding factor graph. Thus the
structure of the factor graph does not match the node graph
G. In order to obtain a factor graph that matches the topology
of the graph in Fig. 1–(a), we introduce

III. T WO S OLUTION A PPROACHES
In this section, we describe techniques that can be used to
compute the posterior distribution from the local likelihood
functions at each node in a distributed manner: belief consensus and belief propagation.
A. Belief Consensus
The problem in (2) can be solved by reaching consensus on
the average of the log-likelihood functions, and multiplying
the consensus value by the number of nodes. The belief
consensus algorithm aims to compute the consensus value by
letting the nodes iteratively exchange information with their
neighbors and updating their state according to an update

f (θ1 , . . . , θN ) =

N
Y

m=1

p(ym |θm )

Y

I{θm =θn } ,

(7)

(m,n)∈E

which is shown in Fig. 1–(c). The marginal of this function
with respect to θm is given by
fm (θm ) =

X

∼θm

f (θ1 , . . . , θN ) =

N
Y
l=1

p(yl |θm ),

(8)

so that for any θ, fm (θ) = fn (θ), allowing every node
to determine the posterior by multiplying fm (θ) with p(θ).
The functions fm (θ) can be computed using message-passing
algorithms, such as BP or URW-BP. The initial belief of node

3

Communication graph

Normal factor graph
θ1

θ

2

3

Modified factor graph
θ2

θ3

θ4

θ5

1

=
p(y1 |θ) p(y2 |θ) p(y3 |θ) p(y4 |θ) p(y5 |θ)

4

=

=

=

p(y1 |θ1 ) p(y2 |θ2 ) p(y3 |θ3 ) p(y4 |θ4 ) p(y5 |θ5 )

5
y1

y2

(a)

y3

y4

(0)

m∈Nn

x(ℓ−2)
(θ)
n

X

+ρ

(x(ℓ−1)
(θ)
m

m∈Nn

−

x(ℓ−2)
(θ)),
n

(10)

for ℓ > 1, where ρ ∈ (0, 1) is the reweighting parameter
of URW-BP (where standard BP corresponds to ρ = 1).
We call the resulting algorithm uniformly reweighted belief
propagation consensus (URW-BPC), due to its linear update
resembling a consensus algorithm. Defining the 2N × 2N
URW-BPC matrix


ρA IN − ρD
,
(11)
Pρ =
IN
ON
the update rule in matrix form for URW-BPC for ℓ > 1 is
 (ℓ−1)



x
(θ)
(12)
x(ℓ) (θ) = IN ON Pρ
x(ℓ−2) (θ)
 (1)



x (θ)
.
(13)
= IN ON Pρℓ−1
x(0) (θ)
The convergence behavior depends on the power series of the
update matrix Pρ .
Remark 1. We note that, due to (9), it holds that




ρA + IN
x(0) (θ), (14)
x(ℓ) (θ) = IN ON Pρℓ−1
IN

which can equivalently be expressed as
x

(ℓ)

(θ) =



IN

y2

y3

ON



y4

y5

(c)

original factor graph structure of the centralized problem (the left of the factor graphs), with one θ, is transformed into
distributed problem (the graph on the right side), as described in Section III-B, with factor vertices as gray boxes and
Note that the connections between the equality factors and the θn ’s are decided by the edge set E. The communication
how these edges map to edges in the modified factor graph.

n in the log-domain is xn (θ) = log p(yn |θ). By applying the
URW-BP rules in the log-domain, we find (see Appendix I)
X
(0)
x(1)
x(0)
(9)
n (θ) = xn (θ) + ρ
m (θ)
=

y1

(b)

Figure 1. This figure shows how the
the factor graph of its corresponding
variable vertices as light gray circles.
links are highlighted in blue to show

x(ℓ)
n (θ)

y5

Pρℓ−1

(Pρ + I2N )

IV. G ENERAL C ONVERGENCE R ESULTS



FOR

x(0) (θ)
0



.

(15)

URW-BPC

Since URW-BPC results in an update rule that can be
described in terms of a matrix-vector multiplication, the
convergence behavior depends on how the power series Pρℓ

behaves as ℓ grows large, which will here be analyzed. First,
we establish the fact that λ1 = 1 is an eigenvalue of any Pρ ,
and give its corresponding right and left eigenvectors.
Proposition 2. For any URW-BPC matrix Pρ there is one
eigenvalue λ1 = 1 with geometric multiplicity 1. Its corresponding
 T Tright and
left eigenvectors are b1 = 1, and
T
cT
=
1
,
1
−
ρ1
D
, respectively.
1

Proof: See Appendix II-A.
Hence, if all other eigenvalues are strictly less than 1, the
convergence of URW-BPC is guaranteed. In contrast to the
W matrix in belief consensus, the matrix Pρ may not be
diagonalizable. Hence, we must consider two cases before
providing general convergence conditions.

A. Case 1: Diagonalizable Pρ
If Pρ is a diagonalizable matrix, then by eigendecomposition we have that Pρℓ = BΛℓ B −1 , where the columns of
B form an eigenbasis of Pρ and Λ is a matrix with the
eigenvalues of Pρ on the diagonal. Let
z (0) (θ) =



ρA + IN
IN



x(0) (θ),

(16)

and express z (0) (θ) in the eigenbasis of Pρ as z (0) (θ) = Bα.
Now we see that
z (ℓ) (θ) = Pρℓ z (0) (θ) = BΛℓ B −1 Bα = BΛℓ α.

(17)

We can also express this as
z (ℓ) (θ) =

2N
X
i=1

λℓi bi αi ,

(18)

4

where λi is the ith eigenvalue of Pρ , bi is the ith eigenvector
of Pρ (and the ith column of B), and αi is the ith element
of α. Since according to Proposition 2, λ1 = 1, so that
z (ℓ) (θ) = b1 α1 +

2N
X

λℓi bi αi

(19)

i=2

= b1 α1 + ε.

(20)

Later, in Proposition 3 we will establish that α1 is the sought
value, therefore we consider ε to be an error term.

B. Case 2. Nondiagonalizable Pρ
If Pρ is not diagonalizable, it can be decomposed in its
Jordan normal form. Then, Pρ = BJB −1 , where the columns
of B are the generalized eigenvectors of Pρ forming a Jordan
basis, and J is a Jordan matrix, which is a block diagonal
matrix with M < 2N Jordan blocks on its diagonal, i.e.,


J1 0
0


J =  0 ...
(21)
0 .
0

0

JM

Each Jordan block corresponds to a certain eigenvalue and its
generalized eigenvectors. For example, if the eigenvalue λm
has three generalized eigenvectors, bm,1 , bm,2 and bm,3 , then


λm 1
0
Jm =  0 λm 1  .
0
0 λm

Note that if Pρ is diagonalizable, its Jordan normal form is
equal to its eigendecomposition. By expressing z (0) (θ) = Bα
in the Jordan basis of Pρ and decomposing Pρ in Jordan
normal form, we can write
z (ℓ) (θ) = Pρℓ z (0) (θ) = BJ ℓ α,

(22)

which we can also express as



min(ℓ,rm −j) 
rm
M X
X
X
ℓ
 bm,j αm,j ,

λℓ−i
z (ℓ) (θ) =
m
i
m=1 j=1

i=0

(24)

= b1 α1 + ε̃ + ε.

We are now able to provide insights into α1 as well as the
error terms ε̃ and ε.
(ℓ)

(ℓ)
Proposition 3. The quantity α1 = cT
(θ)/(cT
1z
1 b1 ) is
preserved by the URW-BPC algorithm at each iteration ℓ.
If URW-BPC converges, then the consensus value is the
preserved quantity, and it is equal to

α1 =

2
cT
1 b1

(25)

Following the reasoning of the case with a diagonalizable Pρ ,
any quantity that is not α1 is considered an error term. For
the nondiagonalizable case, we split it up into ε and ε̃, since
these two terms behave fundamentally different with respect
to the eigenvalues of Pρ .

1T x(0) (θ) .

(26)

Proof: See Appendix II-B.
Note according to Proposition 2
cT
1 b1 = 2N − ρ trace(D).

(27)

Hence, what remains is to establish sufficient conditions for
URW-BPC to converge and then to establish the corresponding
convergence rate. We note the following:
(i) When Pρ has an eigenvalue λ = −1 with equal geometric
and algebraic multiplicities, the corresponding value αi
in (19) or αm,j in (23) is zero, since the eigenvector of
λ = −1 is in the null space of Pρ + I2N and is thus
canceled out by the initialization (15).
(ii) When Pρ is diagonalizable, there is only one eigenvalue
λ1 = 1. If all other eigenvalues are strictly inside the unit
circle, or equal to −1 with equal geometric and algebraic
multiplicities, then ε → 0 and convergence of URW-BPC
(14) is guaranteed to (26) by Proposition 3.
(iii) When Pρ is not diagonalizable, if λ1 has a Jordan block
of size 1 × 1 and all other eigenvalues are strictly inside
the unit circle, or equal to −1 with equal geometric
and algebraic multiplicities, then ε̃ = 0, ε → 0, and
convergence of URW-BPC (14) is guaranteed to (26) by
Proposition 3.
Finally, the convergence rate is defined as

i=0

(23)
where rm is the size of the mth Jordan block, bm,j is the jth
generalized eigenvector of λm , and αm,j the corresponding
entry in α. With λ1 = 1 and denoting b1,1 α1,1 by b1 α1 , we
can break the sum into three parts
r1 min(ℓ,r
X1 −j)  ℓ 
X
(ℓ)
b1,j α1,j
z (θ) = b1 α1 +
i
i=0
j=2



min(ℓ,rm −j) 
rm
M X
X
X
ℓ
 bm,j αm,j

λℓ−i
+
m
i
m=2 j=1

C. General Convergence Conditions

r (Pρ ) =

sup

lim

x(0) (θ)6=c1 ℓ→∞

x(ℓ) (θ) − c1

x(0) (θ) − c1

2
2

!1/ℓ

,

(28)

provided that the algorithm is convergent, and at least one
eigenvalue strictly inside the unit circle is nonzero. For such
cases, we consider the eigenvalues of Pρ to be sorted such
that |λ1 | ≥ |λ2 | ≥ · · · ≥ |λ2N |. The convergence rate is
determined by |λ̃| where λ̃ = maxi |λi | for i such that |λi | <
1, such that a smaller |λ̃| gives a faster convergence.
V. C ONVERGENCE

ON

S PECIFIC G RAPH T YPES

In this section, we analyze the convergence properties
of URW-BPC for three specific types of graphs. We first
consider tree-graphs, recovering the well-known finite-time BP
convergence result via the formulation (15). Then, we consider
the regular graphs, for which BP is generally not guaranteed
to converge. Finally, we consider general connected graphs,
for which we can build on the results from regular graphs.

5

A. Tree Graphs
For trees, the following proposition establishes the possible
eigenvalues of P1 .
Proposition 4. The URW-BPC matrix P1 of any tree-graph
has three distinct eigenvalues: λ1 = 1, λ2 = −1, and λi = 0
for i = 3, . . . , 2N .
Proof: See Appendix II-C.
We then immediately find the following well-known results
for trees, that BP converges in a finite number of iterations.
Theorem 5. If G is a tree graph of N nodes, then URW-BPC
with P1 converges to consensus after at most 2N −3 iterations.
Moreover, with the initialization as in (14), the consensus value
after κ iterations (κ such that consensus is reached) is
x(κ) (θ) =

N
X

x(0)
m (θ)1.

(29)

We conclude that for λi = 0, we must have that kρ = 1. Note
however, that this does not mean that all eigenvalues are equal
to 0 for ρ = 1/k.
Now, since µ1 = k, the magnitude of λ1 of Pρ is either 1
or |ρk − 1|. Thus, we can prove the following result regarding
the convergence conditions of URW-BPC.
Theorem 7. For any k-regular graph, URW-BPC is convergent if and only if ρ ∈ (0, 2/k), and the asymptotic consensus
value is
lim x(ℓ) (θ) =

ℓ→∞

N
X
1
x(0) (θ) 1.
N (1 − ρk/2) m=1 m

(33)

Proof: See Appendix III-B.
This result provides the interval for ρ within which we
can guarantee convergence, and to which value the algorithm
converges.

m=1

Proof: Due to Proposition 4, P1 has 2N − 2 eigenvalues
λ = 0. Hence, the largest possible size of its corresponding
Jordan block, denoted by J0 , is 2N − 2. Since J02N −2 = O,
the error contribution from the eigenvalues equal to zero is
zero after at most 2N − 3 iterations. Furthermore, applying
the results from Propositions 2 and 3, and using the fact that
the sum of the degrees trace(D) = 2N − 2 for undirected
tree-graphs in (27), the consensus value α1 is given by (29).

2) Optimizing the Convergence Rate: In order to maximize
convergence rate, we show which ρ minimizes the largest
eigenvalue within the unit circle, denoted by |λ̃| < 1.
Theorem 8. The choice of ρ that minimizes |λ̃| is

p
2 
ρopt = 2 k − k 2 − µ̃2 ,
µ̃

where µ̃ = maxi |µi | for i such that |µi | < k. The magnitude
of the second largest eigenvalue of Pρopt is
|λ̃| =

B. Regular Graphs
In order to understand when URW-BPC converges, we first
show how to choose the weighting parameter ρ in order to
guarantee convergence. Then we proceed to optimize ρ for a
given graph G such that the magnitude of the largest eigenvalue
inside the unit circle, |λ̃|, is minimized. We recall that for kregular graphs, the largest eigenvalue of the adjacency matrix
is µ1 = k for non-bipartite graphs, while for bipartite graphs,
eigenvalues come in symmetric pairs, so that both µ1 = k and
µ2 = −k are eigenvalues [25, Prop.2.3].
1) Convergence: To find for which ρ URW-BPC converges
on k-regular graphs, we first show how the eigenvalues of Pρ
and A are connected in terms of magnitudes. Note, that the
eigenvalues of Pρ and A are sorted such that |λ1 | ≥ |λ2 | ≥
· · · ≥ |λ2N | and |µ1 | ≥ |µ2 | ≥ · · · ≥ |µN |.
Lemma 6. Let ρ ∈ (0, 1]. Then the eigenvalue λi of Pρ ,
λi 6= 0, can be expressed in terms of µi , and its magnitude is
q
1
(30)
µi ρ + µ2i ρ2 − 4kρ + 4 .
|λi | =
2
Proof: See Appendix III-A.
Note that for λi = 0 with eigenvector [v T , wT ]T , we have
that
ρAv + w − ρDw = 0

v = 0.

(31)
(32)

(34)


p
1
k − k 2 − µ̃2 .
µ̃

(35)

Proof: See Appendix III-C.

Remark 9. For any k-regular non-bipartite graph G, µ̃ = µ2 .
However, for a k-regular bipartite graph we have that µ2 =
−µ1 = −k. Hence, choosing ρopt with µ2 instead of µ̃ in this
case would yield ρopt = 2/k, which in turn gives (see (30)),
2
p
|λi |2 = 1/k 2 µ ± µ2 − k 2 = 1, for every eigenvalue λi
of Pρ . Hence, the optimal reweighting for k-regular bipartite
graphs is achieved with µ̃ = µ3 . Another consequence of
µ2 = −k is that there is always an eigenvalue λ = −1 for
bipartite graphs. This remark also applies to tree-graphs, which
is a class of bipartite graphs, where P1 of a tree-graph has
an eigenvalue λ = −1. However, the component associated
with this eigenvalue is irrelevant, as it is removed by the
initialization procedure. This relies on the following result.
Proposition 10. For a URW-BPC matrix Pρ , the algebraic
and geometric multiplicites of λ = ±1 are equal.
Proof: See Appendix III-D.
3) Limit Results for k-regular Graphs: Due to their structure, the eigenvalue distribution of A for large k-regular graphs
is given by [26] (with G satisfying certain properties regarding
the number of cycles in the graph, for details see [26])

√
 k(4(k−1)−µ2 )1/2
, |µ| ≤ 2 k − 1
2 −µ2 )
2π(k
f (µ) =
(36)
√
0,
|µ| > 2 k − 1.

6

1.50
ut

bc

ut

(37)

so that the second largest eigenvalue of Pρ for non-bipartite
graphs tends to


p
1
k − k 2 − 4 (k − 1) . (38)
lim |λ2,BPC | = √
N →∞
2 k−1

For the belief consensus, |λ2,Metr | of W = IN − ξL tends to
√
1+2 k−1
> lim |λ2,BPC | , (39)
lim |λ2,Metr | =
N →∞
N →∞
k+1
so that BPC always converges faster than belief consensus on
large k-regular graph.

1.25
ut
ut

1.00

0.75
bc

bc

0.50

bc
bc

ut
bc
bc
bc
bc
bc
bc

0.25

0

C. General Graphs

ut

0

5

ut

10

15
ℓ

ut

ut

20

bc
bc

ut

ut

bc
bc

bc

ut

ut

ut

25

30

Figure 2. The normalized MSE of URW-BPC vs. BC with Metropolis-type
weights over a random tree-graph, with diameter 12 and N = 100. The error
is averaged over 100 instances of random initial data x(0) (θ), but with a
fixed graph G.

2.00
1.75
1.50
1.25
|λ2 |

For general graphs, it is not obvious how to render BPC
convergent. A possible approach is to determine a spanning
tree of the network graph and then running BPC with finitetime convergence [27]. However, we can also build on the
results from regular graphs. We outline two procedures to
convert a general graph to a regular graph.
(i) Edge addition: The simplest way to make a graph into a
k-regular graph, is to first determine the maximum node
degree dmax (this can be done through max-consensus).
Then a node i with degree di adds dmax − di self-loops.
Then BPC with ρopt set based on k = dmax and µ̃ of the
new A, is applied.
(ii) Edge deletion: A more complex way to create a k-regular
graph is by selectively deleting edges from those nodes
with maximum degree, while maintaining connectivity.
This procedure can be applied until a certain minimal
value for dmax is attained.

Metropolis-weight consensus
URW-BPC (ρ = 1)
ut

ut

(normalized) MSE

√
This means that limN →∞ |µ2 | = 2 k − 1, and thus


p
1
k − k 2 − 4(k − 1) ,
lim ρopt =
N →∞
2(k − 1)

1.00
|λ| = 1
0.75
ρ = 2/k
0.50
0.25

VI. N UMERICAL R ESULTS AND D ISCUSSION
A. Simulation Parameters
We present numerical results comparing the URW-BPC
algorithms with Metropolis weighted belief consensus. The
simulations were performed with the number of nodes N =
100, with a fixed G for tree-graphs and random G for k-regular
graphs. The node degree for the k-regular graphs was fixed to
k = 4. The elements of the initial data x(0) (θ) were generated
according to a standard normal distribution. We calculated the
averaged (over instances of x(0) (θ) for tree-graphs, and over
both x(0) (θ) and G for k-regular graphs) and normalized mean
squared error (MSE), with the MSE being normalized with
respect to the initial consensus error. The simulations were
performed over 100 Monte Carlo runs.
B. Results for Tree-graphs
The simulated error of URW-BPC on a tree-graph is shown
in Fig. 2. We observe that the algorithm indeed reaches consensus in a finite number of steps. However, before reaching
consensus, the error of URW-BPC behaves differently from
that of the other consensus algorithm. The increasing error we
see can be explained by ε1 in (25). It takes a few iterations for

0
−0.25

0

0.25

0.50
ρ

0.75

1.00

1.25

Figure 3. The magnitude of the eigenvalue λ2 of Pρ generated from the
eigenvalue µ2 of A plotted as a function of the weighting parameter ρ, for
the k-regular small-world graph with k = 4 and N = 10 described in the
example in Section VI-C.

the Jordan blocks of the eigenvalues λi = 0 to become zero,
and until they do, the error they contribute with increases as
k increases.
C. Results for k-regular Graphs
To illustrate the benefit of URW-BPC on k-regular graphs,
we provide the following example of URW-BPC on a so called
small-world graph [28]. Let G be of the type detailed in [28,
Appendix A]. For this type of graph, there exist closed-form
expressions for the eigenvalues of A. In particular, if we let
G be such a graph with N = 10 and k = 4, we have that
µ2 ≈ 2.23. Hence, using (34) to calculate the optimal ρ, we
get from (35) that |λ2 | ≈ 0.31. On the other hand, using BC
on this graph with step-size ε = 0.25 yields |λ2 | ≈ 0.56.

7

101
bc

utbc
ut

Metropolis-weight consensus
Optimally weighted URW-BPC

3

5

2

4

utbc

(normalized) MSE

10

bc
ut

0

bc

1
bc

ut

bc
bc

ut

bc
bc

bc

ut

10

bc

Figure 6. Example of nonregular graph made k-regular by adding self loops.
In this case k = 3. The original communication graph is indicated by the
blue edges, while the added self-loops are indicated in green.

ut

−1

ut
ut
ut

101
bc

ut
ut

10−2

Metropolis-weight consensus
Optimally weighted URW-BPC with self-loops

utbc

100
bc

bc

10−3

0

1

2

3

4

5

6

7

8

9

10

ℓ

Figure 4. The normalized MSE of URW-BPC with ρ = ρopt vs. BC with
Metropolis-type weights over random regular graphs with N = 100 and
k = 4, plotted in log scale as a function of iterations. The error is averaged
over 100 instances of random initial data x(0) (θ), and graphs G.

(normalized) MSE

ut

bc
bc

bc
bc

ut

bc
bc

ut

10−1

bc

ut

10

ut

−2

ut
ut
ut

10−3
bc

1.0
bc
bc

0.8

bc

ut
ut

N = 101
N = 33

ut

F (r)

bc

ut

0.4

bc

ut

bc

ut

0 ut
0.55

bc
bc

0.60

0

1

2

3

4

5
ℓ

6

7

8

9

10

bc

ut

0.2

10−4

Figure 7. The normalized MSE of URW-BPC with ρ = ρopt with added
self-loops to make the graph k-regular vs. BC with Metropolis-type weights,
with N = 100 and k = 3, plotted in log scale as a function of iterations.
The error is averaged over 100 instances of random initial data x(0) (θ).

ut bc
ut

ut

ut

bc ut

0.6

bc

ut

0.65

0.70

0.75

0.80

0.85

0.90

0.95

r

Figure 5. Empirical cdf’s of r = λ2,BPC / λ2,Metr for two types of
k-regular graphs with N = 101 (red) and N = 33 (blue), and k = 4. The
empirical cdf is from 1000 instances of random graphs.

D. Results for a General Graph
To illustrate the method for general graphs discussed in
Section V-C, we perform numerical simulations for the graph
shown in Fig. 6, both without self-loops and Metropolis weight
consensus, and with added self-loops and optimally weighted
(according to the result of Theorem 8) URW-BPC. The results
are shown in Fig. 7. We see that the strategy of adding selfloops and running URW-BPC on the resulting k = 3 regular
graph indeed works well, and asymptotically outperforms
belief consensus on the original graph.
VII. C ONCLUSION

In Fig. 4 we show how the average error of optimally
weighted URW-BPC and belief consensus compare. The error
is averaged over instances of the graph G as well as the initial
data x(0) (θ). Clearly, URW-BPC outperforms belief consensus
in terms of convergence rate.
In Fig. 5 we compare the magnitude of λ2 for the two consensus algorithms by taking the ratio r = |λ2,BPC | / |λ2,Metr |,
plotting the empirical cumulative distribution function (cdf)
over 10,000 Monte Carlo runs. Clearly, URW-BPC always
outperforms belief consensus, since the ratio stays well below
one. Moreover, as we increase the network size, we see that the
ratio converges to the specific limit value discussed in Section
V-B3.

We studied the uniformly reweighted belief propagation algorithm for distributed likelihood fusion, which was described
by a factor graph with strong interactions, generally considered
a challenging case for belief propagation. The belief propagation consensus algorithm resulted in a linear update rule
much like a consensus algorithm with memory. By eigenvalue
analysis we were able to prove a collection of results on
several types of graphs: (i) we recovered the classical finitetime convergence of belief propagation on tree graphs for
the likelihood fusion problem; (ii) we provided conditions
on the reweighting parameter necessary and sufficient for
convergence, and (iii) we found an analytical expression for
the reweighting parameter optimizing convergence rate, on kregular graphs, and on general graphs artificially transformed

8

into k-regular graphs by adding self-loops or removing edges.
Based on both numerical results, and eigenvalue limits on large
k-regular graphs, belief propagation consensus outperformed
consensus with Metropolis-type weights. Open issues include
analytically comparing the performance of belief propagation
consensus to other algorithms for distributed likelihood fusion,
and to investigate how it compares to consensus algorithms
with memory.

which boils down to Lv = 0, where L = D − A is the graph
Laplacian. The graph Laplacian L of a connected graph has
an eigenvalue ν = 0 with algebraic multiplicity equal to 1, and
its right eigenvector is v = 1. Thus, λ1 = 1 has geometric
multiplicity equal to 1. Since (48) states
 that w = v, we see
T
T
that b1 = 1. Now, let cT
be a left eigenvector
1 = v ,w
corresponding to the eigenvalue λ1 = 1. Then, we know that
v T = ρv T A + wT

D ERIVATION

OF

A PPENDIX I
THE URW-BPC

T

T

T

w = v − ρv D.

ALGORITHM

According to the message-passing equations of the uniformly reweighted BP [19], we can write the marginal belief
of some variable θn of node n at iteration ℓ as
ρ
Y 
µ(ℓ)
b(ℓ)
,
(40)
m→n (θn )
n (θn ) ∝ p(yn |θn )
m∈Nn

(49)
(50)

Plugging (50) into (49) gives us that
ρv T A + v T − ρv T D = v T ,

(51)

which implies that v T L = 0, and in turn that v T = 1T .
this result in (50) we immediately get that cT
1 =
Using
T
T
1 , 1 − ρ1T D .

for ρ ∈ (0, 1], where the message from node m to node n at
iteration ℓ is computed by

ρ
Q
(ℓ−1)
µ
(θ
)
X
u→m m
u∈Nm \n
B. Proof of Proposition 3
µ(ℓ)
I{θm =θn } p(ym |θm )

1−ρ
m→n (θn ) ∝
(ℓ−1)
θm
µn→m (θm )
Proof: Denote by C̃ T = B −1 the matrix whose rows are
(41) the scaled left eigenvectors, such that c̃T b = 1. In particular
i i
(ℓ−1)
T
T
X
this means that c̃T
bm (θm )
1 = c1 /(c1 b1 ). Now, since
I{θm =θn } 
=
1−ρ 
ρ
(ℓ−1)
(ℓ−1)
θm
µn→m (θm )
µn→m (θm )
α = B −1 z (0) (θ)
(52)
(42)
T (0)
= C̃ z (θ),
(53)
(ℓ−1)
bm (θn )
.
(43)
= (ℓ−1)
(0)
µn→m (θn )
and the first row of C̃ T is c̃T
=
1 , then clearly α1
(ℓ)
T (0)
T
is
the
coordinate
c
z
(θ)/(c
b
).
Furthermore,
since
α
We note that θn = θm = θ, and plug (43) into (40)
1
1 1
1
of z (ℓ) (θ) in the basis B corresponding the eigenvalue λ1 = 1,
!ρ
(ℓ−1)
(ℓ)
Y
bm (θ)
the part of z (ℓ) (θ) (in B) preserved at each iteration is α1 .
b(ℓ)
(44)
n (θ) ∝ p(yn |θ)
(ℓ−1)
Moreover, if URW-BPC converges then from (19) and (24) we
µn→m (θ)
m∈Nn
!ρ
observe that α1 (which is the preserved value) is the consensus
(ℓ−1)
Y
T (0)
T (0)
bm (θ) (ℓ−2)
µm→n (θ)
(45) value, and since c1 z = 21 x (θ) the consensus value is
= p(yn |θ)
(ℓ−2)
given
by
(θ)
bn
m∈Nn
!ρ
(ℓ−1)
2
Y
bm (θ)
(54)
α1 = T 1T x(0) (θ).
(ℓ−2)
.
(46)
= bn
(θ)
c1 b1
(ℓ−2)
bn
(θ)
m∈Nn
For the initial values of the marginals, we assume that
(0)
µm→n (θ) = 1 for all nodes n, all m ∈ Nn . Hence, by
(0)
(40) we have that bn (θ) = p(yn |θ). Now we can compute
the marginals at iteration ℓ = 1 by using (44), which gives
Q
(2)
ρ
bn (θ) = p(yn |θ) m∈Nn (p(ym |θ)) .
A PPENDIX II
P ROOFS OF P ROPOSITIONS

A. Proof of Proposition 2
Proof: Let b1 = [v T , wT ]T be a right eigenvector corresponding to the eigenvalue λ1 = 1. Then, it holds that
v = ρAv + (IN − ρD)w

w = v,

(47)
(48)

C. Proof of Proposition 4
Proof: The eigenvalues of P1 are given by the roots of
the polynomial

(a)
det (P1 − λI2N ) = det λ2 IN − λA + D − IN = 0,
(55)
where the equality (a) holds due to the four N × N -blocks
of P1 − λI2N being mutually commutative [29, Theorem 3].
For brevity, denote Ψ = λ2 IN − λA + D − IN . Consider
now the case where we add a leaf node to G. Without loss
of generality, we assume that the leaf node is node 1, and its

9

parent node is node 2. Then, the eigenvalues of P̃1 are given
by the roots of

 2
λ
−λ
0T
 
det Ψ̃ = det  −λ Ψ1,1 + 1 Ψ1,2:N  (56)
0
Ψ2:N,1 Ψ2:N,2:N


Ψ1,1 + 1 Ψ1,2:N
2
= λ det
(57)
Ψ2:N,1 Ψ2:N,2:N


−λ Ψ1,2:N
(58)
+ λ det
0 Ψ2:N,2:N



1 Ψ1,2:N
= λ2 det (Ψ) + det
0 Ψ2:N,2:N
(59)


1
Ψ
1,2:N
− λ2 det
(60)
0 Ψ2:N,2:N
2

= λ det (Ψ) .

(61)

Hence, adding a leaf node only adds two extra roots λ = 0
to the eigenvalue generating polynomial. By exchanging G for
G̃ and vice versa, we see that by removing a leaf node, we
remove two roots λ = 0 instead. Consequently, the nonzero
eigenvalues of P̃1 are the same as those of P1 . Starting from
a graph with only one node, with URW-BPC matrix


0 1
P1 =
,
(62)
1 0
and thus eigenvalues λ1 = 1 and λ2 = −1, we see that any
tree graph with N ≥ 2 has eigenvalues λ1 = 1, λ2 = −1, and
λi = 0 for i = 3, . . . , 2N .

A PPENDIX III
P ROOFS RELATED TO S ECTION V-B
First, we prove a few results regarding the behavior of the
eigenvalues of the URW-BPC matrix of a k-regular graph,
with respect to the eigenvalues of the adjacency matrix. After
these useful results are obtained, we proceed to prove the main
results.
Lemma 11. The roots of the polynomial λ2 −µρλ+ρk−1 = 0
are given by

p
1
λa,b (µ) =
µρ ± µ2 ρ2 − 4kρ + 4 .
(63)
2
For k ≥ 2, µ ∈ [−k, k] and ρ > 0 they have the following
properties:
(i) If λa (µ) and
p λb (µ) are complex-valued, then |λa (µ)| =
|λb (µ)| = |ρk − 1|.
(ii) Let µ = k, then λb (k) = 1 and λa (k) = ρk − 1.
(iii) |λa (µ)| = |λb (−µ)|.
(iv) |λa (µ)| is a nondecreasing function of µ; |λb (µ)| is a
nonincreasing function of µ.
Proof: When the roots λa (µ), λb (µ) are complex-valued,
the squared absolute values are given by
p
2
1
2
µρ ± i |4kρ − 4| − µ2 ρ2
|λa,b (µ)| =
(64)
4

1 2 2
(65)
µ ρ + |4kρ − 4| − µ2 ρ2
=
4
= |kρ − 1| ,
(66)

√
where i = −1. Hence,
p for complex-valued λa,b (µ) we have
|λa (µ)| = |λb (µ)| = |kρ − 1|.
For property (ii), suppose first that kρ ≥ 2. We plug in
µ=k
p
1
kρ + k 2 ρ2 − 4kρ + 4
|λa (k)| =
(67)
2
1
(68)
= |kρ + (kρ − 2)|
2
= kρ − 1.
(69)
1
|kρ − kρ + 2|
2
= 1.

|λb (k)| =

For kρ < 2, the roots are interchanged.
For (iii) we have that
p
|λb (−µ)| = −µρ − µ2 ρ2 − 4kρ + 4


p
= − µρ + µ2 ρ2 − 4kρ + 4
p
= µρ + µ2 ρ2 − 4kρ + 4
= |λa (µ)| .

(70)
(71)

(72)
(73)
(74)
(75)

To show (iv), we focus on the case when λa (µ) is real, since
for complex λa (µ), |λa (µ)| is constant in µ. We check that
the derivative of λ2a (µ) wrt. µ is positive, and since λa (µ)
is assumed to be real this holds for |λa (µ)| as well. The
derivative of λ2a (µ) wrt. µ is given by
∂
∂ 2
λ (µ) = 2λa (µ)
λa (µ)
∂µ a
∂µ
2λ2a (µ) ρ
= p
.
µ2 ρ2 − 4kρ + 4

(76)
(77)

Since ρ > 0, the derivative of λ2a (µ) is clearly positive,
and thus so is the derivative of |λa (µ)|. We conclude that
|λa (µ)| is nondecreasing in µ, and due to (iii) that |λb (µ)| is
nonincreasing in µ. Note that the functions are not necessarily
monotonic since they are constant for complex eigenvalues.
A. Proof of Lemma 6
Proof: Let λ 6= 0 be an eigenvalue of Pρ and
 T T T
v ,w
6= 0 the corresponding eigenvector. By definition,
it holds that
λv = ρAv + (IN − ρD)w
λw = v.

(78)
(79)

Substituting v by λw in (78) gives
λ2 w = ρAλw + (IN − ρD)w.

(80)

Since G is a k-regular graph, we have that D = kIN , and
since λ 6= 0, this is equivalent to
Aw =

λ2 + ρk − 1
w.
ρλ

(81)

10

This means that the eigenvalues of Pρ are given by the roots
of the polynomial

p
1
λ=
µρ ± µ2 ρ2 − 4kρ + 4 ,
(82)
2
where µ is an eigenvalue of A with eigenvector w. Suppose
that µi > 0. Then, Lemma 11, which says that λa (µ) is a
nondecreasing function in µ, implies that λi = λa (µi ) and
thus its magnitude is given by
p
1
(83)
µi ρ + µi ρ − 4kρ + 4 .
|λi | =
2
Since |λa (µ)| = |λb (−µ)| by Lemma 11, we observe that we
achieve the same result should µi < 0.
B. Proof of Theorem 7
Proof: Let µ̃ = maxi |µi | for i such that |µi | < k. Note
that for a non-bipartite G, µ̃ = µ2 , whereas for a bipartite G
we have that µ2 = −k, and hence µ̃ = µ3 . Since |λa (µ)| is a
nondecreasing function in µ (due to Lemma 11) and µ̃ < k,
and if kρ < 2 we have that
p
1
(84)
µ̃ρ + µ̃2 ρ2 − 4kρ + 4
|λ̃| =
2
p
1
<
(85)
kρ + k 2 ρ2 − 4kρ + 4
2
1
(86)
= |kρ + (2 − kρ)|
2
= 1.
(87)
Hence, |λi | < 1 for i = 2, . . . , 2N . On the other hand, if
kρ > 2, we have that
p
1
|λ1 | =
(88)
kρ + k 2 ρ2 − 4kρ + 4
2
1
(89)
= |kρ + kρ − 2|
2
= kρ − 1
(90)
> 1.
(91)
So, in that case URW-BPC is not convergent. In particular for
ρ = 2/k we have that
!
r
1
2
4
2
λ=
µ ± µ 2 −4 ,
(92)
2
k
k
so all eigenvalues are complex-valued except the ones generated from µ = k or µ = −k (the smallest eigenvalue of A
for bipartite G is µ = −k [25]), which are equal to λ = 1 or
λ = −1. Thus, using property (i) we find that |λi | = 1 for
all i = 1, . . . , 2N . Moreover, for ρ = 0 we clearly see that
|λi | = 1 for all i = 1, . . . , 2N . For ρ < 0 it is obvious that
|λ1 | > 1.
Using the results from Propositions 2 and 3, and that
the
PN sum of the degrees for undirected k-regular graphs is
i=1 Dii = N k, the consensus value α1 is given
N
X
2
α1 =
x(0) (θ).
2N − ρN k m=1 m

(93)

C. Proof of Theorem 8
Proof: We want to find the ρ that minimizes the magnitude of the largest eigenvalue inside the unit circle, i.e., |λ̃|. Let
µ̃ be the eigenvalue of A that generates λ̃. Then, we minimize
|λ̃| by
p
1
(94)
µ̃ρ + µ̃2 ρ2 − 4kρ + 4 ,
min
ρ∈(0,1] 2

First we get the roots with respect to ρ of the polynomial
under the square-root
s
2k
4k 2
ρ= 2 ±
−4
(95)
µ̃
µ̃4

p
2 
= 2 k ± k 2 − µ̃2 .
(96)
µ̃
p
p
Since k 2 − µ̃2 > 0 and k > k 2 − µ̃2 , we see that the
smallest ρ is given by

p
2 
ρ⋆ = 2 k − k 2 − µ̃2 .
(97)
µ̃

This value of ρ will make the second term inside the absolute
value in (94) equal to zero, yielding
|λ̃| = |µ̃ρ⋆ | .

(98)

However, it is still not clear that this is the global minimum,
since there is a linear term in the expression too. First, since µ̃
is positive, ρ > ρ⋆ cannot give smaller |λ̃| than the one given
by ρ⋆ . But, there might be a ρ < ρ⋆ that gives a smaller |λ̃|.
So, consider using ρǫ = ρ⋆ − ǫ, where ǫ > 0. Then we get
q
p
1
⋆
(99)
µ̃ρ − µ̃ǫ + µ̃2 ǫ2 + 4ǫ k 2 − µ̃2 .
|λ̃ǫ | =
2
p
Since 4ǫ k 2 − µ̃2 > 0, we have that
q
p
µ̃2 ǫ2 + 4ǫ k 2 − µ̃2 > µ̃ǫ,
(100)
and hence |λ̃ǫ | > |λ̃|. Consequently, the optimal ρ is

p
2 
ρopt = 2 k − k 2 − µ̃2 ,
µ̃

and, plugging this value into (98) gives

p
1 2
k − k 2 − µ̃2
|λ̃| =
2 µ̃

p
1
k − k 2 − µ̃2 .
=
µ̃

(101)

(102)
(103)

D. Proof of Proposition 10
Proof: Denote by α(λ) and γ(λ) the algebraic and
geometric multiplicities of an eigenvalue λ of a URW-BPC
matrix Pρ . Suppose that α(λ) 6= γ(λ), i.e., α(λ) > γ(λ).
Then, there exist vectors v and w such that



 

v
v
ṽ
=λ
+
Pρ
,
(104)
w
w
w̃

11

where [ṽ T , w̃T ]T is an eigenvector of Pρ with eigenvalue λ.
As established in (78)–(81), if λ 6= 0

 

ṽ
λz
=
,
(105)
w̃
z
for some z such that
Az = µz
λ2 + ρk − 1
.
µ=
ρλ

(106)
(107)

Using (105) in (104), we get that
ρAv + (1 − ρk)w = λv + λz
v = λw + z.

(108)
(109)

Substituting v in (108), we have
ρAλw + ρAz + (1 − ρk)w = λ2 w + 2λz,

(110)

which in turn, using (106), becomes
ρλAw = −ρµz + (ρk − 1)w + λ2 w + 2λz.

(111)

Rearranging the terms, we have that
2λ − ρµ
λ2 + ρk − 1
w+
z
ρλ
ρλ
2λ − ρµ
= µw +
z.
ρλ

Aw =

(112)
(113)

Left-multiplying by z T and using the symmetry of A (so that
z T A = z T µ), we get
µz T w = µz T w +

2λ − ρµ
kzk2 .
ρλ

(114)

This implies that (2λ − ρµ)/ρλ = 0, and thus that
2λ = ρµ
λ2 + ρk − 1
=
.
λ

(115)
(116)

Hence, we have that λ2 = ρk − 1. For λ = ±1, this implies
that ρk = 2. But, ρ ∈ (0, 2/k), hence the original claim is
false. We conclude that α(λ) = γ(λ) for λ = ±1.
R EFERENCES
[1] J. Pearl, “Fusion, propagation, and structuring in belief networks,”
Artificial intelligence, vol. 29, no. 3, pp. 241–288, Sep. 1986.
[2] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and
the sum-product algorithm,” IEEE Transactions on Information Theory,
vol. 47, no. 2, pp. 498–519, Feb. 2001.
[3] J. S. Yedidia, W. T. Freeman, and Y. Weiss, “Constructing free-energy
approximations and generalized belief propagation algorithms,” IEEE
Transactions on Information Theory, vol. 51, no. 7, pp. 2282–2312, Jul.
2005.
[4] J. Sun, N.-N. Zheng, and H.-Y. Shum, “Stereo matching using belief
propagation,” IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 25, no. 7, pp. 787–800, Jul. 2003.
[5] C. C. Moallemi and B. Van Roy, “Convergence of min-sum message
passing for quadratic optimization,” IEEE Transactions on Information
Theory, vol. 55, no. 5, pp. 2413–2423, May 2009.
[6] C. Chamley, A. Scaglione, and L. Li, “Models for the diffusion of beliefs
in social networks: An overview,” IEEE Signal Processing Magazine,
vol. 30, no. 3, pp. 16–29, May 2013.

[7] Y. Kabashima, “A CDMA multiuser detection algorithm on the basis of
belief propagation,” Journal of Physics A: Mathematical and General,
vol. 36, no. 43, p. 11111, Oct. 2003.
[8] H. Wymeersch, J. Lien, and M. Z. Win, “Cooperative localization in
wireless networks,” Proceedings of the IEEE, vol. 97, no. 2, pp. 427–
450, Feb. 2009.
[9] M. P. Fossorier, M. Mihaljević, and H. Imai, “Reduced complexity
iterative decoding of low-density parity check codes based on belief
propagation,” IEEE Transactions on Communications, vol. 47, no. 5,
pp. 673–680, May 1999.
[10] R. J. McEliece, D. J. C. MacKay, and J.-F. Cheng, “Turbo decoding as
an instance of Pearl’s "belief propagation" algorithm,” IEEE Journal on
Selected Areas in Communications, vol. 16, no. 2, pp. 140–152, Feb.
1998.
[11] S. Zarrin and T. J. Lim, “Belief propagation on factor graphs for
cooperative spectrum sensing in cognitive radio,” in Proceedings of the
3rd IEEE Symposium on New Frontiers in Dynamic Spectrum Access
Networks, Oct. 2008.
[12] F. Meyer, E. Riegler, O. Hlinka, and F. Hlawatsch, “Simultaneous
distributed sensor self-localization and target tracking using belief propagation and likelihood consensus,” in Conference Record of the 46th
Asilomar Conference on Signals, Systems and Computers, Mar. 2013,
pp. 1212–1216.
[13] B. Etzlinger, H. Wymeersch, and A. Springer, “Cooperative synchronization in wireless networks.” IEEE Transactions on Signal Processing,
vol. 62, no. 11, pp. 2837–2849, Jun. 2014.
[14] W. Zhong and J. Garcia-Frias, “LDGM codes for channel coding and
joint source-channel coding of correlated sources,” EURASIP Journal
on Applied Signal Processing, vol. 2005, pp. 942–953, Jan. 2005.
[15] Z. Zhang, Z. Han, H. Li, D. Yang, and C. Pei, “Belief propagation based
cooperative compressed spectrum sensing in wideband cognitive radio
networks,” IEEE Transactions on Wireless Communications, vol. 10,
no. 9, pp. 3020–3031, Jul. 2011.
[16] M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, “Tree-reweighted
belief propagation algorithms and approximate ml estimation by pseudomoment matching,” in Proceedings of the 9th International Workshop
on Artificial Intelligence and Statistics, Jan. 2003.
[17] ——, “A new class of upper bounds on the log partition function,” IEEE
Transactions on Information Theory, vol. 51, no. 7, pp. 2313–2335, Jun.
2005.
[18] H. Wymeersch, F. Penna, and V. Savić, “Uniformly reweighted belief
propagation: A factor graph approach,” in Proceedings of the IEEE
International Symposium on Information Theory, Oct. 2011, pp. 2000–
2004.
[19] ——, “Uniformly reweighted belief propagation for estimation and
detection in wireless networks,” IEEE Transactions on Wireless Communications, vol. 11, no. 4, pp. 1587–1595, Feb. 2012.
[20] J. Liu and R. C. de Lamare, “Knowledge-aided reweighted belief
propagation decoding for regular and irregular ldpc codes with short
blocks,” in Proceedings of the International Symposium on Wireless
Communication Systems, Oct. 2012, pp. 984–988.
[21] ——, “Low-latency reweighted belief propagation decoding for ldpc
codes,” IEEE Communications Letters, vol. 16, no. 10, pp. 1660–1663,
Aug. 2012.
[22] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE,
vol. 95, no. 1, pp. 215–233, Mar. 2007.
[23] L. Xiao, S. Boyd, and S. Lall, “Distributed average consensus
with time-varying metropolis weights,” 2006. [Online]. Available:
http://web.stanford.edu/~boyd/papers/pdf/avg_metropolis.pdf
[24] H. Dai and Y. Zhang, “Consensus estimation via belief propagation,”
in Proceedings of the 41st Annual Conference on Information Sciences
and Systems, Sep. 2007, pp. 277–281.
[25] L. Lovász, “Eigenvalues of graphs,” 2007. [Online]. Available:
http://www.cs.elte.hu/~lovasz/eigenvals-x.pdf
[26] B. D. McKay, “The expected eigenvalue distribution of a large regular
graph,” Linear Algebra and its Applications, vol. 40, pp. 203–216, Oct.
1981.
[27] V. Savić, A. Población, S. Zazo, and M. García, “Indoor positioning using nonparametric belief propagation based on spanning trees,”
EURASIP Journal on Wireless Communications and Networking, vol.
2010, no. 1, Jul. 2010.
[28] I. J. Farkas, I. Derényi, A.-L. Barabási, and T. Vicsek, “Spectra of realworld graphs: Beyond the semicircle law,” Physical Review E, vol. 64,
no. 2, Jul. 2001.
[29] J. R. Silvester, “Determinants of block matrices,” The Mathematical
Gazette, vol. 84, no. 501, pp. 460–467, Nov. 2000.

