Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation over Adaptive Networks

I Introduction

Adaptive networks consist of a collection of spatially distributed nodes that are linked together through a topology and that cooperate with each other through local interactions. Adaptive networks are well-suited to perform decentralized information processing and inference tasks and to model complex and self-organized behavior encountered in biological systems .

We examine two types of fully decentralized strategies, namely, consensus strategies and diffusion strategies. The consensus strategy was originally proposed in the statistics literature and has since then been developed into an elegant procedure to enforce agreement among cooperating nodes. Average consensus and gossip algorithms have been studied extensively in recent years, especially in the control literature , and applied to the study of multi-agent formations , distributed optimization , and distributed estimation problems . Original implementations of the consensus strategy relied on the use of two time-scales : one time-scale for the collection of measurements across the nodes and another time-scale to iterate sufficiently enough over the collected data to attain agreement before the process is repeated. Unfortunately, two time-scale implementations hinder the ability to perform real-time recursive estimation and adaptation when measurement data keep streaming in. For this reason, in this work, we focus instead on consensus implementations that operate in a single time-scale. Such implementations appear in several recent works, including , and are largely motivated by the procedure developed earlier in for the solution of distributed optimization problems.

The second class of algorithms that we consider deals with diffusion strategies, which were originally introduced for the solution of distributed estimation and adaptation problems in . The main motivation for the introduction of diffusion strategies in these works was the desire to develop distributed schemes that are able to respond in real-time to continuous streaming of data at the nodes by operating over a single time-scale. A useful overview of diffusion strategies appears in . Since their inception, diffusion strategies have been applied to model various forms of complex behavior encountered in nature ; they have also been adopted to solve distributed optimization problems advantageously in ; and have been studied under varied conditions in as well. Diffusion strategies are inherently single time-scale implementations and are therefore naturally amenable to real-time and recursive implementations. It turns out that the dynamics of the consensus and diffusion strategies differ in important ways, which in turn impact the mean-square behavior of the respective networks in a fundamental manner.

The analysis in this paper will confirm that under constant step-sizes, diffusion strategies allow information to diffuse more thoroughly through networks and this property has a favorable effect on the evolution of the network. It will be shown that diffusion networks converge faster and reach lower mean-square deviation than consensus networks, and their mean-square stability is insensitive to the choice of the combination weights. In comparison, and surprisingly, it is shown that consensus networks can become unstable even if all the individual nodes are stable and able to solve estimation task on their own. In other words, the learning curve of a cooperative consensus network can diverge even if the learning curves for the non-cooperative individual nodes converge. When this occurs, cooperation over the network leads to a catastrophic failure of the estimation task. This behavior does not occur for diffusion networks: we will show that stability of the individual nodes is sufficient to ensure stability of the diffusion network regardless of the combination weights. The properties revealed in this paper indicate that there needs to be some care with the use of consensus strategies for adaptation because they can lead to network failure even if the individual nodes are stable and well-behaved. The analysis also suggests that diffusion strategies provide a proper way to enforce cooperation over networks; their operation is such that diffusion networks will always remain stable irrespective of the combination topology.

II Estimation Strategies over Networks

where $\boldsymbol{v}_{k}(i)$ is measurement noise with variance $\sigma^{2}_{v,k}$ and assumed to be temporally white and spatially independent, i.e.,

in terms of the Kronecker delta function. The regression data $\boldsymbol{u}_{k,i}$ are likewise assumed to be temporally white and spatially independent. The noise $\boldsymbol{v}_{k}(i)$ and the regressors $\{\boldsymbol{u}_{l,j}\}$ are assumed to be independent of each other for all $\{k,l,i,j\}$. All random processes are assumed to be zero mean. Note that we use boldface letters to denote random quantities and normal letters to denote their realizations or deterministic quantities. Models of the form (1) are useful in capturing many situations of interest, such as estimating the parameters of some underlying physical phenomenon, tracking a moving target by a collection of nodes, or estimating the location of a nutrient source or predator in biological networks (see, e.g., ); these models are also useful in the study of the performance limits of combinations of adaptive filters .

The objective of the network is to estimate $w^{\circ}$ in a distributed manner through an online learning process. The nodes estimate $w^{\circ}$ by seeking to minimize the following global cost function:

In the sequel, we describe the algorithms pertaining to the consensus and diffusion strategies that we study in this article, in addition to the non-cooperative mode of operation. Afterwards, we move on to the main theme of this work, which is to show why diffusion networks outperform consensus networks. We may remark that the same strategies can be used to optimize global cost functions where the individual costs are not necessarily quadratic in $w$ as in (3). Most of the mean-square analysis performed here can be extended to this more general scenario — see, e.g., and the references therein.

In the non-cooperative mode of operation, each node $k$ operates independently of the other nodes and estimates $w^{\circ}$ by means of a local LMS adaptive filter applied to its data $\{d_{k}(i),u_{k,i}\}$. The filter update takes the following form :

where $\mu_{k}>0$ is the constant step-size used by node $k$. In (4), the vector $w_{k,i}$ denotes the estimate for $w^{\circ}$ that is computed by node $k$ at time $i$. Note that for the underlying model where $R_{u,k}>0$ for all $k$, every individual node can employ (4) to estimate $w^{\circ}$ independently if desired. Studies allowing for other observability conditions for diffusion and consensus strategies, including possibly singular covariance matrices, appear in .

II-B Cooperative Strategies

In the cooperative mode of operation, nodes interact with their neighbors by sharing information. In this article, we study three cooperative strategies for distributed estimation.

The consensus strategy often appears in the literature in the following form (see, e.g., Eq. (1.20) in , Eq. (19) in , and Eq. (9) in ):

where $\{b_{l,k}\}$ is a set of nonnegative coefficients. It should be noted that in most works on consensus implementations, especially in the context of distributed optimization problems , the step-sizes $\{\mu_{k}(i)\}$ that are used in (5) depend on the time-index $i$ and are required to satisfy

In other words, for each node $k$, the step-size sequence $\mu_{k}(i)$ is required to vanish as $i\rightarrow\infty$. Under such conditions, it is known that consensus strategies allow the nodes to reach agreement about $w^{\circ}$ . Here, instead, we will use constant step-sizes $\{\mu_{k}\}$. This is because we are interested in studying the adaptation and learning abilities of the networks. Constant step-sizes are critical to endow networks with continuous adaptation and tracking abilities; otherwise, under (6), once the step-sizes have decayed to zero, the network stops adapting and learning is turned off.

