

We consider distributed multitask learning problems over a network of agents where each agent is interested in estimating its own parameter vector, <span>also called task, and where the tasks at neighboring agents are related according to a set of linear equality constraints</span>. Each agent possesses its own convex cost function of its parameter vector and a set of linear equality constraints <span>involving its own parameter vector and the parameter vectors of its neighboring agents.</span> We propose an adaptive stochastic algorithm based on the projection gradient method and diffusion strategies <span>in order to allow</span> the network to optimize the individual costs subject to all constraints. Although the derivation is carried out for linear equality constraints, the technique can be applied to other <span>forms</span> of convex constraints. We conduct a detailed mean-square-error analysis of the proposed algorithm and derive closed-form expressions to predict its learning behavior. We provide simulations to illustrate the theoretical findings. <span>Finally, the algorithm is employed for solving two problems in a distributed manner: a minimum-cost flow problem over a network and a space-time varying field reconstruction problem.</span>

Introduction
============

Single-task distributed optimization over networks allows to minimize the aggregate sum of convex cost functions, each available at an agent, subject to convex constraints that are also distributed across the agents. Each learner seeks to estimate the minimizer through local computations and communications among neighboring agents without the need to know any of the constraints or costs besides their own. Several useful strategies have been proposed to solve constrained and unconstrained versions of this problem in a fully decentralized . Diffusion strategies @lopes2008diffusion [@chen2013distributed; @sayed2014adaptation; @towfic2014adaptive; @sayed2014diffusion; @towfic2015stability] are attractive since they are scalable, robust, <span>and</span> enable continuous learning and adaptation in response to drifts in the location of the minimizer due to changes in the costs or in the constraints.

Multitask distributed learning over networks <span>is particularly well-suited for applications</span> where several parameter vectors need to be estimated simultaneously from successive noisy measurements using in-network The network is decomposed into clusters of agents and each cluster <span>estimates</span> its own parameter vector @chen2014multitask. Distributed strategies for <span>solving</span> multitask problems have been addressed in two main ways. In a first scenario, agents do not know the cluster they belong to and no prior information on possible relationships between tasks is assumed. In this case, all agents cooperate with each other as dictated by the network topology. It is shown in @chen2013distributed that, <span>in this case,</span> the diffusion iterates <span>will converge</span> to a Pareto optimal solution corresponding to a multi-objective optimization problem. To avoid cooperation with neighbors seeking different objectives, automatic clustering techniques based on diffusion strategies have <span>also been proposed</span> @zhao2012clustering [@chen2015diffusion; @zhao2015distributed]. In a second scenario, it is assumed that agents know which cluster they belong to. Multitask diffusion strategies <span>are then derived</span> by exploiting prior information about relationships among the tasks. For example, one way to model and exploit relationships among tasks is to formulate convex optimization problems with appropriate co-regularizers between In @bertrand2012distributed, distributed algorithms are derived to estimate node-specific signals that lie in a common latent signal subspace in the presence of node-specific linear equality constraints. In @chen2014diffusion, a diffusion algorithm is derived to solve multitask estimation problem where the parameter space is decomposed into two orthogonal subspaces, with one of the subspaces being common to all agents. that the optimum parameter vectors to be estimated <span>at neighboring agents</span> are related according to a set of constraints. <span>This observation motivates us to consider in this work</span> multitask problems subject to linear equality constraints of the form:

\[eq: problem in the introduction\] $$\begin{aligned}
    &\operatorname*{minimize}\limits_{{\boldsymbol{w}}_1,\ldots,{\boldsymbol{w}}_N}~J^{\text{glob}}({\boldsymbol{w}}_1,\ldots,{\boldsymbol{w}}_N)\triangleq\sum_{k=1}^N J_k({\boldsymbol{w}}_k),\\
    &\operatorname*{subject\,to}~\sum_{\ell\in{\mathcal{I}}_p}{\boldsymbol{D}}_{p\ell}\,{\boldsymbol{w}}_\ell+{\boldsymbol{b}}_p=\Zero, ~p=1,\ldots,P.\label{eq: multitask problem (b)}
    \end{aligned}$$

Each agent $k$ in the network seeks to estimate its own $M_k \times 1$ parameter vector ${\boldsymbol{w}}_k$, and <span>has knowledge of</span> its cost function $J_k(\cdot)$ and the set of linear equality <span>constraints that agent $k$ is involved in</span>. Each constraint is indexed by $p$, and defined by the $L_p\times M_\ell$ matrices ${\boldsymbol{D}}_{p\ell}$, the $L_p\times1$ vector ${\boldsymbol{b}}_p$, and the set ${\mathcal{I}}_p$ of agent indices involved in this constraint.

**Assumption.** In the current work, it is assumed that each agent $k$ in ${\mathcal{I}}_p$ can collect estimates from all agents in ${\mathcal{I}}_p$ in order to satisfy the $p$-th constraint, i.e., ${\mathcal{I}}_p\subseteq{\mathcal{N}}_k$ for all $k\in{\mathcal{I}}_p$ where ${\mathcal{N}}_k$ denotes the neighborhood of agent $k$. This assumption is reasonable in many applications, for instance, in remote monitoring of physical phenomena involving discretization of spatial differential equations @bertsekas1989parallel, and in network monitoring involving conservation laws at each junction @ahuja1993network.

<span>For illustration purposes, consider a minimum-cost flow problem over the network shown in Fig. \[fig: network flow problem - intro\]. This network consists of $10$ nodes, $1$ destination sink $D$, and $15$ communication links. With each link $j$, we associate a directed arc and we let $f_j$ denote the flow or traffic on this link, with $f_j>0$ meaning that the flow is in the direction of the arc, and $f_j<0$ otherwise. At each node $k$, an external source flow $s_k$ enters and flows through the network to the destination sink. The flow must satisfy a conservation equation, which states that at each node $k$, the sum of flows entering the node, plus the external source $s_k$, is equal to the sum of flows leaving node $k$. Given the external sources $s_k$ and the network topology, a number of studies have been devoted to finding the optimal flows $f_j^\star$ that minimize a total flow transmission cost and satisfy the conservation equations @ahuja1993network [@boyd2004convex; @ventura1991computational]. Problems of this type arise in applications such as electrical networks, telecommunication networks, pipeline networks @ahuja1993network. In some of these applications, it happens that node $k$ has only access to noisy measurements $s_k(i)$ of the external source at each time instant $i$. Denoting by ${\boldsymbol{w}}_k$ the $M_k\times 1$ vector containing the flows $f_j$ entering and leaving node $k$, we are interested in distributed online learning settings where each node $k$ seeks to estimate ${\boldsymbol{w}}_k$ from noisy measurements $s_k(i)$ by relying only on local computations and communications with its neighbors. This problem can be recast in the form (\[eq: problem in the introduction\]a)–(\[eq: problem in the introduction\]b) and addressed with the multitask strategy proposed in this paper. This example will be considered further in the numerical experiments section.</span>

![Flow network topology with $10$ nodes, $1$ destination sink $D$, and $15$ communication links.<span data-label="fig: network flow problem - intro"></span>](figure1.pdf)

on the use of constant <span>step-sizes</span> to enable continuous adaptation and learning from streaming data. Since we are learning from streaming data, the dual function cannot be computed exactly and the use of primal-dual methods may result in stability problems as <span>already shown</span> in @towfic2015stability. For this reason, we focus on primal techniques. <span>Our</span> current work is able to cope with the following two scenarios: 1) multitask problems with prior information on linear relationships between tasks, <span>and</span> 2) constrained multitask problems with distributed information access. We analyze the behavior of our algorithm in the mean and mean-square-error sense (w.r.t. the minimizers of the local costs and w.r.t. the solution of the constrained multitask problem) and we derive expressions to predict its transient and steady-state behavior. that, for small constant step-sizes, the expected distance between the estimates at each agent and the optimal value can be made arbitrarily small.

**Notation.** Normal font letters denote scalars, boldface lowercase letters denote column vectors, and boldface uppercase letters denote matrices. We use the symbol $(\cdot)^\top$ to denote matrix transpose, the symbol $(\cdot)^{-1}$ to denote matrix inverse, the symbol $(\cdot)^{\dagger}$ to denote the pseudo-inverse of a full <span>row-rank</span> matrix, and the symbol ${\text{tr}}(\cdot)$ to denote the trace operator. The symbol ${\text{diag}}\{\cdot\}$ forms a matrix from block arguments by placing each block immediately below and to the right of its predecessor. The operator ${\text{col}}\{\cdot\}$ stacks the column vector entries on top of each other. The symbols $\otimes$ and $\otimes_b$ denote the Kronecker product and the block Kronecker product, respectively. The symbol ${\text{vec}}(\cdot)$ refers to the standard vectorization operator that stacks the columns of a matrix on top of each other and the symbol ${\text{bvec}}(\cdot)$ refers to the block vectorization operation that vectorizes each block of a matrix and stacks the vectors on top of each other. The identity matrix of size $N\times N$ is denoted by ${\boldsymbol{I}}_N$. The $N\times 1$ vector of ones is denoted by $\One_{N\times 1}$. <span>For a $P\times N$ block matrix ${\boldsymbol{\cal{A}}}$, the $1\times N$ $k$-th block row is denoted by $[{\boldsymbol{\cal{A}}}]_{k,\bullet}$ and the $P\times 1$ $k$-th block column is denoted by $[{\boldsymbol{\cal{A}}}]_{\bullet,k}$.</span> The notation ${\text{P}}_\Omega({\boldsymbol{w}})$ denotes the projection of ${\boldsymbol{w}}$ onto the manifold $\Omega$.

Problem formulation and centralized solution
============================================

Problem formulation and assumptions
-----------------------------------

<span>Consider a network of $N$ agents, labeled $k=1,\ldots, N$.</span> At each time instant $i$, each agent $k$ has access to a zero-mean real-valued observation <span>$d_k(i)$,</span> and a zero-mean real-valued $M_k\times 1$ regression vector <span>${\boldsymbol{x}}_k(i)$, with positive covariance matrix ${\boldsymbol{R}}_{x,k}={\mathbb{E}}\{{\boldsymbol{x}}_k(i){\boldsymbol{x}}^\top_k(i)\}>0$.</span> We assume the data to be related via the linear data model: $$\label{eq: linear data model}
    d_k(i)={\boldsymbol{x}}_k^\top(i){\boldsymbol{w}}^o_k+z_k(i),$$ where ${\boldsymbol{w}}^o_k$ is an $M_k\times 1$ unknown parameter vector, and $z_k(i)$ is a zero-mean measurement noise of variance $\sigma^2_{z,k}$, independent of ${\boldsymbol{x}}_{\ell}(j)$ for all $\ell$ and $j$, and independent of $z_{\ell}(j)$ for $\ell\neq k$ or $i\neq j$. We <span>let</span> ${\boldsymbol{r}}_{dx,k}\triangleq{\mathbb{E}}\{d_k(i){\boldsymbol{x}}_k(i)\}$ <span>and</span> $\sigma^2_{d,k}\triangleq{\mathbb{E}}|d_k(i)|^2$.

Let ${\boldsymbol{w}}_k$ denote <span>some generic</span> $M_k\times 1$ vector <span>that is associated</span> with agent $k$. The objective <span>of agent $k$</span> is to find an estimate for ${\boldsymbol{w}}^o_k$, and we associate with this agent the mean-square-error criterion: $$\label{eq: MSE at each agent}
    J_k({\boldsymbol{w}}_k)={\mathbb{E}}\,|d_k(i)-{\boldsymbol{x}}^\top_k(i){\boldsymbol{w}}_k|^2,$$ which is strongly convex, second-order differentiable, and minimized at ${\boldsymbol{w}}^o_k$. In addition, $P$ linear equality constraints of the form  are imposed on the <span>parameter vectors $\{{\boldsymbol{w}}_k\}$</span> at each time instant $i$. Let us collect the parameter vectors $\{{\boldsymbol{w}}_k\}$ and $\{{\boldsymbol{w}}^o_k\}$ from across the network into $N\times 1$ block column <span>vectors</span> ${\boldsymbol{w}}$ and ${\boldsymbol{w}}^o$, respectively: $${\boldsymbol{w}}\triangleq{\text{col}}\{{\boldsymbol{w}}_1,\ldots,{\boldsymbol{w}}_N\},\qquad
    {\boldsymbol{w}}^o\triangleq{\text{col}}\{{\boldsymbol{w}}^o_1,\ldots,{\boldsymbol{w}}^o_N\}\label{eq: network block column vector w0},$$ and <span>let us write the</span> $P$ linear equality constraints in  more compactly as: $$\label{eq: constraint}
    {\boldsymbol{\cal{D}}}{\boldsymbol{w}}+{\boldsymbol{b}}=\Zero,$$ where ${\boldsymbol{\cal{D}}}$ <span>is a</span> $P\times N$ block matrix, with each block ${\boldsymbol{D}}_{p\ell}$ having dimensions $L_p\times M_{\ell}$, and ${\boldsymbol{b}}$ <span>is a</span> <span>$P\times 1$</span> block column vector where each <span>block ${\boldsymbol{b}}_p$ has dimensions $L_p\times 1$.</span> Combining  and , the network optimization problem becomes: $$\label{eq: network optimization problem}
    \begin{split}
        \operatorname*{minimize}_{{\boldsymbol{w}}}\quad&\sum_{k=1}^N{\mathbb{E}}\,|d_k(i)-{\boldsymbol{x}}^\top_k(i){\boldsymbol{w}}_k|^2,\\
        \operatorname*{subject\,to}\quad&{\boldsymbol{\cal{D}}}{\boldsymbol{w}}+{\boldsymbol{b}}=\Zero,
    \end{split}$$ where each agent $k$ is in charge of estimating the $k$-th sub-vector ${\boldsymbol{w}}_k$ of ${\boldsymbol{w}}$. Since the mean-square-error criterion in  is separable, we shall assume without loss of generality that each parameter vector ${\boldsymbol{w}}_k$ is involved in at least one constraint so <span>that cooperation is justified</span>. We shall also assume that ${\boldsymbol{\cal{D}}}$ is full row-rank to ensure that equation ${\boldsymbol{\cal{D}}}{\boldsymbol{w}}+{\boldsymbol{b}}=\Zero$ has at least one solution. <span>We also introduce an assumption on the availability of the constraints. Let ${\mathcal{I}}_p $ be the set of agent indices involved in the $p$-th constraint. We shall assume that every agent $k$ in ${\mathcal{I}}_p$ is aware of the $p$-th constraint, and that the network topology permits this agent to collect estimates from all agents in ${\mathcal{I}}_p$, that is, ${\mathcal{I}}_p\subseteq{\mathcal{N}}_k$, so it can apply this constraint to its own estimate. This assumption is reasonable in many applications, for instance, in remote monitoring of physical phenomena @bertsekas1989parallel, and in network distribution system monitoring (as described in the introduction) @ahuja1993network. These examples will be considered in numerical experiments section.</span>

Before proceeding, note that problem  can be recast as a quadratic program (QP) @boyd2004convex, <span>and any</span> algorithm that solves QPs can solve it. We are <span>interested instead</span> in distributed adaptive <span>solutions that can operate in real-time on streaming data</span>. As we will see later, the <span>traditional constrained LMS</span> algorithm @frost1972algorithm can solve  in a centralized manner. In <span>this</span> centralized solution, each agent at each iteration sends its data to a fusion center<span>, which in turn</span> processes <span>the</span> data and sends the estimates <span>back to</span> the agents. The entire matrix ${\boldsymbol{\cal{D}}}$ and the entire vector ${\boldsymbol{b}}$ then need to be available at the fusion center.

