A distributed estimation method over network based on compressed sensing

Abstract

This article presents a distributed estimation method called compressed-combine-reconstruct-adaptive to estimate an unknown sparse parameter of interest from noisy measurement over networks based on compressed sensing. It is useful in some distributed networks where the robustness and low consumption are desired features. The compressed sensing theory is introduced in the distributed estimation to further reduce the communication load as the unknown parameter of interest is sparse in many situations. With the proposed method, each node compresses its estimation in a compressed dimension form. The nodes only exchange their compressed estimations to reduce the communication load over the network. Next, each node combines the compressed estimations of neighbors with its own compressed estimation using combination coefficients depend on the topology of the network. Then, the compressed estimations are reconstructed in full dimension form with a reconstruction algorithm. At last, the nodes update their estimations with normalized least mean square algorithm. The stability analysis of the proposed compressed-combine-reconstruct-adaptive method is illustrated in this article. Our method is compared with standard diffusion methods and communication reduced methods in simulations. The results show that the compressed-combine-reconstruct-adaptive method achieves nearly the same performance as the standard diffusion methods while reducing the communication load significantly, and with a better performance (network mean square error), network mean square error, steady-state mean-square deviation and steady-state mean-square deviation) than other communication reduced methods.

Introduction

In a network like wireless sensor network, sensor nodes collect data in a distributed way in applications such as target localization and tracking, environment monitoring, spectrum sensing and so on. An unknown common parameter of interest is the distortion of the collected regression data by noise, which occurs when the local copy of the underlying system input signal at each node is corrupt by various sources of impairment such as measurement or quantization noise. ¹ A critical issue is how to estimate the unknown parameter from the obtained data from each node over the network.

To solve the problem of parameter estimation in a network has two main strategies: one is centralized strategy and the other is distributed strategy. In a centralized strategy, all the nodes send the information to a central node to process and estimate the unknown parameter. Since the distributed networks are usually limited with energy and the communications between nodes are multi-hop, distributed strategies have attracted more and more attention. In a distributed strategy, each node estimates the parameter based on its own local computation and the estimation information received from its neighbors without the need for the central node. ² One approach of the existing distributed strategies can be classified into incremental,^3,4 diffusion^1,5–8 and hierarchical methods.^9,10 The diffusion least mean square (LMS) method is the most popular strategy, and we focus on it in this article. Each node performs an LMS update after exchanging the estimation with its neighbors in a diffusion method. ⁶ Compared with the centralized strategy, it can achieve the scalability, robustness and low communication load. There are many distributed diffusion methods proposed in articles. In work, ⁵ a simple adaptive diffusion LMS method is illustrated. Cattivelli and Sayed ⁶ analyzed the performance of combine-then-adapt (CTA) and adapt-then-combine (ATC) diffusion methods in a distributed network. Fernandezbes et al. ⁸ use the normalize step-size in the adaptive stage to adapt the input signal. As most networks contain a large number of nodes and the dimensions of the unknown parameter may be incredibly high, the communication load of estimation is still considerable in a distributed diffusion method. To further reduce the communication load, reduced-communication diffusion LMS (RC-DLMS) method allows each node to receive the intermediate estimations of a subset of its neighbors. ¹¹ The set-membership normalized LMS (SM-NLMS) ¹² reduces the communication load with selective cooperation. In the study by Wang et al., ¹³ they use a intermittent diffusion method called adapt-thenintermittently-combine (ATIC). However, these methods reduce the communication load at the cost of the performance of parameter estimation. The other approach of distributed strategies is distributed consensus method. Distributed consensus strategies develop into an elegant procedure to enforce agreement among cooperating nodes. The work by Sayed and Tu ¹⁴ confirms that diffusion networks are shown to converge faster and reach lower mean-square deviation than consensus networks.

Since the unknown parameter of interest is sparse, containing only a few non-zero elements among many negligible ones in various applications,^15–17 we introduce the compressed sensing (CS) theory in this article. The CS theory has received much attention in the researcher community. CS has been shown to bring significant performance gain in wide-ranging application from astronomy, biology, communications, image and video processing, medicine, and radar. ¹⁸ By CS, it is possible to reconstruct signal of interest with a number of samples which is far smaller than the desired resolution of signal. ¹⁹ In literature,^15,20 the researchers apply the CS to parameter estimation in a full dimension case by adding another function to consider the sparsity of unknown parameters. Nevertheless, the communication load between nodes is not considered. Xu et al.^21,22 implement the CS in parameter estimation while the input signal in their method needs to be compressed by the same sensing matrix of the estimation, and it is difficult to operate.