We can rewrite recursion (5) in a more compact and revealing form by combining the first two terms on the right-hand side of (5) and by introducing the following coefficients:

In this way, recursion (5) can be rewritten equivalently as (see, e.g., expression (7.1) in and expression (1.20) in ):

The entry $a_{l,k}$ denotes the weight that node $k$ assigns to the estimate $w_{l,i-1}$ received from its neighbor $l$ (see Fig. 1); note that the weights $\{a_{l,k}\}$ are nonnegative for $l\neq k$ and that $a_{k,k}$ is nonnegative for sufficiently small step-sizes. If we collect the nonnegative weights $\{a_{l,k}\}$ into an $N\times N$ matrix $A$, then it follows from (7) that the combination matrix $A$ satisfies the following properties:

where $\mathds{1}$ is a vector of size $N$ with all entries equal to one. That is, the weights on the links arriving at node $k$ add up to one, which is equivalent to saying that the matrix $A$ is left-stochastic. Moreover, if two nodes $l$ and $k$ are not linked, then their corresponding entry $a_{l,k}$ is zero.

B.2. ATC Diffusion Strategy

Diffusion strategies for the optimization of (3) in a fully decentralized manner were derived in by applying a completion-of-squares argument, followed by a stochastic approximation step and an incremental approximation step — see . The adapt-then-combine (ATC) form of the diffusion strategy is described by the following update equations :

The above strategy consists of two steps. The first step of (10) involves local adaptation, where node $k$ uses its own data $\{d_{k}(i),u_{k,i}\}$ to update its weight estimate from $w_{k,i-1}$ to an intermediate value $\psi_{k,i}$. The second step of (10) is a consultation (combination) step where the intermediate estimates $\{\psi_{l,i}\}$ from the neighborhood of node $k$ are combined through weights $\{a_{l,k}\}$ that satisfy (9) to obtain the updated weight estimate $w_{k,i}$.

B.3. CTA Diffusion Strategy

Another variant of the diffusion strategy is the combine-then-adapt (CTA) form, which is described by the following update equations :

Thus, comparing the ATC and CTA strategies, we note that the order of the consultation and adaptation steps are simply reversed. The first step of (11) involves a consultation step, where the existing estimates $\{w_{l,i-1}\}$ from the neighbors of node $k$ are combined through the weights $\{a_{l,k}\}$. The second step of (11) is a local adaptation step, where node $k$ uses its own data $\{d_{k}(i),u_{k,i}\}$ to update its weight estimate from the intermediate value $\psi_{k,i-1}$ to $w_{k,i}$.

B.4. Comparing Diffusion and Consensus Strategies

For ease of comparison, we rewrite below the recursions that correspond to the consensus (8), ATC diffusion (10), and CTA diffusion (11) strategies in a single update:

Note that the first terms on the right hand side of these recursions are all the same. For the second terms, only variable $w_{k,i-1}$ appears in the consensus strategy (12), while the diffusion strategies (13)-(14) incorporate the estimates $\{w_{l,i-1}\}$ from the neighborhood of node $k$ into the update of $w_{k,i}$. Moreover, in contrast to the consensus (12) and CTA diffusion (14) strategies, the ATC diffusion strategy (13) further incorporates the influence of the data $\{d_{l}(i),u_{l,i}\}$ from the neighborhood of node $k$ into the update of $w_{k,i}$. These differences in the order by which the computations are performed have important implications on the evolution of the weight-error vectors across consensus and diffusion networks. It is important to note that the diffusion strategies (13)-(14) are able to incorporate additional information into their processing steps without being more complex than the consensus strategy. All three strategies have the same computational complexity and require sharing the same amount of data (see Table I), as can be ascertained by comparing the actual implementations (8), (10), and (11). The key fact to note is that the diffusion implementations first generate an intermediate state variable, which is subsequently used in the final update. This important ordering of the calculations has a critical influence on the performance of the algorithms, as we now move on to reveal.

III Mean-Square Performance Analysis

The mean-square performance of diffusion networks has been studied in detail in by applying energy conservation arguments . Following , we will first show how to carry out the performance analysis in a unified manner that covers both diffusion and consensus strategies (see Table II further ahead, which highlights how the parameters for both strategies differ). Subsequently, we use the resulting performance expressions to carry out detailed comparisons and to establish and highlight some surprising and interesting differences in performance.

Let the error vector for an arbitrary node $k$ be denoted by

We collect all error vectors and step-sizes across the network into a block vector and block matrix:

where the notation $\text{col}\{\cdot\}$ denotes the vector that is obtained by stacking its arguments on top of each other, and the notation $\text{diag}\{\cdot\}$ constructs a diagonal matrix from its arguments. We further introduce the extended combination matrix:

where the quantities $\boldsymbol{\mathcal{B}}_{i}$ and $\boldsymbol{y}_{i}$ are listed in Table II and where $\boldsymbol{\mathcal{R}}_{i}$ is a block diagonal matrix and $\boldsymbol{s}_{i}$ is a block column vector:

III-B Mean Stability

To begin with, the matrix $\mathcal{B}$ is block diagonal in the non-cooperative case and equal to

Therefore, for each of the individual nodes to be stable in the mean, it is necessary and sufficient that the step-sizes $\{\mu_{k}\}$ be selected to satisfy

since the matrices $\mathcal{M}$ from (17) and $\mathcal{R}$ from (23) are block diagonal. Condition (26) is equivalent to

where $\lambda_{\max}(\cdot)$ denotes the maximum eigenvalue of its Hermitian matrix argument. Condition (27) guarantees that when each node acts individually and applies the LMS recursion (4), then the mean of its weight error vector will tend asymptotically to zero. That is, by selecting the step-sizes to satisfy (27), all individual nodes will be stable in the mean.

Now consider the matrix $\mathcal{B}$ in the consensus case; it is equal to

It is seen in this case that the stability of $\mathcal{B}_{\text{cons}}$ depends on $\mathcal{A}$. The fact that the stability of the consensus strategy is sensitive to the choice of the combination matrix is known in the consensus literature for the conventional implementation for computing averages and which does not involve streaming data or gradient noise . Here, we are studying the more demanding case of the single time-scale consensus iteration (8) in the presence of both noisy and streaming data. It is clear from (28) that the choice of $A$ can destroy the stability of the consensus network even when the step-sizes are chosen according to (27) and all nodes are stable on their own. This behavior does not occur for diffusion networks where the matrices $\{\mathcal{B}\}$ for the ATC and CTA diffusion strategies are instead given by