Centralized solution {#subsec: Centralized solution}
--------------------

<span>Let us first describe the centralized solution. We</span> assume that the agents transmit the collected data $\{d_k(i), {\boldsymbol{x}}_k(i)\}$ to a fusion center for processing. Problem  can be written equivalently as:

$$\label{eq: network optimization problem centralized}
    \begin{split}
    \operatorname*{minimize}_{{\boldsymbol{w}}}\quad&{\boldsymbol{w}}^\top{\boldsymbol{\cal{R}}}_x{\boldsymbol{w}}-2{\boldsymbol{r}}_{dx}^\top{\boldsymbol{w}}+{\boldsymbol{r}}_{d}^\top\One_{N\times 1},\\
    \operatorname*{subject\,to}\quad&{\boldsymbol{\cal{D}}}{\boldsymbol{w}}+{\boldsymbol{b}}=\Zero,
    \end{split}$$

where the $N\times N$ block diagonal matrix ${\boldsymbol{\cal{R}}}_x$, the $N\times 1$ block column vector ${\boldsymbol{r}}_{dx}$, and the $N\times 1$ column vector ${\boldsymbol{r}}_d$ are given by: $$\begin{aligned}
    {\boldsymbol{\cal{R}}}_x&\triangleq{\text{diag}}\{{\boldsymbol{R}}_{x,1},\ldots,{\boldsymbol{R}}_{x,N}\},\\
    {\boldsymbol{r}}_{dx}&\triangleq{\text{col}}\{{\boldsymbol{r}}_{dx,1},\ldots,{\boldsymbol{r}}_{dx,N}\},\\
    {\boldsymbol{r}}_{d}&\triangleq{\text{col}}\{\sigma^2_{d,1},\ldots,\sigma^2_{d,N}\}.\end{aligned}$$ Since ${\boldsymbol{\cal{R}}}_x$ is positive definite, problem  is a positive definite quadratic program with equality constraints. It has a unique global minimum given by: $$\label{eq: closed form solution}
    {\boldsymbol{w}}^\star={\boldsymbol{w}}^o-{\boldsymbol{\cal{R}}}_x^{-1}{\boldsymbol{\cal{D}}}^\top({\boldsymbol{\cal{D}}}{\boldsymbol{\cal{R}}}_x^{-1}{\boldsymbol{\cal{D}}}^\top)^{-1}({\boldsymbol{\cal{D}}}{\boldsymbol{w}}^o+{\boldsymbol{b}}).$$ Let $\Omega$ <span>denote</span> the linear manifold: $$\Omega\triangleq\{{\boldsymbol{w}}\!:\,{\boldsymbol{\cal{D}}}{\boldsymbol{w}}+{\boldsymbol{b}}=\Zero\}.$$ If ${\boldsymbol{w}}^o\in\Omega$, the optimum ${\boldsymbol{w}}^{\star}$ coincides with ${\boldsymbol{w}}^o$. In this case, <span>the constrained optimization problem  can be thought as estimating the unknown parameter vectors ${\boldsymbol{w}}^o_k$ given prior information about relationships between tasks of the form . Exploiting such prior information</span> may improve the estimation as we will see in the experiments. Let $M$ denote the dimension of the network parameter vector ${\boldsymbol{w}}$, i.e., $M=\sum_{k=1}^N M_k$. The projection of any vector $\cblue{{\boldsymbol{y}}}\in\R^M$ onto $\Omega$ is given by: $$\label{eq: projection onto linear manifolds}
    {\text{P}}_{\Omega}(\cblue{{\boldsymbol{y}}})={\boldsymbol{\cal{P}}}\cblue{{\boldsymbol{y}}}-{\boldsymbol{f}},$$ where $${\boldsymbol{\cal{P}}}\triangleq{\boldsymbol{I}}_M-{\boldsymbol{\cal{D}}}^\dagger{\boldsymbol{\cal{D}}},\qquad
    {\boldsymbol{f}}\triangleq{\boldsymbol{\cal{D}}}^\dagger{\boldsymbol{b}}.$$ Let ${\boldsymbol{w}}(i)$ denotes the estimate of ${\boldsymbol{w}}^\star$ at iteration $i$. In order to solve  iteratively, the gradient projection method @bertsekas1999nonlinear can be <span>applied on top of a gradient-descent iteration:</span> $$\label{eq: offline centralized solution}
    {\boldsymbol{w}}(i+1)={\text{P}}_{\Omega}\big({\boldsymbol{w}}(i)+\mu[{\boldsymbol{r}}_{dx}-{\boldsymbol{\cal{R}}}_x{\boldsymbol{w}}(i)]\big),\qquad i\geq 0.$$ In order to run recursion , we need to have access to the second-order moments $\{{\boldsymbol{R}}_{x,k},{\boldsymbol{r}}_{dx,k}\}$. Since these moments are rarely available beforehand, the agents use their instantaneous data $\{d_k(i),{\boldsymbol{x}}_k(i)\}$ to approximate the second-order moments, namely, ${\boldsymbol{R}}_{x,k}\approx{\boldsymbol{x}}_k(i){\boldsymbol{x}}_k^\top(i)$ and ${\boldsymbol{r}}_{dx,k}\approx d_k(i){\boldsymbol{x}}_k(i)$. Doing so and replacing ${\text{P}}_{\Omega}(\cdot)$ by , we obtain the following stochastic-gradient algorithm in lieu of : $$\label{eq: online centralized solution}
    {\boldsymbol{w}}(i+1)={\boldsymbol{\cal{P}}}\cdot{\text{col}}\big\{{\boldsymbol{w}}_k(i)+\mu{\boldsymbol{x}}_k(i)[d_k(i)-{\boldsymbol{x}}_k^\top(i){\boldsymbol{w}}_k(i)]\big\}_{k=1}^N-{\boldsymbol{f}}.$$ Collecting the regression vectors into <span>the $M\times N$ matrix ${\boldsymbol{X}}(i)\triangleq{\text{diag}}\{{\boldsymbol{x}}_k(i)\}_{k=1}^N$ and the observations into the $N\times 1$ vector ${\boldsymbol{d}}(i)\triangleq{\text{col}}\{d_k(i)\}_{k=1}^N$</span>, algorithm  becomes the Constrained <span>Least-Mean-Squares</span> (CLMS) algorithm: $$\label{eq: CLMS}
    {\boldsymbol{w}}(i+1)={\boldsymbol{\cal{P}}}\big({\boldsymbol{w}}(i)+\mu{\boldsymbol{X}}(i)[{\boldsymbol{d}}(i)-{\boldsymbol{X}}^\top(i){\boldsymbol{w}}(i)]\big)-{\boldsymbol{f}}.$$ <span>This procedure</span> was originally proposed in @frost1972algorithm as an online linearly constrained minimum variance (LCMV) <span>filter for solving mean-square-error estimation problems subject to linear constraints; the motivation there was not concerned with multi-task problems. In this section, we showed that the centralized multitask constrained problem reduces to a similar problem, for which algorithm  can be applied. The performance of such stand-alone centralized solutions</span> was studied <span>in @frost1972algorithm [@arablouei2015mean; @sayed2011adaptive]</span>.

Problem reformulation and Distributed solution
==============================================

Problem reformulation
---------------------

<span>We move on to develop a distributed solution with a continuous adaptation mechanism. First, note that several</span> works for solving problems of the form  with possible distributed information access <span>already exist</span> in the . However, , these <span>other works</span> solve single-task estimation problems where the entire network is employed to estimate the minimizer of . Furthermore, , we <span>shall assume</span> stochastic errors in the evaluation of the gradients of local cost functions.

<span>To proceed with the analysis, one of the challenges we now face is</span> that <span>any</span> given agent $k$ may be involved in several constraints. Our strategy is to transform  into an equivalent optimization problem exhibiting structure amenable to distributed optimization with separable constraints. Let $j_k$ denote the number of constraints <span>that</span> agent $k$ is involved in. We expand each node $k$ into a cluster ${\mathcal{C}}_k$ of $j_k$ <span>*virtual*</span> sub-nodes, namely, ${\mathcal{C}}_k\triangleq\{k_m\}_{m=1}^{j_k}$. Each one of these sub-nodes is involved in a single constraint. Let ${\boldsymbol{w}}_{k_m}$ denote the $M_k\times 1$ auxiliary vector associated with sub-node $k_m$. In order to ensure that agent $k$ satisfies simultaneously all the constraints at convergence, we <span>will allow</span> all sub-nodes at agent $k$ <span>to run</span> diffusion <span>learning to reach agreement on their estimates $\{{\boldsymbol{w}}_{k_m}\}$ asymptotically.</span> We denote by ${\mathcal{I}}_{e,p}$ the set of sub-nodes which are involved <span>in</span> the $p$-th constraint.

<span>In order to clarify the presentation, an illustrative example is provided in Fig. \[fig: illustrative example 2\]. On the left of this panel is the original network topology</span> with $N=6$ agents and $P=3$ constraints. On the right is the network topology model with clusters of sub-nodes shown in grey color. Observe that , which means that agent $k$ is involved in . Agent $k$ is thus expanded into a cluster . Each other agent, say $\ell$, involved in a single constraint is renamed $\ell_1$ and assigned to a single-node cluster ${\mathcal{C}}_\ell=\{\ell_1\}$ for consistency of notation. where all sub-nodes are involved in a single constraint.

![(<span>*Left*</span>) Network topology with constraints identified by the subsets of nodes ${\mathcal{I}}_1$, ${\mathcal{I}}_2$, ${\mathcal{I}}_3$, . (<span>*Right*</span>) Network topology model with clusters shown in grey color and constraints now identified by the subsets of sub-nodes ${\mathcal{I}}_{e,1}$, ${\mathcal{I}}_{e,2}$, ${\mathcal{I}}_{e,3}$, . All sub-nodes in this model are involved in a single constraint. Diffusion learning is run in clusters with more than one sub-node to reach agreement on local estimates while satisfying their respective constraints. <span data-label="fig: illustrative example 2"></span>](figure2a.pdf "fig:") ![(<span>*Left*</span>) Network topology with constraints identified by the subsets of nodes ${\mathcal{I}}_1$, ${\mathcal{I}}_2$, ${\mathcal{I}}_3$, . (<span>*Right*</span>) Network topology model with clusters shown in grey color and constraints now identified by the subsets of sub-nodes ${\mathcal{I}}_{e,1}$, ${\mathcal{I}}_{e,2}$, ${\mathcal{I}}_{e,3}$, . All sub-nodes in this model are involved in a single constraint. Diffusion learning is run in clusters with more than one sub-node to reach agreement on local estimates while satisfying their respective constraints. <span data-label="fig: illustrative example 2"></span>](figure2b.pdf "fig:")

Accordingly, we <span>can</span> now reformulate problem . We start by collecting the vectors ${\boldsymbol{w}}_{k_m}$ into the $N_e\times 1$ network block column vector: $$\label{eq: vector extended}
    {\boldsymbol{w}}_e\triangleq{\text{col}}\Big\{{\text{col}}\big\{{\boldsymbol{w}}_{k_m}\big\}_{m=1}^{j_k}\Big\}_{k=1}^N,$$ where <span>$N_e\triangleq\sum_{k=1}^Nj_k$</span>. We introduce for each agent $k$ a set of $j_k$ coefficients $\{c_{k_m}\}$ that satisfy two conditions: $$\label{eq: conditions on c}
    c_{k_m}>0,\text{ for }m=1,\ldots, j_k, \quad\text{and}\quad \sum_{m=1}^{j_k}c_{k_m}=1.$$ The coefficients $\{c_{k_m}\}$ are free parameters that are chosen by the user. A natural choice is $c_{k_m}=\frac{1}{j_k}$ for all $m$. The global cost in (\[eq: problem in the introduction\]a) can be written as: $$J^{\text{glob}}({\boldsymbol{w}}_1,\ldots,{\boldsymbol{w}}_N)\triangleq\sum_{k=1}^N J_k({\boldsymbol{w}}_k)=\sum_{k=1}^N\sum_{m=1}^{j_k} c_{k_m}J_k({\boldsymbol{w}}_k).$$ We reformulate problem  in the following equivalent form by introducing the auxiliary variables <span>$\{{\boldsymbol{w}}_{k_m}\}$</span>:

\[eq: problem reformulation\] $$\begin{aligned}
    &\operatorname*{minimize}\limits_{{\boldsymbol{w}}_e}\quad\sum\limits_{k=1}^N\sum\limits_{m=1}^{j_k}{c_{k_m}J_{k}({\boldsymbol{w}}_{k_m})}\label{eq: cost function of the problem}\\
    &\operatorname*{subject\,to}\quad {\sum_{\ell_n\in{\mathcal{I}}_{e,p}}{\boldsymbol{D}}_{p\ell_n}{\boldsymbol{w}}_{\ell_n}+{\boldsymbol{b}}_p=\Zero,\quad p=1,\ldots,P,}\label{eq: constraint set 1}\\ 
    &\qquad\qquad\qquad{\boldsymbol{w}}_{k_1}=\ldots={\boldsymbol{w}}_{k_{j_k}},\quad {k=1,\ldots,N}\label{eq: constraint set 2}.
    \end{aligned}$$

In the following, we shall address the equality constraints  with a diffusion algorithm within each cluster of sub-nodes with the objective of reaching <span>an agreement</span> within each cluster (all sub-nodes converge to the same estimate). <span>Since the</span> diffusion strategy in a single-task network allows the agents to converge to the same limit point asymptotically for sufficiently small constant step-sizes when the network is strongly connected @sayed2014adaptation, we <span>allow the</span> sub-nodes in cluster ${\mathcal{C}}_k$ to be connected such that the resultant cluster ${\mathcal{C}}_k$ is strongly connected. This does not lead to a change in the network topology since each sub-node in a cluster refers to <span>the</span> same agent. We refer to the *virtual* set of neighboring sub-nodes of $k_m$ in ${\mathcal{C}}_k$ by <span>${\mathcal{N}}_{k_m}\!\!\cap{\mathcal{C}}_k$</span>.

The cost function in  can be written as: $$\sum\limits_{k=1}^N\sum\limits_{m=1}^{j_k}{c_{k_m}J_{k}({\boldsymbol{w}}_{k_m})}={\boldsymbol{w}}_e^\top{\boldsymbol{\cal{R}}}_{x,e}{\boldsymbol{w}}_e-2{\boldsymbol{r}}_{dx,e}^\top{\boldsymbol{w}}_e+{\boldsymbol{r}}_{d,e}^\top\One_{N_e\times1},$$ where the $N_e\times N_e$ block diagonal matrix ${\boldsymbol{\cal{R}}}_{x,e}$, the $N_e\times 1$ block column vector ${\boldsymbol{r}}_{dx,e}$, and the $N_e\times 1$ column vector ${\boldsymbol{r}}_{d,e}$ are given by: $$\begin{aligned}
    {\boldsymbol{\cal{R}}}_{x,e}&\triangleq{\text{diag}}\big\{{\boldsymbol{C}}_k\otimes{\boldsymbol{R}}_{x,k}\big\}_{k=1}^N,\label{eq: R_x e}\\
    {\boldsymbol{r}}_{dx,e}&\triangleq{\text{col}}\big\{{\boldsymbol{c}}_k\otimes{\boldsymbol{r}}_{dx,k}\big\}_{k=1}^N,\label{eq: r_dx e}\\
    {\boldsymbol{r}}_{d,e}&\triangleq{\text{col}}\big\{\sigma^2_{d,k}{\boldsymbol{c}}_k\big\}_{k=1}^N,\label{eq: r_d e}\end{aligned}$$ with ${\boldsymbol{C}}_k\triangleq{\text{diag}}\{c_{k_m}\}_{m=1}^{j_k}$ and ${\boldsymbol{c}}_k\triangleq{\text{col}}\{c_{k_m}\}_{m=1}^{j_k}$. The <span>equality</span> constraints in – can be written more compactly as: $${\boldsymbol{\cal{D}}}_e'{\boldsymbol{w}}_e+{\boldsymbol{b}}' = \Zero$$ with $$\label{eq: D'_e and b'}
    {\boldsymbol{\cal{D}}}'_e=\left[
    \begin{array}{lr}
    {\boldsymbol{\cal{D}}}_e\\
    {\boldsymbol{\cal{H}}}\end{array}
    \right],\quad
    {\boldsymbol{b}}'=\left[
    \begin{array}{lr}
    {\boldsymbol{b}}\\
    \Zero
    \end{array}
    \right],$$ where ${\boldsymbol{\cal{D}}}_e$ is a $P\times N_e$ block matrix constructed according to  which can be viewed as an expanded form of the $P\times N$ block matrix ${\boldsymbol{\cal{D}}}$, and ${\boldsymbol{\cal{H}}}$ is a $\sum_{k=1}^N(j_k-1)\times N_e$ block matrix constructed according to .

