3.09.1.1 Networks and neighborhoods

In this chapter we focus mainly on connected networks, although many of the results hold even if the network graph is separated into disjoint subgraphs. In a connected network, if we pick any two arbitrary nodes, then there will exist at least one path connecting them: the nodes may be connected directly by an edge if they are neighbors, or they may be connected by a path that passes through other intermediate nodes. Figure 9.1 provides a graphical representation of a connected network with nodes. Nodes that are able to share information with each other are connected by edges. The sharing of information over these edges can be unidirectional or bi-directional. The neighborhood of any particular node is defined as the set of nodes that are connected to it by edges; we include in this set the node itself. The figure illustrates the neighborhood of node 3, which consists of the following subset of nodes: . For each node, the size of its neighborhood defines its degree. For example, node in the figure has degree , while node 8 has degree . Nodes that are well connected have higher degrees. Note that we are denoting the neighborhood of an arbitrary node by and its size by . We shall also use the notation to refer to .

The neighborhood of any node therefore consists of all nodes with which node can exchange information. We assume a symmetric situation in relation to neighbors so that if node is a neighbor of node , then node is also a neighbor of node . This does not necessarily mean that the flow of information between these two nodes is symmetrical. For instance, in future sections, we shall assign pairs of nonnegative weights to each edge connecting two neighboring nodes—see Figure 9.2. In particular, we will assign the coefficient to denote the weight used by node to scale the data it receives from node ; this scaling can be interpreted as a measure of trustworthiness or reliability that node assigns to its interaction with node . Note that we are using two subscripts, , with the first subscript denoting the source node (where information originates from) and the second subscript denoting the sink node (where information moves to) so that:

(9.2)

In this way, the alternative coefficient will denote the weight used to scale the data sent from node to :

(9.3)

The weights can be different, and one or both of them can be zero, so that the exchange of information over the edge connecting the neighboring nodes need not be symmetric. When one of the weights is zero, say, , then this situation means that even though nodes are neighbors, node is either not receiving data from node or the data emanating from node is being annihilated before reaching node . Likewise, when , then node scales its own data, whereas corresponds to the situation when node does not use its own data. Usually, in graphical representations like those in Figure 9.1, edges are drawn between neighboring nodes that can share information. And, it is understood that the actual sharing of information is controlled by the values of the scaling weights that are assigned to the edge; these values can turn off communication in one or both directions and they can also scale one direction more heavily than the reverse direction, and so forth.

3.09.1.2 Cooperation among agents

Now, depending on the application under consideration, the solution vector from (9.1) may admit different interpretations. For example, the entries of may represent the location coordinates of a nutrition source that the agents are trying to find, or the location of an accident involving a dangerous chemical leak. The nodes may also be interested in locating a predator and tracking its movements over time. In these localization applications, the vector is usually two or three-dimensional. In other applications, the entries of may represent the parameters of some model that the network wishes to learn, such as identifying the model parameters of a biological process or the occupied frequency bands in a shared communications medium. There are also situations where different agents in the network may be interested in estimating different entries of , or even different parameter vectors altogether, say, for node , albeit with some relation among the different vectors so that cooperation among the nodes can still be rewarding. In this chapter, however, we focus exclusively on the special (yet frequent and important) case where all agents are interested in estimating the same parameter vector .

Since the agents have a common objective, it is natural to expect cooperation among them to be beneficial in general. One important question is therefore how to develop cooperation strategies that can lead to better performance than when each agent attempts to solve the optimization problem individually. Another important question is how to develop strategies that endow networks with the ability to adapt and learn in real-time in response to changes in the statistical properties of the data. This chapter provides an overview of results in the area of diffusion adaptation with illustrative examples. Diffusion strategies are powerful methods that enable adaptive learning and cooperation over networks. There have been other useful works in the literature on the use of alternative consensus strategies to develop distributed optimization solutions over networks. Nevertheless, we explain in Appendix E why diffusion strategies outperform consensus strategies in terms of their mean-square-error stability and performance. For this reason, we focus in the body of the chapter on presenting the theoretical foundations for diffusion strategies and their performance.

3.09.1.3 Notation

In our treatment, we need to distinguish between random variables and deterministic quantities. For this reason, we use boldface letters to represent random variables and normal font to represent deterministic (non-random) quantities. For example, the boldface letter denotes a random quantity, while the normal font letter denotes an observation or realization for it. We also need to distinguish between matrices and vectors. For this purpose, we use CAPITAL letters to refer to matrices and small letters to refer to both vectors and scalars; Greek letters always refer to scalars. For example, we write to denote a covariance matrix and to denote a vector of parameters. We also write to refer to the variance of a random variable. To distinguish between a vector (small letter) and a scalar (also a small letter), we use parentheses to index scalar quantities and subscripts to index vector quantities. Thus, we write to refer to the value of a scalar quantity at time , and to refer to the value of a vector quantity at time . Thus, denotes a scalar while denotes a vector. All vectors in our presentation are column vectors, with the exception of the regression vector (denoted by the letter ), which will be taken to be a row vector for convenience of presentation. The symbol denotes transposition, and the symbol denotes complex conjugation for scalars and complex-conjugate transposition for matrices. The notation denotes a column vector with entries and stacked on top of each other, and the notation denotes a diagonal matrix with entries and . Likewise, the notation vectorizes its matrix argument and stacks the columns of on top of each other. The notation denotes the Euclidean norm of its vector argument, while denotes the block maximum norm of a block vector (defined in Appendix D). Similarly, the notation denotes the weighted square value, . Moreover, denotes the block maximum norm of a matrix (also defined in Appendix D), and denotes the spectral radius of the matrix (i.e., the largest absolute magnitude among its eigenvalues). Finally, denotes the identity matrix of size ; sometimes, for simplicity of notation, we drop the subscript from when the size of the identity matrix is obvious from the context. Table 9.1 provides a summary of the symbols used in the chapter for ease of reference.

3.09.2.1 Application: autoregressive modeling

Our first example relates to identifying the parameters of an auto-regressive (AR) model from noisy data. Thus, consider a situation where agents are spread over some geographical region and each agent is observing realizations of an AR zero-mean random process , which satisfies a model of the form:

(9.4)

The scalars represent the model parameters that the agents wish to identify, and represents an additive zero-mean white noise process with power:

(9.5)

It is customary to assume that the noise process is temporally white and spatially independent so that noise terms across different nodes are independent of each other and, at the same node, successive noise samples are also independent of each other with a time-independent variance :

(9.6)

The noise process is further assumed to be independent of past signals across all nodes . Observe that we are allowing the noise power profile, , to vary with . In this way, the quality of the measurements is allowed to vary across the network with some nodes collecting noisier data than other nodes. Figure 9.3 illustrates an example of a network consisting of nodes spread over a region in space. The figure shows the neighborhood of node , which consists of nodes .

3.09.2.2 Application: tapped-delay-line models