The following result clarifies these statements.

irrespective of the choice of the left-stochastic matrices $A$. Moreover, if the combination matrix $A$ is symmetric, then the eigenvalues of $\mathcal{B}_{\rm{cons}}$ are less than or equal to the corresponding eigenvalues of $\mathcal{B}_{\rm{ncop}}$, i.e.,

where the eigenvalues $\{\lambda_{l}(\cdot)\}$ are arranged in decreasing order, i.e., $\lambda_{l_{1}}(\cdot)\geq\lambda_{l_{2}}(\cdot)$ if $l_{1}\leq l_{2}$.

Result (30) establishes the important conclusion that the coefficient matrix $\mathcal{B}$ for the diffusion strategies is stable whenever $\mathcal{B}_{\text{ncop}}$ (or, from (26), each of the matrices $\{I_{M}-\mu_{k}R_{u,k}\}$) is stable; this conclusion is independent of $A$. The stability of the matrices $\{I_{M}-\mu_{k}R_{u,k}\}$ is ensured by any step-size satisfying (27). Therefore, stability of the individual nodes will always guarantee the stability of $\mathcal{B}$ in the ATC and CTA diffusion cases, regardless of the choice of $A$. This is not the case for the consensus strategy (8); even when the step-sizes $\{\mu_{k}\}$ are selected to satisfy (27) so that all individual nodes are mean stable, the matrix $\mathcal{B}_{\rm cons}$ can still be unstable depending on the choice of $A$ (and, therefore, on the network topology as well). Therefore, if we start from a collection of nodes that are behaving in a stable manner on their own, and if we connect them through a topology and then apply consensus to solve the same estimation problem through cooperation, then the network may end up being unstable and the estimation task can fail drastically (see Fig. 2 further ahead). Moreover, it is further shown in Appendix A that when $A$ is symmetric, the consensus strategy is mean-stable for step-sizes satisfying:

Note from (9) that since $A$ is a left-stochastic matrix, its spectral radius is equal to one and one of its eigenvalues is also equal to one , i.e., $\lambda_{1}(A)=\rho(A)=1$. This implies that the upper bound in (32) is less than the upper bound in (27) so that diffusion networks are stable over a wider range of step-sizes. Actually, the upper bound in (32) can be much smaller than the one in (27) or even zero because $\lambda_{\min}(A)$ can be negative or equal to $-1$.

What if some of the nodes are unstable in the mean to begin with? How would the behavior of the diffusion and consensus strategies differ? Assume that there is at least one individual unstable node, i.e., $\lambda_{l}(\mathcal{B}_{\text{ncop}})\leq-1$ for some $l$ so that $\rho(\mathcal{B}_{\text{ncop}})\geq 1$. Then, we observe from (30) that the spectral radius of $\mathcal{B}_{\text{atc}}$ can still be smaller than one even if $\rho(\mathcal{B}_{\text{ncop}})\geq 1$. It follows that even if some individual node is unstable, the diffusion strategies can still be stable if we properly choose $A$. In other words, diffusion cooperation has a stabilizing effect on the network. In contrast, if there is at least one individual unstable node and the combination matrix $A$ is symmetric, then from (31), no matter how we choose $A$, the $\rho(\mathcal{B}_{\text{cons}})$ will be larger than or equal to one and the consensus network will be unstable.

The above results suggest that fusing results from neighborhoods according to the consensus strategy (8) is not necessarily the best thing to do because it can lead to instability and catastrophic failure. On the other hand, fusing the results from neighbors via diffusion ensures stability regardless of the topology.

B.2. Example: Two-Node Networks

To illustrate these important observations, let us consider an example consisting of two cooperating nodes; in this case, it is possible to carry out the calculations analytically in order to highlight the various patterns of behavior. Later, in the simulations section, we illustrate the behavior for networks with multiple nodes. Thus, consider a network consisting of $N=2$ nodes. For simplicity, we assume the weight vector $w^{\circ}$ is a scalar, and $R_{u,1}=\sigma^{2}_{u,1}$ and $R_{u,2}=\sigma^{2}_{u,2}$. Without loss of generality, we assume $\mu_{1}\sigma^{2}_{u,1}\leq\mu_{2}\sigma^{2}_{u,2}$. The combination matrix for this example is of the form (Fig. 2):

with $a,b\in$. When desired, a symmetric $A$ can be selected by simply setting $a=b$. Then, using (33), we get

so that both individual nodes are stable in the mean by virtue of (27). Then, by Theorem 1, the ATC diffusion network will also be stable in the mean for any choice of the parameters $\{a,b\}$. We now verify that there are choices for $\{a,b\}$ that will turn the consensus network unstable. Specifically, we verify below that if $a$ and $b$ happen to satisfy

then consensus will lead to unstable network behavior even though both individual nodes are stable. Indeed, note first that the minimum eigenvalue of $\mathcal{B}_{\text{cons}}$ is given by:

From the first equality of (39), we know that $D\geq 0$ and, hence, $\lambda_{\min}(\mathcal{B}_{\text{cons}})$ is real. When (36)-(37) are satisfied, we have that $(a+b+\mu_{1}\sigma^{2}_{u,1}-\mu_{2}\sigma^{2}_{u,2})$ and $4b(\mu_{2}\sigma^{2}_{u,2}-\mu_{1}\sigma^{2}_{u,1})$ in the second equality of (39) are nonnegative. It follows that the consensus network is unstable since

In Fig. 2(a), we set $\mu_{1}\sigma^{2}_{u,1}=0.4$ and $\mu_{2}\sigma^{2}_{u,2}=0.6$ so that each individual node is stable. If we now set $a=b=0.85$, then (37) is satisfied and the consensus strategy becomes unstable.

so that node $1$ is still stable, whereas node $2$ becomes unstable. From the first equality of (39), we again conclude that

That is, in this second case, no matter how we choose the parameters $\{a,b\}$, the consensus network is always unstable. In contrast, the diffusion network is able to stabilize the network. To see this, we set $b=1-a$ so that the eigenvalues of $\mathcal{B}_{\text{atc}}$ in (34) are $\{0,1-\mu_{1}\sigma^{2}_{u,1}-(\mu_{2}\sigma^{2}_{u,2}-\mu_{1}\sigma^{2}_{u,1})a\}$. Some algebra shows that the diffusion network is stable if $a$ satisfies