Using similar arguments as in Section \[subsec: Centralized solution\], we find that the solution of  is given by: $$\label{eq: extended closed form solution 1}
    {\boldsymbol{w}}^\star_e={\boldsymbol{w}}^o_e-{\boldsymbol{\cal{R}}}_{x,e}^{-1}{\boldsymbol{\cal{D}}}_e'^\top({\boldsymbol{\cal{D}}}_e'{\boldsymbol{\cal{R}}}_{x,e}^{-1}{\boldsymbol{\cal{D}}}_e'^\top)^{-1}({\boldsymbol{\cal{D}}}_e'{\boldsymbol{w}}^o_e+{\boldsymbol{b}}'){,}$$ where the $N_e\times 1$ block column vector ${\boldsymbol{w}}^o_e$ is given by: $${\boldsymbol{w}}^o_e\triangleq{\text{col}}\big\{\One_{{j_k}\times1}\otimes{\boldsymbol{w}}^o_k\big\}_{k=1}^N\label{eq: expanded w0}.$$ Let ${\boldsymbol{w}}^\star_k$ <span>denote</span> the $k$-th block of ${\boldsymbol{w}}^\star$ in . The optimum vector ${\boldsymbol{w}}^\star_e$ can be written alternatively as: $$\label{eq: extended closed form solution 2}
    {\boldsymbol{w}}^\star_e={\text{col}}\big\{\One_{{j_k}\times1}\otimes{\boldsymbol{w}}^\star_k\big\}_{k=1}^N.$$