Considering the communication load in a distributed network, we propose a new distributed estimation method which called compressed-combine-reconstruct-adaptive (CCRA) in this article. First, with the CCRA method, each node translates its estimation in full dimension form into a compressed dimension form so that the nodes only need to transmit the estimation in compressed form. Then, each node combines the compressed estimations from neighbors with its local compressed estimation. Next, they reconstruct the compressed estimations in the full dimension form accurately with a reconstruction algorithm called Stagewise Orthogonal Matching Pursuit (StOMP). At last, each node performs a LMS update of estimation with a normalized step-size. Moreover, by using the proposed CCRA method, the communication load in the whole network has significantly reduced without affecting the estimation performance.

This article is organized as follows. In section “Problem statement,” we state the distributed estimation problem and define the cost functions. Then, the derivation of the diffusion solution method is presented. In section “The proposed CCRA method,” we introduce the CS theory and describe our CCRA method. In section “Stability analysis,” the stability analyze of the CCRA method is illustrated. In section “Stability analysis,” we provide the detail simulation results of a distributed network with 20 nodes to illustrate the performance of our method compared with the existing standard and communication reduction diffusion methods. In section “Conclusion,” we have a conclusion to this article.

Problem statement

Network model

In this article, we consider a network with N nodes which is in a topology connected with each other illustrated in Figure 1. The nodes are denoted by neighbors as they can exchange their information directly without transferring. A usual linear regression model is shown as follows

$$d_i(t)=w_o^T{u}_i(t)+v_i(t)$$

(1)

Figure 1.

Model of a simple distributed network.

The node i output, a scalar measurement $d_i(t)$ in instant time t, relates to the input regression vector $u_i(t)$ and the true parameter $w_o$ , where $d_i(t)$ is a scalar value. The $u_i(t)$ is an M × 1 vector and so is the $w_o$ . We assume that $w_o$ is a sparse vector with S << M non-zero coefficients. $v_i(t)$ denotes the observation noise or disturbance of each node i, and we assume that $v_i(t)$ of each node i is independent and unrelated.

Cost function

To achieve an estimation vector $w$ for $w_o$ , the global cost function of the whole network should be minimized given by

$$J_{\mathrm{global}}(w)=\sum _{i=1}^N{E|d_i(t)-u_i^T(t)w)|}^2$$

(2)

where E denotes the expectation operator. Assuming the process $u_i(t)$ is jointly wide sense stationary. A centralized least mean square (LMS) algorithm update which is shown as

$$w(t+1)=w(t)+\mu \sum _{i=1}^N{u}_i(t)(d_i(t)-u_i^T(t)w(t))$$

(3)

where $\mu$  > 0 and $\mu$ is a step size, $w(t)$ is the estimation of $w_o$ in time t.

Distributed diffusion strategy

By the centralized LMS algorithm, the whole network information should be collected and processed in a central node. To send and transmit the information to central node, the communication burden is greatly increased. It is impractical in a distributed network due to the limited resources of nodes. Moreover, if some links fail and change in the network, the centralized algorithm will not have a good performance.

On the contrary, we introduce the distributed diffusion method to overcome these drawbacks. In a distributed estimation method, each node only needs to exchange the information with its neighbors to achieve the estimation. It is assumed that two nodes are connected if they can communicate with each other directly. The neighbor denoted by ${\mathrm{\Omega }}_i$ of node i is a set of nodes (include node i itself), which are connected to the node i. Each node can process its local estimation and get the diffusion estimations from its neighbors. In Figure 1, there is an example of a network consists with 10 nodes. The arrows indicate the connections of the nodes, while the nodes at the end of an arrow can exchange information with each other. The neighbor of node 7 denoted by ${\mathrm{\Omega }}_7$ includes the nodes 3, 5, 6, 7, 8. In this case, the distributed estimation does not collapse even if some nodes fail.

The distributed strategy is commonly performed in two stages: adaption and combination. Based on the topology of the network, the estimations are combined with combination coefficients

$${\gamma }_{\mathrm{ii}}+\sum _{j\in {\mathrm{\Omega }}_i}{\gamma }_{\mathrm{ij}}=1j\ne i$$

(4)