Our second example to motivate MSE cost functions, , and linear models relates to identifying the parameters of a moving-average (MA) model from noisy data. MA models are also known as finite-impulse-response (FIR) or tapped-delay-line models. Thus, consider a situation where agents are interested in estimating the parameters of an FIR model, such as the taps of a communications channel or the parameters of some (approximate) model of interest in finance or biology. Assume the agents are able to independently probe the unknown model and observe its response to excitations in the presence of additive noise; this situation is illustrated in Figure 9.4, with the probing operation highlighted for one of the nodes (node 4).

The schematics inside the enlarged diagram in Figure 9.4 is meant to convey that each node probes the model with an input sequence and measures the resulting response sequence, , in the presence of additive noise. The system dynamics for each agent is assumed to be described by a MA model of the form:

(9.41)

In this model, the term again represents an additive zero-mean noise process that is assumed to be temporally white and spatially independent; it is also assumed to be independent of the input process, , for all , and . The scalars represent the model parameters that the agents seek to identify. If we again collect the model parameters into an column vector :

(9.42)

and the input data into a row regression vector:

(9.43)

then, we can again express the measurement equation (9.41) at each node in the same linear model as (9.9), namely,

(9.44)

As was the case with model (9.9), we can likewise verify that, in view of (9.44), the desired parameter vector satisfies the same normal equations (9.15), i.e.,

(9.45)

where the moments continue to be defined by expressions (9.11) and (9.12) with now defined by (9.43). Therefore, each node can determine on its own by solving the same MMSE estimation problem (9.16). This solution method requires knowledge of the moments and, according to (9.20), each agent would then attain an MSE level that is equal to the noise power level at its location.

Alternatively, when the statistical information is not available, each agent can estimate iteratively by feeding data into the adaptive implementation (9.26) and (9.27). In this way, each agent will achieve the same performance level shown earlier in (9.36) and (9.37), with the limiting performance being again dependent on the local noise power level, . Therefore, nodes with larger noise power will perform worse than nodes with smaller noise power. However, since all nodes are observing data arising from the same underlying model , it is natural to expect cooperation among the nodes to be beneficial. As we are going to see, starting from the next section, one way to achieve cooperation and improve performance is by developing algorithms that optimize the same global cost function (9.38) in an adaptive and distributed manner, such as algorithms (9.153) and (9.154) further ahead.

3.09.2.3 Application: target localization

Our third example relates to the problem of locating a destination of interest (such as the location of a nutrition source or a chemical leak) or locating and tracking an object of interest (such as a predator or a projectile). In several such localization applications, the agents in the network are allowed to move towards the target or away from it, in which case we would end up with a mobile adaptive network [8]. Biological networks behave in this manner such as networks representing fish schools, bird formations, bee swarms, bacteria motility, and diffusing particles [8–12]. The agents may move towards the target (e.g., when it is a nutrition source) or away from the target (e.g., when it is a predator). In other applications, the agents may remain static and are simply interested in locating a target or tracking it (such as tracking a projectile).

To motivate mean-square-error estimation in the context of localization problems, we consider the situation corresponding to a static target and static nodes. Thus, assume that the unknown location of the target in the cartesian plane is represented by the vector . The agents are spread over the same region of space and are interested in locating the target. The location of every agent is denoted by the vector in terms of its and coordinates—see Figure 9.5. We assume the agents are aware of their location vectors. The distance between agent and the target is denoted by and is equal to:

(9.46)

The unit-norm direction vector pointing from agent towards the target is denoted by and is given by:

(9.47)

Observe from (9.46) and (9.47) that can be expressed in the following useful inner-product form:

(9.48)

In practice, agents have noisy observations of both their distance and direction vector towards the target. We denote the noisy distance measurement collected by node at time by:

(9.49)

where denotes noise and is assumed to be zero-mean, and temporally white and spatially in-dependent with variance

(9.50)

We also denote the noisy direction vector that is measured by node at time by . This vector is a perturbed version of . We assume that continues to start from the location of the node at , but that its tip is perturbed slightly either to the left or to the right relative to the tip of —see Figure 9.6. The perturbation to the tip of is modeled as being the result of two effects: a small deviation that occurs along the direction that is perpendicular to , and a smaller deviation that occurs along the direction of . Since we are assuming that the tip of is only slightly perturbed relative to the tip of , then it is reasonable to expect the amount of perturbation along the parallel direction to be small compared to the amount of perturbation along the perpendicular direction.

Thus, we write

(9.51)

where denotes a unit-norm row vector that lies in the same plane and whose direction is perpendicular to . The variables and denote zero-mean independent random noises that are temporally white and spatially independent with variances:

(9.52)

We assume the contribution of is small compared to the contributions of the other noise sources, and , so that

(9.53)

The random noises are further assumed to be independent of each other.

Using (9.48) we find that the noisy measurements are related to the unknown via:

(9.54)

where the modified noise term is defined in terms of the noises in and as follows:

(9.55)

since, by construction,

(9.56)

and the contribution by is assumed to be sufficiently small. If we now introduce the adjusted signal:

(9.57)

then we arrive again from (9.54) and (9.55) at the following linear model for the available measurement variables in terms of the target location :

(9.58)

There is one important difference in relation to the earlier linear models (9.9) and (9.44), namely, the variables in (9.58) do not have zero means any longer. It is nevertheless straightforward to determine the first and second-order moments of the variables . First, note from (9.49), (9.51), and (9.57) that

(9.59)

Even in this case of non-zero means, and in view of (9.58), the desired parameter vector can still be shown to satisfy the same normal equations (9.15), i.e.,

(9.60)

where the moments continue to be defined as

(9.61)

To verify that (9.60) holds, we simply multiply both sides of (9.58) by from the left, compute the expectations of both sides, and use the fact that has zero mean and is assumed to be independent of for all times and nodes . However, the difference in relation to the earlier normal equations (9.15) is that the matrix is not the actual covariance matrix of any longer. When is not zero mean, its covariance matrix is instead defined as:

(9.62)

so that

(9.63)

We conclude from this relation that is positive-definite (and, hence, invertible) so that expression (9.60) is justified. This is because the covariance matrix, , is itself positive-definite. Indeed, some algebra applied to the difference from (9.51) shows that

(9.64)

where the matrix

(9.65)

is full rank since the rows are linearly independent vectors.

Therefore, each node can determine on its own by solving the same minimum mean-square-error estimation problem (9.16). This solution method requires knowledge of the moments and, according to (9.20), each agent would then attain an MSE level that is equal to the noise power level, , at its location.

Alternatively, when the statistical information is not available beforehand, each agent can estimate iteratively by feeding data into the adaptive implementation (9.26) and (9.27). In this case, each agent will achieve the performance level shown earlier in (9.36) and (9.37), with the limiting performance being again dependent on the local noise power level, . Therefore, nodes with larger noise power will perform worse than nodes with smaller noise power. However, since all nodes are observing distances and direction vectors towards the same target location , it is natural to expect cooperation among the nodes to be beneficial. As we are going to see, starting from the next section, one way to achieve cooperation and improve performance is by developing algorithms that solve the same global cost function (9.38) in an adaptive and distributed manner, by using algorithms such as (9.153) and (9.154) further ahead.

