DRAFT

1

Partial Diffusion Recursive Least-Squares for
Distributed Estimation under Noisy Links Condition

arXiv:1607.05539v1 [cs.DC] 19 Jul 2016

Vahid Vahidpour, Amir Rastegarnia, Azam Khalili, and Saeid Sanei, Senior Member, IEEE

Abstract—Partial diffusion-based recursive least squares
(PDRLS) is an effective method for reducing computational load
and power consumption in adaptive network implementation.
In this method, each node shares a part of its intermediate
estimate vector with its neighbors at each iteration. PDRLS
algorithm reduces the internode communications relative to the
full-diffusion RLS algorithm. This selection of estimate entries
becomes more appealing when the information fuse over noisy
links. In this paper, we study the steady-state performance of
PDRLS algorithm in presence of noisy links and investigate
its convergence in both mean and mean-square senses. We
also derive a theoretical expression for its steady-state meansquare deviation (MSD). The simulation results illustrate that the
stability conditions for PDRLS under noisy links are not sufficient
to guarantee its convergence. Strictly speaking, considering nonideal links condition adds a new complexity to the estimation
problem for which the PDRLS algorithm becomes unstable and
do not converge for any value of the forgetting factor.
Index Terms—Adaptive networks, diffusion adaptation, distributed estimation, energy conservation, recursive least-square,
partial diffusion, noisy links.

I. I NTRODUCTION

W

E study the problem of distributed estimation over
adaptive networks, in which a set of agents are interacted with each other to solve distributed estimation and
inference problems in a collaborative manner. There exist several useful techniques for solving such optimization problems
in distributed manner that enable adaptation and learning in
real-time. They include incremental [1], [2], [3], consensus
[4], [5], [6], and diffusion [7], [8], [9], [10], [11], [12], [13],
[14], [15] strategies. The diffusion strategies are effective
methods for performing distributed estimation over adaptive
networks. In the original diffusion strategy, all agents in
the network generate their individual intermediate estimates
using the data accessible to them locally. Then, the nodes
exchange their intermediate estimates to all their immediate
neighbors. However, the most expensive part of realizing a
cooperative task over a wireless ad hoc network is usually
the data communications through radio links. Therefore, it
is of practical importance to reduce the amount of internode
communications in diffusion strategies while maintaining the
benefits of cooperation.
To aim this, various techniques have been proposed, such as
choosing a subset of the nodes [16], [17], [18], [19], selecting
V. Vahidpour, A. Rastegarnia, and A. Khalili and are with the Department of Electrical Engineering, Malayer University, Malayer 6571995863, Iran (email: v.vahidpour@gmail.com; rastegar@tabrizu.ac.ir; akhalili@tabrizu.ac.ir).
S. Sanei is with the Department of Computer Science, University of Surrey,
Surrey GU2 7XH, UK (email: s.sanei@surrey.ac.uk).

a subset of the entries of the estimates [20], [21], and reducing
the dimension of the estimates [22], [23], [24]. Among these
methods, we focus on the second method in which a subset
of the entries are selected in communications.
In all mentioned works, the data are assumed to be exchanged among neighboring nodes without distortion. However, due to the link noise, this assumption may not be true
in practice. Some useful results out of studying the effect of
link noise during the exchange of weight estimates, already
appear for traditional diffusion algorithm [25], [26], [27], [28],
for incremental case [29], [30], [31], and for consensus-based
algorithms [32], [33].
In partial-diffusion strategies proposed in [20], [21], the
links between nodes are assumed to be ideal. However, the
performance of these strategies, due to replacing the unavailable entries by their corresponding ones in each nodes own
intermediate estimate vector, are strongly affected under noisy
information exchange.
The main contributions of this paper can be summarized as
follows:
(i) Focusing on [21], we consider the fact that the weight
estimates exchanged among the nodes can be subject to
quantization errors and additive noise over communication links. We also consider two different schemes [20]
for selecting the weight vector entries for transmission
at each iteration. We allow for noisy exchange just
during the two combination steps. It should be noted that
since our objective is to minimize the internode communication, the nodes only exchange their intermediate
estimates with their neighbors;
(ii) Using the energy conservation argument [34] we analyze
the stability of algorithms in mean and mean square sense
under certain statistical conditions;
(iii) Stability conditions for PDRLS are derived under noisy
links, and it is demonstrated that the steady-state performance of the new algorithm is not as good as that of the
PDRLS algorithm with ideal links;
(iv) We derive a variance relation which contains an additional terms in comparison to original PDRLS algorithm
that represent the effects of noisy links. We evaluate
these moments and derived closed-form expressions for
mean-square derivation (MSD) to explain the steady-state
performance.
(v) It is demonstrated through different examples that the
stability conditions for PDRLS under noisy links are
not sufficient to guarantee its convergence. Considering
noisy links adds a new complexity to estimation problem
for which the PDRLS algorithm suffers a significant

DRAFT

2

degradation in steady-state performance for any value of
forgetting factor.
The remainder of this paper is organized as follows: In
Section II, we formulate the PDLMS under imperfect information exchange. The performance analyses are examined in
Section III, where the methods of entry selection matrix are
also examined. We provide simulation results in Section IV
and draw the conclusions in Section V.
A. Notation
We use the lowercase boldface letters to denote vectors,
uppercase boldface letter for matrices, and lowercase plain
letters for scalar variables. We also use (.)∗ to denote conjugate
transposition, Tr(.) for the trace of its matrix argument, ⊗
for the Kronecker product, and vec. for a vector formed by
stacking the columns of its matrix argument. We further use
diag{· · · } to denote a (block) diagonal matrix formed from its
argument, and col{· · · } to denote a column vector formed by
stacking its arguments on top of each other. All vectors in our
treatment are column vectors, with the exception of regression
vectors, uk,i .
II. A LGORITHM D ESCRIPTION
A. Diffusion Recursive Least-Squares Algorithm with Noisy
Links
To begin with, consider a set of N nodes, spatially distributed over some region, aim to identify an unknown parameter vector, wo ∈ C M ×1 , in a collective manner. At every
time instant i, node k collects a measurement dk (i) that is
assumed to be related to an unknown vector by
dk (i) = uk,i wo + vk (i)