where ${\gamma }_{\mathrm{ii}}$ is the combination coefficient of itself and the ${\gamma }_{\mathrm{ij}}$ is the combination coefficient of the node j and its neighbors, satisfied by equation (4). In this particle, we use the Metropolis rules to get the combination coefficients with equation (5)

$$\{\begin{array}{c}{\gamma }_{\mathrm{ij}}=\frac{1}{max(\left|{\mathrm{\Omega }}_i\right|,\left|{\mathrm{\Omega }}_j\right|)}\mathrm{if}j\in {\mathrm{\Omega }}_{i}j\ne i\hfill \\ {\gamma }_{\mathrm{ij}}=0\mathrm{if}j\notin {\mathrm{\Omega }}_{i}j\ne i\hfill \\ {\gamma }_{\mathrm{ii}}=1-\sum _{j\in {\mathrm{\Omega }}_i}{\gamma }_{\mathrm{ij}}\mathrm{if}j\in {\mathrm{\Omega }}_{i}j\ne i\hfill \end{array}$$

(5)

where $\left|{\mathrm{\Omega }}_i\right|$ denotes the cardinality of the set ${\mathrm{\Omega }}_i$ .

In this article, we seek to estimate the parameter of $w_o$ only by processing the information of the neighbors in a distributed diffusion method. The node i has a priori estimate $w_i(t)$ of parameter $w_o$ in the instant time t. The update function is generated in equation (6)

$$w_i(t+1)=\underset{w_i}{\arg min}\left\{\begin{array}{c}{\gamma }_{\mathrm{ii}}\Vert w_i-w_i(t){\Vert }^2+\hfill \\ \multicolumn{1}{c}{\sum _{j\in {\mathrm{\Omega }}_i,i\ne j}{\gamma }_{\mathrm{ij}}\Vert w_i-w_j(t){\Vert }^2}\\ \multicolumn{1}{c}{+{\mu }_i(d_i(t)-u_i^T(t)w_i{)}^2}\end{array}\right\}$$

(6)

where ${\mu }_i$ is the step size of node i.

To simplify the update function, we expand the last item $(d_i(t)-u_i^T(t)w_i{)}^2$ of the unknown $w_i$ around $w_j(t)$ in Taylor formula

$$\begin{array}{c}(d_i(t)-u_i^T(t)w_i{)}^2\hfill \\ =e_{\mathrm{ij}}^2(t)-2e_{\mathrm{ij}}(t)u_i^T(t)(w_i-w_j(t))+o\Vert w_i{\Vert }^2\hfill \end{array}$$

(7)

where $e_{\mathrm{ij}}(t)=d_i(t)-u_i^T(t)w_j(t)$ .

In the same way, the expansion of the last term around $w_i(t)$ is equation (8)

$$\begin{array}{c}(d_i(t)-u_i^T(t)w_i{)}^2\hfill \\ =e_i^2(t)-2e_i(t)u_i^T(t)(w_i-w_i(t))+o\Vert w_i{\Vert }^2\hfill \end{array}$$

(8)

where $e_i(t)=d_i(t)-u_i^T(t)w_i(t)$ .

Then, we substitute equations (7) and (8) into equation (6). Since the combination coefficients satisfy equation (4), we have the function in equation (9).

$$\begin{array}{c}{w}_i(t+1)\hfill \\ =\underset{w_i}{\arg min}\hfill \\ \left\{\begin{array}{c}{\gamma }_{\mathrm{ii}}\Vert w_i-w_i(t){\Vert }^2+\hfill \\ \multicolumn{1}{c}{\sum _{j\in {\mathrm{\Omega }}_i,i\ne j}{\gamma }_{\mathrm{ij}}\Vert w_i-w_j(t){\Vert }^2+}\\ \multicolumn{1}{c}{{\mu }_{\mathrm{i}}{\gamma }_{\mathrm{ii}}[e_i^2(t)-2e_i(t)u_i^T(t)(w_i-w_i(t))]}\\ \multicolumn{1}{c}{+{\mu }_i{\gamma }_{\mathrm{ij}}\sum _{j\in {\mathrm{\Omega }}_i,i\ne j}[e_{\mathrm{ij}}^2(t)-2e_{\mathrm{ij}}(t)w_j(t)u_i^T(t)(w_i-w_j(t))]}\end{array}\right\}\hfill \end{array}$$

(9)

The term of the big large brackets is a function of the $w_i$ . To get the $w_i(t+1)$ , we differentiate the function of $w_i$ and let it equal to 0. Then the distributed update estimation $w_i(t+1)$ is shown as follows

$$w_i(t+1)={\mathit{\phi }}_i(t+1)+{\mu }_i{u}_i(t)(d_i(t)-u_i^T(t){\mathit{\phi }}_i(t+1))$$

(10)

where

$${\mathit{\phi }}_i(t+1)={\gamma }_{\mathrm{ii}}{w}_i(t)+\sum _{j\in {\mathrm{\Omega }}_i,i\ne j}{\gamma }_{\mathrm{ij}}{w}_j(t)$$

(11)

Equation (10) is regarded as the combination stage and equation (11) is the adaptive stage. The distributed diffusion LMS is shown in Figure 2.

Figure 2.

Distributed diffusion strategy.

The proposed CCRA method

CS

By the strategy in Section 2, the amount of information exchange is reduced. The communication burden is still considerable in an energy-limited network since the $w_i(t)$ is full dimension vector of (M x 1). To further reduce the communication burden and improve the network performance, the CS theory is introduced in this method. CS is an emerging field in signal processing. By CS theory, the sparse signals can be reconstructed from what was previously believed to be incomplete measurements.

We consider the $w$ is an M x 1 vector with S sparsity and $\mathrm{\Phi }$ is called a sensing matrix of D x M where D ≪ M. The basic compress model is defined in equation (12)

$$\overline{w}=\mathrm{\Gamma }w$$

(12)

Since both $\mathrm{\Gamma }$ and $\overline{w}$ are exactly known in the compressed phase, it is easy to get the $\overline{w}$ vector of D x 1 dimension which is called compressed vector. The term of model means that each element of $\overline{w}$ is obtained as inner product between the vector $\mathrm{w}$ and each row vector of $\mathrm{\Gamma }$ . ²²

As equation (12) is an underdetermined equation, it is hard to acquire the original vector $\overline{w}$ by the known compressed vector and sensing matrix in the reconstruction phase. The CS theory suggests that, under some conditions, we can fully reconstruct the original vector. Since the vector $w$ is S-sparse which means that the $w$ has less than s non-zero elements in an orthonormal basis. An D x M i.i.d. Gaussian matrix $\mathrm{\Gamma }$ can be shown to have the restricted isometry property (RIP) with high probability if $D\ge \tau K\log (M/K)$ , where $\tau$ is a small constant. ²³ A natural and straightforward approach to obtain a sparse solution from the underdetermined equation (12) will be formulated as the optimization problem

$$\underset{w}{\arg min}\Vert w{\Vert }_{\ell 0}\mathrm{subject}\mathrm{to}\overline{w}=\mathrm{\Gamma }w$$

(13)

The solution is still difficult to solve because it is an non-deterministic polynomial (NP)-hard problem. We can replace $\ell 0$ norm by $\ell 1$ norm

$$\underset{w}{\arg min}\Vert w{\Vert }_{\ell 1}\mathrm{subject}\mathrm{to}\overline{w}=\mathrm{\Gamma }w$$

(14)

It is shown that the optimization solution in equations (13) and (14) are the same if the vector is sufficiently sparse. ²⁴ There are many reconstruction algorithms to pursue sparse solutions with, which are proposed by researchers such as basis pursuit (BP), ²⁴ orthogonal matching pursuit (OMP), ²⁵ subspace pursuit (SP), ²⁶ precognition matching pursuit (PMP) ²⁷ and so on. In this article, we use Stagewise Orthogonal Matching Pursuit (StOMP) to reconstruct the signal which can reconstruct the compressed vector without setting its sparsity. ²⁸ The reconstruction phase is denoted as $\hslash (•)$

$$w=\hslash (\overline{w})$$

(15)

CCRA method

In the proposed method in this article, we add the compressed stage and reconstruction stage in the standard diffusion method. Our method can be denoted as the CCRA. At the first stage in instant time t, each node acquires its local compressed estimation by own calculation. The compressed stage in function is shown in equation (16)

$${\overline{w}}_i(t)={\mathrm{\Gamma }}_i{w}_i(t)i\in N$$

(16)

Then, the information exchanges between the nodes are the compressed estimations that are described in equation (17)

$${\overline{\mathit{\phi }}}_i(t+1)={\gamma }_{\mathrm{ii}}{\overline{w}}_i(t)+\sum _{j\in {\mathrm{\Omega }}_i,i\ne j}{\gamma }_{\mathrm{ij}}{\overline{w}}_j(t)$$

(17)

Similar to equation (11), the compressed ${\overline{\phi }}_i(t+1)$ is used instead of ${\mathit{\phi }}_i(t+1)$ and ${\overline{w}}_i(t)$ instead of $w_i(t)$ . Then the node i in time instant t reconstructs ${\mathit{\phi }}_i(t+1)$ by operating the StOMP algorithm just once since equation (17) in a linear function. It is denoted by equation (18)

$${\mathit{\phi }}_i(t+1)=\hslash ({\overline{\mathit{\phi }}}_i(t+1))$$

(18)

Since the performance of the LMS algorithm depends strongly on the step size parameter $\mu$ , the normalized algorithm is proposed. We use the ${{\mu }_i}^{\prime }={\mu }_i/u_i^T(t)u_i(t)$ instead of ${\mu }_i$ . With the function in equation (19), the $w_i(t+1)$ is obtained since ${\mathit{\phi }}_i(t+1)$ has been acquired

$$w_i(t+1)={\mathit{\phi }}_i(t+1)+{{\mu }_i}^{\prime }{u}_i(t)(d_i(t)-u_i^T(t){\mathit{\phi }}_{\mathrm{i}}(t+1))$$

(19)

The proposed distributed CCRA method is shown in Figure 3.

Figure 3.

CCRA method.

Compared with the standard CTA diffusion algorithm, there are two more stages. With the help of the compressed stage, the dimension of the exchange information is reduced from M x 1 to D x 1. The reconstruction stage is to insure that the adaptive stage works. Through the proposed CCRA method, the communication burden is significantly reduced while the estimation is obtained. Here is the process running of CCRA in Table 1.

Table I.

Process running of CCRA.

Initialize:

For each node i $w_i(0)=0$ for where $w_i$ is M x 1 estimation vector

end

Running:

For each time instant t = 1,2,…, T

For each node i = 1,2,…,N

Compressed ${\overline{w}}_i(t)={\mathrm{\Gamma }}_i{w}_i(t)$ where ${\mathrm{\Gamma }}_i$ is a D x M sensing matrix.

end

For each node i = 1,2,…,N

Combination ${\overline{\phi }}_i(t+1)={\gamma }_{\mathrm{ii}}{\overline{w}}_i(t)+\sum _{j\in {\mathrm{\Omega }}_i,i\ne j}{\gamma }_{\mathrm{ij}}{\overline{w}}_j(t)$

Reconstruction ${\mathit{\phi }}_i(t+1)=\hslash ({\overline{\phi }}_i(t+1))$

Adaptation $w_i(t+1)={\mathit{\phi }}_i(t+1)+{{\mu }^{\prime }}_i{u}_i(t)(d_i(t)-u_i^T(t){\mathit{\phi }}_i(t+1))$

end

end

Stability analysis

To analyze the stability of the whole network, we introduce the global state–space model with representation to describe it. The quantities of the whole network are defined as the priori estimation vector of the whole network $\mathit{\phi }(t)\stackrel{\mathrm{\Delta }}{=}\mathrm{col}\{\begin{array}{ccc}{\mathit{\phi }}_1(t),\hfill & \dots ,\hfill & {\mathit{\phi }}_N\hfill \end{array}(t)\}$ and the estimation vector $W(t)\stackrel{\mathrm{\Delta }}{=}\mathrm{col}\{\begin{array}{ccc}{w}_1(t),\hfill & \dots ,\hfill & w_N\hfill \end{array}(t)\}$ are MN x 1 dimensions;

The compressed priori estimation vector $\overline{\phi }(t)\stackrel{\mathrm{\Delta }}{=}\mathrm{col}\{\begin{array}{ccc}{\overline{\phi }}_1(t),\hfill & \dots ,\hfill & {\overline{\phi }}_N\hfill \end{array}(t)\}$ and the compressed estimation vector $\overline{W}(t)\stackrel{\mathrm{\Delta }}{=}\mathrm{col}\{\begin{array}{ccc}{\overline{w}}_1(t),\hfill & \dots ,\hfill & {\overline{w}}_N\hfill \end{array}(t)\}$ are DN x 1 dimensions; the global regression matrix is $U(t)\stackrel{\mathrm{\Delta }}{=}\left[\begin{array}{ccc}{u}_1(t)\hfill & \dots \hfill & 0\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{0}& \cdots \hfill & u_N(t)\hfill \end{array}\right]$ with MN x N dimensions. The global measurement matrix $d(t)\stackrel{\mathrm{\Delta }}{=}\mathrm{col}\{\begin{array}{ccc}{d}_1(t),\hfill & \dots ,\hfill & d_N\hfill \end{array}(t)\}$ and the global noise vector $V(t)\stackrel{\mathrm{\Delta }}{=}\mathrm{col}\{\begin{array}{ccc}{v}_1(t),\hfill & \dots ,\hfill & v_N(t)\hfill \end{array})\}$ are N x 1 dimensions. The $\mathrm{\mu }\prime \stackrel{\mathrm{\Delta }}{=}\mathrm{diag}\left\{\begin{array}{ccc}{{\mu }^{\prime }}_1{\mathrm{I}}_{\mathrm{M}},\hfill & \dots ,\hfill & {{\mu }^{\prime }}_N{\mathrm{I}}_{\mathrm{M}}\hfill \end{array}\right\}$ is the step size matrix with NM x NM dimensions, where the ${\mathrm{I}}_{\mathrm{M}}$ is the identity matrix with M x M dimensions; $\mathrm{\Lambda }\stackrel{\mathrm{\Delta }}{=}\left[\begin{array}{ccc}{\gamma }_{11}\hfill & \dots \hfill & {\gamma }_{1N}\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{{\gamma }_{N1}}& \cdots \hfill & {\gamma }_{\mathrm{NN}}\hfill \end{array}\right]\otimes {\mathrm{I}}_{\mathrm{M}}=\gamma \otimes {\mathrm{I}}_{\mathrm{M}}$ is the global combination matrix with NM x NM, where ⊗ denotes the Kronecker product; $\mathrm{\Gamma }\stackrel{\mathrm{\Delta }}{=}\left[\begin{array}{ccc}{\mathrm{\Gamma }}_1\hfill & \dots \hfill & 0\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{0}& \cdots \hfill & {\mathrm{\Gamma }}_N\hfill \end{array}\right]$ is the global sensing matrix with DN x NM dimensions.