3.09.2.4 Application: collaborative spectral sensing

Our fourth and last example to illustrate the role of mean-square-error estimation and cooperation relates to spectrum sensing for cognitive radio applications. Cognitive radio systems involve two types of users: primary users and secondary users. To avoid causing harmful interference to incumbent primary users, unlicensed cognitive radio devices need to detect unused frequency bands even at low signal-to-noise (SNR) conditions [13–16]. One way to carry out spectral sensing is for each secondary user to estimate the aggregated power spectrum that is transmitted by all active primary users, and to locate unused frequency bands within the estimated spectrum. This step can be performed by the secondary users with or without cooperation.

Thus, consider a communications environment consisting of primary users and secondary users. Let denote the power spectrum of the signal transmitted by primary user . To facilitate estimation of the spectral profile by the secondary users, we assume that each can be represented as a linear combination of some basis functions, , say, of them [17]:

(9.72)

In this representation, the scalars denote the coefficients of the basis expansion for user . The variable denotes the normalized angular frequency measured in radians/sample. The power spectrum is often symmetric about the vertical axis, , and therefore it is sufficient to focus on the interval . There are many ways by which the basis functions, , can be selected. The following is one possible construction for illustration purposes. We divide the interval into identical intervals and denote their center frequencies by . We then place a Gaussian pulse at each location and control its width through the selection of its standard deviation, , i.e.,

(9.73)

Figure 9.7 illustrates this construction. The parameters are selected by the designer and are assumed to be known. For a sufficiently large number, , of basis functions, the representation (9.72) can approximate well a large class of power spectra.

We collect the combination coefficients for primary user into a column vector :

(9.74)

and collect the basis functions into a row vector:

(9.75)

Then, the power spectrum (9.72) can be expressed in the alternative inner-product form:

(9.76)

Let denote the path loss coefficient from primary user to secondary user . When the transmitted spectrum travels from primary user to secondary user , the spectrum that is sensed by node is . We assume in this example that the path loss factors are known and that they have been determined during a prior training stage involving each of the primary users with each of the secondary users. The training is usually repeated at regular intervals of time to accommodate the fact that the path loss coefficients can vary (albeit slowly) over time. Figure 9.8 depicts a cognitive radio system with primary users and secondary users. One of the secondary users (user ) is highlighted and the path loss coefficients from the primary users to its location are indicated; similar path loss coefficients can be assigned to all other combinations involving primary and secondary users.

Each user senses the aggregate effect of the power spectra that are transmitted by all active primary users. Therefore, adding the effect of all primary users, we find that the power spectrum that arrives at secondary user is given by:

(9.77)

where denotes the receiver noise power at node , and where we introduced the following vector quantities:

(9.78)

(9.79)

The vector is the collection of all combination coefficients for all primary users. The vector contains the path loss coefficients from all primary users to user . Now, at every time instant , user observers its received power spectrum, , over a discrete grid of frequencies, , in the interval in the presence of additive measurement noise. We denote these measurements by:

(9.80)

The term denotes sampling noise and is assumed to have zero mean and variance ; it is also assumed to be temporally white and spatially independent; and is also independent of all other random variables. Since the row vectors in (9.79) are defined in terms of the path loss coefficients , and since these coefficients are estimated and subject to noisy distortions, we model the as zero-mean random variables in (9.80) and use the boldface notation for them.

Observe that in this application, each node collects measurements at every time instant and not only a single measurement, as was the case with the three examples discussed in the previous sections (AR modeling, MA modeling, and localization). The implication of this fact is that we now deal with an estimation problem that involves vector measurements instead of scalar measurements at each node. The solution structure continues to be the same. We collect the measurements at node at time into vectors and introduce the quantities:

(9.81)

and the regression matrix:

(9.82)

The time subscript in is used to model the fact that the path loss coefficients can change over time due to the possibility of node mobility. With the above notation, expression (9.80) is equivalent to the linear model:

(9.83)

Compared to the earlier examples (9.9), (9.44), and (9.58), the main difference now is that each agent collects a vector of measurements, , as opposed to the scalar , and its regression data are represented by the matrix quantity, , as opposed to the row vector . Nevertheless, the estimation approach will continue to be the same. In cognitive network applications, the secondary users are interested in estimating the aggregate power spectrum of the primary users in order for the secondary users to identify vacant frequency bands that can be used by them. In the context of model (9.83), this amounts to determining the parameter vector since knowledge of its entries allows each secondary user to reconstruct the aggregate power spectrum defined by:

(9.84)

where the notation denotes the Kronecker product operation, and denotes a vector whose entries are all equal to one.

As before, we can again verify that, in view of (9.83), the desired parameter vector satisfies the same normal equations:

(9.85)

where the moments are now defined by

(9.86)

(9.87)

Therefore, each secondary user can determine on its own by solving the following minimum mean-square-error estimation problem:

(9.88)

This solution method requires knowledge of the moments and, in an argument similar to the one that led to (9.20), it can be verified that each agent would attain an MSE performance level that is equal to the noise power level, , at its location.

Alternatively, when the statistical information is not available, each secondary user can estimate iteratively by feeding data into an adaptive implementation similar to (9.26) and (9.27), such as the following vector LMS recursion:

(9.89)

(9.90)

In this case, each secondary user will achieve performance levels similar to (9.36) and (9.37) with replaced by and replaced by . The performance will again be dependent on the local noise level, . As a result, secondary users with larger noise power will perform worse than secondary users with smaller noise power. However, since all secondary users are observing data arising from the same underlying model , it is natural to expect cooperation among the users to be beneficial. As we are going to see, starting from the next section, one way to achieve cooperation and improve performance is by developing algorithms that solve the following global cost function in an adaptive and distributed manner:

(9.91)

a. First, even for MSE cost functions, it is often the case that the required moments are not known beforehand. In this case, the optimal cannot be determined from the solution of the normal equations (9.103). The alternative methods that we shall describe will lead to adaptive techniques that enable each node to estimate directly from data realizations.

b. Second, since adaptive strategies rely on instantaneous data, these strategies possess powerful tracking abilities. Even when the moments vary with time due to non-stationary behavior (such as changing with time), these changes will be reflected in the observed data and will in turn influence the behavior of the adaptive construction. This is one of the key advantages of adaptive strategies: they enable learning and tracking in real-time.

c. Third, cooperation among nodes is generally beneficial. When nodes act individually, their performance is limited by the noise power level at their location. In this way, some nodes can perform significantly better than other nodes. On the other hand, when nodes cooperate with their neighbors and share information during the adaptation process, we will see that performance can be improved across the network.

3.09.3.1 Relating the global cost to neighborhood costs

Let us therefore consider the optimization of the following global cost function:

(9.104)

where is given by (9.93) or (9.97)(9.93) or (9.97). Our strategy to optimize in a distributed manner is based on two steps [2,18]. First, using a completion-of-squares argument (or, equivalently, a second-order Taylor series expansion), we approximate the global cost function (9.104) by an alternative local cost that is amenable to distributed optimization. Then, each node will optimize the alternative cost via a steepest-descent method.