y k,i = col {dk (i), . . . , dk (0)}

(2)

H k,i = col {uk (i), . . . , uk (0)}

(3)

v k,i = col {vk (i), . . . , vk (0)}

(4)

the objective is to estimate wo by solving the following
weighted least-squares problem
ψ

2
Λi

The solution ψ k,i is given by [35]
−1

ψ k,i = H ∗k,i Λi H k,i
H ∗k,i Λi y k,i

H ∗k,i Λi H k,i = λH ∗k,i−1 Λi−1 H k,i−1 + u∗k,i uk,i

(5)

(6)

where Λi ≥ 0 denotes a Hermitian weighting matrix. Common
choice for λi is

Λi = diag 1, λ, . . . , λi
(7)
where 0  λ ≤ 1 is a forgetting factor whose value is
generally very close to one.

(8)

H ∗k,i Λi y k,i = λH ∗k,i−1 Λi−1 y k,i−1 + u∗k,i dk (i)
(9)

−1
Let P k,i = H ∗k,i Λi H k,i
. Then applying the socalled matrix inversion formula [36][36] to (8) the following
recursions for calculating ψ k,i are obtained
!
λ−1 P k,i−1 u∗k,i uk,i P k,i−1
−1
(10)
P k,i−1 −
P k,i = λ
1 + λ−1 uk,i P k,i−1 u∗k,i

ψ k,i = ψ k,i−1 + P k,i u∗k,i dk (i) − uk,i ψ k,i−1
(11)
Since wk,i is a better estimate compared with ψ k,i , it is
beneficial to replace ψ k,i−1 with wk,i−1 in (11)
ψ k,i = wk,i−1 + P k,i u∗k,i (dk (i) − uk,i wk,i−1 )

(12)

Hence, the local estimates are diffused outside of each node’s
own neighborhood. Then, for every time instant i, each node
k performs an adaptation step followed by a combination step
as follows:
1) Adaptation: Each node computes an intermediate estimate of wo by (10) and (12). The resulting pre-estimates
are named ψ k,i as in (13).
2) Combination: The nodes exchange their local preestimates with their neighbors and perform a weighted
average as in (14) to obtain the estimate wk,i (via socalled spatial update).
N
X
wk,i =
alk ψ l,i
(13)
l=1

(1)

where uk (i) is a row vector of length M (the regressor of
node k at time i) and vk (i) represent additive noise with zero
2
mean and variance συ,k
and the unknown vector wo denotes
the parameter of interest.
Collecting the measurements and noise samples of node k
up to time i into vector quantities as follows:

min y k,i − H k,i ψ

It can be verified from the properties of recursive leastsquares solutions [35], [34] that

The scalar alk is non-negative real coefficient corresponding
to the (l, k)entries of N × N combination matrix A = {alk }.
These coefficients are zero whenever node l ∈
/ Nk , where Nk
denotes the neighborhood of node k. This matrix is assumed
to satisfy the condition:
AT 1 N = 1 N

(14)

where the notation 1 denotes an N × 1 column vector with
all its entries equal to one.
The above algorithm only uses the local input-output data,
observed by each node, in the adaptation phase. However, in
[15], a more general algorithm has been proposed in which
each node shares its input-output data as well as its intermediate estimate with its neighbors and updates its intermediate
estimate using all available data. This is carried out via a
convex combination of the update terms induced by each
input-output data pair. For the obvious reason of minimizing
the communications, here, we will only consider the abovementioned diffusion RLS algorithm.
We model the noisy data received by node k from its
neighbor l as follows:
(ψ)

ψ lk,i = ψ l,i + v lk,i
(ψ)

(15)

where v lk,i (M × 1) denotes vector noise signal. It is temporally white and spatially independent random process with

DRAFT

3

(ψ)

(ψ)

zero mean and covariance given by Rv,lk . The quantity Rv,lk
are all zero if l ∈
/ Nk or when l = k. it should be noted that
the subscript lk indicates that l is the source and k is the sink,
i.e. the flow of information is from l to k.
Using the perturbed estimate (15), the combination step in
adaptive strategy becomes
X
wk,i =
alk ψ lk,i
(16)
l∈Nk

B. Partial-Diffusion RLS Algorithm under Noisy Information
Exchange
In order to reduce the amount of communication required
among the nodes we utilize partial-diffusion strategy proposed
in [20], to transmit L out of M entries of the intermediate
estimates at each time instant where the integer L is fixed and
pre-specified. The selection of the to-be-transmitted entries at
node k and time instant i can be characterized by an M × M
diagonal entry-selection matrix, denoted by Kk,i , that has L
ones and M −L zeros on its diagonal. The proposition of ones
specifies the selected entries. Multiplication of an intermediate
estimate vector by this matrix replaces its non-selected entries
with zero.
Rewriting (16) as
X
wk,i = akk ψ k,i +
alk [Kl,i ψ lk,i
l∈Nk \{k}

+ (I M − Kl,i ) ψ lk,i ]

(17)

