IEEE Signal Processing - May 2018 - 120

up to instant n - 1; for simplicity of notation, we omit in this section the conditioning on the measurements in the notation
p n - 1 | n - 1, r (x n) .

Adapt step

Using again the mutual independence
assumptions in the signal model, the general form of the adapt step at node r at
instant n is given by
p n | n -1, r (x n) =

Let Nr (r) denote the closed neighborhood
of the node r consisting of the union of
the single-element set {r} and the set of
the indexes of all network nodes that are
connected to node r according to the
topology of the graph G that describes the
network, i.e., the set of all indexes u such
that (r, u) is a valid edge on the graph G.
First, each node r independently runs at
instant n a local Bayes filter that updates
p n -1 | n -1, r (x n) using the locally available
observations {y n, u}, for all u ! Nr (r) .

#0

N

6 p (x n | x n -1)

# p n -1 | n -1, r (x n -1)@ dx n -1
(7)

pu n | n, r (x n) ? ;

%

u ! Nr (r)

p (y n, u |x n)E

# p n | n -1, r (x n) .

(8)

Figure 2 illustrates the adapt step at a
particular node r. Let 9 denote the inner
product in 0 N between functions f ($)
and g ($) such that
f 9g _

#0

N

Following the local update in (7) and (8),
the combine step replaces pu n | n, r (x n) at
each node r with a merged pdf
p n|n, r (x n) ?

6 pu n|n, u (x n)@a r,u, (9)

where the real exponents a r, u are such
that R u ! Nr (r) a r, u = 1, 6r. As shown in [4],
p n | n, r is the merged pdf that minimizes,
at instant n and at node r, the weighted
average KL divergence

/

a r, u D KL (p * || pu n | n, u)

(10)

u ! Nr (r)

over all possible pdfs p * .
Figure 3 summarizes the combine
step. More specifically, it shows how the
local posterior pu n | n, r (x n) at node r and
the neighbors' posteriors {pu n | n, u (x n)},
u ! N (r), from the adapt step are fused
into a pdf p n | n, r (x n) as in (9), where
N (r) _ Nr (r) = {r} denotes the open
neighborhood of the node r.
Alternatively, it is possible to use
an iterative version of the combine step
as proposed, e.g., in [5]. In particular,
the R # R real matrix A that collects
the coefficients {a r, u} for r and u in
{1, 2, f, R} is usually a primitive, doubly
stochastic matrix, i.e., a r, u $ 0 for any
pair (r, u), R u a r, u = R u a u, r = 1 for all r,
and A has one single eigenvalue equal to
one and all other eigenvalues with modulus less than one. Under those constraints,
it is relatively easy to prove (see also
in another context [5]), that, at all nodes
r ! {1, 2, f, R}, the respective merged
pdf converges, as the number of iterations go to infinity, to the function that
minimizes over all possible pdfs p * the
average network KL divergence

pn |n - 1, r (xn)
p (yn, u | xn)

p (yn, u 1 | xn)

4

p (yn, u 2 | xn)
p (yn, u |N(r )| | xn)

p (yn, u 3 | xn)
~
∝ pn |n, r (xn)

Figure 2. The adapt step.

~
[ pn |n, r (xn) ]ar, r
~
[ pn |n, u 1 (xn) ]ar, u

~
[ pn |n, u 4 (xn) ]ar, u

1

4

2

~
[ pn |n, u |N(r )| (xn) ]ar, |N(r )|

3

∝ pn |n, r (xn)

/ 8 R1 D K L (p * || pu n | n,u)B.
R

Figure 3. The combine step.
120

%

f (x) g (x) dx.

p (xn | xn - 1)

~
[ pn |n, u 3 (xn) ]ar, u

Combine step

u ! Nr (r)

pn - 1|n - 1, r (xn - 1)

~
[ pn |n, u 2 (xn) ]ar, u

Thus, as shown in Figure 2, the predicted posterior p n | n -1, r (x n) in (7) can
be written as the inner product between
the posterior p n -1 | n -1, r (x n -1) at instant
n - 1 and the transition pdf p (x n | x n -1) .
Next, the symbol , in Figure 2 denotes
the product between the local likelihoods
{p (y n, u | x n)}, u ! Nr (r), and the predicted
posterior p n | n -1, r (x n) as in (8).

u =1

IEEE Signal Processing Magazine

|

May 2018

|
Table of Contents for the Digital Edition of IEEE Signal Processing - May 2018