In Fig. 2(b), we set $\mu_{1}\sigma^{2}_{u,1}=0.4$ and $\mu_{1}\sigma^{2}_{u,1}=2.4$ so that node $1$ is stable, but node $2$ is unstable. If we now set $a=1-b=0.2$, then (43) is satisfied and the diffusion strategies become stable even when the non-cooperative and consensus strategies are unstable.

III-C Mean-Square Stability

We now examine the stability in the mean-square sense of the consensus and diffusion strategies. Let $\Sigma$ denote an arbitrary nonnegative-definite matrix that we are free to choose. From (19), we get the following weighted variance relation for sufficiently small step-sizes:

III-D Mean-Square Deviation

The mean-square deviation (MSD) measure is used to assess how well the nodes in the network estimate the weight vector, $w^{\circ}$. The MSD at node $k$ is defined as follows:

where $\|\cdot\|$ denotes the Euclidean norm for vectors. The network MSD is defined as the average MSD across the network, i.e.,

Iterating (44), we can obtain a series expression for the network MSD as:

We can also obtain a series expansion for the MSD at each individual node $k$ as follows:

where $e_{k}$ denotes the $k$th column of the identity matrix $I_{N}$. Expressions (49)-(48) relate the MSDs directly to the quantities $\{\mathcal{B},\mathcal{Y}\}$ from Table II.

IV Comparison of Mean-Square Performance for Homogeneous Agents

In the previous section, we compared the stability of the various estimation strategies in the mean and mean-square senses. In particular, we established that stability of the individual nodes ensures stability of diffusion networks irrespective of the combination topology. In the sequel, we shall assume that the step-sizes are sufficiently small so that conditions (27) and (32) hold and the diffusion and consensus networks are stable in the mean and mean-square sense; as well as the individual nodes. Under these conditions, the networks achieve steady-state operation. We now use the MSD expressions derived above to establish that ATC diffusion achieves lower (and, hence, better) MSD values than the consensus, CTA, and non-cooperative strategies. In this way, diffusion strategies do not only ensure stability of the cooperative behavior but they also lead to improved mean-square-error performance. We establish these results under the following reasonable condition.

All nodes in the network use the same step-size, $\mu_{k}=\mu$, and they observe data arising from the same covariance data so that $R_{u,k}=R_{u}$ for all $k$. In other words, we are dealing with a network of homogeneous nodes interacting with each other. In this way, it is possible to quantify the differences in performance without biasing the results by differences in the adaptation mechanism (step-sizes) or in the covariance matrices of the regression data at the nodes.

Under Assumption 1, it holds that $\mathcal{M}=\mu I_{NM}$ and $\mathcal{R}=I_{N}\otimes R_{u}$, and thus the matrices $\mathcal{B}$ and $\mathcal{Y}$ in Table II reduce to the expressions shown in Table III, where we introduced the diagonal matrix

Note that the ATC and CTA diffusion strategies now have the same coefficient matrix $\mathcal{B}$. We explain in the sequel the terms that appear in the last row of Table III.

As mentioned before, the stability and mean-square-error performance of the various algorithms depend on the corresponding matrix $\mathcal{B}$; therefore, in this section, we examine more closely the eigen-structure of $\mathcal{B}$. For the distributed strategies (diffusion and consensus), the eigen-structure of $\mathcal{B}$ will depend on the combination matrix $A$. Thus, let $r_{l}$ and $s_{l}$ ($l=1,2,\ldots,N$) denote an arbitrary pair of right and left eigenvectors of $A^{T}$ corresponding to the eigenvalue $\lambda_{l}(A)$. That is,

We scale the vectors $r_{l}$ and $s_{l}$ to satisfy:

Recall that $\lambda_{1}(A)=\rho(A)=1$. Furthermore, we let $z_{m}$ ($m=1,2,\ldots,M$) denote the eigenvector of the covariance matrix $R_{u}$ that is associated with the eigenvalue $\lambda_{m}(R_{u})$. That is,

Since $R_{u}$ is Hermitian and positive-definite, the $\{z_{m}\}$ are orthonormal, i.e., $z^{*}_{m_{2}}z_{m_{1}}=\delta_{m_{1}m_{2}}$, and the $\{\lambda_{m}(R_{u})\}$ are positive. The following result describes the eigen-structure of the matrix $\mathcal{B}$ in terms of the eigen-structures of $\{A^{T},R_{u}\}$ for the diffusion and consensus algorithms of Table III. Note that the results for any of these distributed strategies collapse to the result for the non-cooperative strategy when we set $\lambda_{l}(A)=1$ for all $l$.

The matrices $\{\mathcal{B}\}$ appearing in Table III for the diffusion and consensus strategies have right and left eigenvectors $\{r^{b}_{l,m},s^{b}_{l,m}\}$ given by:

with the corresponding eigenvalues, $\lambda_{l,m}(\mathcal{B})$, shown in Table III for $l=1,2,\ldots,N$ and $m=1,2,\ldots,M$. Note that while the eigenvectors are the same for the diffusion and consensuses strategies, the corresponding eigenvalues are different.

We only consider the diffusion case and denote its coefficient matrix by $\mathcal{B}_{\text{diff}}=A^{T}\otimes I_{M}-A^{T}\otimes\mu R_{u}$; the same argument applies to the consensus strategy. We multiply $\mathcal{B}_{\text{diff}}$ by the $r^{b}_{l,m}$ defined in (54) from the right and obtain

where we used the Kronecker product property $(A\otimes B)(C\otimes D)=AC\otimes BD$ for matrices $\{A,B,C,D\}$ of compatible dimensions . In a similar manner, we can verify that $\mathcal{B}_{\text{diff}}$ has left eigenvector $s^{b}_{l,m}$ defined in (54) with the corresponding eigenvalue $\lambda_{l,m}(\mathcal{B})$ from Table III. ∎

where equality holds if $A=I_{N}$ or when the step-size satisfies:

IV-B Network MSD Performance

We now compare the MSD performance. Note that the expressions for the individual MSD in (49) and the network MSD in (48) depend on $\mathcal{B}$ in a nontrivial manner. To simplify these MSD expressions, we introduce the following assumption on the combination matrix.

The combination matrix $A$ is diagonalizable, i.e., there exists an invertible matrix $U$ and a diagonal matrix $\Lambda$ such that