We get the global compressed stage representation: $\overline{W}(t)=\mathrm{\Gamma }W(t)$ and $\overline{\phi }(t)=\mathrm{\Gamma }\phi (t)$ . Then, the combination stage is formed in state-space: $\phi (t+1)=\mathrm{\Lambda }W(t)$ , $\overline{\phi }(t+1)=\mathrm{\Lambda }\overline{W}(t)$ . The reconstruction StOMP algorithm of the global model is denoted by $\mathrm{H}(•)$ . And the global reconstruction stage is obtained by $\phi (t+1)=\mathrm{H}(\overline{\phi }(t+1))$ .

The simple global update function of the linear regression network model without cooperation can be represented as in equation (20)

$$W(t+1)=\phi (t+1)+\mu \prime \mathrm{U}(t)(d(t)-{\mathrm{U}}^T(t)\phi (t+1))$$

(20)

The global update function of the network with the proposed distributed CCRA can be illustrated as in equation (21)

$$\begin{array}{cc}\multicolumn{1}{c}{W(t+1)}& =\mathrm{H}(\mathrm{\Lambda }\mathrm{\Gamma }W(t))\hfill \\ \multicolumn{1}{c}{}& +\mu \prime \mathrm{U}(t)(d(t)-{\mathrm{U}}^{\mathrm{T}}(t)\mathrm{H}(\mathrm{\Lambda }\mathrm{\Gamma }W(t)))\hfill \end{array}$$