To motivate the distributed diffusion-based approach, we start by introducing a set of nonnegative coefficients that satisfy two conditions:

(9.105)

where denotes the neighborhood of node . Condition (9.105) means that for every node , the sum of the coefficients that relate it to its neighbors is one. The coefficients are free parameters that are chosen by the designer; obviously, as shown later in Theorem 9.6.8, their selection will have a bearing on the performance of the resulting algorithms. If we collect the entries into an matrix , so that the th row of is formed of , then condition (9.105) translates into saying that each of row of adds up to one, i.e.,

(9.106)

where the notation denotes an column vector with all its entries equal to one:

(9.107)

We say that is a right stochastic matrix. Using the coefficients so defined, we associate with each node , a local cost function of the following form:

(9.108)

This cost consists of a weighted combination of the individual costs of the neighbors of node (including itself)—see Figure 9.9. Since the are all nonnegative and each is strictly convex, then is also strictly convex and its minimizer occurs at the same . Using the alternative representation (9.99) for the individual , we can re-express the local cost as

(9.109)

or, equivalently,

(9.110)

where corresponds to the minimum value of at the minimizer :

(9.111)

and is a positive-definite weighting matrix defined by:

(9.112)

That is, is a weighted combination of the covariance matrices in the neighborhood of node . Equality (9.110) amounts to a (second-order) Taylor series expansion of around . Note that the right-hand side consists of two terms: the minimum cost and a weighted quadratic term in the difference .

Now note that we can express from (9.104) as follows:

(9.113)

Substituting (9.110) into the second term on the right-hand side of the above expression gives:

(9.114)

The last term in the above expression does not depend on . Therefore, minimizing over is equivalent to minimizing the following alternative global cost:

(9.115)

Expression (9.115) relates the optimization of the original global cost function, or its equivalent , to the newly-introduced local cost function . The relation is through the second term on the right-hand side of (9.115), which corresponds to a sum of quadratic factors involving the minimizer ; this term tells us how the local cost can be corrected to the global cost . Obviously, the minimizer that appears in the correction term is not known since the nodes wish to determine its value. Likewise, not all the weighting matrices are available to node ; only those matrices that originate from its neighbors can be assumed to be available. Still, expression (9.115) suggests a useful way to replace by another local cost that is closer to . This alternative cost will be shown to lead to a powerful distributed solution to optimize through localized interactions.

Our first step is to limit the summation on the right-hand side of (9.115) to the neighbors of node (since every node can only have access to information from its neighbors). We thus introduce the modified cost function at node :

(9.116)

The cost functions and are both associated with node ; the difference between them is that the expression for the latter is closer to the global cost function (9.115) that we want to optimize.

The weighting matrices that appear in (9.116) may or may not be available because the second-order moments may or may not be known beforehand. If these moments are known, then we can proceed with the analysis by assuming knowledge of the . However, the more interesting case is when these moments are not known. This is generally the case in practice, especially in the context of adaptive solutions and problems involving non-stationary data. Often, nodes can only observe realizations of the regression data arising from distributions whose covariance matrices are the unknown . One way to address the difficulty is to replace each of the weighted norms in (9.116) by a scaled multiple of the un-weighted norm, say,

(9.117)

where is some nonnegative coefficient; we are even allowing its value to change with the node index . The above substitution amounts to having each node approximate the from its neighbors by multiples of the identity matrix

(9.118)

Approximation (9.117) is reasonable in view of the fact that all vector norms are equivalent [19–21]; this norm property ensures that we can bound the weighted norm by some constants multiplying the un-weighted norm say, as:

(9.119)

for some positive constants . Using the fact that the are Hermitian positive-definite matrices, and calling upon the Rayleigh-Ritz characterization of eigenvalues [19,20], we can be more specific and replace the above inequalities by

(9.120)

We note that approximations similar to (9.118) are common in stochastic approximation theory and they mark the difference between using a Newton’s iterative method or a stochastic gradient method [5,22]; the former uses Hessian matrices as approximations for and the latter uses multiples of the identity matrix. Furthermore, as the derivation will reveal, we do not need to worry at this stage about how to select the scalars ; they will end up being embedded into another set of coefficients that will be set by the designer or adjusted by the algorithm—see (9.132) further ahead.

Thus, we replace (9.116) by

(9.121)

The argument so far has suggested how to modify from (9.108) and replace it by the cost (9.121) that is closer in form to the global cost function (9.115). If we replace by its definition (9.108), we can rewrite (9.121) as

(9.122)

With the exception of the variable , this approximate cost at node relies solely on information that is available to node from its neighborhood. We will soon explain how to handle the fact that is not known beforehand to node .

3.09.3.2 Steepest-descent iterations

Node can apply a steepest-descent iteration to minimize . Let denote the estimate for the minimizer that is evaluated by node at time . Starting from an initial condition , node can compute successive estimates iteratively as follows:

(9.123)

where is a small positive step-size parameter, and the notation denotes the gradient vector of the function relative to and evaluated at . The step-size parameter can be selected to vary with time as well. One choice that is common in the optimization literature [5,22,23] is to replace in (9.123) by step-size sequences that satisfy the two conditions (9.25). However, such step-size sequences are not suitable for applications that require continuous learning because they turn off adaptation as ; the steepest-descent iteration (9.123) would stop updating since would be tending towards zero. For this reason, we shall focus mainly on the constant step-size case described by (9.123) since we are interested in developing distributed algorithms that will endow networks with continuous adaptation abilities.

Returning to (9.123) and computing the gradient vector of (9.122) we get:

(9.124)

Using the expression for from (9.97) we arrive at

(9.125)

This iteration indicates that the update from to involves adding two correction terms to . Among many other forms, we can implement the update in two successive steps by adding one correction term at a time, say, as follows:

(9.126)

(9.127)

Step (9.126) updates to an intermediate value by using local gradient vectors from the neighborhood of node . Step (9.127) further updates to . Two issues stand out from examining (9.127):

With the substitutions described in items (a) and (b) above, we replace the second step (9.127) by

(9.128)

Introduce the weighting coefficients:

(9.129)

(9.130)

(9.131)

and observe that, for sufficiently small step-sizes , these coefficients are nonnegative and, moreover, they satisfy the conditions:

(9.132)

Condition (9.132) means that for every node , the sum of the coefficients that relate it to its neighbors is one. Just like the , from now on, we will treat the coefficients as free weighting parameters that are chosen by the designer according to (9.132); their selection will also have a bearing on the performance of the resulting algorithms—see Theorem 9.6.8. If we collect the entries into an matrix , such that the th column of consists of , then condition (9.132) translates into saying that each column of adds up to one:

(9.133)

We say that is a left stochastic matrix.

3.09.3.3 Adapt-then-Combine (ATC) diffusion strategy

Using the coefficients so defined, we replace (9.126) and (9.128) by the following recursions for :

(9.134)

for some nonnegative coefficients that satisfy conditions (9.106) and (9.133), namely,

(9.135)

or, equivalently,

(9.136)