That is, the columns of $U$ consist of the right eigenvectors of $A^{T}$ and the rows of $U^{-1}$ consist of the left eigenvectors of $A^{T}$, as defined by (51).

Note that, besides condition (52), it follows from Assumption 2 that $s^{*}_{l_{2}}r_{l_{1}}=\delta_{l_{1}l_{2}}$. Furthermore, any symmetric combination matrix $A$ is diagonalizable and therefore satisfies condition (58) automatically. Actually, when $A$ is symmetric, more can be said about its eigenvectors. In that case, the matrix $U$ will be orthogonal so that $U^{-1}=U^{T}$ and it will further hold that $r_{l_{2}}^{*}r_{l_{1}}=\delta_{l_{1}l_{2}}$. Assumption 2 allows the analysis to apply to important cases in which $A$ is not necessarily symmetric but is still diagonalizable (such as when $A$ is constructed according to the uniform rule by assigning to the links of node $k$ weights that are equal to the inverse of its degree, $n_{k}$). We can now simplify the MSD expressions by using the eigen-decomposition of $\mathcal{B}$ from Lemma 1 and the above eigen-decomposition of $A$.

The MSD at node $k$ from (49) can be expressed as:

Furthermore, if the right eigenvectors $\{r_{l}\}$ of $A^{T}$ are approximately orthonormal, i.e.,

then the network MSD from (48) can be approximated by:

Note that any symmetric combination matrix $A$ satisfies condition (62) since, as mentioned above, its right eigenvectors can be chosen to be orthonormal.

Using the expressions for $\lambda_{l,m}(\mathcal{B})$ and $s^{b*}_{l,m}\mathcal{Y}s^{b}_{l,m}$ from Table III and substituting into (63), we can obtain the network MSD expressions for the various strategies. The following result shows how these MSD values compare to each other.

If condition (62) is satisfied, then the ATC diffusion strategy achieves the lowest network MSD in comparison to the other strategies (CTA diffusion, consensus, and non-cooperative). More specifically, it holds that

Furthermore, if $1\leq\mu\lambda_{\min}(R_{u})<2$, the consensus strategy is the worst even in comparison to the non-cooperative strategy:

Therefore, the ATC diffusion strategy outperforms consensus, CTA diffusion, and non-cooperative strategies when condition (62) is satisfied. However, the relation among MSD${}_{\text{cta}}$, MSD${}_{\text{cons}}$, and MSD${}_{\text{ncop}}$ depends on the combination matrix $A$. To illustrate this fact, we reconsider the two-node network from Section III.B with $\sigma^{2}_{u,1}=\sigma^{2}_{u,2}=\sigma^{2}_{u}$, $\mu_{1}=\mu_{2}=\mu$, and $0<\mu\sigma^{2}_{u}<1$. Furthermore, to ensure the stability of the consensus strategy and from (37), the parameters $\{a,b\}$ in (33) are now chosen to satisfy $a+b<2-\mu\sigma^{2}_{u}$. In this case, the eigenvalues of the combination matrix $A$ in (33) are $\{1,1-a-b\}$. It can be verified from (63) and Table III that the CTA diffusion strategy achieves lower network MSD (better mean-square performance) than the consensus strategy if

Similarly, the network MSDs of the consensus and non-cooperative strategies have the following relation:

Combining (67)-(68), we can divide the $a\times b$ plane into three regions, as shown in Fig. 3, where each region corresponds to one possible relation among MSD${}_{\text{cta}}$, MSD${}_{\text{cons}}$, and MSD${}_{\text{ncop}}$.

IV-C MSD of Individual Nodes

In Theorem 3, we established that the ATC diffusion strategy performs the best in terms of the average network MSD. It is still not clear how well the individual nodes perform under each strategy. It is generally more challenging to compare diffusion and consensus strategies in terms of the MSDs of their individual nodes due to the structure of the matrix $\mathcal{B}$ for the consensus strategy. Nevertheless, this can be accomplished as follows. We observe from (61) and Table III that the $\{\text{MSD}_{k}\}$ for the CTA diffusion and consensus strategies differ only in the value of $\lambda_{l,m}(\mathcal{B})$. From Table III, the difference between the values of $\lambda_{l,m}(\mathcal{B})$ for these two strategies is

where the term $\mathcal{O}(\mu)$ denotes a factor that is of the order of the step-size $\mu$. It follows that for sufficiently small step-sizes, expression (69) is close to zero and the CTA diffusion and consensus strategies will exhibit similar MSDs at the individual nodes, i.e., $\text{MSD}_{\text{cta},k}\approx\text{MSD}_{\text{cons},k}$ for all $k$. As a result, in the following, we only compare $\text{MSD}_{\text{atc},k}$, $\text{MSD}_{\text{cta},k}$, and $\text{MSD}_{\text{ncop},k}$. In particular, we will show that under certain conditions on the combination matrix $A$, the ATC diffusion strategy continues to perform the best in terms of the MSD at the individual nodes in comparison to the other strategies. To do so, starting from (61) and the expressions for $\{\lambda_{l,k}(\mathcal{B}),\mathcal{Y}\}$ in Table III, we can express the MSD at node $k$ for the ATC diffusion strategy as:

where we introduced the notation MSD${}_{\text{atc},k}(m)$ to denote the MSD component at node $k$ that is contributed by the $m$th eigenvalue of $R_{u}$, i.e.,

In a similar vein, we can define the corresponding MSD${}_{k}(m)$ terms for the other strategies. We list these terms in Table IV in two equivalent forms (we will use the series form later). We first have the following useful preliminary result.

The following ratios are positive and independent of the node index $k$:

From the eigen-forms of $\{\text{MSD}_{k}(m)\}$ in Table IV, the differences between MSD${}_{\text{atc},k}(m)$, MSD${}_{\text{cta},k}(m)$, and MSD${}_{\text{ncop},k}(m)$ are given by:

Then, dividing (74) by (75) and (74) by (76), we arrive at (72)-(73). ∎

The relation among ${\rm{MSD}}_{{\rm{atc}},k}(m)$, ${\rm{MSD}}_{{\rm{cta}},k}(m)$, and ${\rm{MSD}}_{{\rm{ncop}},k}(m)$ is either