Each node requires the knowledge of all entries of its neighbors intermediate estimate vectors for combination. However,
when the intermediate estimates are partially transmitted (0 <
L < M ), the nodes have no access to the non-communicated
entries. To resolve this ambiguity, we let the nodes use the
entries of their own intermediate estimates in lieu of ones from
the neighbors that have not been communicated, i.e., at node
k, substitute
(I M − Kl,i ) ψ k,i , ∀l ∈ Nk \ {k}

(18)

(I M − Kl,i ) ψ lk,i , ∀l ∈ Nk \ {k}

(19)

for

Based on this approach, we formulate a partial-diffusion
recursive least-squares (PDRLS) algorithm under imperfect
information exchange using (10) and (12) for adaptation and
the following equation for combination:

C. Entry Selection Methods
In order to select L out of M entries of the intermediate
estimates of each node at each iteration, the processes we
utilized are analogous to the selection processes in stochastic
and sequential partial-update schemes [37], [38], [39], [40].
In other words, we use the same schemes as introduced in
[20]. Here, we just review these methods named sequential
partial-diffusion and stochastic partial-diffusion.
In sequential partial-diffusion the entry selection matrices,
Kk,i , are diagonal matrices:


(
κ1,i · · ·
0
1 if ` ∈ J(i mod B̄)+1
 ..

..
..
Kk,i =  .
.
.  , κ1,i = 0 otherwise
0
· · · κM,i
(22)
with B̄ = dM/Le. The number of selection entries at each
iteration is limited by L. The coefficient subsets Ji are not
unique as long as they obey the following requirements [37]:
1) Cardinality of Ji is between 1 and L;
SB̄
2) κ=1 = S where S ={1, 2, . . . , M };
3) Jκ ∩ Jη = ∅, ∀κ, η ∈ 1, . . . , B̄ and κ 6= η.
The description of the entry selection matrices, Kk,i , in
stochastic partial-diffusion is similar to that of sequential one.
The only difference is as follows. At a given
 iteration, i, of the
sequential case one of the sets Jκ , κ = 1, . . . , B̄ is chosen
in advance, whereas for stochastic case, one of the sets Jκ
is sampled at random from {J1 , J2 , . . . , JB̄ }. One might ask
why these methods are considered to organize these selection
matrices. To answer this question, it is worth mentioning that
the nodes need to know which entries of their neighbors
intermediate estimates have been transmitted at each iteration.
These schemes bypass the need for addressing.
Remark. The probability of transmission for all the entries at
each node is equal and expressed as
ρ = L/M

(23)

Moreover, the entry selection matrices, Kk,i , do not depend
on any data/parameter other than L and M .
III. P ERFORMANCE A NALYSIS

In this section, we analyze the performance of the algorithm
(10), (12) and (20) and show that it is asymptotically unbiased
in the mean and converges in the mean-square error sense
wk,i =
X
under some simplifying assumptions. We also provide an
akk ψ k,i +
alk [Kl,i ψ lk,i + (I M − Kl,i ) ψ k,i
]
expression
for mean-square deviation (MSD). We presume
l∈Nk \{k}
that the input data is stochastic in nature and utilize the en(ψ)
ergy conservation arguments previously applied to LMS-type
+v k,i
(20)
adaptive distributed algorithms in, e.g., [9],[12], [21]. Here,
(ψ)
where v k,i denotes the aggregate M × 1 zero mean noise we study the performance of PDRLS algorithm considering
signal and is introduced as follows:
both sequential and stochastic partial-diffusion schemes under
X
(ψ)
(ψ)
v k,i =
alk Kl,i v lk,i
(21) noisy information exchange.
l∈Nk \{k}

This noise represents the aggregate effect on node k of all
selected exchange noises 
from the neighbors of node k while
exchanging the estimates ψ l,i during the combination step.

A. Assumptions
Several simplifying assumptions have been traditionally
adopted in the literature to gain insight into the performance

DRAFT

4

of such adaptive algorithms. To proceed with the analysis we
shall therefore introduce similar assumptions to what has been
used before in the literature, and use them to derive useful
performance measures.
Assumptions. In order to make the analysis tractable, we
introduce the following assumptions on statistical properties
of the measurement data and noise signals.
1) The regression data uk,i are temporally white and spatially independent random variables
with
h
i zero mean and
∗
covariance matrix Ru,k , E uk,i uk,i ≥ 0.

diagonal matrices as follows:
n
o
(ψ)
(ψ)
(ψ)
v i , col v 1,i , . . . , v N,i
n
o
(ψ)
(ψ)
R(ψ)
,
col
R
,
.
.
.
,
R
v
v,1
v,N

(ψ)

The quantities Rv,lk are all zero if l ∈ Nk or when
l = k.
3) The regression data {um,i1 }, the model noise signals
(ψ)
v n (i2 ), and the link noise signals v l1 k1 ,j1 are mutually independent random variables for all indexes
{i1 , i2 , j1 , k1 , l1 , m, n}.
4) In order to make the performance analysis tractable, we
introduce the following ergodicity assumption. For sufficiently large i, at any node k, we can replace Phk,i and
i
−1
P −1
with
their
expected
values,
E
[P
]
and
E
P
k,i
k,i
k,i ,
respectively.
5) For a sufficiently
h
ilarge i, at any node k, we have
E [P k,i ] = E P −1
k,i

ψ̃ k,i = w̃k,i−1 − P k,i u∗k,i [uk,i w̃k,i−1 + v k (i)]
∗
ψ̃ k,i = P k,i P −1
k,i w̃ k,i−1 − P k,i uk,i uk,i w̃ k,i−1

−P k,i u∗k,i v k (i)

Our objective is to examine whether, and how fast, the
weight estimates wk,i from the distributed implementation
(10), (11), and (20) converge towards the solution wo (5).
To do so, we introduce the M1 error vectors:
ψ̃ k,i , wo − ψ k,i

(24)

w̃k,i , wo − wk,i

(25)

Furthermore, denote the network intermediate estimate-error
and estimate-error vector as
n
o
ψ̃ i , col ψ̃ 1,i , . . . , ψ̃ N,i
(26)
w̃i , col {w̃1,i , . . . , w̃N,i }

(27)

Also, collecting the noise signal (21) and its covariances from
across the network into N × 1 block vectors and N × N block

(31)

rewriting (12) as
−1
∗
P −1
k,i = λP k,i−1 + uk,i uk,i

(32)

Substituting (32) into the first term on RHS of (31) yields
∗
ψ̃ k,i = λP k,i P −1
k,i−1 w̃ k,i−1 − P k,i uk,i v k (i)

(33)

We are interested in the steady-state behavior of the matrix
P k,i . As i → ∞, and 0  λ ≤ 1, the steady-state mean value
of P −1
k,i is given by


i
X
lim E [P k,i ] = lim E 
λi−j u∗k,i uk,i 
i→∞

i→∞

j=1
i
X

= lim

B. Network Update Equation

(30)

which can be written as

−1

Assumption 4 is a common assumption in the analysis
of performance of RLS-type algorithm (see for example,
[34], pp.318-319) and the results from assuming that the
regressor vector of each node is an ergodic process, so that
the time average of the nodes rank-one instantaneous regressor
covariance matrix, u∗k,i uk,i , over a sufficiently long time range
can be replaced with the ensemble average (expected value).
Assumption 5 is a good approximation when λ is close to
unity and the condition number of Ru,k is not very large [9],
[15], [21], [34].

(29)

Using the data model (1) and subtracting wo from both sides
of the relation (12) we obtain

(ψ)

2) The noise signal v k (i) and v k,i are temporally white and
spatially independent random variable with zero mean
(ψ)
2
and co(variance)n σv,k
and
o Rv,k , respectively. In addition,

(28)

i→∞



λi−j E u∗k,i uk,i

j=1


=  lim

i→∞

i
X


λi−j  Ru,k

j=1

1
Ru,k
(34)
=
1−λ
Using Assumptions (4) and (5) and relation (31), we have
for large enough i
h
i
−1
P k,i P −1
≈
E
[P
]
E
P
k,i
k,i−1
k,i−1
h
i−1 h
i
≈ E P −1
E P −1
k,i
k,i−1
≈ IM

(35)

and
h
i−1
P k,i ≈ E [P k,i ] ≈ E P −1
≈ (1 − λ) R−1
k,i
u,k

(36)

Consequently for a sufficiently large i, (33) can be approximated by
∗
ψ̃ k,i = λw̃k,i − (1 − λ) R−1
u,k uk,i vk (i)

(37)

On the other hand, subtracting both sides of (20) from wo
gives


X
w̃k,i = I M −
alk Kl,i  ψ̃ k,i
l∈Nk \{k}

+

X
l∈Nk \{k}

(ψ)

alk Kl,i ψ̃ l,i − v k,i

(38)

DRAFT

5

To describe these relations more compactly, we collect the
information from across the network into block vectors and
matrices. Using (26)-(28), leads to
ψ̃ i = λw̃i−1 − Γsi
w̃i = Bi ψ̃ i−1 −
where

(39)

(ψ)
vi

(40)

o
n
−1
Γ , (1 − λ) diag R−1
u,1 , . . . , Ru,N

(41)


si , u∗1,i v 1 (i), . . . , u∗N,i v N (i)


B 1,1,i · · · B 1,N,i

.. 
..
Bi =  ...
.
. 

(42)

B N,1,i

···

(43)

B N,N,i

where
B p,q,i


P

I M − l∈Np \{p} alp Kl,i
= aqp Kq,i


OM

if p = q
if q ∈ Np \ {p} (44)
otherwise

and O M is the M × M zero matrix. So, the network weight
error vector, w̃i , ends up evolving according to the following
stochastic recursion:
(ψ)

w̃i = λBi w̃i−1 − Bi Γsi − v i

(45)

C. Convergence in Mean
Taking expectation of both sides of (45) under Remark and
Assumptions 1 and 2, we find that the mean error vector
evolves according to the following recursion:
E [w̃]i = λQE [w̃i−1 ]

(46)

Q = E [Bi ]

(47)

where

D. Mean-Square Stability
We now study the mean-square performance of PDRLS
under imperfect information exchange. We will also derive
closed-form expressions that characterize the network performance. Doing so, we resort to the energy conservation analysis
of [21], [35], [41], [42]. The details are as follows.
Equating the squared weighted Euclidean norm of both sides
of (45) and applying the expectation operator together with
using Remark and Assumptions 1 and 2 yield the following
weighted variance relation:
h
i
h
i
2
E kw̃i kΣ = E w̃∗i−1 λ2 BTi ΣBi w̃i−1
h
i
h
i
∗(ψ)
(ψ)
+ E s∗i ΓBTi ΣBi Γsi + E v i Σv i
(49)
where Σ is an arbitrary symmetric nonnegative-definite matrix.
Let us evaluate each of the expectations on the right-hand side.
The first expectation is given by
h
i
E w̃∗i−1 λ2 BTi ΣBi w̃i−1
h h
ii
= E E w̃∗i−1 λ2 BTi ΣBi w̃i−1 |w̃i−1
i

 h
= E w̃∗i−1 E λ2 BTi ΣBi


, E w̃∗i−1 Σ0 w̃i−1
h
i
2
= E kw̃i kΣ0
(50)
where we introduce the nonnegative-definite weighting matrix
h
i
Σ0 = E λ2 BTi ΣBi
(51)
Since w̃i−1 is independent of Σ0 , we have
h
i
h
i
2
2
E kw̃i−1 kΣ0 = E kw̃i−1 kE[Σ0 ]

(52)
2

Like [20], Q can be obtained for both stochastic and sequential
partial-diffusion using the definition of Bi . What is most
noteworthy here is to find the value of each Q entry after
applying expectation operator. Therefore, we can write


(1 − ρ + ρar,lp ) I M if p = q
E [B p,q,i ] = ρar,qp I M
if q ∈ Np \ {p} (48)


OM
otherwise
All the entries of Q are real and non-negative and all the
rows of Q add up to unity. This property can be established
for both stochastic and sequential partial-diffusion schemes
and for any value of L [20]. This implies that Q is a right
stochastic matrix. In view of the fact that the eigenvalue of
a stochastic matrix with the largest absolute value (spectral
radius) is equal to one [36], [41], the spectral radius of the
matrix λQ is equal to λ. Thus, for 0  λ ≤ 1, every element
of E [w̃i ] converges to zero as i → ∞, and the estimator is
asymptotically unbiased and convergent in mean. Note that
this is not in fact the necessary and sufficient condition for
convergence of E [w̃i ] as (46) has been obtained under an
independence assumption which is not true in general.

It is convenient to introduce the alternative notation kxkσ
2
to refer to the weighted square quantity kxkΣ , where σ =
vec {Σ}. We shall use these two notations interchangeably.
Using the following equalities for arbitrary matrices
{U , W , Σ, Z} of compatible dimensions:
(U ⊗ W ) (Σ ⊗ Z)

= UΣ ⊗ W Z
(53)


T
vec {U ΣW } =
W ⊗ U vec {Σ}
(54)
h
n
oiT
Tr (ΣW ) = vec W T
vec {Σ} (55)

we have

h
i
σ 0 = E λ2 BTi ΣBi = F σ

(56)

F = λ2 Φ

(57)

Φ = EBTi ⊗ BTi

(58)

where

Here, the efforts to find (58) in [20] can be extended. Therefore, Φ can be established in general form. Again, what is
most important here is to discuss about the probability of
transmitted entries of nodes. This would be helpful in finding
some expectations, E [κt,p,i Kq,i ], we are faced with.

DRAFT

6

At a given iteration, the probability of transmitting two
different entries of single node is [20]


L−1
(59)
ρ
M −1
In the stochastic partial-diffusion scheme, at a given iteration,
the probability of transmitting two entries from two different
nodes is ρ2 . Thus, we have [20]
E [κt,p,i Kq,i ]
=




( 
t,t
M −L
L−1
I
+
ρ
ρ M
M
−1
M −1 J M
2

ρ IM

if p = q
if p 6= q
(60)

where J t,t
M is an M × M single-entry matrix with one at
its (t, t)th entry and zeros elsewhere, for p = 1, . . . , N ,
q = 1, . . . , N , and t = 1, . . . , M . Furthermore, in sequential
partial-diffusion and under same entry selection pattern, at a
given iteration, we have [20]




M −L
L−1
IM + ρ
J t,t
E [κt,p,i Kq,i ] = ρ
M (61)
M −1
M −1
As shown in [20], all the entries of Φ are real and nonnegative. moreover, all their columns sum up to one both for
stochastic and sequential partial-diffusion scheme and for any
value of L.
Second term on RHS of (49)
h
i
E s∗i ΓBTi ΣBi Γsi = vecT {G} Φσ
(62)
where
G = ΓE [si s∗i ] Γ
which, in view of Assumptions, can be expressed as
n
o
2
−1
2
2
G = (1 − λ) σv,1
R−1
u,1 , . . . , σv,N Ru,N
Last term on RHS of (49):
h
i
h n
oi
∗(ψ)
(ψ)
(ψ) ∗(ψ)
E v i Σv i
= E Tr Σv i v i


= vecT R(ψ)
σ
v
The variance relation becomes
h
i
h
i
2
2
E kw̃i kσ = E kw̃i−1 kλ2 Φσ + vecT {G} Φσ


+vecT R(ψ)
σ
v

E. Mean-Square Performance
At steady state, when i → ∞, (66) can be written as
h
i
2
lim E kw̃i k(I 2 2 −F )σ =
N M
i→∞
n
o
vecT {G} Φσ + vecT R(ψ)
σ
v
(67)
Expression (66) is a very useful relation; it allows us to
evaluate the network MSD through proper selection of the
weighting vector σ. The network MSD is defined as the
average value:
N
i
1 X h
2
E kw̃k,i k
i→∞ N

MSDnetwork , lim

which amounts to averaging the MSDs of the individual nodes.
Therefore,
i
h
i
1 h
2
2
E kw̃i k = lim E kw̃i k1/N
MSDnetwork = lim
i→∞
i→∞ N
(69)
This means that in order to recover the network MSD from
relation (66), we should select the weighting vector σ such
that
1
(I N 2 M 2 − F ) σ = vec {I N M }
(70)
N
Solving for σ and substituting back into (66) we arrive at the
following expression for the network MSD
h
n
oi
= N1 vecT {G} Φ + vecT R(ψ)
MSDnetwork
noisy
v
−1

(I N 2 M 2 − F )

(63)

(64)

vec {I N M }

(71)

In perfect information exchange, the last two terms of (66)
don not appear, so we can conclude that the network MSD
deteriorates as follows:
MSDnetwork
noisy

(65)

(68)

k=1

=

+
MSDnetwork
ideal
n
o
1
−1
vecT R(ψ)
(I N 2 M 2 − F ) vec {I N M }
v
N
(72)
IV. S IMULATION R ESULTS

(66)

A recursion of type (66) is stable and convergent if the
matrix λ2 Φ is stable [34]. The entries of Φ are all real-valued
and non-negative. In addition, all the columns of Φ add up
to unity. As a result, Φ is left-stochastic and has unit spectral
radius. Hence, the spectral radius of the matrix λ2 Φ is equal
to λ2 that is smaller than one. Therefore, the mean-square
stability condition for PDRLS under noisy links is the same
as that of PDRLS under noise-free links and the rate of this
convergence is dependent on the value of λ. Again, this need
not translate to be the necessary and sufficient condition for
convergence of recursion of type (66) in actuality as (66) has
been obtained under independence assumption which is not
true in general. Therefore, the mean-square convergence of
PDRLS under noisy links is an open question.

In order to illustrate the performance of each PDRLS
strategy under imperfect information exchange, we consider
an adaptive network with a random topology and N = 10
where each node is, on average, connected to two other
nodes. The measurements were generated according to model
(1), and regressors, uk,i , were chosen Gaussian i.i.d with
randomly generated different diagonal covariance matrices,
Ru,k . The additive noises at nodes are zero mean Gaussian
with variances σ 2v,k and independent of the regression data.
The traces of the covariance matrix regressors and the noise
variances at all nodes, T r (Ru,k ) and σ 2v,k , are shown in
Fig. 1. We also use white Gaussian link noise signals such
(ψ)
2
2
that Rv,lk = σψ,lk
IM . All link noise variances σψ,lk
IM , are
randomly generated and illustrated in Fig. 2. We assign the
link number by the following procedure. We denote the link
from node l to node k as `l,k , where l 6= k. Then, we collect
the links {`l,k , l ∈ Nk \ {k}} in an ascending order of l in the

DRAFT

7

−18

−40

−22
−24
−26

−45
1

2

3

4

5

6

7

8

9

10

Tr(Ru,k ) (dB)

12
11.5

σ 2w,lk (dB)

2
σ v,k
(dB)

−20

−50

11
10.5
10
9.5
9

1

2

3

4

5

6

7

8

9

10

Node Number k

Fig. 1. Variance of the noise (top) and Covariance matrix trace of the input
signal (bottom) at each node.

list Lk (which is a set with ordered elements) for each node.
We concatenate {Lk } in an ascending order of k to get the
overall list L = {L1 , L2 , . . . , LN }. Eventually, the mth link
in the network is given by the mth element in the list L. It is
noteworthy that we adopt the network MSD learning curves of
all figures by averaging over 50 experiments and the unknown
parameter wo of length M = 8 is randomly generated. In Fig.
3, we illustrate the simulated time evolution of network MSD
of the PDRLS algorithm under noisy information exchange
using both sequential and stochastic partial-diffusion schemes
for λ = 0.995. Fig. 4, demonstrates a similar scenario as that in
Fig. 3 when λ = 1. To compare the steady-state performance
of network MSD curves of PDRLS strategies, we examine the
network MSD learning curve of PDRLS strategies again with
ideal links under various numbers of entries communicated at
each iteration, L, when λ = 1 as illustrated in Fig. 5. From
the results above, we can make the following observations:
• The PDRLS algorithm delivers a tradeoff between communications cost and estimation performance under
noise-free links [21];
• The MSD performance of PDRLS with noisy links is
strictly come under the influence of forgetting factor,
λ. So, a minimal change in λ leads to a significant
degradation on MSD performance;
• As can be seen, PDLMS algorithm with noisy links fails
to converge for both stochastic and sequential schemes,
whereas it converges for the noise-free links case..
• The more entries are communicated at each iteration, the
more perturbed weight estimates are interred in the consultation phase. Therefore, the number of communicated
entries has a marked effect on the MSD performance of
PDRLS with noisy links.
V. C ONCLUSION AND F UTURE W ORK
In this work, we investigated the performance of PDRLS
algorithm when links between nodes were noisy. We derived
an analytical expression for the network mean-square deviation, MSD, using weighted energy conservation relation. Our

−55

0

5

10

15

20

25

30

35

40

45

Link Number

2
Fig. 2. The variance profiles for various sources of link noises in dB, σψ,lk
.

results revealed that the noisy links are the main factor in
the performance degradation of PDRLS algorithm. They also
illustrated that the stability conditions for PDRLS under noisy
links are not sufficient to guarantee its convergence. In other
words, considering non-ideal links condition added a new
complexity to the estimation problem for which the PDRLS
algorithm became unstable and did not converge for any value
of forgetting factor, λ. It was also showed that the PDLMS
algorithm with noisy links shows divergent behavior for both
selection schemes (stochastic and sequential), while it does
not for the noise-free links case. In the future, tighter and
accurate bounds on the convergence rate of the mean and
mean-square update equations of PDRLS algorithm with noisy
links can be established. Necessary and sufficient conditions
for convergence of the algorithm with noisy links need to be
derived. These can be addressed in the future.
R EFERENCES
[1] C. G. Lopes and A. H. Sayed, “Incremental adaptive strategies over
distributed networks,” Signal Processing, IEEE Transactions on, vol. 55,
no. 8, pp. 4064–4077, 2007.
[2] M. G. Rabbat and R. D. Nowak, “Quantized incremental algorithms
for distributed optimization,” Selected Areas in Communications, IEEE
Journal on, vol. 23, no. 4, pp. 798–808, 2005.
[3] A. Nedic and D. P. Bertsekas, “Incremental subgradient methods for
nondifferentiable optimization,” SIAM Journal on Optimization, vol. 12,
no. 1, pp. 109–138, 2001.
[4] A. Bertrand and M. Moonen, “Consensus-based distributed total least
squares estimation in ad hoc wireless sensor networks,” Signal Processing, IEEE Transactions on, vol. 59, no. 5, pp. 2320–2330, 2011.
[5] S. S. Stanković, M. S. Stanković, and D. M. Stipanović, “Decentralized
parameter estimation by consensus based stochastic approximation,”
Automatic Control, IEEE Transactions on, vol. 56, no. 3, pp. 531–543,
2011.
[6] G. Mateos, I. D. Schizas, and G. B. Giannakis, “Distributed recursive
least-squares for consensus-based in-network adaptive estimation,” Signal Processing, IEEE Transactions on, vol. 57, no. 11, pp. 4583–4588,
2009.
[7] J. Chen and A. H. Sayed, “Diffusion adaptation strategies for distributed
optimization and learning over networks,” Signal Processing, IEEE
Transactions on, vol. 60, no. 8, pp. 4289–4305, 2012.
[8] X. Zhao, S.-Y. Tu, and A. H. Sayed, “Diffusion adaptation over networks
under imperfect information exchange and non-stationary data,” Signal
Processing, IEEE Transactions on, vol. 60, no. 7, pp. 3460–3475, 2012.

DRAFT

8

−5

−5

L
L
L
L
L

−10

−15

−20
−25
−30
−35
−40

−20
−25
−30
−35
−40

−50

0

100

200

300

400

500

600

700

800

900

−55

1000

0

100

200

300

−5

500

600

700

800

900

1000

−5

L
L
L
L
L

−10

=0
=1
=2
=4
=8

L
L
L
L
L

−10
−15

Network MSD (dB)

−15

Network MSD (dB)

400

i (iteration)

i (iteration)

−20
−25
−30
−35
−40

=0
=1
=2
=4
=8

−20
−25
−30
−35
−40
−45

−45
−50

=0
=1
=2
=4
=8

−45

−45
−50

L
L
L
L
L

−10

Network MSD (dB)

Network MSD (dB)

−15

=0
=1
=2
=4
=8

−50

0

100

200

300

400

500

600

700

800

900

1000

i (iteration)

−55

0

100

200

300

400

500

600

700

800

900

1000

i (iteration)

Fig. 3. Simulated network MSD curves for partial diffusion RLS algorithms
using sequential (top) and stochastic (bottom) with different number of entries
communicated under noisy links when λ = 0.995.

Fig. 4. Simulated network MSD curves for partial diffusion RLS algorithms
using sequential (top) and stochastic (bottom) with different number of entries
communicated under noisy links λ = 1.

[9] A. Bertrand, M. Moonen, and A. H. Sayed, “Diffusion bias-compensated
RLS estimation over adaptive networks,” Signal Processing, IEEE
Transactions on, vol. 59, no. 11, pp. 5212–5224, 2011.
[10] S. Chouvardas, K. Slavakis, and S. Theodoridis, “Adaptive robust
distributed learning in diffusion sensor networks,” Signal Processing,
IEEE Transactions on, vol. 59, no. 10, pp. 4692–4707, 2011.
[11] N. Takahashi, I. Yamada, and A. H. Sayed, “Diffusion least-mean
squares with adaptive combiners: Formulation and performance analysis,” Signal Processing, IEEE Transactions on, vol. 58, no. 9, pp. 4795–
4810, 2010.
[12] F. S. Cattivelli and A. H. Sayed, “Diffusion LMS strategies for distributed estimation,” Signal Processing, IEEE Transactions on, vol. 58,
no. 3, pp. 1035–1048, 2010.
[13] C. G. Lopes and A. H. Sayed, “Diffusion least-mean squares over
adaptive networks: Formulation and performance analysis,” Signal Processing, IEEE Transactions on, vol. 56, no. 7, pp. 3122–3136, 2008.
[14] S.-Y. Tu and A. H. Sayed, “Diffusion strategies outperform consensus
strategies for distributed estimation over adaptive networks,” Signal
Processing, IEEE Transactions on, vol. 60, no. 12, pp. 6217–6234, 2012.
[15] F. S. Cattivelli, C. G. Lopes, and A. H. Sayed, “Diffusion recursive
least-squares for distributed estimation over adaptive networks,” Signal
Processing, IEEE Transactions on, vol. 56, no. 5, pp. 1865–1877, 2008.
[16] Ø. L. Rørtveit, J. H. Husøy, and A. H. Sayed, “Diffusion LMS
with communication constraints,” in Signals, Systems and Computers
(ASILOMAR), 2010 Conference Record of the Forty Fourth Asilomar
Conference on. IEEE, 2010, pp. 1645–1649.
[17] C. G. Lopes and A. H. Sayed, “Diffusion adaptive networks with changing topologies,” in 2008 IEEE International Conference on Acoustics,
Speech and Signal Processing, 2008.

[18] N. Takahashi and I. Yamada, “Link probability control for probabilistic
diffusion least-mean squares over resource-constrained networks,” in
Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on. IEEE, 2010, pp. 3518–3521.
[19] X. Zhao and A. H. Sayed, “Single-link diffusion strategies over adaptive
networks,” in Acoustics, Speech and Signal Processing (ICASSP), 2012
IEEE International Conference on. IEEE, 2012, pp. 3749–3752.
[20] R. Arablouei, S. Werner, Y.-F. Huang, and K. Dogancay, “Distributed
least mean-square estimation with partial diffusion,” Signal Processing,
IEEE Transactions on, vol. 62, no. 2, pp. 472–484, 2014.
[21] R. Arablouei, K. Dogancay, S. Werner, and Y.-F. Huang, “Adaptive
distributed estimation based on recursive least-squares and partial diffusion,” Signal Processing, IEEE Transactions on, vol. 62, no. 14, pp.
3510–3522, 2014.
[22] M. O. Sayin and S. S. Kozat, “Single bit and reduced dimension diffusion strategies over distributed networks,” Signal Processing Letters,
IEEE, vol. 20, no. 10, pp. 976–979, 2013.
[23] ——, “Compressive diffusion strategies over distributed networks for
reduced communication load,” Signal Processing, IEEE Transactions
on, vol. 62, no. 20, pp. 5308–5323, 2014.
[24] S. Chouvardas, K. Slavakis, and S. Theodoridis, “Trading off complexity
with communication costs in distributed adaptive learning via Krylov
subspaces for dimensionality reduction,” Selected Topics in Signal
Processing, IEEE Journal of, vol. 7, no. 2, pp. 257–273, 2013.
[25] R. Abdolee and B. Champagne, “Diffusion LMS algorithms for sensor
networks over non-ideal inter-sensor wireless channels,” in Distributed
Computing in Sensor Systems and Workshops (DCOSS), 2011 International Conference on. IEEE, 2011, pp. 1–6.
[26] A. Khalili, M. A. Tinati, A. Rastegarnia, and J. A. Chambers, “Tran-

DRAFT

9

[37] K. Dogancay, Partial-update adaptive signal processing: Design Analysis and Implementation. Academic Press, 2008.
[38] M. Godavarti and A. O. Hero III, “Partial update LMS algorithms,”
Signal Processing, IEEE Transactions on, vol. 53, no. 7, pp. 2382–2399,
2005.
[39] S. C. Douglas, “Adaptive filters employing partial updates,” Circuits and
Systems II: Analog and Digital Signal Processing, IEEE Transactions
on, vol. 44, no. 3, pp. 209–216, 1997.
[40] J. R. Treichler, C. R. Johnson, and M. G. Larimore, Theory and design
of adaptive filters. Wiley, 1987.
[41] T. Y. Al-Naffouri and A. H. Sayed, “Transient analysis of datanormalized adaptive filters,” Signal Processing, IEEE Transactions on,
vol. 51, no. 3, pp. 639–652, 2003.
[42] N. R. Yousef and A. H. Sayed, “A unified approach to the steadystate and tracking analyses of adaptive filters,” Signal Processing, IEEE
Transactions on, vol. 49, no. 2, pp. 314–324, 2001.

0

Network MSD (dB)

−10

−20

−52.5
−53

−30
−53.5
780

800

820

−40

−50

−60

0

100

200

300

400

500

600

700

800

900

1000

700

800

900

1000

i (iteration)

0

Network MSD (dB)

−10

−20

−52
−52.5
−53

−30

−53.5
780

800

820

−40

−50

−60

0

100

200

300

400

500

600

i (iteration)

Fig. 5. Simulated network MSD curves for partial diffusion RLS algorithms
using sequential (top) and stochastic (bottom) with different number of entries
communicated under ideal links when λ = 1.

[27]

[28]

[29]

[30]

[31]
[32]

[33]

[34]
[35]
[36]

sient analysis of diffusion leastmean squares adaptive networks with
noisy channels,” International Journal of Adaptive Control and Signal
Processing, vol. 26, no. 2, pp. 171–180, 2012.
A. Khalili, M. A. Tinati, A. Rastegarnia, and J. Chambers, “Steady-state
analysis of diffusion LMS adaptive networks with noisy links,” Signal
Processing, IEEE Transactions on, vol. 60, no. 2, pp. 974–979, 2012.
S.-Y. Tu and A. H. Sayed, “Adaptive networks with noisy links,”
in Global Telecommunications Conference (GLOBECOM 2011), 2011
IEEE. IEEE, 2011, pp. 1–5.
A. Khalili, M. A. Tinati, and A. Rastegarnia, “Performance analysis of
distributed incremental LMS algorithm with noisy links,” International
Journal of Distributed Sensor Networks, vol. 2011, 2011.
——, “Steady-state analysis of incremental LMS adaptive networks with
noisy links,” Signal Processing, IEEE Transactions on, vol. 59, no. 5,
pp. 2416–2421, 2011.
——, “Analysis of incremental RLS adaptive networks with noisy links,”
IEICE Electronics Express, vol. 8, no. 9, pp. 623–628, 2011.
S. Kar and J. M. F. Moura, “Distributed consensus algorithms in sensor
networks with imperfect communication: Link failures and channel
noise,” Signal Processing, IEEE Transactions on, vol. 57, no. 1, pp.
355–369, 2009.
G. Mateos, I. D. Schizas, and G. B. Giannakis, “Performance analysis
of the consensus-based distributed LMS algorithm,” EURASIP Journal
on Advances in Signal Processing, vol. 2009, p. 68, 2009.
A. H. Sayed, Adaptive filters. John Wiley {&} Sons, 2011.
——, Fundamentals of adaptive filtering. John Wiley & Sons, 2003.
C. D. Meyer, Matrix analysis and applied linear algebra. Siam, 2000,
vol. 2.