To run algorithm (9.134), we only need to select the coefficients that satisfy (9.135) or (9.136); there is no need to worry about the intermediate coefficients any longer since they have been blended into the . The scalars that appear in (9.134) correspond to weighting coefficients over the edge linking node to its neighbors . Note that two sets of coefficients are used to scale the data that are being received by node : one set of coefficients, is used in the first step of (9.134) to scale the moment data , and a second set of coefficients, is used in the second step of (9.134) to scale the estimates . Figure 9.10 explains what the entries on the columns and rows of the combination matrices stand for using an example with and the matrix for illustration. When the combination matrix is right-stochastic (as is the case with ), each of its rows would add up to one. On the other hand, when the matrix is left-stochastic (as is the case with ), each of its columns would add up to one.

At every time instant , the ATC strategy (9.134) performs two steps. The first step is an information exchange step where node receives from its neighbors their moments . Node combines this information and uses it to update its existing estimate to an intermediate value . All other nodes in the network are performing a similar step and updating their existing estimates into intermediate estimates by using information from their neighbors. The second step in (9.134) is an aggregation or consultation step where node combines the intermediate estimates of its neighbors to obtain its updated estimate . Again, all other nodes in the network are simultaneously performing a similar step. The reason for the name Adapt-then-Combine (ATC) strategy is that the first step in (9.134) will be shown to lead to an adaptive step, while the second step in (9.134) corresponds to a combination step. Hence, strategy (9.134) involves adaptation followed by combination or ATC for short. The reason for the qualification “diffusion” is that the combination step in (9.134) allows information to diffuse through the network in real time. This is because each of the estimates is influenced by data beyond the immediate neighborhood of node .

In the special case when , so that no information exchange is performed but only the aggregation step, the ATC strategy (9.134) reduces to:

(9.137)

where the first step relies solely on the information that is available locally at node .

Observe in passing that the term that appears in the information exchange step of (9.134) is related to the gradient vectors of the local costs evaluated at , i.e., it holds that

(9.138)

so that the ATC strategy (9.134) can also be written in the following equivalent form:

(9.139)

The significance of this general form is that it is applicable to optimization problems involving more general local costs that are not necessarily quadratic in , as detailed in [1–3]—see also Section 3.09.10.4. The top part of Figure 9.11 illustrates the two steps involved in the ATC procedure for a situation where node has three other neighbors labeled . In the first step, node evaluates the gradient vectors of its neighbors at , and subsequently aggregates the estimates from its neighbors. The dotted arrows represent flow of information towards node from its neighbors. The solid arrows represent flow of information from node to its neighbors. The CTA diffusion strategy is discussed next.

3.09.3.4 Combine-then-Adapt (CTA) diffusion strategy

Similarly, if we return to (9.125) and add the second correction term first, then (9.126) and (9.127) are replaced by:

(9.140)

(9.141)

Following similar reasoning to what we did before in the ATC case, we replace in step (9.140) by and replace in (9.141) by . We then introduce the same coefficients and arrive at the following Combine-then-Adapt (CTA) strategy:

(9.142)

where the nonnegative coefficients satisfy the same conditions (9.106) and (9.133), namely,

(9.143)

or, equivalently,

(9.144)

At every time instant , the CTA strategy (9.142) also consists of two steps. The first step is an aggregation step where node combines the existing estimates of its neighbors to obtain the intermediate estimate . All other nodes in the network are simultaneously performing a similar step and aggregating the estimates of their neighbors. The second step in (9.142) is an information exchange step where node receives from its neighbors their moments and uses this information to update its intermediate estimate to . Again, all other nodes in the network are simultaneously performing a similar information exchange step. The reason for the name Combine-then-Adapt (CTA) strategy is that the first step in (9.142) involves a combination step, while the second step will be shown to lead to an adaptive step. Hence, strategy (9.142) involves combination followed by adaptation or CTA for short. The reason for the qualification “diffusion” is that the combination step of (9.142) allows information to diffuse through the network in real time.

In the special case when , so that no information exchange is performed but only the aggregation step, the CTA strategy (9.142) reduces to:

(9.145)

where the second step relies solely on the information that is available locally at node . Again, the CTA strategy (9.142) can be rewritten in terms of the gradient vectors of the local costs as follows:

(9.146)

The bottom part of Figure 9.11 illustrates the two steps involved in the CTA procedure for a situation where node has three other neighbors labeled . In the first step, node aggregates the estimates from its neighbors, and subsequently performs information exchange by evaluating the gradient vectors of its neighbors at .

3.09.3.5 Useful properties of diffusion strategies

Note that the structure of the ATC and CTA diffusion strategies (9.134) and (9.142) are fundamentally the same: the difference between the implementations lies in which variable we choose to correspond to the updated weight estimate . In the ATC case, we choose the result of the combination step to be , whereas in the CTA case we choose the result of the adaptation step to be .

For ease of reference, Table 9.2 lists the steepest-descent diffusion algorithms derived in the previous sections. The derivation of the ATC and CTA strategies (9.134) and (9.142) followed the approach proposed in [18,28]. CTA estimation schemes were first proposed in the works [29–33], and later extended in [18,28,34,35]. The earlier versions of CTA in [29–31] used the choice . This form of the algorithm with , and with the additional constraint that the step-sizes should be time-dependent and decay towards zero as time progresses, was later applied by [36,37] to solve distributed optimization problems that require all nodes to reach consensus or agreement. Likewise, special cases of the ATC estimation scheme (9.134), involving an information exchange step followed by an aggregation step, first appeared in the work [38] on diffusion least-squares schemes and subsequently in the works [18,34,35,39–41] on distributed mean-square-error and state-space estimation methods. A special case of the ATC strategy (9.134) corresponding to the choice with decaying step-sizes was adopted in [42] to ensure convergence towards a consensus state. Diffusion strategies of the form (9.134) and (9.142) (or, equivalently, (9.139) and (9.146)) are general in several respects:

3.09.5.1 General diffusion model

Rather than study the performance of the ATC and CTA steepest-descent strategies (9.134) and (9.142) separately, it is useful to introduce a more general description that includes the ATC and CTA recursions as special cases. Thus, consider a distributed steepest-descent diffusion implementation of the following general form for :

(9.163)

(9.164)

(9.165)

where the scalars denote three sets of nonnegative real coefficients corresponding to the entries of combination matrices , respectively. These matrices are assumed to satisfy the conditions:

(9.166)

so that are left stochastic and is right-stochastic, i.e.,

(9.167)

As indicated in Table 9.4, different choices for correspond to different cooperation modes. For example, the choice and corresponds to the ATC implementation (9.134), while the choice and corresponds to the CTA implementation (9.142). Likewise, the choice corresponds to the case in which the nodes only share weight estimates and the distributed diffusion recursions (9.163) to (9.165) become:

(9.168)

(9.169)

(9.170)

Furthermore, the choice corresponds to the non-cooperative mode of operation, in which case the recursions reduce to the classical (stand-alone) steepest-descent recursion [4–7], where each node minimizes individually its own quadratic cost , defined earlier in (9.97):

(9.171)

3.09.5.2 Error recursions