(21)

With the StOMP algorithm, we can reconstruct the compressed estimation fully by choosing appropriate sensing matrix and parameter D, the stability in the mean of the function (21) is similar to that of equation (22)

$$W(t+1)=\mathrm{\Lambda }W(t)+\mu \prime U(t)(d(t)-U^T(t)\mathrm{\Lambda }W(t))$$

(22)

The true parameter matrix ${\mathrm{W}}_{\mathrm{o}}$ is denoted as $W_o\stackrel{\mathrm{\Delta }}{=}\mathrm{col}\{w_o{w}_o\dots w_o\}$ with MN x 1 dimensions. So we get the global regression model in state–space representation

$$d(t)=U^T(t)W_o+V(t)$$

(23)

Let us denote the estimation error matrix $\mathrm{\Delta }(t)\stackrel{\mathrm{\Delta }}{=}{W}_o-W(t)$ . So equation (21) can be demonstrated in another form as in equation (24)

$$\begin{array}{c}\mathrm{\Delta }(t+1)=W_o-\mathrm{\Lambda }W(t)\hfill \\ -\mu \prime U(t)(U^T(t)W_o+V(t)-U^T(t)\mathrm{\Lambda }W(t))\hfill \end{array}$$

(24)

Since $\mathrm{\Lambda }{W}_o=W_o$ , the function is equal to the function in equation (25)