Distributed solution {#subsec: Distributed solution}
--------------------

To solve problem  with distributed information access, we propose an iterative algorithm based on diffusion strategies and gradient-projection principle. First, we present the algorithm when the second order moments of the observations are assumed to be known by each sub-node. Although cluster ${\mathcal{C}}_k$ and agent $k$ refer to the same entity, we shall use the notion of cluster and sub-nodes in order to simplify the presentation.

Let ${\boldsymbol{w}}_{e,p}$ <span>denote</span> the $i_p\times 1$ block column vector given by ${\boldsymbol{w}}_{e,p}={\text{col}}\{{\boldsymbol{w}}_{\ell_n}\}_{\ell_n\in{\mathcal{I}}_{e,p}}$ where $i_p$ is the number of nodes involved in the $p$-th constraint. <span>Also, note that $i_p$ is the cardinality of ${\mathcal{I}}_{p}$ and ${\mathcal{I}}_{e,p}$. Let $\Omega_{p}$ denote the linear manifold corresponding to the $p$-th constraint in , namely, $\Omega_{p}\triangleq\{{\boldsymbol{\cal{D}}}_{p}{\boldsymbol{w}}_{e,p}+{\boldsymbol{b}}_p=\Zero\}$ where ${\boldsymbol{\cal{D}}}_{p}$ is a $1\times i_p$ block matrix.</span> Let ${\boldsymbol{w}}_{k_m}(i)$ be the estimate of ${\boldsymbol{w}}^\star_k$ at sub-node $k_m$ and time instant $i$. We assume that $k_m\in{\mathcal{I}}_{e,p}$. Following the <span>same line of reasoning as</span> @sayed2014diffusion in the single-task case, and extending the argument to our multitask problem, <span>we arrive at</span> the following diffusion algorithm consisting of three steps:

\[eq: diffusion iterates in the absence of gradient noise\] $$\begin{aligned}
        &{\boldsymbol{\psi}}_{k_m}(i+1)={\boldsymbol{w}}_{k_m}(i)+\mu\,c_{k_m}[{\boldsymbol{r}}_{dx,k}-{\boldsymbol{R}}_{x,k}{\boldsymbol{w}}_{k_m}(i)]\label{eq: step 1}\\
        &{\boldsymbol{\phi}}_{k_m}(i+1)=\sum_{k_n\in{{\mathcal{N}}_{k_m}\!\cap\,{\mathcal{C}}_k}}a_{k_n,k_m}{\boldsymbol{\psi}}_{k_n}(i+1)\label{eq: step 2}\\
        &{\boldsymbol{w}}_{k_m}(i+1)=\left[{\text{P}}_{\Omega_{p}}\big({\text{col}}\big\{{\boldsymbol{\phi}}_{\ell_n}(i+1)\big\}_{\ell_n\in{\mathcal{I}}_{e,p}}\big)\right]_{k_m}\label{eq: step 3}
    \end{aligned}$$

where $\mu>0$ is a constant step-size parameter, $[{\boldsymbol{x}}]_{k_m}$ is the block of ${\boldsymbol{x}}$ corresponding to <span>sub-node</span> $k_m$, <span>and ${\boldsymbol{w}}_{k_m}(0)={\boldsymbol{w}}_k(0)$ for all $m$.</span> In the first step , also called adaptation step, each sub-node $k_m$ in the network adapts its estimate ${\boldsymbol{w}}_{k_m}(i)$ via gradient descent on $c_{k_m}J_{k}(\cdot)$. This step results in the intermediate estimate ${\boldsymbol{\psi}}_{k_m}(i+1)$.

In the combination step , each sub-node $k_m$ combines its estimate ${\boldsymbol{\psi}}_{k_m}(i+1)$ with the estimates ${\boldsymbol{\psi}}_{k_n}(i+1)$ of its intra-cluster neighbors <span>${\mathcal{N}}_{k_m}\!\!\cap{\mathcal{C}}_k$</span>. This step results in the intermediate estimate ${\boldsymbol{\phi}}_{k_m}(i+1)$. The nonnegative coefficients $\{a_{k_n,k_m}\}$ are chosen to satisfy the following conditions: $$\begin{split}
    \label{eq: conditions on the combination coefficients}
    a_{k_n,k_m} \geq 0,&
    \sum_{k_m\in{{\mathcal{N}}_{k_n}\cap\,{\mathcal{C}}_k}}a_{k_n,k_m}=1,
    \sum_{k_n\in{{\mathcal{N}}_{k_m}\cap\,{\mathcal{C}}_k}}a_{k_n,k_m}=1,\\
    &\text{and } a_{k_n,k_m}=0 ~~\text{if}~~k_n\notin{{\mathcal{N}}_{k_m}\!\!\cap{\mathcal{C}}_k}.
\end{split}$$ Collecting these coefficients into a $j_k\times j_k$ matrix ${\boldsymbol{A}}_k$ for each cluster ${\mathcal{C}}_k$, it follows that ${\boldsymbol{A}}_k$ is doubly stochastic.

<span>Let $M_p$ denote the dimension of the vector ${\boldsymbol{w}}_{e,p}$, i.e., $M_p=\sum_{\ell_n\in{\mathcal{I}}_{e,p}}M_{\ell}$.</span> Before describing the third step, we recall that the projection of any point $\cblue{{\boldsymbol{y}}}$ onto $\Omega_{p}$ has the form: $$\label{eq: projection onto the local manifolds}
    {\text{P}}_{\Omega_{p}}\big(\cblue{{\boldsymbol{y}}}\big)={\boldsymbol{\cal{P}}}_{p}\,\cblue{{\boldsymbol{y}}}-{\boldsymbol{f}}_{p}$$ where $$\label{eq: cP r p}
    {\boldsymbol{\cal{P}}}_{p}\triangleq{\boldsymbol{I}}_{M_p}-{\boldsymbol{\cal{D}}}_{p}^\dagger{\boldsymbol{\cal{D}}}_{p}\qquad\text{and}\qquad {\boldsymbol{f}}_{p}\triangleq{\boldsymbol{\cal{D}}}_{p}^\dagger{\boldsymbol{b}}_p.$$ To evaluate the block $\big[{\text{P}}_{\Omega_{p}}(\cblue{{\boldsymbol{y}}})\big]_{k_m}$, even if sub-node $k_m$ is only in charge of estimating ${\boldsymbol{w}}_{k_m}$, it needs the entire vector $\cblue{{\boldsymbol{y}}}$, the $M_k\times M_p$ matrix $[{\boldsymbol{\cal{P}}}_{p}]_{k_m,\bullet}$, and the $M_k\times 1$ vector $[{\boldsymbol{f}}_{p}]_{k_m}$. In the projection step , each sub-node $k_m\in{\mathcal{I}}_{e,p}$ collects the intermediate estimates ${\boldsymbol{\phi}}_{\ell_n}(i+1)$ from all sub-nodes $\ell_n\in{\mathcal{I}}_{e,p}$ and combines them according to . This step results in the estimate ${\boldsymbol{w}}_{k_m}(i+1)$ of ${\boldsymbol{w}}^\star_k$ at sub-node $k_m$ and iteration $i+1$.

The adaptation step  requires knowledge of the second-order moments of data. Proceeding as in the centralized <span>case, and replacing the moments by instantaneous approximations,</span> we obtain algorithm  for solving  in a distributed way:

\[eq: multitask algorithm\] $$\begin{aligned}
            &{\boldsymbol{\psi}}_{k_m}(i+1)={\boldsymbol{w}}_{k_m}(i)+\mu\,c_{k_m}{\boldsymbol{x}}_k(i)[d_k(i)-{\boldsymbol{x}}_k^\top(i){\boldsymbol{w}}_{k_m}(i)],\label{eq: 1 adaptation step}\\
            &{\boldsymbol{\phi}}_{k_m}(i+1)= [{\boldsymbol{\cal{P}}}_{p}]_{k_m,\bullet}\cdot{\text{col}}\big\{{\boldsymbol{\psi}}_{\ell_n}(i+1)\big\}_{\ell_n\in{\mathcal{I}}_{e,p}}\hspace{-3mm}-[{\boldsymbol{f}}_{p}]_{k_m},\label{eq: 3 projection step}\\
            &{\boldsymbol{w}}_{k_m}(i+1)=\sum_{k_n\in{{\mathcal{N}}_{k_m}\cap\,{\mathcal{C}}_k}}a_{k_n,k_m}{\boldsymbol{\phi}}_{k_n}(i+1).\label{eq: 2 combination step}
        \end{aligned}$$

Compared to , observe in  that each sub-node $k_m$ projects its intermediate estimate before combining it. We recommend this permutation since it allows, with the appropriate parameter settings described below, to reduce the algorithm complexity without compromising its convergence, as confirmed in the sequel. Consider any agent $k$. By setting factors $c_{k_m}$ to $\frac{1}{j_k}$ for all $m=1,\ldots,j_k$, and combining the intermediate estimate ${\boldsymbol{\phi}}_{k_m}(i+1)$ at each sub-node $k_m$ with the estimates of all other sub-nodes available at node $k$ using uniform combination coefficients, i.e., ${\mathcal{N}}_{k_m}\cap{\mathcal{C}}_k={\mathcal{C}}_k$ and $a_{k_n,k_m}=\frac{1}{j_k}$ for $n=1,\ldots,j_k$, and  reduce to: $$\begin{aligned}
    &{\boldsymbol{\psi}}_{k_m}(i+1)={\boldsymbol{\psi}}_k(i+1), \quad \text{for } m=1,\ldots,j_k,\label{eq: 36}\\
    &{\boldsymbol{w}}_{k_m}(i+1)={\boldsymbol{w}}_k(i+1), \quad \text{for } m=1,\ldots,j_k,\end{aligned}$$ where ${\boldsymbol{\psi}}_k(i+1)$ and ${\boldsymbol{w}}_k(i+1)$ are given by: $$\begin{aligned}
    &{\boldsymbol{\psi}}_k(i+1)={\boldsymbol{w}}_k(i)+\frac{\mu}{j_k}{\boldsymbol{x}}_k(i)\big[d_k(i)-{\boldsymbol{x}}_k^\top(i){\boldsymbol{w}}_k(i)\big],\\
    &{\boldsymbol{w}}_k(i+1)=\frac{1}{j_k}\cblue{\sum_{m=1}^{j_k}{\boldsymbol{\phi}}_{k_m}(i+1)}.\label{eq: 39}\end{aligned}$$

Performance analysis Relative to ${\boldsymbol{w}}_e^o$ {#sec: Performance analysis I}
=======================================================

Network error vector recursion {#subsec: network error vector recursion}
------------------------------

We shall first study the stochastic behavior of algorithm  with respect to the optimal parameter vector ${\boldsymbol{w}}_e^o$. We introduce the error vector ${\widetilde{\boldsymbol{w}}}_{k_m}(i)\triangleq{\boldsymbol{w}}^o_k-{\boldsymbol{w}}_{k_m}(i)$ and the intermediate error vectors ${\widetilde{\boldsymbol{\psi}}}_{k_m}(i)\triangleq{\boldsymbol{w}}^o_k-{\boldsymbol{\psi}}_{k_m}(i)$ and ${\widetilde{\boldsymbol{\phi}}}_{k_m}(i)\triangleq{\boldsymbol{w}}^o_k-{\boldsymbol{\phi}}_{k_m}(i)$. We further introduce the $N_e\times 1$ block network error vector: $$\label{eq: definition of wt_e}
    {\widetilde{\boldsymbol{w}}}_e(i)\triangleq{\text{col}}\left\{{\text{col}}\big\{{\widetilde{\boldsymbol{w}}}_{k_m}(i)\big\}_{m=1}^{{j_k}}\right\}_{k=1}^N.$$ <span>Let $M_e$ denote the length of the network error vector ${\widetilde{\boldsymbol{w}}}_e(i)$, that is, $M_e\triangleq\sum_{k=1}^Nj_kM_k$.</span> Using the linear model , the estimation error in the adaptation step  can be written as: $$\label{eq: estimation error 1}
    d_k(i)-{\boldsymbol{x}}_k^\top(i){\boldsymbol{w}}_{k_m}(i)={\boldsymbol{x}}_k^{\top}(i){\widetilde{\boldsymbol{w}}}_{k_m}(i)+z_k(i).$$ Subtracting ${\boldsymbol{w}}^o_k$ from both sides of the adaptation step , using , and collecting the error vectors ${\widetilde{\boldsymbol{\psi}}}_{k_m}(i)$ into the $N_e\times 1$ block vector ${\widetilde{\boldsymbol{\psi}}}_e(i)\triangleq{\text{col}}\left\{{\text{col}}\big\{{\widetilde{\boldsymbol{\psi}}}_{k_m}(i)\big\}_{m=1}^{{j_k}}\right\}_{k=1}^N$, we obtain: $$\label{eq: bpsit(i+1)}
    {\widetilde{\boldsymbol{\psi}}}_e(i+1)=\big[{\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}(i)\big]{\widetilde{\boldsymbol{w}}}_e(i)-\mu\,{\boldsymbol{p}}_{zx,e}(i),$$ where $$\begin{aligned}
    &{\boldsymbol{\cal{R}}}_{x,e}(i)\triangleq{\text{diag}}\Big\{{\boldsymbol{C}}_k\otimes{\boldsymbol{x}}_k(i){\boldsymbol{x}}^\top_k(i)\Big\}_{k=1}^N \label{eq: R x},\\
    &{\boldsymbol{p}}_{zx,e}(i)\triangleq{\text{col}}\Big\{{\boldsymbol{c}}_k\otimes {\boldsymbol{x}}_k(i)z_k(i)\Big\}_{k=1}^N \label{eq: p zx}.\end{aligned}$$ <span>Projecting ${\boldsymbol{\psi}}_e(i+1)$ onto the sets $\Omega_{p}$ in , we obtain <span>from </span>: $$\label{eq: recursion w}
    {\boldsymbol{\phi}}_e(i+1)={\boldsymbol{\cal{P}}}_e{\boldsymbol{\psi}}_e(i+1)-{\boldsymbol{f}}_e,$$ where $$\begin{aligned}
        {\boldsymbol{\psi}}_e(i)\triangleq{\text{col}}\Big\{{\text{col}}\big\{{\boldsymbol{\psi}}_{k_m}(i)\big\}_{m=1}^{j_k}\Big\}_{k=1}^N,\\
    \quad {\boldsymbol{\phi}}_e(i)\triangleq{\text{col}}\Big\{{\text{col}}\big\{{\boldsymbol{\phi}}_{k_m}(i)\big\}_{m=1}^{j_k}\Big\}_{k=1}^N, \end{aligned}$$ ${\boldsymbol{\cal{P}}}_e$ is an $M_e\times M_e$ orthogonal projection matrix, and ${\boldsymbol{f}}_e$ is an $M_e\times 1$ vector given by (see Appendix A): $$\begin{aligned}
    {\boldsymbol{\cal{P}}}_e&\triangleq{\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{D}}}_e^\dagger{\boldsymbol{\cal{D}}}_e={\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{D}}}_e^\top({\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top)^{-1}{\boldsymbol{\cal{D}}}_e\label{eq: cP e}\\
    {\boldsymbol{f}}_e&\triangleq{\boldsymbol{\cal{D}}}_e^\dagger{\boldsymbol{b}}={\boldsymbol{\cal{D}}}_e^\top({\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top)^{-1}{\boldsymbol{b}}.\label{eq: boldf e}\end{aligned}$$ Subtracting ${\boldsymbol{w}}^o_e$ in  from both sides of recursion , we obtain: $$\begin{aligned}
    {\widetilde{\boldsymbol{\phi}}}_e(i+1)&\triangleq{\text{col}}\Big\{{\text{col}}\big\{{\widetilde{\boldsymbol{\phi}}}_{k_m}(i+1)\big\}_{m=1}^{j_k}\Big\}_{k=1}^N\notag\\
    &={\boldsymbol{\cal{P}}}_e{\widetilde{\boldsymbol{\psi}}}_e(i+1)+\big({\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{P}}}_e\big){\boldsymbol{w}}^o_e+{\boldsymbol{f}}_e.\end{aligned}$$ Subtracting ${\boldsymbol{w}}^o_k$ from both sides of the combination step  and using , we obtain that the network error vector for the diffusion strategy  evolves according to the following recursion: $$\label{eq: weight error vector recursion 0}
    \boxed{
    \begin{aligned}
    &{\widetilde{\boldsymbol{w}}}_e(i+1)={\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e\big[{\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}(i)\big]{\widetilde{\boldsymbol{w}}}_e(i)-\\ 
    &\qquad\mu{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\boldsymbol{p}}_{zx,e}(i)+{\boldsymbol{\cal{A}}}^\top({\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{P}}}_e){\boldsymbol{w}}^o_e+{\boldsymbol{\cal{A}}}^\top{\boldsymbol{f}}_e,
    \end{aligned}
    }$$ where ${\boldsymbol{\cal{A}}}\triangleq{\text{diag}}\{{\boldsymbol{A}}_k\otimes{\boldsymbol{I}}_{M_k}\}_{k=1}^N$.</span> Before proceeding, let us introduce the following assumption on the regression data.

\[assump: independent regressors\] <span>*(Independent regressors)*</span> The regression vectors ${\boldsymbol{x}}_k(i)$ arise from a zero-mean random process that is temporally white and spatially independent.

Under this assumption, ${\boldsymbol{x}}_k(i)$ is independent of ${\boldsymbol{w}}_{\ell_m}(j)$ for $i\geq j$ and for all $\ell_m$. This assumption is commonly used in the adaptive filtering literature since it helps simplify the analysis, and the performance results obtained under this assumption match well the actual performance of stand-alone filters for sufficiently small step-sizes @sayed2011adaptive.

Mean behavior analysis {#subsec: Mean behavior analysis I}
----------------------

Recursion  can be rewritten in a more compact form: $$\label{eq: weight error vector recursion 1}
    {\widetilde{\boldsymbol{w}}}_e(i+1)={\boldsymbol{\cal{B}}}(i){\widetilde{\boldsymbol{w}}}_e(i)-\mu{\boldsymbol{g}}(i)+{\boldsymbol{r}}{,}$$ where we introduced the following notations: <span>$$\begin{aligned}
    {\boldsymbol{\cal{B}}}(i)&\triangleq{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e\big[{\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}(i)\big],\label{eq: B(i)}\\
    {\boldsymbol{g}}(i)&\triangleq{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\boldsymbol{p}}_{zx,e}(i),\label{eq: g(i)}\\
    {\boldsymbol{r}}&\triangleq{\boldsymbol{\cal{A}}}^\top({\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{P}}}_e){\boldsymbol{w}}^o_e+{\boldsymbol{\cal{A}}}^\top{\boldsymbol{f}}_e.\label{eq: br}\end{aligned}$$</span> Taking the expectation of both sides of recursion , using Assumption \[assump: independent regressors\], and ${\mathbb{E}}\,{\boldsymbol{g}}(i)=\Zero$, we find that the mean error vector evolves according to the recursion: $$\label{eq: mean error recursion}
    {\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(i+1)={\boldsymbol{\cal{B}}}\,{\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(i)+{\boldsymbol{r}},$$ Recursion  converges as $i\rightarrow\infty$ if the matrix ${\boldsymbol{\cal{B}}}$ is stable. If we let $i\rightarrow\infty$ on both sides of , we find that the asymptotic mean bias is given by: $$\label{eq: bias}
    {\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(\infty)=\lim_{i\rightarrow\infty}{\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(i)=({\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{B}}})^{-1}{\boldsymbol{r}}.$$ <span>It is known that any induced matrix norm is lower bounded by the spectral radius of the matrix. We can thus write in terms of the $2$-induced matrix norm: $$\rho({\boldsymbol{\cal{B}}})
        \leq\|{\boldsymbol{\cal{A}}}^\top\|_2\cdot\|{\boldsymbol{\cal{P}}}_e\|_2\cdot\|{\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}\|_2,$$ where we used the sub-multiplicative property of the $2$-induced norm. Since ${\boldsymbol{\cal{P}}}_e$ is an orthogonal projection matrix and ${\boldsymbol{\cal{A}}}^\top$ is a doubly-stochastic matrix, their $2$-induced norms are equal to one. Since the matrix ${\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}$ is a symmetric block diagonal matrix, its $2$-induced norm agrees with its spectral radius: $$\begin{split}
    \|{\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}\|_2&=\rho({\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e})\\
        &=\max_{1\leq k \leq N}\max_{1\leq m\leq j_k}\rho({\boldsymbol{I}}_{M_k}-\mu\, c_{k_m}{\boldsymbol{R}}_{x,k}).
\end{split}$$ </span> Thus, the stability of ${\boldsymbol{\cal{B}}}$ is ensured by choosing $\mu$ such that: $$\label{eq: stability conditions}
    0<\mu<\frac{2}{c_{k,\max}\cdot\lambda_{\max}({\boldsymbol{R}}_{x,k})},\quad\forall k=1,\ldots,N.$$ where $c_{k,\max}\triangleq\max\limits_{ 1\leq m\leq j_k}c_{k_m}$. We observe that when ${\boldsymbol{w}}^\star_e={\boldsymbol{w}}^o_e$, i.e., perfect model scenario where ${\boldsymbol{w}}^o$ satisfies the linear equality constraints, the bias reduces to $\Zero$.

Mean-square-error behavior analysis
-----------------------------------

<span>To perform the mean-square-error analysis, we shall use the block Kronecker product <span>operator @Koning1991nlockkronecker</span> and the block vectorization operator ${\text{bvec}}(\cdot)$. As explained in @sayed2014adaptation, these block operators preserve the locality of the blocks in the original matrix arguments. To analyze the convergence in mean-square-error sense, we consider the variance of the weight error vector ${\widetilde{\boldsymbol{w}}}_e(i)$<span>,</span> weighted by any positive-definite matrix ${\boldsymbol{\Sigma}}$, that is, ${\mathbb{E}}\,\|{\widetilde{\boldsymbol{w}}}_e(i)\|^2_{{\boldsymbol{\Sigma}}}$, where $\|{\widetilde{\boldsymbol{w}}}_e(i)\|^2_{{\boldsymbol{\Sigma}}}\triangleq{\widetilde{\boldsymbol{w}}}_e^\top(i){\boldsymbol{\Sigma}}{\widetilde{\boldsymbol{w}}}_e(i)$. The freedom in selecting ${\boldsymbol{\Sigma}}$ allows us to extract various types of information about the network and the sub-nodes. From  and Assumption \[assump: independent regressors\], we obtain:</span> $$\begin{split}
    \label{eq: variance relation 1}
    {\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e(i+1)\|^2_{{\boldsymbol{\Sigma}}}\}&={\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e(i)\|^2_{{\boldsymbol{\Sigma}}'}\}+\mu^2{\mathbb{E}}\{\|{\boldsymbol{g}}(i)\|^2_{{\boldsymbol{\Sigma}}}\}+\\
    &\qquad\|{\boldsymbol{r}}\|^2_{{\boldsymbol{\Sigma}}}+2{\boldsymbol{r}}^\top{\boldsymbol{\Sigma}}{\boldsymbol{\cal{B}}}{\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(i),
\end{split}$$ where matrix ${\boldsymbol{\Sigma}}'$ is given by: $$\label{eq: sigma'}
{\boldsymbol{\Sigma}}'\triangleq{\mathbb{E}}\{{\boldsymbol{\cal{B}}}^\top(i){\boldsymbol{\Sigma}}{\boldsymbol{\cal{B}}}(i)\}.$$

Let ${\boldsymbol{\sigma}}$ denotes the $M_e^2\times 1$ vector representation of ${\boldsymbol{\Sigma}}$ that is obtained by the block vectorization operator, namely, ${\boldsymbol{\sigma}}\triangleq{\text{bvec}}({\boldsymbol{\Sigma}})$. In the sequel, it will be more convenient to work with ${\boldsymbol{\sigma}}$ than with ${\boldsymbol{\Sigma}}$ itself. We will use the notations $\|{\boldsymbol{x}}\|^2_{{\boldsymbol{\Sigma}}}$ and $\|{\boldsymbol{x}}\|^2_{{\boldsymbol{\sigma}}}$ to denote the same quantity ${\boldsymbol{x}}^\top{\boldsymbol{\Sigma}}{\boldsymbol{x}}$. Let ${\boldsymbol{\sigma}}'={\text{bvec}}({\boldsymbol{\Sigma}}')$. Using the property ${\text{bvec}}({\boldsymbol{U}}{\boldsymbol{\Sigma}}{\boldsymbol{W}})=({\boldsymbol{W}}^\top\otimes_b{\boldsymbol{U}}){\boldsymbol{\sigma}}$, the vector ${\boldsymbol{\sigma}}'$ can be related to ${\boldsymbol{\sigma}}$: $${\boldsymbol{\sigma}}'={\boldsymbol{\cal{F}}}{\boldsymbol{\sigma}},$$ where ${\boldsymbol{\cal{F}}}$ is an $M_e^2\times M_e^2$ matrix given by: $$\label{eq: matrix F}
    {\boldsymbol{\cal{F}}}\triangleq{\mathbb{E}}\{{\boldsymbol{\cal{B}}}^\top(i)\otimes_b{\boldsymbol{\cal{B}}}^\top(i)\}.$$ The evaluation of the matrix ${\boldsymbol{\cal{F}}}$ requires knowledge of the <span>fourth-order</span> moments of the regression vectors.

The second term on the RHS of relation  can be written as: $$\begin{aligned}
    \mu^2{\mathbb{E}}\{\|{\boldsymbol{g}}(i)\|^2_{{\boldsymbol{\Sigma}}}\}&=\mu^2{\mathbb{E}}\{{\boldsymbol{g}}^\top(i){\boldsymbol{\Sigma}}{\boldsymbol{g}}(i)\}\notag\\
    &=\mu^2{\text{tr}}({\boldsymbol{\Sigma}}{\boldsymbol{\cal{G}}})=\mu^2\big[{\text{bvec}}({\boldsymbol{\cal{G}}}^\top)\big]^\top{\boldsymbol{\sigma}},\end{aligned}$$ where ${\boldsymbol{\cal{G}}}$ is the $M_e\times M_e$ matrix given by: <span>$${\boldsymbol{\cal{G}}}\triangleq{\mathbb{E}}\{{\boldsymbol{g}}(i){\boldsymbol{g}}^\top(i)\}={\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\text{diag}}\big\{{\boldsymbol{c}}_k{\boldsymbol{c}}_k^\top\otimes\sigma^2_{z,k}{\boldsymbol{R}}_{x,k}\big\}_{k=1}^N{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}.$$ </span> <span>Similarly</span>, the third term on the RHS of relation  can be written as: $$\|{\boldsymbol{r}}\|^2_{{\boldsymbol{\Sigma}}}=\big[{\text{bvec}}({\boldsymbol{r}}{\boldsymbol{r}}^\top)\big]^\top{\boldsymbol{\sigma}},$$ <span>and</span> the fourth term can be written as: $$\begin{aligned}
    2{\boldsymbol{r}}^\top{\boldsymbol{\Sigma}}{\boldsymbol{\cal{B}}}{\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(i)&=2{\text{tr}}({\boldsymbol{r}}^\top{\boldsymbol{\Sigma}}{\boldsymbol{\cal{B}}}{\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(i))\notag\\
    &=2\big[{\text{bvec}}({\boldsymbol{r}}{\mathbb{E}}\{{\widetilde{\boldsymbol{w}}}_e^\top(i)\}{\boldsymbol{\cal{B}}}^\top)\big]^\top{\boldsymbol{\sigma}}.\end{aligned}$$ Let us define the $M_e\times M_e$ time dependent matrix ${\boldsymbol{\cal{Y}}}(i)$ given by: $$\label{eq: Y(i)}
    {\boldsymbol{\cal{Y}}}(i)\triangleq\mu^2{\boldsymbol{\cal{G}}}^\top+{\boldsymbol{r}}{\boldsymbol{r}}^\top+2{\boldsymbol{r}}{\mathbb{E}}\{{\widetilde{\boldsymbol{w}}}_e(i)\}^\top{\boldsymbol{\cal{B}}}^\top.$$ <span>Then</span>, the variance relation  can be expressed as: $$\label{eq: variance relation 2}
    {\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e(i+1)\|^2_{{\boldsymbol{\sigma}}}\}={\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e(i)\|^2_{{\boldsymbol{\cal{F}}}{\boldsymbol{\sigma}}}\}+\big[{\text{bvec}}({\boldsymbol{\cal{Y}}}(i))\big]^\top{\boldsymbol{\sigma}}.$$

Provided that ${\boldsymbol{\cal{F}}}$ is stable, recursion  is stable. Since ${\boldsymbol{\cal{G}}}$, ${\boldsymbol{r}}$, ${\boldsymbol{\cal{B}}}$, ${\boldsymbol{\sigma}}$, and $\mu$ are constant and finite terms, the boundedness of $\big[{\text{bvec}}({\boldsymbol{\cal{Y}}}(i))\big]^\top{\boldsymbol{\sigma}}$ depends on ${\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(i)$ being bounded. We know from  that ${\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(i)$ is bounded because  is a <span>Bounded-Input Bounded-Output</span> (BIBO) stable recursion with a bounded driving term ${\boldsymbol{r}}$. It follows that $\big[{\text{bvec}}({\boldsymbol{\cal{Y}}}(i))\big]^\top{\boldsymbol{\sigma}}$ is uniformly bounded. As a result,

Following similar arguments as in @chen2014multitask [@nassif2016multitask; @chen2014diffusion] and doing the required adjustments, we find that the weighted variance ${\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e(i+1)\|^2_{{\boldsymbol{\sigma}}}\}$ evolves according to the following recursion: $$\begin{split}
    \label{eq: MSD transient curve}
    {\mathbb{E}}&\{\|{\widetilde{\boldsymbol{w}}}_e(i+1)\|^2_{{\boldsymbol{\sigma}}}\}={\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e(i)\|^2_{{\boldsymbol{\sigma}}}\}+\\
    &\big[{\text{bvec}}({\mathbb{E}}\{{\widetilde{\boldsymbol{w}}}_e(0){\widetilde{\boldsymbol{w}}}_e^\top(0)\})\big]^\top({\boldsymbol{\cal{F}}}-{\boldsymbol{I}}_{M_e^2}){\boldsymbol{\cal{F}}}^{i}{\boldsymbol{\sigma}}+\\
    &\big[{\text{bvec}}({\boldsymbol{\cal{Y}}}(i))\big]^\top{\boldsymbol{\sigma}}+{\boldsymbol{\Gamma}}(i){\boldsymbol{\sigma}},
    \end{split}$$ where ${\widetilde{\boldsymbol{w}}}_e(0)$ is the initial condition and ${\boldsymbol{\Gamma}}(i+1)$ is a $1\times M_e^2$ vector that can be evaluated from ${\boldsymbol{\Gamma}}(i)$ according to: $${\boldsymbol{\Gamma}}(i+1)={\boldsymbol{\Gamma}}(i){\boldsymbol{\cal{F}}}+\big[{\text{bvec}}({\boldsymbol{\cal{Y}}}(i))\big]^\top({\boldsymbol{\cal{F}}}-{\boldsymbol{I}}_{M_e^2}),$$ with ${\boldsymbol{\Gamma}}(0)=\Zero$.

The steady-state network performance with metric ${\boldsymbol{\sigma}}_{ss}$ is defined as: $$\label{eq: zeta star}
    \zeta^\star=\lim_{i\rightarrow\infty}{\mathbb{E}}\|{\widetilde{\boldsymbol{w}}}_e(i)\|^2_{{\boldsymbol{\sigma}}_{ss}}.$$ If the matrix ${\boldsymbol{\cal{F}}}$ is stable, from the recursive expression , we obtain as $i\rightarrow\infty$: $$\label{eq: steady-state variance}
    \lim_{i\rightarrow\infty}{\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e(i)\|^2_{({\boldsymbol{I}}_{M_e^2}-{\boldsymbol{\cal{F}}}){\boldsymbol{\sigma}}}\}=[{\text{bvec}}({\boldsymbol{\cal{Y}}}(\infty))]^\top{\boldsymbol{\sigma}},$$ where, from  and , we have: $$\label{eq: Yinf}
{\boldsymbol{\cal{Y}}}(\infty)=\mu^2{\boldsymbol{\cal{G}}}^\top+{\boldsymbol{r}}{\boldsymbol{r}}^\top+2{\boldsymbol{r}}{\mathbb{E}}\{{\widetilde{\boldsymbol{w}}}_e(\infty)\}^\top{\boldsymbol{\cal{B}}}^\top.$$ To obtain , we replace ${\boldsymbol{\sigma}}$ in  by $({\boldsymbol{I}}_{M_e^2}-{\boldsymbol{\cal{F}}})^{-1}{\boldsymbol{\sigma}}_{ss}$. The theoretical findings , , , and  allow us to predict the behavior in the mean and in the mean-square-error sense of the stochastic algorithm  w.r.t. the parameter vector ${\boldsymbol{w}}_e^o$. <span>Note that, the network MSD w.r.t. ${\boldsymbol{w}}^o_e$ given by: $$\text{MSD}_{\text{net}}(i)\triangleq\frac{1}{N}\sum_{k=1}^N\left(\frac{1}{j_k}\sum_{m=1}^{j_k}{\mathbb{E}}\|{\widetilde{\boldsymbol{w}}}_{k_m}(i)\|^2\right),$$ can be obtained by setting ${\boldsymbol{\Sigma}}=\frac{1}{N}\,{\text{diag}}\left\{\frac{1}{j_k}{\boldsymbol{I}}_{j_k\cdot M_k}\right\}_{k=1}^N$. </span>

Performance Analysis Relative to ${\boldsymbol{w}}^\star_e$ {#sec: Performance analysis II}
===========================================================

We shall now study the convergence behavior of algorithm  toward the solution ${\boldsymbol{w}}^\star_e$ of the optimization problem with constraints . To this end, we introduce for each sub-node $k_m$ the weight error vector: $${\widetilde{\boldsymbol{w}}}'_{k_m}(i)\triangleq{\boldsymbol{w}}^\star_k-{\boldsymbol{w}}_{k_m}(i),\qquad$$ and the $N_e\times 1$ network block error vector: $$\label{eq: definition of wt'_e}
    {\widetilde{\boldsymbol{w}}}_e'(i)\triangleq{\text{col}}\Big\{{\text{col}}\big\{{\widetilde{\boldsymbol{w}}}'_{k_m}(i)\big\}_{m=1}^{{j_k}}\Big\}_{k=1}^N$$ We note that the behavior of algorithm  with respect to ${\boldsymbol{w}}_e^\star$ can be deduced from its behavior with respect to ${\boldsymbol{w}}_e^o$ using the following relation: $$\label{eq: relation between wt and wt'}
    {\widetilde{\boldsymbol{w}}}_e'(i+1)={\widetilde{\boldsymbol{w}}}_e(i+1)-{\boldsymbol{w}}^\delta_e.$$ where ${\boldsymbol{w}}^\delta_e\triangleq{\boldsymbol{w}}^o_e-{\boldsymbol{w}}^\star_e$. Using with , the fact that ${\boldsymbol{w}}^\star_e$ verifies the constraints $\{{\boldsymbol{\cal{D}}}_e{\boldsymbol{w}}_e+{\boldsymbol{b}}=\Zero\}$, namely, $${\boldsymbol{\cal{P}}}_e{\boldsymbol{w}}^\star_e-{\boldsymbol{f}}_e={\boldsymbol{w}}^\star_e,$$ and the fact that ${\boldsymbol{\cal{A}}}^\top\One=\One$, we obtain that ${\widetilde{\boldsymbol{w}}}_e'(i+1)$ evolves according to the following recursion: <span>$$\label{eq: weight error vector recursion 0'}
    \boxed{
    \begin{aligned}
    &{\widetilde{\boldsymbol{w}}}_e'(i+1)={\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e\big[{\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}(i)\big]{\widetilde{\boldsymbol{w}}}_e'(i)-\\
    &\qquad\mu{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\boldsymbol{p}}_{zx,e}(i)-\mu{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{R}}}_{x,e}(i){\boldsymbol{w}}^\delta_e.
    \end{aligned}}$$</span> Taking the expectation of both sides of recursion , using Assumption \[assump: independent regressors\], and ${\mathbb{E}}\,{\boldsymbol{p}}_{zx,e}(i)=\Zero$, the mean error vector evolves according to: $$\label{eq: mean error recursion'}
    {\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e'(i+1)={\boldsymbol{\cal{B}}}\,{\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e'(i)-\mu{\boldsymbol{r}}',$$ where ${\boldsymbol{\cal{B}}}$ is given by  and <span>$$\label{eq: r'}
    {\boldsymbol{r}}'\triangleq{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{R}}}_{x,e}{\boldsymbol{w}}^\delta_e.$$</span> Using arguments similar to subsection \[subsec: Mean behavior analysis I\], we find that the multitask diffusion algorithm  is stable in the mean if the step-size is chosen such that the matrix ${\boldsymbol{\cal{B}}}$ is stable. The asymptotic mean bias is given by: $$\label{eq: bias 2}
    \lim_{i\rightarrow\infty}{\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e'(i)=-\mu[{\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{B}}}]^{-1}{\boldsymbol{r}}'.$$ Note that the bias depends on the step-size $\mu$ and the vector ${\boldsymbol{w}}^\delta_e={\boldsymbol{w}}^o_e-{\boldsymbol{w}}^\star_e$. In the next section, we shall <span>illustrate</span> with simulation results that $\lim_{i\rightarrow\infty}\|{\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e'(i)\|^2$ is on the order of $\mu^2$. The bias is $\Zero$ in two cases: 1) in the perfect model scenario where ${\boldsymbol{w}}^o_k$ satisfy the constraints (${\boldsymbol{w}}_e^\delta=\Zero$); 2) if each agent is involved in at most one constraint (${\boldsymbol{\cal{D}}}_e={\boldsymbol{\cal{D}}}'_e={\boldsymbol{\cal{D}}}$). In this second case, consider  and observe that ${\boldsymbol{\cal{A}}}={\boldsymbol{I}}_{M_e}$. Replacing ${\boldsymbol{w}}_e^\delta$ by its expression obtained from , and ${\boldsymbol{\cal{P}}}_e$ by , yields ${\boldsymbol{r}}' =\Zero$.

To obtain the behavior of algorithm  toward ${\boldsymbol{w}}^\star_e$ in the mean-square sense, we use  to write: $$\begin{split}
    \label{eq: relation between the variances}
    &{\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e'(i+1)\|^2_{{\boldsymbol{\Sigma}}}\}={\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e(i+1)\|^2_{{\boldsymbol{\Sigma}}}\}-\\
    &\qquad2\,{\mathbb{E}}\{{\widetilde{\boldsymbol{w}}}_e^\top(i+1)\}{\boldsymbol{\Sigma}}{\boldsymbol{w}}_e^\delta+\|{\boldsymbol{w}}^\delta_e\|^2_{{\boldsymbol{\Sigma}}}.
    \end{split}$$ The transient and steady-state behaviors of ${\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e'(i)\|^2_{{\boldsymbol{\Sigma}}}\}$ can be derived from the models derived for ${\widetilde{\boldsymbol{w}}}_e(i)$ in the mean and mean-square sense. We shall show with simulation results that the steady-state $\lim_{i\rightarrow\infty}{\mathbb{E}}\,\|{\widetilde{\boldsymbol{w}}}_e'(i)\|^2$ is <span>on</span> the order of $\mu$. We observed experimentally that modeling the behavior of ${\mathbb{E}}\{\|{\widetilde{\boldsymbol{w}}}_e'(i)\|^2_{{\boldsymbol{\Sigma}}}\}$ accurately needs the exact expression of ${\boldsymbol{\cal{F}}}$. <span>For zero-mean real valued regressors with $M_k=M_0$ $\forall~k$, the evaluation of ${\boldsymbol{\cal{F}}}$ leads to (see Appendix B): $$\begin{split}
&{\boldsymbol{\cal{F}}}={\boldsymbol{\cal{B}}}^\top\otimes_b{\boldsymbol{\cal{B}}}^\top+\\
&\mu^2\sum_{k=1}^N\Big[\left({\mathcal{S}}_k^\top({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k})\otimes_b{\mathcal{S}}_k({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k})\right)+\\
&\qquad\left({\mathcal{S}}_k^\top\otimes_b\left({\mathcal{S}}_k({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k})\right)\right)\\
&\left({\boldsymbol{I}}_{N_e^2}\otimes{\text{vec}}({\boldsymbol{I}}_{M_0})\otimes[{\text{vec}}({\boldsymbol{R}}_{x,k})]^\top\right)\Big]({\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}\otimes_b{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}),
\end{split}$$ where ${\mathcal{S}}_k$ is the $N\times N$ block diagonal matrix whose $(k,k)$-th block is equal to ${\boldsymbol{C}}_k\otimes{\boldsymbol{I}}_{M_0}$. </span>

Simulation results {#sec: Simulation results}
==================

<span>Throughout this section, the factors $c_{k_m}$ were set to $\frac{1}{j_k}$, and ${\mathcal{N}}_{k_m}\cap{\mathcal{C}}_k={\mathcal{C}}_k$ for all $m$. We run algorithm  with uniform combination coefficients $a_{k_n,k_m}=\frac{1}{j_k}$ for all $n$.</span>

Theoretical model validation
----------------------------

We considered a network consisting of $15$ agents with the topology shown in Fig. \[fig: experimental setup\]. The regression vectors ${\boldsymbol{x}}_k(i)$ were $2\times 1$ zero-mean Gaussian distributed with covariance matrices ${\boldsymbol{R}}_{x,k}=\sigma^2_{x,k}{\boldsymbol{I}}_2$. The noises $z_k(i)$ were zero-mean i.i.d. Gaussian random variables, independent of any other signal with variances $\sigma^2_{z,k}$. The variances $\sigma^2_{x,k}$ and $\sigma^2_{z,k}$ are shown in Fig. \[fig: experimental setup\]. We randomly sampled $9$ linear equality constraints of the form: $$\label{eq:constraints-ref}
    \sum_{\ell\in{\mathcal{I}}_p}d_{p\ell}{\boldsymbol{w}}_{\ell}=b_p\cdot\One_{2\times 1},$$ where the scalars $d_{p\ell}$ and $b_p$ were randomly chosen from the set $\{-3,-2,-1,1,2,3\}$. We used a constant step-size $\mu=0.025$ for all agents. The results were averaged over 200 Monte-Carlo runs.

\[t\]

![image](figure3.pdf) ![image](figure4.pdf)

First, we considered the case of a perfect model scenario where the observation parameter vector ${\boldsymbol{w}}^o$ satisfies the equality constraints, i.e., ${\boldsymbol{w}}^\star={\boldsymbol{w}}^o$. In Fig. \[fig: MSD comparisons\] (left), we compare three algorithms: the non-cooperative LMS algorithm (obtained from  by setting ${\boldsymbol{\cal{P}}}={\boldsymbol{I}}_{M}$ and ${\boldsymbol{f}}=\Zero$), the centralized CLMS algorithm  which assumes that the constraints are available at the fusion center, and algorithm . For each algorithm, we report the theoretical transient MSD, the theoretical steady-state MSD, and the simulated MSD. We observe that the simulation results match well the actual performance. Furthermore, the network MSD is improved by promoting relationships between tasks. Finally, our algorithm performs well compared to the centralized solution.

<span>Next,</span> we perturbed the optimum parameter vector ${\boldsymbol{w}}^o$ as follows: $$\label{eq: optimum parameter vector perturbation}
    {\boldsymbol{w}}^o_\text{pert}={\boldsymbol{w}}^o+{\boldsymbol{u}}^o,$$ so ${\boldsymbol{w}}^o_\text{pert}$ does not satisfy the constraints . The entries of ${\boldsymbol{u}}^o$ were sampled from Gaussian distribution ${\mathcal{N}}(0,\sigma^2)$. We evaluated algorithm  on $6$ different setups characterized by $\sigma\in\{0,0.01,0.05,0.1,0.2,0.5,1\}$. The theoretical and simulated learning curves with respect to ${\boldsymbol{w}}^o_e$ and ${\boldsymbol{w}}^\star_e$ are reported in Fig. \[fig: MSD comparisons\]. Observe that the performance with respect to ${\boldsymbol{w}}^o_e$ highly deteriorates when $\sigma$ increases. However, even for the largest values of $\sigma=1$, algorithm  still performs well with respect to the solution ${\boldsymbol{w}}^\star_e$ of the optimization problem with constraints.

\[t\] ![image](figure5.pdf) ![image](figure6.pdf) ![image](figure7.pdf)

For comparison purposes, we illustrate in Fig. \[fig: MSD comparisons CLMS\] the theoretical and simulated learning curves with respect to ${\boldsymbol{w}}^\star$ for the settings where $\sigma=0.5$ (left) and $\sigma=1$ (right) of the centralized CLMS algorithm , algorithm  where the sub-nodes "project-then-combine", and the stochastic version (obtained by replacing the moments by instantaneous approximations) of algorithm  where the sub-nodes "combine-then-project" (Appendix C explains how the performance of this algorithm can be obtained). Observe that both algorithms  and the stochastic version of  have approximately the same performance. However, with the settings considered in this section, algorithm  is less complex than algorithm  as explained in subsection \[subsec: Distributed solution\]. Furthermore, we observe that the larger the vector ${\boldsymbol{w}}^\delta_e$ is, the larger the performance gap between the centralized solution and the distributed solutions is. This is due to the bias  induced in the distributed solution which does not exist in the centralized CLMS algorithm (see Appendix C). In order to characterize the constraints violation at the sub-nodes for the setting where $\sigma=0.5$, we evaluate the steady-state quantity $\|{\boldsymbol{\cal{D}}}'_e{\boldsymbol{w}}_e(\infty)+{\boldsymbol{b}}'\|^2$ where ${\boldsymbol{\cal{D}}}'_e$ and ${\boldsymbol{b}}'$ are given by  and ${\boldsymbol{w}}_e(\infty)\triangleq\lim_{i\rightarrow\infty}{\boldsymbol{w}}_e(i)$. When the sub-nodes project first and then combine, we obtain $\|{\boldsymbol{\cal{D}}}'_e{\boldsymbol{w}}_e(\infty)+{\boldsymbol{b}}'\|^2=\|{\boldsymbol{\cal{D}}}_e{\boldsymbol{w}}_e(\infty)+{\boldsymbol{b}}\|^2=0.0264$. On the contrary, when the sub-nodes combine first and then project, we obtain $\|{\boldsymbol{\cal{D}}}'_e{\boldsymbol{w}}_e(\infty)+{\boldsymbol{b}}'\|^2=\|{\boldsymbol{\cal{H}}}{\boldsymbol{w}}_e(\infty)\|^2=0.0072$. Thus, at the expense of a higher computational complexity, the constraints violation, measured by $\|{\boldsymbol{\cal{D}}}'_e{\boldsymbol{w}}_e(\infty)+{\boldsymbol{b}}'\|^2$, is smaller when the projection step is performed after the combination step[^2].

![image](figure6a.pdf) ![image](figure7a.pdf)

In order to characterize the influence of the step-size $\mu$ on the performance of algorithm , Fig. \[fig: variable step-size\] (left) reports the theoretical steady-state MSD with respect to ${\boldsymbol{w}}^\star_e$ for different values of $\mu$. We observe that the network MSD increases $10$ dB per decade (when the step-size goes from $\mu_1$ to $10\mu_1$). This means that the steady-state MSD is <span>on</span> the order of $\mu$. Fig. \[fig: variable step-size\] (right) reports the squared norm of the bias  for different values of $\mu$. We note that it increases approximately $20$ dB per decade. This shows that, as expected, this quantity is <span>on</span> the order of $\mu^2$.

\[h\]

![image](figure8.pdf) ![image](figure9.pdf)

Next, we considered the case of non-diagonal matrices ${\boldsymbol{D}}_{p\ell}$ defined as: $${\boldsymbol{D}}_{p\ell}=d_{p\ell}{\boldsymbol{I}}_2+\boldsymbol{\Delta}_{p\ell}$$ Parameters $d_{p\ell}$ were randomly selected as in . The entries of the $2\times 2$ matrix $\boldsymbol{\Delta}_{p\ell}$ were sampled from Gaussian distribution ${\mathcal{N}}(0,\sigma^2_{D})$. As shown in Fig. \[fig: perturbed D\], the variance $\sigma^2_{D}$ was set to $0.01$ (left) and $1$ (right). To test the tracking ability of algorithm , we also perturbed the parameter vector ${\boldsymbol{w}}^o$ as in  by increasing $\sigma^2$ every 500 iterations. In both cases, i.e., $\sigma^2_{D}=0.01$ and $\sigma^2_{D}=1$, ${\boldsymbol{w}}^o$ in  was set to satisfy the equality constraints defined by ${\boldsymbol{D}}_{p\ell}$. We observe that the theoretical models match well the actual performance whatever the constraints are. Furthermore, algorithm  adapts its response to drifts in the location of ${\boldsymbol{w}}^\star$ when ${\boldsymbol{w}}^o$ changes over time.

\[h\]

![image](figure10.pdf) ![image](figure11.pdf)

Optimal network flow
--------------------

As briefly discussed in the Introduction, we shall now consider the minimum-cost flow problem over the network with topology shown in Fig. \[fig: network flow problem - intro\]. We are interested in online distributed learning where each node $k$ seeks to estimate the entering and leaving flows $f_j$ from noisy measurement $s_k(i)$ of the external source, by relying only on local computations and communications with its neighbors.

Let $M_k$ be the number of flows to be estimated at node $k$. We denote by ${\boldsymbol{w}}_k$ the $M_k\times 1$ parameter vector containing the flows $f_j$ entering and leaving node $k$, negatively and positively signed, respectively. For instance, for nodes $1$ and $2$, we have: $${\boldsymbol{w}}_1\triangleq[f_1~f_2]^\top \quad {\boldsymbol{w}}_2\triangleq[-f_1~f_3~f_4~f_5]^\top$$ From the flow conservation principle, the noisy measurement $s_k(i)$ can be related to ${\boldsymbol{w}}_k(i)$ as follows: $$s_k(i)={\bf{1}}_{M_k \times 1}^\top{\boldsymbol{w}}_k+z_k(i),$$ with $z_k(i)$ a zero-mean measurement noise, and ${\bf{1}}_{M_k \times 1}$ an $M_k \times 1$ vector of ones. We consider the bi-objective problem consisting of minimizing ${\mathbb{E}}\,|z_k(i)|^2$ and the cost network flow. We shall assume that the cost for flow through an arc is quadratic in the flow, as in applications such as electrical network monitoring and urban traffic control @ahuja1993network [@ventura1991computational]. We formulate the estimation problem as follows: $$\label{eq: optimization problem of the network flow}
    \begin{split}
        &\operatorname*{minimize}\limits_{{\boldsymbol{w}}_1,\ldots,{\boldsymbol{w}}_N}~        \sum_{k=1}^N \Big({\mathbb{E}}~|s_k(i)-{\bf{1}}_{M_k \times 1}^\top{\boldsymbol{w}}_k|^2+\frac{\eta}{2}\|{\boldsymbol{w}}_k\|^2\Big),\\
        &\operatorname*{subject\,to}~[{\boldsymbol{w}}_k]_{f({k,\ell})}+[{\boldsymbol{w}}_\ell]_{f({\ell,k})}=0,~ \ell\in{\mathcal{N}}_k,~\text{for all } k,
    \end{split}$$ where $[{\boldsymbol{w}}_p]_{f(p,q)}$ returns the flow entry in ${\boldsymbol{w}}_p$ that node $p$ has in common with node $q$, and $\eta$ is a tuning parameter to trade off between both objectives.

For each agent $k$, the external flow $s_k$ and the variance $\sigma^2_{z,k}$ of the Gaussian noise $z_k(i)$ were randomly generated from the uniform distributions $\mathcal{U}(0,3)$ and $\mathcal{U}(0.1,0.14)$, respectively. In order to solve the multitask problem  in a fully distributed manner, we applied algorithm  by modifying the adaptation step according to: $$\label{eq: leaky LMS}
\begin{split}
    {\boldsymbol{\psi}}_{k_m}(i+1)&={\boldsymbol{w}}_{k_m}(i)+\mu\,c_{k_m}\boldsymbol{1}_{M_k \times 1}[s_k(i)-\boldsymbol{1}_{M_k \times 1}^\top{\boldsymbol{w}}_{k_m}(i)]\\
    &\qquad-\frac{\mu}{2} c_{km}\eta\,{\boldsymbol{w}}_{k_m}(i),
\end{split}$$ and setting $\mu=0.2$ and $\eta=0.002$. In order to test the tracking ability of the algorithm, the external flow $s_k$ at each node $k$ was re-generated from $\mathcal{U}(0,3)$ after $45000$ iterations. The MSD learning curve with respect to the solution of problem  is reported in Fig. \[fig: network flow problem MSD\]. This result was obtained by averaging over 150 Monte-Carlo runs. This figure shows that our strategy was able to solve the minimum-cost flow problem in a fully distributed manner. The estimated flows over the network for both settings considered in the tracking experiment are showed in Fig. \[fig: network flow results\] (left and middle). Note that the direction of the estimated flow between nodes $3$ and $4$ is reversed. The true and estimated flows are reported in Fig. \[fig: network flow results\] (right) for both settings.

![MSD performance and tracking ability of algorithm  for the minimum cost network flow problem.<span data-label="fig: network flow problem MSD"></span>](figure12.pdf)

\[h\]

![image](figure13.pdf) ![image](figure14.pdf) ![image](figure15.pdf)

Numerical solution of a two-dimensional process
-----------------------------------------------

Consider now the problem of estimating a two-dimensional process driven by a partial differential equation (PDE) with a sensor network. To see how our distributed algorithm can be tuned to address this issue, we shall focus on the Poisson's PDE defined by: $$\label{eq:poisson}
    \frac{\partial^2 f(x,y)}{\partial x^2}+\frac{\partial^2 f(x,y)}{\partial y^2}=g(x,y), \qquad (x,y)\in[0,1]^2,$$ with $g:[0,1]^2\rightarrow\mathbb{R}$ an input function, and on a two dimensional network of $(n-2)^2$ sensor nodes and $4(n-1)$ boundary points equally spaced over the unit square $(x,y)\in[0,1]^2$ with $\Delta_x=\Delta_y=\Delta=\frac{1}{n-1}$, as illustrated in Fig. \[fig: grid network\] (a).

We introduce the grid point $(x_k,y_\ell)\triangleq (k\Delta,\ell\Delta)$ and the sampled values at this point $f_{k,\ell}\triangleq f(k\Delta,\ell\Delta)$ and $g_{k,\ell}\triangleq g(k\Delta,\ell\Delta)$ with $0\leq k,\ell \leq n-1$. We use the central difference approximation for the second derivative @bertsekas1989parallel: $$\begin{aligned}
    \frac{\partial^2 f(k\Delta,\ell\Delta)}{\partial x^2}&\approx\frac{1}{\Delta^2}\Big(f_{k+1,\ell}-2 f_{k,\ell}+f_{k-1,\ell}\Big)\\
    \frac{\partial^2 f(k\Delta,\ell\Delta)}{\partial y^2}&\approx\frac{1}{\Delta^2}\Big(f_{k,\ell+1}-2 f_{k,\ell}+f_{k,\ell-1}\Big)\end{aligned}$$ which leads to: $$\label{eq: linear relation between f and g}
    \frac{1}{\Delta^2}\Big(-4 f_{k,\ell}+f_{k-1,\ell}+f_{k,\ell-1}+f_{k,\ell+1}+f_{k+1,\ell}\Big)=g_{k,\ell}.$$ In this experiment, we shall consider the unknown physical process $f$ and the input function $g$ given by: $$\begin{aligned}
    &f(x,y)=(1-x^2)(2y^3-3y^2+1),\\
    &g(x,y)=-2(2y^3-3y^2+1)+6(1-x^2)(2y-1),\end{aligned}$$ for $(x,y)\in[0,1]^2$ with boundary conditions $f(0,y)=2y^3-3y^2+1$, $f(x,0)=1-x^2$, and $f(1,y)=f(x,1)=0$. These functions are illustrated in Fig. \[fig: grid network\] (b), (c).

The objective is to estimate $f(x,y)$ at the interior grid points $(x_k,y_\ell)$ with $0<k,\ell<n-1$, given noisy measurements $g_{k\ell}(i)=g_{k\ell}+z_{k\ell}(i)$ of $g(x,y)$ collected by the sensors located at these interior grid points. The noise process $z_{k\ell}(i)$ is assumed to be zero mean, temporally white, and spatially independent. The values of $f(x,y)$ at the boundary points are known a priori as they correspond to boundary conditions. We denote by $f^o_{k\ell}$ the value at $(x_k,y_{\ell})$ of the function $f(x,y)$ that satisfies , and by $f_{k\ell}$ the estimated value of $f^o_{k\ell}$. To each node $(k,\ell)$ we associate an $M_{k\ell}\times1$ parameter vector ${\boldsymbol{w}}_{k\ell}$ to estimate, an $M_{k\ell} \times 1$ regression vector ${\boldsymbol{x}}_{k\ell}$ and a scalar $v^o_{k\ell}$, defined in Table \[tab:parameter vectors and regression vectors\] depending on the node location on the grid. according to , the linear regression model can be written as follows: $$g_{k\ell}(i)={\boldsymbol{x}}_{k\ell}^\top{\boldsymbol{w}}_{k\ell}+v^o_{k\ell}+z_{k\ell}(i).$$ As can be seen in Table \[tab:parameter vectors and regression vectors\], equality constraints of the form  need to be imposed on the parameter vectors of neighboring sensor nodes in order to achieve equality between common entries. For instance, let us consider neighboring nodes $(k,\ell)$ and $(k+1,\ell)$ with $2\leq k \leq n-4$ and $2\leq \ell \leq n-3$. Since these nodes are jointly estimating $f_{k,\ell}$ and $f_{k+1,\ell}$, the following equality constraint is required: $$\left[ \setlength\arraycolsep{2pt}
    \begin{array}{ccccc} 
        1 & 0 &0 & 0&0 \\
        0&0&0&0&1
    \end{array}
    \right]{\boldsymbol{w}}_{k\ell}+
    \left[  \setlength\arraycolsep{2pt}
    \begin{array}{ccccc} 
        0 & -1 &0 & 0&0 \\
        -1&0&0&0&0
    \end{array}
    \right]{\boldsymbol{w}}_{(k+1)\ell}=\Zero.
 $$

\[t\]

\[t\]

                                          $1$                                                           $2,\ldots, n-3$                                                         $n-2$
  ----------- ------------------------------------------------------------ ------------------------------------------------------------------------- ------------------------------------------------------------
                     $[f_{k,\ell},f_{k,\ell+1},f_{k+1,\ell}]^\top$                $[f_{k,\ell},f_{k-1,\ell},f_{k,\ell+1},f_{k+1,\ell}]^\top$                $[f_{k,\ell},f_{k-1,\ell},f_{k,\ell+1}]^\top$
                                    $[-4,1,1]^\top$                                                    $[-4,1,1,1]^\top$                                                   $[-4,1,1]^\top$
                                 $f^o_{1,0}+f^o_{0,1}$                                                    $f^o_{k,0}$                                                 $f^o_{n-2,0}+f^o_{n-1,1}$
      $2$      $[f_{k,\ell},f_{k,\ell-1},f_{k,\ell+1},f_{k+1,\ell}]^\top$   $[f_{k,\ell},f_{k-1,\ell},f_{k,\ell-1},f_{k,\ell+1},f_{k+1,\ell}]^\top$   $[f_{k,\ell},f_{k-1,\ell},f_{k,\ell-1},f_{k,\ell+1}]^\top$
   $ \vdots$                       $[-4,1,1,1]^\top$                                                  $[-4,1,1,1,1]^\top$                                                 $[-4,1,1,1]^\top$
     $n-3$                           $f^o_{0,\ell}$                                                            0                                                           $f^o_{n-1,\ell}$
                     $[f_{k,\ell},f_{k,\ell-1},f_{k+1,\ell}]^\top$                $[f_{k,\ell},f_{k-1,\ell},f_{k,\ell-1},f_{k+1,\ell}]^\top$                $[f_{k,\ell},f_{k-1,\ell},f_{k,\ell-1}]^\top$
                                    $[-4,1,1]^\top$                                                    $[-4,1,1,1]^\top$                                                   $[-4,1,1]^\top$
                               $f^o_{0,n-2}+f^o_{1,n-1}$                                                 $f^o_{k,n-1}$                                              $f^o_{n-2,n-1}+f^o_{n-1,n-2}$

Algorithm  can be used to address this problem by replacing the adaptation step  by: $${\boldsymbol{\psi}}_{k\ell_m}(i+1)={\boldsymbol{w}}_{k\ell_m}(i)+\mu\,c_{k\ell_m}{\boldsymbol{x}}_{k\ell}\big[g_{k\ell}(i)-{\boldsymbol{x}}_{k\ell}^\top{\boldsymbol{w}}_{k\ell_m}(i)-v^o_{k\ell}\big],$$ where ${\boldsymbol{w}}_{k\ell_m}(i)$ denotes the estimate of ${\boldsymbol{w}}_{k\ell}$ at the $m$-th sub-node of $(k,\ell)$. The noises $z_{k,\ell}(i)$ were zero-mean i.i.d. Gaussian distributed with variances $\sigma^2_{z,k\ell}$ randomly generated from the uniform distribution $\mathcal{U}(0.1,0.14)$. We used a constant step-size $\mu=7\cdot10^{-5}$ for all nodes. Figure \[fig: poisson process problem MSD\] shows the network MSD learning curves for $n=9$. The simulated curves were obtained by averaging over $100$ independent runs. Figure \[fig: poisson process estimation\] shows the true (left) and estimated (right) process after convergence of our algorithm.

![Network MSD performance for $n=9$.<span data-label="fig: poisson process problem MSD"></span>](figure19.pdf)

![Poisson process $f(x,y)$ over the network grid. (<span>*Left*</span>) True process. (<span>*Right*</span>) Estimated process.<span data-label="fig: poisson process estimation"></span>](figure20.pdf "fig:") ![Poisson process $f(x,y)$ over the network grid. (<span>*Left*</span>) True process. (<span>*Right*</span>) Estimated process.<span data-label="fig: poisson process estimation"></span>](figure21.pdf "fig:")

Conclusion and Perspectives
===========================

In this work, we proposed a multitask LMS algorithm for solving problems that require <span>the</span> simultaneous estimation of multiple parameter vectors that are related <span>locally</span> via linear constraints. Our primal technique was based on the stochastic gradient projection algorithm with constant step-sizes. The behavior of the algorithm in the mean and mean-square-error sense was studied. agents are able to reach the optimal solution with good precision. In future <span>work</span>, we shall extend our approach to other <span>types</span> of constraints and also consider other constraints distribution over networks.

Projection matrix structure {#sec: Projection matrix structure}
===========================

We denote by ${\boldsymbol{\cal{D}}}_{e,p}$ the $p$-th block row in ${\boldsymbol{\cal{D}}}_e$ and by $[{\boldsymbol{\cal{D}}}_{e}]_{p,k_m}$ the $L_p\times M_k$ block of ${\boldsymbol{\cal{D}}}_{e,p}$ corresponding to the $k_m$-th sub-node. First, we show that the $M_k\times M_\ell$ $(k_m,\ell_n)$-th block of the $N_e\times N_e$ block matrix ${\boldsymbol{\cal{P}}}_e$ in  is equal to: $$\label{eq: result 1}
    [{\boldsymbol{\cal{P}}}_e]_{k_m,\ell_n}=
    \left\lbrace
    \begin{array}{lr}
    {\boldsymbol{I}}_{M_k}-[{\boldsymbol{\cal{D}}}_{e}]_{p,k_m}^\top({\boldsymbol{\cal{D}}}_{e,p}{\boldsymbol{\cal{D}}}^\top_{e,p})^{-1}[{\boldsymbol{\cal{D}}}_{e}]_{p,k_m},\\
    \qquad\qquad\text{if $k_m=\ell_n$ and $k_m\in{\mathcal{I}}_{e,p}$,} \\
        -[{\boldsymbol{\cal{D}}}_{e}]_{p,k_m}^\top({\boldsymbol{\cal{D}}}_{e,p}{\boldsymbol{\cal{D}}}^\top_{e,p})^{-1}[{\boldsymbol{\cal{D}}}_{e}]_{p,\ell_n},\\
    \qquad\qquad~\text{if $k_m\neq\ell_n$ and $k_m,\ell_n\in{\mathcal{I}}_{e,p}$,}\\
\Zero_{M_k\times M_\ell},\quad\qquad\quad\qquad~\quad\text{otherwise.}
\end{array}
\right.$$ Furthermore, we show that the $k_m$-th block of the $N_e\times 1$ block column vector ${\boldsymbol{f}}_e$ in  is equal to: $$\label{eq: result 2}
    [{\boldsymbol{f}}_e]_{k_m}=
    \left\lbrace
    \begin{array}{lr}
        [{\boldsymbol{\cal{D}}}_{e}]_{p,k_m}^\top({\boldsymbol{\cal{D}}}_{e,p}{\boldsymbol{\cal{D}}}^\top_{e,p})^{-1}{\boldsymbol{b}}_p,\text{ if $k_m\in{\mathcal{I}}_{e,p}$,}\\
        \Zero_{M_k\times 1}, \qquad\qquad\qquad\qquad\text{otherwise.}
    \end{array}
    \right.$$

It can be verified that ${\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top$ is a $P\times P$ block diagonal matrix whose $(p,p)$-th block is of dimension $L_p\times L_p$ and is given by: $$[{\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top]_{p,p}={\boldsymbol{\cal{D}}}_{e,p}{\boldsymbol{\cal{D}}}^\top_{e,p}={\boldsymbol{\cal{D}}}_{p}{\boldsymbol{\cal{D}}}_{p}^\top.$$ The inverse of the block diagonal matrix ${\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top$ is: $$({\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top)^{-1}={\text{diag}}\Big\{({\boldsymbol{\cal{D}}}_{e,p}{\boldsymbol{\cal{D}}}^\top_{e,p})^{-1}\Big\}_{p=1}^P.$$ By multiplying the matrix $({\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top)^{-1}$ from the left by ${\boldsymbol{\cal{D}}}_e^\top$ we obtain an $N_e\times P$ block matrix whose $(k_m,p)$-th block is of dimension $M_k\times L_p$ given by: $$\label{eq: pinvD}
\begin{split}
&[{\boldsymbol{\cal{D}}}_e^\top({\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top)^{-1}]_{k_m,p}\\
&=\left\lbrace
\begin{array}{lr}
[{\boldsymbol{\cal{D}}}_{e}]^\top_{p,k_m}({\boldsymbol{\cal{D}}}_{e,p}{\boldsymbol{\cal{D}}}^\top_{e,p})^{-1},~ \text{if} ~k_m\in{\mathcal{I}}_{e,p}\\
\Zero_{M_k\times L_p},\qquad\qquad\qquad~\text{otherwise}.
\end{array}
\right.
\end{split}$$ When we multiply the matrix ${\boldsymbol{\cal{D}}}_e^\top({\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top)^{-1}$ from the right by ${\boldsymbol{\cal{D}}}_e$, we obtain an $N_e\times N_e$ block matrix whose $(k_m,\ell_n)$-th block corresponding to sub-nodes $k_m$, $\ell_n$ is of dimension $M_k\times M_\ell$ and is given by: $$\label{eq: pinvDD}
\begin{split}
&[{\boldsymbol{\cal{D}}}_e^\top({\boldsymbol{\cal{D}}}_e{\boldsymbol{\cal{D}}}_e^\top)^{-1}{\boldsymbol{\cal{D}}}_e]_{k_m,\ell_n}\\
&=
\left\lbrace
\begin{array}{lr}
[{\boldsymbol{\cal{D}}}_{e}]^\top_{p,k_m}({\boldsymbol{\cal{D}}}_{e,p}{\boldsymbol{\cal{D}}}^\top_{e,p})^{-1}[{\boldsymbol{\cal{D}}}_e]_{p,\ell_n},\quad\text{if $k_m,\ell_n\in{\mathcal{I}}_{e,p}$,}\\
\Zero_{M_k\times M_\ell},\qquad\qquad\qquad\qquad\qquad~\text{otherwise.}
\end{array}
\right.
\end{split}$$ From  and , we obtain .

Evaluation of the matrix ${\boldsymbol{\cal{F}}}$ {#sec: matrix F}
=================================================

<span>Without loss of generality, we assume in the following that $M_k$ is uniform across the network, i.e., $M_k=M_0$ for all $k$.</span> We note that for any <span>symmetric</span> matrix ${\boldsymbol{T}}$, we have @isserlis1918formula: $$\begin{split}
&{\mathbb{E}}\{{\boldsymbol{x}}_k(i){\boldsymbol{x}}_k^\top(i){\boldsymbol{T}}{\boldsymbol{x}}_{\ell}(i){\boldsymbol{x}}_{\ell}^\top(i)\}\\
&={\boldsymbol{R}}_{x,k}{\boldsymbol{T}}{\boldsymbol{R}}_{x,\ell}+\delta_{k,\ell}\big({\boldsymbol{R}}_{x,k}{\boldsymbol{T}}{\boldsymbol{R}}_{x,k}+{\boldsymbol{R}}_{x,k}{\text{tr}}({\boldsymbol{R}}_{x,k}{\boldsymbol{T}})\big).
\end{split}$$ From  and , we obtain: $$\begin{split}
&{\boldsymbol{\Sigma}}'={\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}{\boldsymbol{\Sigma}}{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e-\mu{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}{\boldsymbol{\Sigma}}{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{R}}}_{x,e}-\\
&\mu{\boldsymbol{\cal{R}}}_{x,e}{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}{\boldsymbol{\Sigma}}{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e+\mu^2{\mathbb{E}}\{{\boldsymbol{\cal{R}}}_{x,e}(i){\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}{\boldsymbol{\Sigma}}{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{R}}}_{x,e}(i)\}.
\end{split}$$ In order to evaluate ${\boldsymbol{\Sigma}}'$ we need to evaluate the fourth term on the RHS of the above equation. Let: <span>$$\begin{aligned}
{\boldsymbol{\cal{K}}}&\triangleq&{\mathbb{E}}\{{\boldsymbol{\cal{R}}}_{x,e}(i){\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}{\boldsymbol{\Sigma}}{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{R}}}_{x,e}(i)\},\label{eq: matrix K} \\
{\boldsymbol{\cal{T}}}&\triangleq&{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}{\boldsymbol{\Sigma}}{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e.\end{aligned}$$</span> It can be verified that the $(k_m,\ell_n)$-th block of the matrix ${\boldsymbol{\cal{K}}}$ corresponding to the $(k_m,\ell_n)$-th sub-node is given by: $$\begin{split}
&[{\boldsymbol{\cal{K}}}]_{k_m,\ell_n}\\
&=c_{k_m}c_{\ell_n}{\mathbb{E}}\big\{{\boldsymbol{x}}_k(i){\boldsymbol{x}}_{k}^\top(i)[{\boldsymbol{\cal{T}}}]_{k_m,\ell_n}{\boldsymbol{x}}_{\ell}(i){\boldsymbol{x}}_{\ell}^\top(i)\big\}\\
&=c_{k_m}c_{\ell_n}{\boldsymbol{R}}_{x,k}[{\boldsymbol{\cal{T}}}]_{k_m,\ell_n}{\boldsymbol{R}}_{x,\ell}+\\
&~ ~\delta_{k,\ell}c_{k_m}c_{\ell_n}\big({\boldsymbol{R}}_{x,k}[{\boldsymbol{\cal{T}}}]_{k_m,\ell_n}{\boldsymbol{R}}_{x,k}+{\boldsymbol{R}}_{x,k}{\text{tr}}({\boldsymbol{R}}_{x,k}[{\boldsymbol{\cal{T}}}]_{k_m,\ell_n})\big),
\end{split}$$ where the $M_0\times M_0$ matrix $[{\boldsymbol{\cal{T}}}]_{k_m,\ell_n}$ is the $(k_m,\ell_n)$-th block of the matrix ${\boldsymbol{\cal{T}}}$. The matrix ${\boldsymbol{\cal{K}}}$ in  can be written as: $$\begin{split}
{\boldsymbol{\cal{K}}}=&{\boldsymbol{\cal{R}}}_{x,e}{\boldsymbol{\cal{T}}}{\boldsymbol{\cal{R}}}_{x,e}+\sum_{k=1}^N{\mathcal{S}}_k({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k}){\boldsymbol{\cal{T}}}({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k}){\mathcal{S}}_k+\\
&\quad\sum_{k=1}^N{\mathcal{S}}_k({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k}){\boldsymbol{\cal{Z}}}_k{\mathcal{S}}_k,
\end{split}$$ where ${\mathcal{S}}_k$ is the $N\times N$ block diagonal matrix whose $(k,k)$-th block is equal to ${\boldsymbol{C}}_k\otimes{\boldsymbol{I}}_{M_0}$, and ${\boldsymbol{\cal{Z}}}_k$ is the $N_e\times N_e$ block matrix whose $(k_m,\ell_n)$-th block is given by: $$\big[{\boldsymbol{\cal{Z}}}_k\big]_{h_m,\ell_n}={\boldsymbol{I}}_{M_0}[{\text{vec}}({\boldsymbol{R}}_{x,k})]^\top{\text{vec}}([{\boldsymbol{\cal{T}}}]_{k_m,\ell_n}).$$ Applying the block-vectorization operator to ${\boldsymbol{\cal{K}}}$ and using the property ${\text{bvec}}({\boldsymbol{A}}{\boldsymbol{B}}{\boldsymbol{C}})=({\boldsymbol{C}}^\top\otimes_b{\boldsymbol{A}}){\text{bvec}}({\boldsymbol{B}})$, we obtain: $$\begin{split}
    &{\text{bvec}}({\boldsymbol{\cal{K}}})=({\boldsymbol{\cal{R}}}_{x,e}\otimes_b{\boldsymbol{\cal{R}}}_{x,e}){\text{bvec}}({\boldsymbol{\cal{T}}})+\\
    &\sum_{k=1}^N\Big({\mathcal{S}}_k^\top({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k})\otimes_b{\mathcal{S}}_k({\boldsymbol{I}}_{N_e}\otimes  {\boldsymbol{R}}_{x,k})\Big){\text{bvec}}({\boldsymbol{\cal{T}}})+\\
    &\sum_{k=1}^N\Big({\mathcal{S}}_k^\top\otimes_b\big({\mathcal{S}}_k[{\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k}]\big)\Big){\text{bvec}}({\boldsymbol{\cal{Z}}}_k),
    \end{split}$$ where ${\text{bvec}}({\boldsymbol{\cal{Z}}}_k)$ can be expressed as: $${\text{bvec}}({\boldsymbol{\cal{Z}}}_k)=\Big({\boldsymbol{I}}_{N_e^2}\otimes{\text{vec}}({\boldsymbol{I}}_{M_0})\otimes[{\text{vec}}({\boldsymbol{R}}_{x,k})]^\top\Big){\text{bvec}}({\boldsymbol{\cal{T}}}),$$ where <span>${\text{bvec}}({\boldsymbol{\cal{T}}})=({\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}\otimes_b{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}){\boldsymbol{\sigma}}$</span>. Finally, we conclude that the matrix ${\boldsymbol{\cal{F}}}$ in  can be written as: <span>$$\begin{split}
&{\boldsymbol{\cal{F}}}={\boldsymbol{\cal{B}}}^\top\otimes_b{\boldsymbol{\cal{B}}}^\top+\\
&\mu^2\sum_{k=1}^N\Big({\mathcal{S}}_k^\top({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k})\otimes_b{\mathcal{S}}_k({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k})\Big)({\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}\otimes_b{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}})\\
&+\mu^2\sum_{k=1}^N\Big({\mathcal{S}}_k^\top\otimes_b\big({\mathcal{S}}_k({\boldsymbol{I}}_{N_e}\otimes{\boldsymbol{R}}_{x,k})\big)\Big)\cdot\\
&\qquad\qquad\Big({\boldsymbol{I}}_{N_e^2}\otimes{\text{vec}}({\boldsymbol{I}}_{M_0})\otimes[{\text{vec}}({\boldsymbol{R}}_{x,k})]^\top\Big)({\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}\otimes_b{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}).
\end{split}$$</span>

Performance of competing algorithms {#app: Performance of competing algorithms}
===================================

We compare in the simulation section algorithm  with the non-cooperative LMS algorithm (obtained from  by setting ${\boldsymbol{\cal{P}}}={\boldsymbol{I}}_{M}$ and ${\boldsymbol{f}}=\Zero$), the centralized CLMS algorithm , and the following algorithm:

\[eq: multitask algorithm with steps inversion\] $$\begin{aligned}
            {\boldsymbol{\psi}}_{k_m}(i+1)&=&{\boldsymbol{w}}_{k_m}(i)+\nonumber
            \\
            &&\mu\,c_{k_m}{\boldsymbol{x}}_k(i)[d_k(i)-{\boldsymbol{x}}_k^\top(i){\boldsymbol{w}}_{k_m}(i)],\label{eq: 1 adaptation step}\\
            {\boldsymbol{\phi}}_{k_m}(i+1)&=&\sum_{k_n\in{{\mathcal{N}}_{k_m}\cap\,{\mathcal{C}}_k}}a_{k_n,k_m}{\boldsymbol{\psi}}_{k_n}(i+1),\label{eq: 2 combination step}\\
            {\boldsymbol{w}}_{k_m}(i+1)&= &[{\boldsymbol{\cal{P}}}_{p}]_{k_m,\bullet}\cdot{\text{col}}\big\{{\boldsymbol{\phi}}_{\ell_n}(i+1)\big\}_{\ell_n\in{\mathcal{I}}_{e,p}}-[{\boldsymbol{f}}_{p}]_{k_m},\nonumber\\
            \label{eq: 3 projection step}
        \end{aligned}$$

where the sub-nodes "combine-then-project" instead of "project-then-combine". In the following, we show how the theoretical learning curves of these algorithms can be obtained from the analysis in Sections \[sec: Performance analysis I\] and \[sec: Performance analysis II\]. Consider the centralized CLMS algorithm . Let ${\widetilde{\boldsymbol{w}}}(i)$ and ${\widetilde{\boldsymbol{w}}}'(i)$ denote the $N\times 1$ block error vectors at the fusion center given by: $${\widetilde{\boldsymbol{w}}}(i)\triangleq{\boldsymbol{w}}^o-{\boldsymbol{w}}(i),\qquad
    {\widetilde{\boldsymbol{w}}}'(i)\triangleq{\boldsymbol{w}}^\star-{\boldsymbol{w}}(i).$$ Subtracting ${\boldsymbol{w}}^o$ from both sides of recursion  and using the linear data model , we obtain: $$\label{eq: evolution of w}
\begin{split}
{\widetilde{\boldsymbol{w}}}(i+1)&={\boldsymbol{\cal{P}}}\left({\boldsymbol{I}}_{M}-\mu{\boldsymbol{\cal{R}}}_x(i)\right){\widetilde{\boldsymbol{w}}}(i)-\mu{\boldsymbol{\cal{P}}}{\boldsymbol{p}}_{xz}(i)+\\
&\qquad\left({\boldsymbol{I}}_{M}-{\boldsymbol{\cal{P}}}\right){\boldsymbol{w}}^o+{\boldsymbol{f}},
\end{split}$$ where ${\boldsymbol{\cal{R}}}_x(i)$ and ${\boldsymbol{p}}_{xz}(i)$ are given by: $$\begin{aligned}
&{\boldsymbol{\cal{R}}}_x(i)\triangleq{\text{diag}}\left\{{\boldsymbol{x}}_k(i){\boldsymbol{x}}_k^\top(i)\right\}_{k=1}^N, \\
&{\boldsymbol{p}}_{xz}(i)\triangleq{\text{col}}\left\{d_k(i){\boldsymbol{x}}_k(i)\right\}_{k=1}^N.\end{aligned}$$ Let ${\boldsymbol{w}}^\delta\triangleq{\boldsymbol{w}}^o-{\boldsymbol{w}}^\star$. Using ${\widetilde{\boldsymbol{w}}}'(i)={\widetilde{\boldsymbol{w}}}(i)-{\boldsymbol{w}}^\delta$ with  and the fact that ${\boldsymbol{w}}^\star$ satisfies ${\boldsymbol{\cal{P}}}{\boldsymbol{w}}^\star-{\boldsymbol{f}}={\boldsymbol{w}}^\star$, we obtain: $$\label{eq: evolution of w'}
{\widetilde{\boldsymbol{w}}}'_b(i+1)={\boldsymbol{\cal{P}}}\left({\boldsymbol{I}}_{M}-\mu{\boldsymbol{\cal{R}}}_x(i)\right){\widetilde{\boldsymbol{w}}}'(i)-\mu{\boldsymbol{\cal{P}}}{\boldsymbol{p}}_{xz}(i)-\mu{\boldsymbol{\cal{P}}}{\boldsymbol{\cal{R}}}_x(i){\boldsymbol{w}}^\delta.$$ Comparing recursions  and with recursions  and , we observe that the learning curves of the centralized solution  can be deduced from those of the decentralized solution  by properly modifying the coefficient matrices and vectors. Note that, the centralized solution is unbiased with respect to ${\boldsymbol{w}}^\star$ since $\mu{\boldsymbol{\cal{P}}}{\mathbb{E}}{\boldsymbol{\cal{R}}}_x(i){\boldsymbol{w}}^\delta=\Zero$.

Next, consider the distributed solution . Following the same line of reasoning as in Subsection \[subsec: network error vector recursion\], we obtain the following recursions for the block error vectors  and : $$\label{eq: weight error vector recursion 0 with step inverse}
    \begin{split}
    {\widetilde{\boldsymbol{w}}}_e(i+1)&={\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top\left[{\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}(i)\right]{\widetilde{\boldsymbol{w}}}_e(i)-\\
    &\mu{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top{\boldsymbol{p}}_{xz,e}(i)+\left({\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{P}}}_e\right){\boldsymbol{w}}^o_e+{\boldsymbol{f}}_e,
    \end{split}$$ $$\label{eq: weight error vector recursion 0' with step inverse}
    \begin{split}
    {\widetilde{\boldsymbol{w}}}_e'(i+1)&={\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top\left[{\boldsymbol{I}}_{M_e}-\mu{\boldsymbol{\cal{R}}}_{x,e}(i)\right]{\widetilde{\boldsymbol{w}}}_e'(i)-\\
    &\mu{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top{\boldsymbol{p}}_{xz,e}(i)-\mu{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{R}}}_{x,e}(i){\boldsymbol{w}}^\delta_e.
    \end{split}$$ Comparing recursions  and with recursions  and , we observe that the learning curves of the distributed solution  can be deduced from the theoretical curves of the decentralized solution  by properly replacing the product ${\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e$ in the analysis of Sections \[sec: Performance analysis I\] and \[sec: Performance analysis II\] by the product ${\boldsymbol{\cal{P}}}_e\,{\boldsymbol{\cal{A}}}^\top$ and the vector ${\boldsymbol{r}}$ in  by ${\boldsymbol{r}}\triangleq\left({\boldsymbol{I}}_{M_e}-{\boldsymbol{\cal{P}}}_e\right){\boldsymbol{w}}^o_e+{\boldsymbol{f}}_e$.

Performance comparison {#app: Performance comparison}
======================

As explained after algorithm (35), this permutation of the projection and the aggregation steps is very useful since it allows to simplify the algorithm. We show hereafter that, for the perfect model scenario (i.e., ${\boldsymbol{w}}^o={\boldsymbol{w}}^\star$), this permutation enhances the steady-state mean-square-error performance.

First, let us consider the algorithm where agent $k$ performs the projection step before the aggregation step. In the case of the perfect model scenario, we know that ${\boldsymbol{r}}=0$ (see (56)), and ${\mathbb{E}}\,{\widetilde{\boldsymbol{w}}}_e(\infty)=0$ (see (59)). When matrix ${\boldsymbol{\cal{F}}}$ is stable, from (75)–(77), we obtain the following steady-state network performance with metric ${\boldsymbol{\sigma}}_{ss}\triangleq{\text{bvec}}({\boldsymbol{\Sigma}}_{ss})$: $$\begin{split}
\zeta^\star&=[{\text{bvec}}({\boldsymbol{\cal{Y}}}(\infty))]^\top({\boldsymbol{I}}-{\boldsymbol{\cal{F}}})^{-1}{\boldsymbol{\sigma}}_{ss}\\
&=[{\text{bvec}}({\boldsymbol{\cal{Y}}}(\infty))]^\top\sum_{j=0}^{+\infty}[({\boldsymbol{\cal{B}}}^{\top})^j\otimes_b({\boldsymbol{\cal{B}}}^{\top})^j]{\boldsymbol{\sigma}}_{ss}\\
&=[{\text{bvec}}({\boldsymbol{\cal{Y}}}(\infty))]^\top\sum_{j=0}^{+\infty}{\text{bvec}}\left(({\boldsymbol{\cal{B}}}^{\top})^j{\boldsymbol{\Sigma}}_{ss}{\boldsymbol{\cal{B}}}^j\right)\\
&=\sum_{j=0}^{+\infty}{\text{tr}}\left({\boldsymbol{\cal{Y}}}(\infty)({\boldsymbol{\cal{B}}}^{\top})^j{\boldsymbol{\Sigma}}_{ss}{\boldsymbol{\cal{B}}}^j\right)\\
&=\sum_{j=0}^{+\infty}{\text{tr}}\left({\boldsymbol{\Sigma}}_{ss}{\boldsymbol{\cal{B}}}^j{\boldsymbol{\cal{Y}}}(\infty)({\boldsymbol{\cal{B}}}^{\top})^j\right)
\end{split}$$ Replacing ${\boldsymbol{\cal{B}}}$ and ${\boldsymbol{\cal{Y}}}(\infty)$ in the above expression by (58) and (77), we obtain: $$\begin{split}
\zeta^\star=\mu^2\sum_{j=0}^{+\infty}{\text{tr}}\Big({\boldsymbol{\Sigma}}_{ss}&\left({\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e})\right)^j{\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{P}}}_e{\mathcal{S}}{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}\cdot\\
&\qquad\qquad\Big(({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e}){\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}\Big)^j\Big),
\end{split}$$ where ${\mathcal{S}}\triangleq{\text{diag}}\left\{{\boldsymbol{c}}_k{\boldsymbol{c}}_k^\top\otimes\sigma^2_{z,k}{\boldsymbol{R}}_{x,k}\right\}_{k=1}^N$.

Let us consider now that agent $k$ performs the aggregation step before projecting. Let $\zeta^\star_1$ be the steady-state network performance with metric ${\boldsymbol{\sigma}}_{ss}\triangleq{\text{bvec}}({\boldsymbol{\Sigma}}_{ss})$. Following the same line of reasoning, we obtain: $$\begin{split}
\zeta^\star_1=\mu^2\sum_{j=0}^{+\infty}{\text{tr}}\Big({\boldsymbol{\Sigma}}_{ss}&\left({\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e})\right)^j{\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top{\mathcal{S}}{\boldsymbol{\cal{A}}}{\boldsymbol{\cal{P}}}_e\\
&\qquad\qquad\Big(({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e}){\boldsymbol{\cal{A}}}{\boldsymbol{\cal{P}}}_e\Big)^j\Big).
\end{split}$$ Let us assume that the factors $c_{k_m}$ are set to $\frac{1}{j_k}$, and ${\mathcal{N}}_{k_m}\cap{\mathcal{C}}_k={\mathcal{C}}_k$ for all $m$. We further assume that $a_{k_n,k_m}$ are set to $\frac{1}{j_k}$ for all $n$. In this case, it can be verified that ${\boldsymbol{\cal{A}}}={\boldsymbol{\cal{A}}}^\top$, ${\boldsymbol{\cal{A}}}^\top({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e})=({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e}){\boldsymbol{\cal{A}}}^\top$, and ${\boldsymbol{\cal{A}}}^\top{\mathcal{S}}{\boldsymbol{\cal{A}}}={\mathcal{S}}$. Thus, $\zeta^\star$ can be written alternatively as: $$\begin{split}
\zeta^\star=\mu^2\sum_{j=0}^{+\infty}{\text{tr}}\Big({\boldsymbol{\Sigma}}_{ss}&{\boldsymbol{\cal{A}}}^\top\underbrace{\left({\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e})\right)^j}_{{\mathcal{W}}_j}{\boldsymbol{\cal{P}}}_e\cdot\\
&~~{\mathcal{S}}{\boldsymbol{\cal{P}}}_e\underbrace{\Big(({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e}){\boldsymbol{\cal{A}}}{\boldsymbol{\cal{P}}}_e\Big)^j}_{{\mathcal{W}}_j^\top}{\boldsymbol{\cal{A}}}\Big).
\end{split}$$ Using ${\boldsymbol{\cal{A}}}^\top{\mathcal{S}}{\boldsymbol{\cal{A}}}={\mathcal{S}}$, $\zeta^\star_1$ can be written alternatively as: $$\begin{split}
\zeta^\star_1=\mu^2\sum_{j=0}^{+\infty}{\text{tr}}\Big({\boldsymbol{\Sigma}}_{ss}&\underbrace{\left({\boldsymbol{\cal{P}}}_e{\boldsymbol{\cal{A}}}^\top({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e})\right)^j}_{{\mathcal{W}}_j}{\boldsymbol{\cal{P}}}_e\cdot\\
&~~{\mathcal{S}}{\boldsymbol{\cal{P}}}_e\underbrace{\Big(({\boldsymbol{I}}-\mu{\boldsymbol{\cal{R}}}_{x,e}){\boldsymbol{\cal{A}}}{\boldsymbol{\cal{P}}}_e\Big)^j}_{{\mathcal{W}}_j^\top}\Big).
\end{split}$$ Hence, we obtain: $$\begin{split}
&\zeta^\star-\zeta^\star_1\\
&=\mu^2\sum_{j=0}^{+\infty}{\text{tr}}\left({\boldsymbol{\Sigma}}_{ss}\left({\boldsymbol{\cal{A}}}^\top{\mathcal{W}}_j{\boldsymbol{\cal{P}}}_e{\mathcal{S}}{\boldsymbol{\cal{P}}}_e{\mathcal{W}}_j^\top{\boldsymbol{\cal{A}}}-{\mathcal{W}}_j{\boldsymbol{\cal{P}}}_e{\mathcal{S}}{\boldsymbol{\cal{P}}}_e{\mathcal{W}}_j^\top\right)\right).
\end{split}$$ When ${\boldsymbol{\Sigma}}_{ss}=\frac{1}{N_e}{\boldsymbol{I}}$, we obtain: $$\begin{split}
&\zeta^\star-\zeta^\star_1\\
&=\frac{\mu^2}{N_e}\sum_{j=0}^{+\infty}{\text{tr}}\left({\boldsymbol{\cal{A}}}^\top{\mathcal{W}}_j{\boldsymbol{\cal{P}}}_e{\mathcal{S}}{\boldsymbol{\cal{P}}}_e{\mathcal{W}}_j^\top{\boldsymbol{\cal{A}}}-{\mathcal{W}}_j{\boldsymbol{\cal{P}}}_e{\mathcal{S}}{\boldsymbol{\cal{P}}}_e{\mathcal{W}}_j^\top\right)\leq 0,
\end{split}$$ where we used the fact that ${\text{tr}}({\boldsymbol{\cal{A}}}^\top{\boldsymbol{\cal{H}}}{\boldsymbol{\cal{A}}})\leq{\text{tr}}({\boldsymbol{\cal{H}}})$ for any doubly-stochastic matrix ${\boldsymbol{\cal{A}}}$ and any non-negative matrix ${\boldsymbol{\cal{H}}}$ of compatible dimensions (see Theorem C.3 in \[11\]).

\[<span>![image](figure22.pdf){width="1in" height="1.25in"}</span> \]<span>Roula Nassif</span>

received the bachelor's degree in Electrical Engineering from the Lebanese University, Lebanon, in 2013. She received the M.S. degrees in Industrial Control and Intelligent Systems for Transport from the Lebanese University, Lebanon, and from Compiègne University of Technology, France, in 2013. She received the Ph.D. degree in 2016, from the University of Côte d'Azur (UCA), France. She is currently a researcher and a teaching ppeters@example.com. Her current research interests include adaptation and learning over networks.

\[\]<span>C<span>é</span>dric Richard</span> (S'98–M'01–SM'07) received the Dipl.-Ing. and the M.S. degrees in 1994, and the Ph.D. degree in 1998, from Compiègne University of Technology, France. He is a Full Professor at the University of Nice Sophia Antipolis, France. He was a junior member of the Institut Universitaire de France in 2010-2015.

His current research interests include statistical signal processing and machine learning. Prof. Richard is the author of over 250 papers. He was the General Co-Chair of the IEEE SSP'11 Workshop that was held in Nice, France. He was the Technical Co-Chair of EUSIPCO'15 that was held in Nice, France, and of the IEEE CAMSAP'15 Workshop that was held in Cancun, Mexico. Since 2015, he serves as a Senior Area Editor of the IEEE Transactions on Signal Processing, and as an Associate Editor of the IEEE Transactions on Signal and Information Processing over Networks. He is an Associate Editor of Signal Processing Elsevier since 2009. Prof. Richard is member of the IEEE Machine Learning for Signal Processing Technical Committee, and served as member of the IEEE Signal Processing Theory and Methods Technical Committee in 2009-2014.

\[<span>![image](figure24.pdf){width="1in" height="1.25in"}</span> \]<span>Andr<span>é</span> Ferrari</span>

(SM'91-M'93) received the Ingénieur degree from École Centrale de Lyon, Lyon, France, in 1988 and the M.Sc. and Ph.D. degrees from the University of Nice Sophia Antipolis (UNS), France, in 1989 and 1992, respectively, all in electrical and computer engineering.

He is currently a ppeters@example.com. He is a member of the Joseph-Louis Lagrange Laboratory (CNRS, OCA), where his research activity is centered around statistical signal processing and modeling, with a particular interest in applications to astrophysics.

\[<span>![image](figure25.pdf){width="1in" height="1.25in"}</span> \]<span>Ali H. Sayed</span>

(S'90-M'92-SM'99-F'01) is a professor and former chairman of electrical engineering at the University of California, Los Angeles, where he directs the UCLA Adaptive Systems Laboratory. An author of over 480 scholarly publications and six books, his research involves several areas including adaptation and learning, statistical signal processing, distributed processing, network and data sciences, and biologically-inspired designs. Dr. Sayed has received several awards including the 2015 Education Award from the IEEE Signal Processing Society, the 2014 Athanasios Papoulis Award from the European Association for Signal Processing, the 2013 Meritorious Service Award, and the 2012 Technical Achievement Award from the IEEE Signal Processing Society. Also, the 2005 Terman Award from the American Society for Engineering Education, the 2003 Kuwait Prize, and the 1996 IEEE Donald G. Fink Prize. He served as Distinguished Lecturer for the IEEE Signal Processing Society in 2005 and as Editor-in-Chief of the IEEE TRANSACTIONS ON SIGNAL PROCESSING (2003?2005). His articles received several Best Paper Awards from the IEEE Signal Processing Society (2002, 2005, 2012, 2014). He is a Fellow of the American Association for the Advancement of Science (AAAS). He is recognized as a Highly Cited Researcher by Thomson Reuters. He is serving as President-Elect of the IEEE Signal Processing Society.

[^1]: The work of C. Richard and A. Ferrari was partly supported by ANR and DGA grant ANR-13-ASTR-0030 (ODISSEE project). The work of A. H. Sayed was supported in part by NSF grants CIF-1524250 and ECCS-1407712.

    R. Nassif, C. Richard, and A. Ferrari are with the Universit<span>é</span> de Nice Sophia-Antipolis, France (email: ppeters@example.com; ppeters@example.com; ppeters@example.com).

    A. H. Sayed is with the department of electrical engineering, University of California, Los Angeles, USA (email: ppeters@example.com).

[^2]: We show in Appendix D that, for the perfect model scenario, the steady-state MSD is lower when the combination step is the last step in the algorithm.

{'source': 'arXiv_out/1610'}