Our objective is to examine whether, and how fast, the weight estimates from the distributed implementation (9.163)–(9.165) converge towards the solution of (9.92) and (9.93). To do so, we introduce the error vectors:

(9.172)

(9.173)

(9.174)

Each of these error vectors measures the residual relative to the desired minimizer . Now recall from (9.100) that

(9.175)

Then, subtracting from both sides of relations in (9.163)–(9.165) we get

(9.176)

(9.177)

(9.178)

We can describe these relations more compactly by collecting the information from across the network into block vectors and matrices. We collect the error vectors from across all nodes into the following block vectors, whose individual entries are of size each:

(9.179)

The block quantities represent the state of the errors across the network at time . Likewise, we introduce the following block diagonal matrices, whose individual entries are of size each:

(9.180)

(9.181)

Each block diagonal entry of , say, the th entry, contains the combination of the covariance matrices in the neighborhood of node . We can simplify the notation by denoting these neighborhood combinations as follows:

(9.182)

so that becomes

(9.183)

In the special case when , the matrix reduces to

(9.184)

with the individual covariance matrices appearing on its diagonal; we denote by in this special case. We further introduce the Kronecker products

(9.185)

The matrix is an block matrix whose block is equal to . Likewise, for . In other words, the Kronecker transformation defined above simply replaces the matrices by block matrices where each entry in the original matrices is replaced by the diagonal matrices . For ease of reference, Table 9.5 lists the various symbols that have been defined so far, and others that will be defined in the sequel.

Returning to (9.176)–(9.178), we conclude that the following relations hold for the block quantities:

(9.186)

(9.187)

(9.188)

so that the network weight error vector, , ends up evolving according to the following dynamics:

(9.189)

For comparison purposes, if each node in the network minimizes its own cost function, , separately from the other nodes and uses the non-cooperative steepest-descent strategy (9.171), then the weight error vector across all nodes would evolve according to the following alternative dynamics:

(9.190)

where the matrices and do not appear, and is replaced by from (9.184). This recursion is a special case of (9.189) when .

3.09.5.3 Convergence behavior

Note from (9.189) that the evolution of the weight error vector involves block vectors and block matrices; this will be characteristic of the distributed implementations that we consider in this chapter. To examine the stability and convergence properties of recursions that involve such block quantities, it becomes useful to rely on a certain block vector norm. In Appendix D, we describe a so-called block maximum norm and establish some of its useful properties. The results of the appendix will be used extensively in our exposition. It is therefore advisable for the reader to review the properties stated in the appendix at this stage.

Using the result of Lemma D.6, we can establish the following useful statement about the convergence of the steepest-descent diffusion strategy (9.163)–(9.165). The result establishes that all nodes end up converging to the optimal solution if the nodes employ positive step-sizes that are small enough; the lemma provides a sufficient bound on the .

Observe that the stability condition (9.191) does not depend on the specific combination matrices and . Thus, as long as these matrices are chosen to be left-stochastic, the weight-error vectors will converge to zero under condition (9.191) no matter what are. Only the combination matrix influences the condition on the step-size through the neighborhood covariance matrices . Observe further that the statement of the lemma does not require the network to be connected. Moreover, when , in which case the nodes only share weight estimates and do not share the neighborhood moments , as in (9.168)–(9.170), condition (9.191) becomes

(9.193)

in terms of the actual covariance matrices . Conditions (9.191) and (9.193) are reminiscent of a classical result for stand-alone steepest-descent algorithms, as in the non-cooperative case (9.171), where it is known that the estimate by each individual node in this case will converge to if, and only if, its positive step-size satisfies

(9.194)

This is the same condition as (9.193) for the case .

The following statement provides a bi-directional statement that ensures convergence of the (distributed) steepest-descent diffusion strategy (9.163)–(9.165) for any choice of left-stochastic combination matrices and .

More importantly, we can verify that under fairly general conditions, employing the steepest-descent diffusion strategy (9.163)–(9.165) enhances the convergence rate of the error vector towards zero relative to the non-cooperative strategy (9.171). The next three results establish this fact when is a doubly stochastic matrix, i.e., it has nonnegative entries and satisfies

(9.196)

with both its rows and columns adding up to one. Compared to the earlier right-stochastic condition on in (9.105), we are now requiring

(9.197)

For example, these conditions are satisfied when is right stochastic and symmetric. They are also automatically satisfied for , when only weight estimates are shared as in (9.168)–(9.170); this latter case covers the ATC and CTA diffusion strategies (9.137) and (9.145), which do not involve information exchange.

The argument can be modified to handle different step-sizes across the nodes if we assume uniform covariance data across the network, as stated below.

The next statement considers the case of ATC and CTA strategies (9.137) and (9.145) without information exchange, which corresponds to the case . The result establishes that these strategies always enhance the convergence rate over the non-cooperative case, without the need to assume uniform step-sizes or uniform covariance data.

The results of the previous theorems highlight the following important facts about the role of the combination matrices in the convergence behavior of the diffusion strategy (9.163)–(9.165):

3.09.6.1 Data model

When we studied the performance of the steepest-descent diffusion strategy (9.163)–(9.165) we exploited result (9.175), which indicated how the moments that appeared in the recursions related to the optimal solution . Likewise, in order to be able to analyze the performance of the adaptive diffusion strategy (9.201)–(9.203), we need to know how the data across the network relate to . Motivated by the several examples presented earlier in Section 3.09.2, we shall assume that the data satisfy a linear model of the form:

(9.208)

where is measurement noise with variance :

(9.209)

and where the stochastic processes are assumed to be jointly wide-sense stationary with moments:

(9.210)

(9.211)

(9.212)

All variables are assumed to be zero-mean. Furthermore, the noise process is assumed to be temporally white and spatially independent, as described earlier by (9.6), namely,

(9.213)

The noise process is further assumed to be independent of the regression data for all and so that:

(9.214)

We shall also assume that the regression data are temporally white and spatially independent so that:

(9.215)

Although we are going to derive performance measures for the network under this independence assumption on the regression data, it turns out that the resulting expressions continue to match well with simulation results for sufficiently small step-sizes, even when the independence assumption does not hold (in a manner similar to the behavior of stand-alone adaptive filters) [4,5].

3.09.6.2 Performance measures

Our objective is to analyze whether, and how fast, the weight estimates from the adaptive diffusion implementation (9.201)–(9.203) converge towards . To do so, we again introduce the weight error vectors:

(9.216)

(9.217)

(9.218)

Each of these error vectors measures the residual relative to the desired in (9.208). We further introduce two scalar error measures:

(9.219)

(9.220)

The first error measures how well the term approximates the measured data, ; in view of (9.208), this error can be interpreted as an estimator for the noise term . If node is able to estimate well, then would get close to . Therefore, under ideal conditions, we would expect the variance of to tend towards the variance of . However, as remarked earlier in (9.31), there is generally an offset term for adaptive implementations that is captured by the variance of the a priori error, . This second error measures how well approximates the uncorrupted term . Using the data model (9.208), we can relate as

(9.221)