$$\begin{array}{c}\mathrm{\Delta }(t+1)=\mathrm{\Lambda }{W}_o-\mathrm{\Lambda }W(t)\hfill \\ -\mu \prime U(t)(U^T(t)\mathrm{\Lambda }{W}_o+V(t)-U^T(t)\mathrm{\Lambda }W(t))\hfill \\ =\mathrm{\Lambda }\mathrm{\Delta }(t)-\mu \prime U(t)(U^T(t)\mathrm{\Lambda }\mathrm{\Delta }(t)-V(t))\hfill \\ =({\mathit{I}}_{\mathrm{MN}}-\mu \prime U(t)U^T(t))\mathrm{\Lambda }\mathrm{\Delta }(t)+\mu \prime U(t)V(t)\hfill \end{array}$$

(25)

Assuming that the regressions are temporal and independent, we take the expectation to the both sides of the equation

$$E(\mathrm{\Delta }(t+1))=(I_{\mathrm{MN}}-\mathrm{\mu }\prime R)\mathrm{\Lambda }\mathrm{E}(\mathrm{\Delta }(t))$$

(26)

where $R=\mathrm{diag}\left\{\begin{array}{ccc}{R}_1,\hfill & \dots ,R_{\mathrm{i}},\dots ,\hfill & R_N\hfill \end{array}\right\}$ and $R_i=E(u_i(t)u_i^T(t))$ .