Assume first that ${\rm{MSD}}_{{\rm{atc}},k}(m)\leq{\rm{MSD}}_{{\rm{ncop}},k}(m)$. Then, using (72), we get ${\rm{MSD}}_{{\rm{ncop}},k}(m)-{\rm{MSD}}_{{\rm{cta}},k}(m)\geq 0$. Similarly, from (73), we get ${\rm{MSD}}_{{\rm{cta}},k}(m)-{\rm{MSD}}_{{\rm{atc}},k}(m)\geq 0$. We conclude that relation (78) holds in this case. Assume instead that ${\rm{MSD}}_{{\rm{atc}},k}(m)\geq{\rm{MSD}}_{{\rm{ncop}},k}(m)$. Then, a similar argument will show that (79) should hold. ∎

The above result is useful since it allows us to deduce the relation among ${\rm{MSD}}_{{\rm{atc}},k}(m)$, ${\rm{MSD}}_{{\rm{cta}},k}(m)$, and ${\rm{MSD}}_{{\rm{ncop}},k}(m)$ by only knowing the relation between any two of them. To proceed, we note that we can alternatively express the MSD${}_{k}(m)$ terms in an equivalent series form. For example, expression (71) can be written as:

In a similar manner, we can obtain the corresponding MSD${}_{k}(m)$ series forms for the other strategies and we list these in Table IV. In the following, we provide conditions to guarantee that the individual node performance in the ATC diffusion strategy outperforms the other strategies.

where $\Sigma_{v}$ is the noise variance (diagonal) matrix defined by (50), then:

From the series forms of $\{\text{MSD}_{k}(m)\}$ in Table IV, the difference ${\rm{MSD}}_{\text{cta},k}(m)-{\rm{MSD}}_{\text{atc},k}(m)$ is given by:

Since $\Sigma_{v}-A^{T}\Sigma_{v}A\geq 0$, we conclude that ${\rm{MSD}}_{\text{cta},k}(m)\geq{\rm{MSD}}_{\text{atc},k}(m)$ for all $m$. Then, applying Lemma 4, we obtain relation (82). ∎

Condition (81) essentially means that the combination matrix $A$ should not magnify the noise effect across the network. However, in general, condition (81) is restrictive in the sense that over the set of feasible diagonalizable left-stochastic matrices $A$ satisfying $a_{l,k}=0$ if $l\notin\mathcal{N}_{k}$, the set of combination matrices $A$ satisfying (81) can be small. We illustrate this situation by reconsidering the two-node network (33) for which

where $t=\sigma^{2}_{v,1}/\sigma^{2}_{v,2}$ denotes the ratio of noise variances at nodes 1 and 2. Note from

that equality holds in (85) if, and only if,

That is, when $a\neq tb$, the matrix $(\Sigma_{v}-A^{T}\Sigma_{v}A)$ has two eigenvalues with different signs. Thus, the only way to ensure $\Sigma_{v}-A^{T}\Sigma_{v}A\geq 0$ in this case is to set $a=tb$ and, thus, the matrix $(\Sigma_{v}-A^{T}\Sigma_{v}A)$ will have at least one eigenvalue at zero since its determinant will be zero. To ensure $\Sigma_{v}-A^{T}\Sigma_{v}A\geq 0$, its other eigenvalue, which is equal to $b(1+t^{2})(2-b-bt)$, needs to be greater than or equal to zero. It follows that $b$ must satisfy:

Moreover, since $a$ and $b$ must lie within the interval $$, we conclude from (86) that$b$ must also satisfy:

It can be verified that condition (88) implies condition (87) since $\min\{1,1/t\}\leq 2/(1+t)$. That is, for any left-stochastic matrix $A$ from (33) satisfying $a=tb$ and (88), relation (82) holds and both nodes improve their own MSDs by employing the diffusion strategies. Note that condition (86) represents a line segment in the unit square $a,b\in$ (see Fig. 4). In the following, we relax condition (81) with a mild constraint on the network topology.

In addition to Assumption 2, we further assume that the combination matrix $A$ is primitive (also called regular). This means that there exists an integer $j$ such that the $j$th power of $A$ has positive entries, $[A^{j}]_{l,k}>0$ for all $l$ and $k$ . We remark that for any connected network (where a path always exists between any two arbitrary nodes), if the combination weights $\{a_{l,k}\}$ satisfy $a_{l,k}>0$ for $l\in\mathcal{N}_{k}$, then $A$ is primitive. Now, since $A$ is primitive, it follows from the Perron-Frobenius Theorem that $(A^{T})^{j}$ converges to the rank-one matrix:

From (9) and (52), $r_{1}$ and $s_{1}$ satisfy:

For any primitive and diagonalizable combination matrix $A$, if

for all $k$, then there exists $\mu^{\circ}>0$ so that for any step-size $\mu$ satisfying $0<\mu\leq\mu^{\circ}$, it holds:

We show in Appendix F that for any primitive $A$, condition (81) implies condition (91). To illustrate these two conditions, we consider again the two-node network. It can be verified that $s^{T}_{1}$ for $A^{T}$ in (33) has the form $s^{T}_{1}=\begin{bmatrix}\sqrt{2}b/(a+b)&\sqrt{2}a/(a+b)\end{bmatrix}$. Then, some algebra shows that condition (91) becomes

Recall that $t=\sigma^{2}_{v,1}/\sigma^{2}_{v,2}$. We illustrate condition (93), along with condition (86), in Fig. 4. We observe that condition (86), shown as the dashed lines, is contained in condition (93), shown as the shaded regions, and that compared to condition (86), condition (93) enlarges the region of $A$ for which the ATC diffusion strategy performs the best in terms of the individual MSD performance.

V Simulation Results

We consider a network with $20$ nodes and random topology. The regression covariance matrix $R_{u}$ is diagonal with entries randomly generated from $$, and the noise variances$\{\sigma^{2}_{v,k}\}$are randomly generated over$$dB (see Fig. 5). The network estimates a$10\times 1$(i.e.,$M=10$) unknown vector$w^{\circ}$with every entry equal to$1/\sqrt{10}$.

The transient network MSD over time is shown on the left hand side of Fig. 6 with three possible combination rules: relative-variance , uniform , and Metropolis (see Table V). Note that the matrix $A$ for the Metropolis rule is symmetric. The step-size $\mu$ is set to $\mu=0.02$. We observe that, as expected, the ATC diffusion strategy outperforms the other strategies, especially for the relative-variance rule. It also suggests that some conventional choices of combination weights, such as the Metropolis rule, may not be the most suitable for adaptation in the presence of both noisy and streaming data because such weights do not take into account the noise profile across the nodes (see, e.g., for more details on this issue). We further show the steady-state MSD at the individual nodes on the right hand side of Fig. 6. We observe that the ATC diffusion strategy achieves the lowest MSD at each node in comparison to the other strategies. These observations are in agreement with the results predicted by the theoretical analysis. The theoretical expressions for MSDs from (49)-(48) are also depicted in Fig. 6 for the ATC diffusion strategy and match well with simulations.