Since the noise component, , is assumed to be zero-mean and independent of all other random variables, we recover (9.31):

(9.222)

This relation confirms that the variance of the output error, is at least as large as and away from it by an amount that is equal to the variance of the a priori error, . Accordingly, in order to quantify the performance of any particular node in the network, we define the mean-square-error (MSE) and excess-mean-square-error (EMSE) for node as the following steady-state measures:

(9.223)

(9.224)

Then, it holds that

(9.225)

Therefore, the EMSE term quantifies the size of the offset in the MSE performance of each node. We also define the mean-square-deviation (MSD) of each node as the steady-state measure:

(9.226)

which measures how far is from in the mean-square-error sense.

We indicated earlier in (9.36) and (9.37) how the MSD and EMSE of stand-alone LMS filters in the non-cooperative case depend on . In this section, we examine how cooperation among the nodes influences their performance. Since cooperation couples the operation of the nodes, with data originating from one node influencing the behavior of its neighbors and their neighbors, the study of the network performance requires more effort than in the non-cooperative case. Nevertheless, when all is said and done, we will arrive at expressions that approximate well the network performance and reveal some interesting conclusions.

3.09.6.3 Error recursions

Using the data model (9.208) and subtracting from both sides of the relations in (9.201)–(9.203) we get

(9.227)

(9.228)

(9.229)

Comparing the second recursion with the corresponding recursion in the steepest-descent case (9.176)–(9.178), we see that two new effects arise: the effect of gradient noise, which replaces the covariance matrices by the instantaneous approximation , and the effect of measurement noise, .

We again describe the above relations more compactly by collecting the information from across the network in block vectors and matrices. We collect the error vectors from across all nodes into the following block vectors, whose individual entries are of size each:

(9.230)

The block quantities represent the state of the errors across the network at time . Likewise, we introduce the following block diagonal matrices, whose individual entries are of size each:

(9.231)

(9.232)

Each block diagonal entry of , say, the th entry, contains a combination of rank-one regression terms collected from the neighborhood of node . In this way, the matrix is now stochastic and dependent on time, in contrast to the matrix in the steepest-descent case in (9.181), which was a constant matrix. Nevertheless, it holds that

(9.233)

so that, on average, agrees with . We can simplify the notation by denoting the neighborhood combinations as follows:

(9.234)

so that becomes

(9.235)

Again, compared with the matrix defined in (9.182), we find that is now both stochastic and time-dependent. Nevertheless, it again holds that

(9.236)

In the special case when , the matrix reduces to

(9.237)

with

(9.238)

where was defined earlier in (9.184).

We further introduce the following block column vector, whose entries are of size each:

(9.239)

Obviously, given that the regression data and measurement noise are zero-mean and independent of each other, we have

(9.240)

and the covariance matrix of is block diagonal with blocks of size :

(9.241)

Returning to (9.227)–(9.229), we conclude that the following relations hold for the block quantities:

(9.242)

(9.243)

(9.244)

where

(9.245)

so that the network weight error vector, , ends up evolving according to the following stochastic recursion:

(9.246)

For comparison purposes, if each node operates individually and uses the non-cooperative LMS recursion (9.207), then the weight error vector across all nodes would evolve according to the following stochastic recursion:

(9.247)

where the matrices and do not appear, and is replaced by from (9.237).

3.09.6.4 Convergence in the mean

Taking expectations of both sides of (9.246) we find that:

(9.248)

where we used the fact that and are independent of each other in view of our earlier assumptions on the regression data and noise in Section 3.09.6.1. Comparing with the error recursion (9.189) in the steepest-descent case, we find that both recursions are identical with replaced by . Therefore, the convergence statements from the steepest-descent case can be extended to the adaptive case to provide conditions on the step-size to ensure stability in the mean, i.e., to ensure

(9.249)

When (9.249) is guaranteed, we say that the adaptive diffusion solution is asymptotically unbiased. The following statements restate the results of Theorems 9.5.1–9.5.5 in the context of mean error analysis.

Observe again that the mean stability condition (9.250) does not depend on the specific combination matrices and that are being used. Only the combination matrix influences the condition on the step-size through the neighborhood covariance matrices . Observe further that the statement of the lemma does not require the network to be connected. Moreover, when , in which case the nodes only share weight estimators and do not share neighborhood data as in (9.204)–(9.206), condition (9.250) becomes

(9.251)

Conditions (9.250) and (9.251) are reminiscent of a classical result for the stand-alone LMS algorithm, as in the non-cooperative case (9.207), where it is known that the estimator by each individual node in this case would converge in the mean to if, and only if, its step-size satisfies

(9.252)

The following statement provides a bi-directional result that ensures the mean convergence of the adaptive diffusion strategy for any choice of left-stochastic combination matrices and .

As was the case with steepest-descent diffusion strategies, the adaptive diffusion strategy (9.201)–(9.203) also enhances the convergence rate of the mean of the error vector towards zero relative to the non-cooperative strategy (9.207). The next results restate Theorems 9.5.3–9.5.5; they assume is a doubly stochastic matrix.

The next statement considers the case of ATC and CTA strategies (9.204)–(9.206) without information exchange, which correspond to the choice . The result establishes that these strategies always enhance the convergence rate over the non-cooperative case, without the need to assume uniform step-sizes or uniform covariance data.

The results of the previous theorems again highlight the following important facts about the role of the combination matrices in the convergence behavior of the adaptive diffusion strategy (9.201)–(9.203):

3.09.6.5 Mean-square stability

It is not sufficient to ensure the stability of the weight-error vector in the mean sense. The error vectors, , may be converging on average to zero but they may have large fluctuations around the zero value. We therefore need to examine how small the error vectors get. To do so, we perform a mean-square-error analysis. The purpose of the analysis is to evaluate how the variances evolve with time and what their steady-state values are, for each node .

In this section, we are particularly interested in evaluating the evolution of two mean-square-errors, namely,

(9.257)

The steady-state values of these quantities determine the MSD and EMSE performance levels at node and, therefore, convey critical information about the performance of the network. Under the independence assumption on the regression data from Section 3.09.6.1, it can be verified that the EMSE variance can be written as:

(9.258)

in terms of a weighted square measure with weighting matrix . Here we are using the notation to denote the weighted square quantity , for any column vector and matrix . Thus, we can evaluate mean-square-errors of the form (9.257) by evaluating the means of weighted square quantities of the following form:

(9.259)

for an arbitrary Hermitian nonnegative-definite weighting matrix that we are free to choose. By setting to different values (say, or ), we can extract various types of information about the nodes and the network, as the discussion will reveal. The approach we follow is based on the energy conservation framework of [4,5,55].

So, let denote an arbitrary block Hermitian nonnegative-definite matrix that we are free to choose, with block entries . Let denote the vector that is obtained by stacking the columns of on top of each other, written as

(9.260)

In the sequel, it will become more convenient to work with the vector representation than with the matrix itself.

We start from the weight-error vector recursion (9.246) and re-write it more compactly as:

(9.261)

where the coefficient matrices and are short-hand representations for

(9.262)