To achieve the stability in the main of the global network model, the function in equation (27) should hold

$$|\lambda ({\mathrm{I}}_{\mathrm{MN}}-\mu \prime R)\mathrm{\Lambda }|<1$$

(27)

Let the data matrix denotes $\mathrm{X}={\mathrm{I}}_{\mathrm{MN}}-\mu \prime R$ . The convergence of estimation for the whole network depends on the time-variant data matrix $\mathrm{X}$ and the combination matrix $\mathrm{\Lambda }$ . If the whole network operates without cooperation, the function can be illustrated as in equation (28)

$$\begin{array}{c}E(\mathrm{\Delta }(t+1))=({\mathrm{I}}_{\mathrm{MN}}-\mu \prime R)E(\mathrm{\Delta }(t))\hfill \\ |\lambda (\mathrm{X})|<1\hfill \end{array}$$

(28)

While the network operates with cooperation, we should consider $\lambda (\mathrm{X}\mathrm{\Lambda })$ . Since $\mathrm{X}$ is a symmetric matrix, then equation (29) can hold

$$\Vert \mathrm{X}\mathrm{\Lambda }{\Vert }_2\le \Vert \mathrm{X}{\Vert }_2•\Vert \mathrm{\Lambda }{\Vert }_2$$

(29)

So that ${\sigma }_{max}(\mathrm{X}\mathrm{\Lambda })\le {\sigma }_{max}(\mathrm{X})•{\sigma }_{max}(\mathrm{\Lambda })$ , where ${\sigma }_{max}$ is the max singular value of the matrix. Since the $\mathrm{\Lambda }$ is symmetric and ${\sigma }_{max}(\mathrm{\Lambda })=1$ , it is known that ${\sigma }_{max}(\mathrm{X})=|{\lambda }_{max}(\mathrm{X})|$ and $|{\lambda }_{max}(\mathrm{X}\mathrm{\Lambda })|\le {\sigma }_{max}(\mathrm{X}\mathrm{\Lambda })$ , and then we have equation (30)

$$|{\lambda }_{max}(\mathrm{X}\mathrm{\Lambda })|\le |{\lambda }_{max}(\mathrm{X})|$$

(30)

In the other words, the spectral radius of $\mathrm{X}\mathrm{\Lambda }$ is smaller than that of $\mathrm{X}$ . Therefore, the stability in mean of the proposed CCRA method has a stabilizing effect on the LMS algorithm.

Simulation results

To illustrate the performance of the proposed method in this article, we compare it with that obtained by other LMS methods such as DLMS, NDLMS (normalized version), ATIC ⁸ and RC-DLMS. ⁹ The considered network topology is in Figure 4 with N = 20 nodes.