We further compare the mean-square performance of the distributed strategies for larger step-sizes. We set the step-size to $\mu=0.075$ and use the relative-variance combination rule. The transient network MSD over time is shown on the left hand side of Fig. 7. We observe that the ATC and CTA diffusion strategies have the same convergence rate and converge faster than the consensus strategy. Moreover, the diffusion strategies achieve lower network MSD than the consensus strategy. We also show the steady-state MSD at the individual nodes on the right hand side of Fig. 7. We see again that ATC diffusion performs the best in comparison to the other strategies at each individual node.

VI Concluding Remarks

We compared analytically several cooperative estimation strategies, including ATC diffusion, CTA diffusion, and consensus for distributed estimation over networks. The results show that diffusion networks are more stable than consensus networks. Moreover, the stability of diffusion networks is independent of the combination weights, whereas consensus networks can become unstable even if all individual nodes are stable. Furthermore, in steady-state, the ATC diffusion strategy performs the best not only in terms of the network MSD, but also in terms of the MSDs at the individual nodes.

Appendix A Proof of Theorem 1

First, note that the matrices $\{\mathcal{B}\}$ for the ATC and CTA diffusion strategies given by (29) have the same eigenvalues (and, therefore, the same spectral radius) because for any matrices $X$ and $Y$ of compatible dimensions, the matrix products $XY$ and $YX$ have the same eigenvalues . So let us evaluate the spectral radius of $\mathcal{B}_{\text{atc}}$. To do so, we introduce a convenient block matrix norm, and denote it by $\|\cdot\|_{b}$; it is defined as follows. Let $\mathcal{X}$ be an $N\times N$ block matrix with blocks of size $M\times M$ each. Its block matrix norm is defined as:

where $\mathcal{X}_{k,l}$ denotes the $(k,l)$th block of $\mathcal{X}$ and $\|\cdot\|_{2}$ denotes the 2-induced norm (largest singular value) of its matrix argument. Now, since $\{I_{NM},\mathcal{M},\mathcal{R}\}$ are block diagonal matrices, the following property holds:

where we used the fact that the 2-induced norm of any Hermitian matrix coincides with its spectral radius. In addition, since $A$ is a left-stochastic matrix, it holds that

Accordingly, using the fact that the spectral radius of a matrix is upper bounded by any norm of the matrix , we get:

Now, assume $A$ is symmetric. Since it is also left-stochastic, it follows that its eigenvalues are real and lie inside the interval $$. Therefore,$(I_{NM}-\mathcal{A}^{T})$is nonnegative-definite. Moreover, since$\mathcal{M}$and$\mathcal{R}$commute, i.e.,$\mathcal{R}\mathcal{M}=\mathcal{M}\mathcal{R}$, it can be verified that$\mathcal{B}_{\text{cons}}$in (28) and$\mathcal{B}_{\text{ncop}}$in (25) are Hermitian. In addition, the matrices$\mathcal{B}_{\text{cons}}$and$\mathcal{B}_{\text{ncop}}$ are related as follows:

with $(I_{NM}-\mathcal{A}^{T})\geq 0$. Using Weyl’s TheoremLet $\{D^{\prime},D,\Delta D\}$ be $M\times M$ Hermitian matrices with ordered eigenvalues $\{\lambda_{m}(D^{\prime}),\lambda_{m}(D),\lambda_{m}(\Delta D)\}$, i.e., $\lambda_{1}(D)\geq\lambda_{2}(D)\geq\ldots\geq\lambda_{M}(D)$, and likewise for the eigenvalues of $\{D^{\prime},\Delta D\}$. Weyl’s Theorem states that if $D^{\prime}=D+\Delta D$, then $\lambda_{m}(D)+\lambda_{M}(\Delta D)\leq\lambda_{m}(D^{\prime})\leq\lambda_{m}(D)+\lambda_{1}(\Delta D)$ for $1\leq m\leq M$. When $\Delta D\geq 0$, it holds that $\lambda_{m}(D^{\prime})\geq\lambda_{m}(D)$. , we arrive at (31). Following a similar argument, it holds for symmetric $A$ that

Thus, the matrix $\mathcal{B}_{\text{cons}}$ is stable (namely, $-1<\lambda_{l}(\mathcal{B}_{\text{cons}})<1$ for $l=1,2,\ldots,NM$) if

for $k=1,2,\ldots,N$ and $m=1,2,\ldots,M$. We then arrive at (32).

Appendix B Proof of Theorem 2

For the diffusion strategies, from Table III and since $\rho(A)=1$, we have

Moreover, since $1\in\{\lambda_{l}(A)\}$, we have

and we arrive at (56). It is obvious that when $A=I_{N}$, then equality in (105) holds and $\rho(\mathcal{B}_{\text{ncop}})=\rho(\mathcal{B}_{\text{cons}})$. We now consider the case when $A\neq I_{N}$. Note that the spectral radius of $\mathcal{B}_{\text{ncop}}$ is given by

We first verify that equality in (105) holds only when $\rho(\mathcal{B}_{\text{ncop}})=1-\mu\lambda_{\min}(R_{u})$. Indeed, if $\rho(\mathcal{B}_{\text{ncop}})=-1+\mu\lambda_{\max}(R_{u})\geq 0$, we have that $\mu\lambda_{\max}(R_{u})\geq 1$ and we get from (105) that

for all $l$ and $m$. It is obvious that relation (108) holds for $l=1$ since $\lambda_{1}(A)=1$ and

For $l=2,3,\ldots,N$, by the triangular inequality of norms, we have that $|\lambda_{l}(A)-\mu\lambda_{m}(R_{u})|\leq|\lambda_{l}(A)|+\mu\lambda_{\max}(R_{u})$. Hence, the inequality in (108) holds if

for $l=2,3,\ldots,N$ and we arrive at (57).

Appendix C Proof of Lemma 2

From Lemma 1, the eigen-decomposition for the matrix power $\mathcal{B}^{j}$ is given by:

Using (111), we can rewrite the MSD at node $k$ from (49) as:

where we used $\text{Tr}(AB)=\text{Tr}(BA)$ and the expression for the infinite sum of a geometric series. Using (54), we have:

since the eigenvectors $\{z_{m}\}$ are orthonormal. Substituting (113) into (112), we arrive at (61). Likewise, from (47) and (61), the network MSD is given by

From assumption (62), we can establish (63) since

Appendix D Proof of Theorem 3

We first verify that ${\rm{MSD}}_{\rm{atc}}\leq{\rm{MSD}}_{\rm{cta}}$, ${\rm{MSD}}_{\rm{cta}}\leq{\rm{MSD}}_{\rm{ncop}}$, and ${\rm{MSD}}_{\rm{atc}}\leq{\rm{MSD}}_{\rm{cons}}$. We show the result by verifying that the individual terms on the right hand side of (63) for the various strategies have the same ordering. That is, from (63) and Table III, we verify that the following ratios, which correspond to ${\rm{MSD}}_{\rm{atc}}\leq{\rm{MSD}}_{\rm{cta}}$, ${\rm{MSD}}_{\rm{cta}}\leq{\rm{MSD}}_{\rm{ncop}}$, and ${\rm{MSD}}_{\rm{atc}}\leq{\rm{MSD}}_{\rm{cons}}$, respectively, are upper bounded by one:

for all $l$ and $m$. Note that relations (116)-(117) hold since $|\lambda_{l}(A)|\leq 1$ for all $l$ in view of the fact that $A$ is left-stochastic and, hence, $\rho(A)=1$. We therefore established (64). On the other hand, relation (118) would hold if, and only if,

To establish that (119) is true for all $l$ and $m$, we introduce the compact notation $\lambda=\lambda_{l}(A)$, $\delta=\mu\lambda_{m}(R_{u})$, and consider the following function of two variables:

The range for $\delta$ ensures condition (27) and the stability of the diffusion network, while the range for $|\lambda-\delta|$ ensures that the consensus network is stable, i.e., $|\lambda_{l,m}(\mathcal{B}_{\text{cons}})|<1$ for all $l$ and $m$. Then, we would like to show that $f(\lambda,\delta)\leq 1$. Since $\lambda$ is generally complex-valued, we denote the real part of $\lambda$ by $\lambda_{r}$. Then, the term $|\lambda-\delta|^{2}$ in (120) is given by $|\lambda-\delta|^{2}=|\lambda|^{2}+\delta^{2}-2\lambda_{r}\delta$ and $f(\lambda,\delta)$ from (120) becomes

Since $f(\lambda,\delta)$ is linear in $\delta$, the maximum value of $f(\lambda,\delta)$ in (121) over $\delta$ occurs at the end points of $\delta$. Since $\delta\in(0,2)$ and $|\lambda_{r}-\delta|\leq|\lambda-\delta|<1$, we conclude that $0<\delta<1+\lambda_{r}$. Substituting the end points of $\delta$ into (121), we have

where we used the fact that $\lambda_{r}^{2}\leq|\lambda|^{2}$ and $|\lambda|\leq 1$. We therefore established (65).

Let us now examine what happens when the step-size is such that $1\leq\mu\lambda_{\min}(R_{u})<2$. Again, from (63) and Table III, we establish that ${\rm{MSD}}_{\rm{ncop}}\leq{\rm{MSD}}_{\rm{cons}}$ this conclusion by showing that the ratio of the individual terms appearing in the sums (63) is upper bounded by one:

for all $l$ and $m$. Condition (124) is equivalent to showing that

where we used the notation from (120). Relation (125) holds since $\delta\geq\mu\lambda_{\min}(R_{u})\geq 1\geq|\lambda|\geq|\lambda_{r}|$ and then

Appendix E Proof of Theorem 5

From the series forms of $\{\text{MSD}_{k}(m)\}$ in Table IV, the difference between MSD${}_{\text{cta},k}(m)$ and MSD${}_{\text{ncop},k}(m)$ can be expressed as:

Therefore, there exists an integer $J_{m}$ such that for any $\varepsilon>0$,

for all $j\geq J_{m}$. From (90), $\Delta$ in (129) becomes $\Delta=\sigma^{2}_{v,k}-s^{T}_{1}\Sigma_{v}s_{1}/N-\varepsilon$. From condition (91), we are able to choose $\varepsilon$ small enough such that $\Delta$ is strictly greater than zero. Therefore, expression (127) is lower bounded by:

where the term $z\geq 0$ is an upper bound for the first $J_{m}$ terms of the summation in (127), i.e.,

It can be verified that the series inside the brackets of (130) is strictly decreasing in $\mu\in(0,1/\lambda_{m}(R_{u}))$. In addition,

Thus, there exists a $\mu^{\circ}_{m}>0$ such that the sum inside the bracket of (130) becomes positive and, hence,

for all $0<\mu\leq\mu^{\circ}_{m}$. Repeating the above argument, we will obtain a collection of step-size bounds $\{\mu^{\circ}_{1},\mu^{\circ}_{2},\ldots,\mu^{\circ}_{M}\}$. We then choose $\mu^{\circ}=\min\{\mu^{\circ}_{1},\mu^{\circ}_{2},\ldots,\mu^{\circ}_{M}\}$ so that relation (133) holds for all $m$. Then, applying Lemma 4, we arrive at (92) for any $\mu$ satisfying $0<\mu\leq\mu^{\circ}$.

Appendix F Condition (81) Implies Condition (91) when A𝐴A is Primitive

It follows from (81) that $A^{Tj}\Sigma_{v}A^{j}-A^{T(j+1)}\Sigma_{v}A^{j+1}\geq 0$ for any nonnegative integer $j$ and then

Since $A$ is primitive, as $J$ tends to infinity, we get from (89) that

Since for any column vectors $\{x,y\}$ of size $N$, it holds that $\text{det}(I_{N}-x\cdot y^{T})=1-y^{T}\cdot x$, relation (136) implies that the following must hold:

However, by the Cauchy-Schwarz inequality and using the fact that $s_{1}^{T}\mathds{1}/\sqrt{N}=1$ from (90), we have

where $s_{l,1}$ denotes the $l$th entry of $s_{1}$. Therefore, relation (137) can hold only with equality in (138). In turn, equality in (138) holds if, and only if, there exists a constant $c$ such that $s_{l,1}/\sqrt{N}=c\cdot\sigma^{-2}_{v,l}$ for all $l$. By the fact that $s_{1}^{T}\mathds{1}/\sqrt{N}=1$, we get:

References