and

(9.263)

Note that is stochastic and time-variant, while is constant. We denote the mean of by

(9.264)

where is defined by (9.181). Now equating weighted square measures on both sides of (9.261) we get

(9.265)

Expanding the right-hand side we find that

(9.266)

Under expectation, the last two terms on the right-hand side evaluate to zero so that

(9.267)

Let us evaluate each of the expectations on the right-hand side. The last expectation is given by

(9.268)

where is defined by (9.241) and where we used the fact that for any two matrices and of compatible dimensions. With regards to the first expectation on the right-hand side of (9.267), we have

(9.269)

where we introduced the nonnegative-definite weighting matrix

(9.270)

where is defined by (9.181) and the term denotes the following factor, which depends on the square of the step-sizes, :

(9.271)

The evaluation of the above expectation depends on higher-order moments of the regression data. While we can continue with the analysis by taking this factor into account, as was done in [4,5,18,55], it is sufficient for the exposition in this chapter to focus on the case of sufficiently small step-sizes where terms involving higher powers of the step-sizes can be ignored. Therefore, we continue our discussion by letting

(9.272)

The weighting matrix is fully defined in terms of the step-size matrix, , the network topology through the matrices , and the regression statistical profile through . Expression (9.272) tells us how to construct from . The expression can be transformed into a more compact and revealing form if we instead relate the vector forms and . Using the following equalities for arbitrary matrices of compatible dimensions [5]:

(9.273)

(9.274)

and applying the vec operation to both sides of (9.272) we get

That is,

(9.275)

where we are introducing the coefficient matrix of size :

(9.276)

A reasonable approximate expression for for sufficiently small step-sizes is

(9.277)

Indeed, if we replace from (9.264) into (9.277) and expand terms, we obtain the same factors that appear in (9.276) plus an additional term that depends on the square of the step-sizes, , whose effect can be ignored for sufficiently small step-sizes.

In this way, and using in addition property (9.274), we find that relation (9.267) becomes:

(9.278)

The last term is dependent on the network topology through the matrix , which is defined in terms of , and the noise and regression data statistical profile through . It is convenient to introduce the alternative notation to refer to the weighted square quantity , where . We shall use these two notations interchangeably. The convenience of the vector notation is that it allows us to exploit the simpler linear relation (9.275) between and to rewrite (9.278) as shown in (9.279) below, with the same weight vector appearing on both sides.

Note that relation (9.279) is not an actual recursion; this is because the weighting matrices on both sides of the equality are different. The relation can be transformed into a true recursion by expanding it into a convenient state-space model; this argument was pursued in [4,5,18,55] and is not necessary for the exposition here, except to say that stability of the matrix ensures the mean-square stability of the filter—this fact is also established further ahead through relation (9.327). By mean-square stability we mean that each term remains bounded over time and converges to a steady-state value. Moreover, the spectral radius of controls the rate of convergence of towards its steady-state value.

3.09.6.6 Network mean-square performance

We can now use the variance relation (9.279) to evaluate the network performance, as well as the performance of the individual nodes, in steady-state. Since the dynamics is mean-square stable for sufficiently small step-sizes, we take the limit of (9.279) as and write:

(9.283)

Grouping terms leads to the following result.

Expression (9.284) is a very useful relation; it allows us to evaluate the network MSD and EMSE through proper selection of the weighting vector (or, equivalently, the weighting matrix ). For example, the network MSD is defined as the average value:

(9.285)

which amounts to averaging the MSDs of the individual nodes. Therefore,

(9.286)

This means that in order to recover the network MSD from relation (9.284), we should select the weighting vector such that

Solving for and substituting back into (9.284) we arrive at the following expression for the network MSD:

(9.287)

Likewise, the network EMSE is defined as the average value

(9.288)

which amounts to averaging the EMSEs of the individual nodes. Therefore,

(9.289)

where is the matrix defined earlier by (9.184), and which we repeat below for ease of reference:

(9.290)

This means that in order to recover the network EMSE from relation (9.284), we should select the weighting vector such that

(9.291)

Solving for and substituting into (9.284) we arrive at the following expression for the network EMSE:

(9.292)

3.09.6.7 Mean-square performance of individual nodes

We can also assess the mean-square performance of the individual nodes in the network from (9.284). For instance, the MSD of any particular node is defined by

(9.293)

Introduce the block diagonal matrix with blocks of size , where all blocks on the diagonal are zero except for an identity matrix on the diagonal block of index , i.e.,

(9.294)

Then, we can express the node MSD as follows:

(9.295)

The same argument that was used to obtain the network MSD then leads to

(9.296)

Likewise, the EMSE of node is defined by

(9.297)

Introduce the block diagonal matrix with blocks of size , where all blocks on the diagonal are zero except for the diagonal block of index whose value is , i.e.,

(9.298)

Then, we can express the node EMSE as follows:

(9.299)

The same argument that was used to obtain the network EMSE then leads to

(9.300)

We summarize the results in the following statement.

We can recover from the above expressions the performance of the nodes in the non-cooperative implementation (9.207), where each node performs its adaptation individually, by setting .

We can express the network MSD, and its EMSE if desired, in an alternative useful form involving a series representation.

3.09.6.8 Uniform data profile

We can simplify expressions (9.307)–(9.309) for in the case when the regression covariance matrices are uniform across the network and all nodes employ the same step-size, i.e., when

(9.310)

(9.311)

and when the combination matrix is doubly stochastic, so that

(9.312)

Thus, under conditions (9.310)–(9.312), expressions (9.180), (9.181), and (9.263) for simplify to

(9.313)

(9.314)

(9.315)

Substituting these values into expression (9.309) for we get

(9.316)

where we used the useful Kronecker product identities:

(9.317)

(9.318)

for any matrices of compatible dimensions. Likewise, introduce the diagonal matrix with noise variances:

(9.319)

Then, expression (9.241) for becomes

(9.320)

It then follows that we can simplify expression (9.307) for as:

(9.321)

3.09.6.9 Transient mean-square performance

Before comparing the mean-square performance of various cooperation strategies, we pause to comment that the variance relation (9.279) can also be used to characterize the transient behavior of the network, and not just its steady-state performance. To see this, iterating (9.279) starting from , we find that

(9.325)

where

(9.326)

in terms of the initial condition, . If this initial condition happens to be , then . Comparing expression (9.325) at time instants and we can relate and as follows:

(9.327)

This recursion relates the same weighted square measures of the error vectors . It therefore describes how these weighted square measures evolve over time. It is clear from this relation that, for mean-square stability, the matrix needs to be stable so that the terms involving do not grow unbounded.

The learning curve of the network is the curve that describes the evolution of the network EMSE over time. At any time , the network EMSE is denoted by and measured as:

(9.328)

The above expression indicates that is obtained by averaging the EMSE of the individual nodes at time . Therefore,

(9.329)

where is the matrix defined by (9.290). This means that in order to evaluate the evolution of the network EMSE from relation (9.327), we simply select the weighting vector such that

(9.330)

Substituting into (9.327) we arrive at the learning curve for the network.