Figure 4.

Network topology in the simulations.

The input regressors are M = 32 vector and generated as sample vectors $u_{i,t}=[u_i(t)u_i(t-1)\dots u_i(t-{\mathrm{M}+1)]}^T$ of an AR-1 process of the form $u_i(t)=x_i(t)+{\rho }_i{u}_i(t-1)$ , where ${\rho }_i$ is a correlation coefficient and $x_i(t)$ is a white process with ${\sigma }_{x,i}=1$ . The trace of each node’s regression matrix $R_i$ is shown in Figure 5. The noise input $v_i(t)$ at each node is zero-mean Gaussian, and we show the variant of each node’s noise in Figure 6. The input regressors and noise are temporary and spatially independent of each other. The parameter vector to be estimated has S sparsity where S = 2. The sensing matrix ${\mathrm{\Gamma }}_i$ is an i.i.d. Gaussian matrix with D x M dimensions, where D = 12 and keep constant. The step size of DLMS, DLMS without cooperation, ATIC and RC-DLMS is set to $\mu =0.01$ . The step of the normalized version as NDLMS and the proposed CCRA is set to $\mu =0.4/u_i^T(t)u_i(t)$ . The period length of ATIC method is set to 2, and the selection probability parameter of RC-DLMS is 0.5. All the curves shown in the figures are the average results of 50 independent runs.

Figure 5.

Trace of regression matrices.

Figure 6.

Noise variance.

For performance metric, we used mean-square error (MSE) of the whole network defined as $\mathrm{MSE}\left(\mathrm{dB}\right)=20\log \left(\frac{1}{N}E{\Vert d(t)-U^T(t)W(t)\Vert }_2\right)$ . Figure 7 shows that the proposed CCRA method has a faster convergence compared with the other methods. Then, we use mean-square deviation (MSD) of the whole network defined as $\mathrm{MSD}\left(\mathrm{dB}\right)=20\log \left(\frac{1}{N}E{\Vert W(t)-W_o\Vert }_2\right)$ and it is shown in Figure 8. At the instant time 520, the network MSD of the proposed CCRA is below −50 dB, while the other methods with cooperation is nearly −50 dB about at the time 1200. As a result in Figures 7 and 8, the proposed CCRA achieves a better convergence rate and a same or better performance in network MSD or network MSE than other methods.

Figure 7.

Network MSE performance.

Figure 8.

Network MSD performance.

To evaluate the performance in the steady state, we average the data of the last 500 time instant as steady state. We define the steady state MSE of node i as $\mathrm{MS}{\mathrm{E}}_i\left(\mathrm{dB}\right)=20\log \left(E{\Vert d_i(t)-u_i^T(t)w_i(t)\Vert }_2\right)$ and steady state MSD as $\mathrm{MS}{\mathrm{D}}_{\mathrm{i}}\left(\mathrm{dB}\right)=20\log \left(E{\Vert w-w_i(t)\Vert }_2\right)$ . In Figure 9, the steady state MSE of CCRA method in this article is about −60 dB which is slightly smaller than the MSE of the other methods with cooperation. Figure 10 shows that the steady state MSE of the CCRA is about −55 dB while the MSD of the other methods with cooperation is between −49 dB and −47 dB.

Figure 9.

Steady state MSE performance per node.

Figure 10.

Steady state MSD performance per node.

Since the DLMS and NDLMS method use a standard diffusion method in communication, ATIC, RC-DLMS and the proposed CCRA are designed to reduce the communication load in different ways. Figure 11 shows the communication load under our simulation for each method. It can be seen that the standard diffusion method has 12,800 dimensions to send and receive in the whole network. The ATIC and RC-DLMS can reduce the communication load to 6400 on average, while they almost achieve the performance of the standard method. Furthermore, the proposed CCRA method in this article reduces the communication load to 4800 without affecting the performance of the network.

Figure 11.

Communication load of the network.

Conclusion

We present a distributed estimation method over network called CCRA to reduce the communication load based on CS. The derivation of diffusion algorithm is illustrated. In this method, only a compressed estimation is distributed between nodes in the network as the unknown parameter is sparse. We describe the whole network in a global state–space model and analyze the global stability in the proposed CCRA method. Compared with other existing methods in the simulation, we achieve the same or better performance (including network MSD, network MSE, steady-state MSD and steady-state MSD) and faster convergence by using the proposed CCRA while reducing the communication load significantly.