# A DCT Regularized Matrix Completion Algorithm for Energy Efficient Data Gathering in Wireless Sensor Networks

Authors: Kefu Yi; Jiangwen Wan; Tianyue Bao; Lei Yao
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

This paper presents a novel matrix completion algorithm to enable energy efficient data gathering in wireless sensor networks. The algorithm takes full advantage of both the low-rankness and the DCT compactness features in the sensory data to improve the recovery accuracy. The time complexity of the algorithm is analyzed, which indicates it has a low computational cost. Moreover, the recovery error is carefully analyzed and a theoretical upper bound is derived. The error bound is then validated by experimental results. Extensive experiments are conducted on three datasets collected from two testbeds. Experimental results show that the proposed algorithm outperforms state-of-the-art methods for low sampling rate and achieves a good recovery accuracy even if the sampling rate is very low.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) have been widely used in a variety of applications such as precision agriculture [1], personal health monitoring [2], and environment surveillance [3], in which sensor nodes with limited battery energy are deployed and periodically report their sensor readings to the base station or sink node. Therefore, a key issue in wireless sensor networks is how to efficiently gather these data from sensors provided with only limited energy resources. In the classical data gathering approach [4], each sensor node simply forwards its sensor readings to the sink, resulting in a large amount of traffic and energy consumption.Recently, Compressive Sensing (CS) [5, 6] has emerged as a new approach to tackle the efficient data gathering problem in WSNs. Taking advantage of the sparsity in sensor readings, CS based methods [7–9] require fewer data packets than the classical approach. However, there are many practical problems when applying CS to data gathering in WSNs. Firstly, CS based methods require a prior dictionary to sparsify the sensor readings. Secondly, the measurement matrix in CS is composed of independent and identically distributed random Gaussian entries, which is dense with very few zero elements. Therefore, sensor nodes need to sample all sensor readings and perform a considerable number of measurement operations, resulting in a large amount of energy waste. Thirdly, CS requires the number of measurements to exceed a certain threshold (depending on the sparsity level of sensor readings) to achieve exact recovery. However, the realistic sensor signal is not always exactly sparse as it should be. Therefore, low sampling rate may lead to insufficient measurements and result in a bad recovery accuracy.As an extension of CS, matrix completion [10] has shown its potential for enabling efficient data gathering in WSNs. Because the sensor readings are highly temporal-spatial correlated, the data matrix structured by the sensor readings will approximate to a low-rank matrix. Therefore, the sink node can gather only a few of the total sensor readings and adopt the matrix completion algorithm to reconstruct the missing data. However, unlike CS based methods, matrix completion based methods do not require the prior dictionary to sparsify the original signal. Furthermore, the sampling matrix (or measurement matrix) in matrix completion is much sparser than CS, which makes it more suitable for wireless sensor networks.Utilizing the low-rankness feature in sensory data, there are many pioneering works [11–13] on applying matrix completion to WSN, which adopt the alternating least squares technique to estimate the low-rank matrix. The recovery accuracy is further improved by utilizing the spatiotemporal structure in the WSN data. However, the improvement is limited because the spatiotemporal structure directly implies the low-rank feature, and in some sense, these two features are equivalent. Moreover, the alternating least squares algorithm does not scale to large rank.Besides the low-rankness feature, we observe that the sensor readings in WSNs also exhibit Discrete Cosine Transform (DCT) compactness feature. In other words, the sensor readings can be approximated by only a small number of DCT coefficients. Therefore, by taking full advantage of the DCT compactness feature of the WSNs data, in this paper, we propose a DCT Regularized Matrix Completion (DRMC) algorithm. We analyze the time complexity of DRMC, which indicates that the proposed algorithm has a low computational cost. Moreover, we analyze the recovery error of DRMC and derive a theoretical upper bound. The error bound is then validated by experimental results. Extensive experiments are carried out on three datasets that are collected from two realistic WSN testbeds. We compare the performance of DRMC with state-of-the-art methods. Experimental results show that DRMC outperforms state-of-the-art methods for low sampling rate and achieves a good recovery accuracy even if the sampling rate is very low.The main contributions of this paper are summarized in the following:(i)
We examine the sensor data collected from real-world WSNs, which reveal two data features: (1)low-rankness, (2)DCT compactness.(ii)
Inspired by these observations, we design a novelDCT Regularized Matrix Completion (DRMC) algorithm to estimate the missing sensory data. Experimental results indicate that DRMC outperforms state-of-the-art methods when the sampling rate is low.(iii)
We analyze the time complexity of the DRMC algorithm, which indicates that DRMC has a low computational cost.(iv)
We analyze the recovery error of the DRMC algorithm and derive a theoretical upper bound, which is then validated by experimental results.The rest of this paper is organized as follows. Section2 reviews the state-of-the-art methods. Section 3 models the problem. Section 4 examines the data features in WSNs. Section 5 proposes the DRMC algorithm. Section 6 analyzes the time complexity of the algorithm. Section 7 analyzes the recovery error of the algorithm. Section 8 evaluates the effectiveness of the proposed algorithm. Section 9 concludes this paper.


## 2. Related Works

In this section, we make a brief review of previous works related to the data gathering problem in wireless sensor networks.


### 2.1. Compressive Sensing

Compressive Sensing (CS) theory suggests that sparse signals can be accurately reconstructed from only a small number of measurements [5, 6]. It is a new paradigm for signal processing of networked data [7] and there are many CS based methods for data gathering in wireless sensor networks. Luo et al. proposed a data gathering scheme that applies Compressive Sensing theory to reduce communication cost [14]. Quer et al. presented a framework for data gathering and signals recovery in actual WSN deployments with the integration of CS [9]. Ebrahimi and Assi recently proposed a decentralized method to apply the Compressive Sensing to data gathering in wireless sensor networks [15].


### 2.2. Matrix Completion

Recently, there are many applications that apply matrix completion technique to wireless sensor networks. Utilizing the low-rankness and spatiotemporal correlation, Zhang et al. proposed a method to recover the lost data in internet traffic matrices [13]. Kong et al. designed an algorithm using the low-rank structure, time stability, space similarity, and multiattribute correlation to estimate the missing data in highly incomplete data matrix [12]. Cheng et al. presented a Spatiotemporal Compressive Data Collection (STCDG) algorithm that utilizes the low-rankness and short-term stability features to reduce data traffic in WSNs [11].In our earlier work [16], we have studied the data recovery problem in wireless sensor networks when historical data are available and proposed a DCT-Regularized Partial Matrix Completion (DCT-RPMC) algorithm. However, the new algorithm proposed in this paper does not depend on any historical data, which greatly widens its applicability to more general scenarios.


## 2.1. Compressive Sensing

Compressive Sensing (CS) theory suggests that sparse signals can be accurately reconstructed from only a small number of measurements [5, 6]. It is a new paradigm for signal processing of networked data [7] and there are many CS based methods for data gathering in wireless sensor networks. Luo et al. proposed a data gathering scheme that applies Compressive Sensing theory to reduce communication cost [14]. Quer et al. presented a framework for data gathering and signals recovery in actual WSN deployments with the integration of CS [9]. Ebrahimi and Assi recently proposed a decentralized method to apply the Compressive Sensing to data gathering in wireless sensor networks [15].


## 2.2. Matrix Completion

Recently, there are many applications that apply matrix completion technique to wireless sensor networks. Utilizing the low-rankness and spatiotemporal correlation, Zhang et al. proposed a method to recover the lost data in internet traffic matrices [13]. Kong et al. designed an algorithm using the low-rank structure, time stability, space similarity, and multiattribute correlation to estimate the missing data in highly incomplete data matrix [12]. Cheng et al. presented a Spatiotemporal Compressive Data Collection (STCDG) algorithm that utilizes the low-rankness and short-term stability features to reduce data traffic in WSNs [11].In our earlier work [16], we have studied the data recovery problem in wireless sensor networks when historical data are available and proposed a DCT-Regularized Partial Matrix Completion (DCT-RPMC) algorithm. However, the new algorithm proposed in this paper does not depend on any historical data, which greatly widens its applicability to more general scenarios.


## 3. Problem Formulation

In this section, we formally formulate the data gathering and recovery problem in wireless sensor networks and state the goal of this paper. The main notations that will be used in the rest of this paper are listed in Summary of Notations.Assume that the network is composed ofn sensor nodes. During a certain sampling period, the ith sensor node acquires m samples, which are modeled as an m-dimensional sensor vector x→i,(1)x→i=xi,0,xi,ΔT,…,xi,m-1ΔTT,where ΔT is the sampling period. Therefore, the entire samples in the network can be organized as an environment matrix X∈Rm×n,(2)X=x→1,x→2,…,x→n.In order to reduce energy consumption, only a fraction of the entries ofX will be transmitted to the sink node. We then define a matrix M∈Rm×n as the sampling matrix to indicate which parts of X are transmitted to the sink:(3)Mi,j=1,ifXi,jistransmitted,0,otherwise.And the sampling rate τ is defined in the following:(4)τ=∑i,jMi,jmn.LetY∈Rm×n denote the data transmitted to the sink. Y is an incomplete version of X, with missing entries replaced by zeros. Therefore, we have(5)Y=M∘X.The symbol ∘ denotes the element-wise matrix production operator.After obtainingY, the sink can reconstruct the original environment matrix X with the proposed algorithm in Section 5. Our goal is to generate a reconstructed matrix X^ that approximates to the original environment matrix X as closely as possible. We measure the recovery performance by the Normalized Mean Absolute Error (NMAE):(6)NMAE=∑i,j:Mi,j=0Xi,j-X^i,j∑i,j:Mi,j=0Xi,j.


## 4. Exploring the Data Features

In this section, we examine the data features in real-world wireless sensor networks.


### 4.1. Experimental Datasets

We use three datasets, which are collected from two WSN testbeds, to serve as the ground truth. The summary of the datasets is shown in Table1.Table 1
Experimental datasets.
Data name
Matrix size
Time interval
Intel Temperature
54 nodes × 96 intervals
10 minutes
Intel Humidity
54 nodes × 96 intervals
10 minutes
PARED Temperature
50 nodes × 96 intervals
10 minutesThe first category of datasets is collected by 54 Mica2Dot nodes deployed in the Intel Berkeley Research Lab [17] between February 28 and April 5, 2004. The Mica2Dot node reports collected sensor data including humidity and temperature once every 30 seconds. However, we find that the raw dataset has considerable missing data. Therefore, we have rearranged the raw data (by changing the reporting interval from 30 seconds to 10 minutes) to avoid the missing data.The second category of dataset consists of temperature readings, which are collected with a 10-minute interval by our own testbed, namely, PARED. PARED consists of 50 sensor nodes. More details about PARED can be found in [18].


### 4.2.  Low-Rank Structure

We first examine the low-rank structure in WSN datasets using the Singular Value Decomposition (SVD). The environment matrixX can be decomposed into three matrices by SVD:(7)X=UΣVT,where U is an m×m orthonormal matrix, V is an n×n orthonormal matrix, and Σ is an m×n diagonal matrix with singular values σ1,σ2⋯σp sorted in a descending order (p=min⁡(m,n)).Because sensor readings in a WSN are spatiotemporal correlated, the environment matrixX would exhibit low-rank feature. More exactly, X should approximate to a low-rank matrix of rank r. So, the first r singular values will occupy the most energy of X. We use the following as the metric to examine the quality of the low-rank approximation:(8)gr=∑i=1rσiX∗=∑i=1rσi∑i=1pσi,where ·∗ is the nuclear norm and X∗=∑i=1p‍σi.Figure1 shows the low-rank approximation quality of the three datasets. We found that the largest 10 singular values occupy the 93%–99% of the total energy, which suggests that the WSN datasets exhibit a good low-rank feature.Figure 1
Low-rankness feature.


### 4.3.  DCT Compactness

We also observed that the sensor readings in WSN exhibit DCT compactness feature. In other words, the firstk DCT coefficients of the sensor vector x→i concentrate the most energy of x→i.We first defineD as the m×m Discrete Cosine Transform Matrix:(9)Di,j=2mcos⁡πmi-12j-12.Then, the m×m orthonormal matrix D can be divided into two submatrices:(10)D=D1D2,where D1 consists of the first k rows of D and D2 consists of the last m-k rows of D.Therefore, if the firstk DCT coefficients occupy the most energy of x→i, we will have D1x→i2/x→i2≈1 and D2x→i2/x→i2≈0. Similarly, for the matrix form, we will have D1XF/XF≈1 and D2XF/XF≈0, where ∗F is the Frobenius norm with XF=∑i,j‍X(i,j)2. So, we use the following function to examine the DCT compactness feature:(11)hk=D1XFXF.From Figure2, we can see that the first 10 DCT coefficients concentrate 99% of the total energy, which suggests that these WSN datasets exhibit a good DCT compactness feature.Figure 2
DCT compactness feature.


## 4.1. Experimental Datasets

We use three datasets, which are collected from two WSN testbeds, to serve as the ground truth. The summary of the datasets is shown in Table1.Table 1
Experimental datasets.
Data name
Matrix size
Time interval
Intel Temperature
54 nodes × 96 intervals
10 minutes
Intel Humidity
54 nodes × 96 intervals
10 minutes
PARED Temperature
50 nodes × 96 intervals
10 minutesThe first category of datasets is collected by 54 Mica2Dot nodes deployed in the Intel Berkeley Research Lab [17] between February 28 and April 5, 2004. The Mica2Dot node reports collected sensor data including humidity and temperature once every 30 seconds. However, we find that the raw dataset has considerable missing data. Therefore, we have rearranged the raw data (by changing the reporting interval from 30 seconds to 10 minutes) to avoid the missing data.The second category of dataset consists of temperature readings, which are collected with a 10-minute interval by our own testbed, namely, PARED. PARED consists of 50 sensor nodes. More details about PARED can be found in [18].


## 4.2.  Low-Rank Structure

We first examine the low-rank structure in WSN datasets using the Singular Value Decomposition (SVD). The environment matrixX can be decomposed into three matrices by SVD:(7)X=UΣVT,where U is an m×m orthonormal matrix, V is an n×n orthonormal matrix, and Σ is an m×n diagonal matrix with singular values σ1,σ2⋯σp sorted in a descending order (p=min⁡(m,n)).Because sensor readings in a WSN are spatiotemporal correlated, the environment matrixX would exhibit low-rank feature. More exactly, X should approximate to a low-rank matrix of rank r. So, the first r singular values will occupy the most energy of X. We use the following as the metric to examine the quality of the low-rank approximation:(8)gr=∑i=1rσiX∗=∑i=1rσi∑i=1pσi,where ·∗ is the nuclear norm and X∗=∑i=1p‍σi.Figure1 shows the low-rank approximation quality of the three datasets. We found that the largest 10 singular values occupy the 93%–99% of the total energy, which suggests that the WSN datasets exhibit a good low-rank feature.Figure 1
Low-rankness feature.


## 4.3.  DCT Compactness

We also observed that the sensor readings in WSN exhibit DCT compactness feature. In other words, the firstk DCT coefficients of the sensor vector x→i concentrate the most energy of x→i.We first defineD as the m×m Discrete Cosine Transform Matrix:(9)Di,j=2mcos⁡πmi-12j-12.Then, the m×m orthonormal matrix D can be divided into two submatrices:(10)D=D1D2,where D1 consists of the first k rows of D and D2 consists of the last m-k rows of D.Therefore, if the firstk DCT coefficients occupy the most energy of x→i, we will have D1x→i2/x→i2≈1 and D2x→i2/x→i2≈0. Similarly, for the matrix form, we will have D1XF/XF≈1 and D2XF/XF≈0, where ∗F is the Frobenius norm with XF=∑i,j‍X(i,j)2. So, we use the following function to examine the DCT compactness feature:(11)hk=D1XFXF.From Figure2, we can see that the first 10 DCT coefficients concentrate 99% of the total energy, which suggests that these WSN datasets exhibit a good DCT compactness feature.Figure 2
DCT compactness feature.


## 5. Algorithm

In this section, we proposed a novel matrix completion algorithm, namely, DCT Regularized Matrix Completion (DRMC), to solve the data recovery problem in WSN data gathering. DRMC takes full advantage of the low-rankness and DCT compactness features to improve the recovery accuracy.


### 5.1. Utilization of Low-Rankness

As mentioned before in Section3, the goal of the recovery problem is to estimate X from only a fraction of known entries. According to [10], we can recover X by solving the following rank optimization problem if X is a low-rank matrix:(12)minimizerankXsubjecttoM∘X=Y.However, the rank minimization problem (12) is NP-hard and is not solvable in polynomial time. Since the nuclear norm is the optimal convex approximation of the rank function, a reasonable solution is to solve a convex relaxation problem with the rank function replaced by the nuclear norm:(13)minimizeX∗subjecttoM∘X=Y.However, in a more realistic occasion, the environment matrixX is not an exactly low-rank matrix. There may not exist low-rank matrices that exactly satisfy the constraints in problem (13). So, we converted the constrained optimization problem (13) into the following nuclear norm regularized optimization problem:(14)minimize12M∘X-YF2+λX∗,where λ>0 is the nuclear regularization parameter.


### 5.2. Utilization of DCT Compactness

Though we can estimateX by solving the optimization problem (14), it will overfit to the known entries of X when the sampling rate is low, which will lead to large recovery error in the estimation of the missing entries.Therefore, to reduce the overfitting in (14), we exploit the DCT compactness feature of the sensor data. As mentioned in Section 4.3, D2XF/XF≈0. So, we added D2XF as the DCT regularization term to (14), and finally, we obtain the following optimization problem:(15)minimize12M∘X-YF2+λX∗+μD2XF2,where μ is the DCT regularization parameter.


### 5.3. The DRMC Algorithm

We present the DRMC algorithm by solving the optimization problem in (15). The pseudocode is shown in Algorithm 1. Next, we will describe the design of DRMC in details.Algorithm 1:DRMC algorithm.
Input:
Y∈Rm×n: collected data matrix
M∈Rm×n: sampling matrix
λ-: nuclear norm regularization parameter
μ: DCT regularization parameter
Output:
X^∈Rm×n: reconstructed environment matrix
Main procedure:
(1)   L←1+2μ;
(2)   Xold←0; Xnew←0;
(3)   Select λ1>λ2>⋯>λK=λ-
(4)   for  λ=λ1,λ2,…,λK  do
(5)    told←1; tnew←1;
(6)    repeat
(7)     Z⟵Xnew+told-1tnewXnew-Xold;
(8)     Xold←Xnew;
(9)     G←Z-L-1(M∘Z-Y+2μD2TD2Z);
(10)   Xnew←SλL-1(G);
(11)   told←tnew;
(12)   tnew⟵1+1+4told22;
(13)  until  Xnew-XoldF/XoldF<ϵ
(14) end for
(15) X^←Xnew;
(16) return  X^The object function in (15) can be rewritten into the following form:(16)FX≔fX+PX,with(17)fX=12M∘X-YF2+μD2XF2,(18)PX=λX∗.Note thatP(X) is a proper, convex, lower semicontinuous (lsc) [19] function but it is nonsmooth, while f(X) is a convex smooth function and is continuously differentiable, with(19)∇fX=M∘X-Y+2μD2TD2X.Furthermore, ∇f(X) is Lipschitz continuous with a positive constant L:(20)∇fX1-∇fX2F≤LX1-X2F,∀X1,X2∈dom⁡P,where dom⁡P={X∣P(X)<∞}. Proposition 2 indicates that the Lipschitz constant of f(X) is L=1+2μ.SinceP(X) is nonsmooth, it is difficult to directly minimize the objective function F(X). Instead, we choose to iteratively minimize a sequence of quadratic approximations of F(X), which is an effective way to minimize the unconstrained nonsmooth convex function [20–22]. The quadratic approximation of F(·) at point Z is defined as the following:(21)QLX,Z≔fZ+∇fZ,X-Z+L2X-ZF2+PX.And the objective variable Xnew is repeatedly updated to the minimizer of QL(X,Z), until Xnew-XoldF/XoldF<ϵ. The convergence of such iterative process is well studied in [21].We then introduce an auxiliary variableG to minimize QL(X,Z). As suggested by Proposition 5, we can minimize QL(X,Z) using the singular value shrinkage operator defined in (26). Thus, we have Xnew=SλL-1(G).What is more, we consider a warm-start technique for the nuclear regularization parameterλ. Rather than remaining unchanged, λ is monotonically decreasing in the iterative process. The nuclear regularization parameter λ starts with an initial value λ1 and gradually declines to λ¯, forming a sequence of λ1>λ2>⋯>λK,(λK=λ¯).Lemma 1.
D
2 is defined as in (10). Then, one has(22)D2TD2XF≤XF,∀X∈Rm×n.Proof.
SinceD is orthonormal, D2D2T=I,DXF=XF.
And note thatXF=Tr(XTX), then we can obtain(23)D2TD2XF=TrXTD2TD2D2TD2X=TrXTD2TD2X=D2XF≤DXF=XF.Proposition 2.
Assume thatf(X) is defined as (17); then, f(X) is Lipschitz continuous with(24)L=1+2μ.Proof.
Note thatM∘XF≤XF, and by using the Lemma 1, we obtain that (25)∇fX1-∇fX2F=M∘X1-X2+2μD2TD2X1-X2F≤M∘X1-X2F+2μD2TD2X1-X2F≤X1-X2F+2μX1-X2F=1+2μX1-X2F.Definition 3.
Decompose the matrixX∈Rm×n of rank r by SVD: X=UΣVT, where U∈Rm×r and V∈Rn×r are orthonormal matrices and Σ=diag({σi}1≤i≤r). Define the singular value shrinkage operator [23] Sλ as follows:(26)SλX=USλΣVT,SλΣ=diagσi-λ+1≤i≤r,where t+ is the positive part of t, t+=max(0,t).Lemma 4.
LetG∈Rm×n. Then,(27)SλG≡argminX∈Rm×n12X-GF2+λX∗,where Sλ(G) is the singular value shrinkage operator of G.Proof.
The proof of Lemma4 can be found in [23].Proposition 5.
LetZ∈Rm×n and P(X)=λX∗. Assume that f(X) is Lipschitz continuous and define G∈Rm×n with(28)G=Z-L-1∇fZ.Then, one has(29)argminX∈Rm×nQLX,Z=SλL-1G.Proof.
Consider(30)QLX,Z=fZ+∇fZ,X-Z+L2X-ZF2+PX=fZ+∇fZ,X-Z+L2X-ZF2+λX∗=L2X-Z-1L∇fZF2+λX∗+fZ-12L∇fZF2=L12X-GF2+λLX∗+fZ-12L∇fZF2.Thus, combined with Lemma 4, we can obtain that(31)argminX∈Rm×nQLX,Z=argminX∈Rm×nL12X-GF2+λLX∗+fZ-12L∇fZF2=argminX∈Rm×n12X-GF2+λLX∗=SλL-1G.


## 5.1. Utilization of Low-Rankness

As mentioned before in Section3, the goal of the recovery problem is to estimate X from only a fraction of known entries. According to [10], we can recover X by solving the following rank optimization problem if X is a low-rank matrix:(12)minimizerankXsubjecttoM∘X=Y.However, the rank minimization problem (12) is NP-hard and is not solvable in polynomial time. Since the nuclear norm is the optimal convex approximation of the rank function, a reasonable solution is to solve a convex relaxation problem with the rank function replaced by the nuclear norm:(13)minimizeX∗subjecttoM∘X=Y.However, in a more realistic occasion, the environment matrixX is not an exactly low-rank matrix. There may not exist low-rank matrices that exactly satisfy the constraints in problem (13). So, we converted the constrained optimization problem (13) into the following nuclear norm regularized optimization problem:(14)minimize12M∘X-YF2+λX∗,where λ>0 is the nuclear regularization parameter.


## 5.2. Utilization of DCT Compactness

Though we can estimateX by solving the optimization problem (14), it will overfit to the known entries of X when the sampling rate is low, which will lead to large recovery error in the estimation of the missing entries.Therefore, to reduce the overfitting in (14), we exploit the DCT compactness feature of the sensor data. As mentioned in Section 4.3, D2XF/XF≈0. So, we added D2XF as the DCT regularization term to (14), and finally, we obtain the following optimization problem:(15)minimize12M∘X-YF2+λX∗+μD2XF2,where μ is the DCT regularization parameter.


## 5.3. The DRMC Algorithm

We present the DRMC algorithm by solving the optimization problem in (15). The pseudocode is shown in Algorithm 1. Next, we will describe the design of DRMC in details.Algorithm 1:DRMC algorithm.
Input:
Y∈Rm×n: collected data matrix
M∈Rm×n: sampling matrix
λ-: nuclear norm regularization parameter
μ: DCT regularization parameter
Output:
X^∈Rm×n: reconstructed environment matrix
Main procedure:
(1)   L←1+2μ;
(2)   Xold←0; Xnew←0;
(3)   Select λ1>λ2>⋯>λK=λ-
(4)   for  λ=λ1,λ2,…,λK  do
(5)    told←1; tnew←1;
(6)    repeat
(7)     Z⟵Xnew+told-1tnewXnew-Xold;
(8)     Xold←Xnew;
(9)     G←Z-L-1(M∘Z-Y+2μD2TD2Z);
(10)   Xnew←SλL-1(G);
(11)   told←tnew;
(12)   tnew⟵1+1+4told22;
(13)  until  Xnew-XoldF/XoldF<ϵ
(14) end for
(15) X^←Xnew;
(16) return  X^The object function in (15) can be rewritten into the following form:(16)FX≔fX+PX,with(17)fX=12M∘X-YF2+μD2XF2,(18)PX=λX∗.Note thatP(X) is a proper, convex, lower semicontinuous (lsc) [19] function but it is nonsmooth, while f(X) is a convex smooth function and is continuously differentiable, with(19)∇fX=M∘X-Y+2μD2TD2X.Furthermore, ∇f(X) is Lipschitz continuous with a positive constant L:(20)∇fX1-∇fX2F≤LX1-X2F,∀X1,X2∈dom⁡P,where dom⁡P={X∣P(X)<∞}. Proposition 2 indicates that the Lipschitz constant of f(X) is L=1+2μ.SinceP(X) is nonsmooth, it is difficult to directly minimize the objective function F(X). Instead, we choose to iteratively minimize a sequence of quadratic approximations of F(X), which is an effective way to minimize the unconstrained nonsmooth convex function [20–22]. The quadratic approximation of F(·) at point Z is defined as the following:(21)QLX,Z≔fZ+∇fZ,X-Z+L2X-ZF2+PX.And the objective variable Xnew is repeatedly updated to the minimizer of QL(X,Z), until Xnew-XoldF/XoldF<ϵ. The convergence of such iterative process is well studied in [21].We then introduce an auxiliary variableG to minimize QL(X,Z). As suggested by Proposition 5, we can minimize QL(X,Z) using the singular value shrinkage operator defined in (26). Thus, we have Xnew=SλL-1(G).What is more, we consider a warm-start technique for the nuclear regularization parameterλ. Rather than remaining unchanged, λ is monotonically decreasing in the iterative process. The nuclear regularization parameter λ starts with an initial value λ1 and gradually declines to λ¯, forming a sequence of λ1>λ2>⋯>λK,(λK=λ¯).Lemma 1.
D
2 is defined as in (10). Then, one has(22)D2TD2XF≤XF,∀X∈Rm×n.Proof.
SinceD is orthonormal, D2D2T=I,DXF=XF.
And note thatXF=Tr(XTX), then we can obtain(23)D2TD2XF=TrXTD2TD2D2TD2X=TrXTD2TD2X=D2XF≤DXF=XF.Proposition 2.
Assume thatf(X) is defined as (17); then, f(X) is Lipschitz continuous with(24)L=1+2μ.Proof.
Note thatM∘XF≤XF, and by using the Lemma 1, we obtain that (25)∇fX1-∇fX2F=M∘X1-X2+2μD2TD2X1-X2F≤M∘X1-X2F+2μD2TD2X1-X2F≤X1-X2F+2μX1-X2F=1+2μX1-X2F.Definition 3.
Decompose the matrixX∈Rm×n of rank r by SVD: X=UΣVT, where U∈Rm×r and V∈Rn×r are orthonormal matrices and Σ=diag({σi}1≤i≤r). Define the singular value shrinkage operator [23] Sλ as follows:(26)SλX=USλΣVT,SλΣ=diagσi-λ+1≤i≤r,where t+ is the positive part of t, t+=max(0,t).Lemma 4.
LetG∈Rm×n. Then,(27)SλG≡argminX∈Rm×n12X-GF2+λX∗,where Sλ(G) is the singular value shrinkage operator of G.Proof.
The proof of Lemma4 can be found in [23].Proposition 5.
LetZ∈Rm×n and P(X)=λX∗. Assume that f(X) is Lipschitz continuous and define G∈Rm×n with(28)G=Z-L-1∇fZ.Then, one has(29)argminX∈Rm×nQLX,Z=SλL-1G.Proof.
Consider(30)QLX,Z=fZ+∇fZ,X-Z+L2X-ZF2+PX=fZ+∇fZ,X-Z+L2X-ZF2+λX∗=L2X-Z-1L∇fZF2+λX∗+fZ-12L∇fZF2=L12X-GF2+λLX∗+fZ-12L∇fZF2.Thus, combined with Lemma 4, we can obtain that(31)argminX∈Rm×nQLX,Z=argminX∈Rm×nL12X-GF2+λLX∗+fZ-12L∇fZF2=argminX∈Rm×n12X-GF2+λLX∗=SλL-1G.


## 6. Complexity Analysis

In this section, we discuss the time complexity of the proposed algorithm.After analyzing the steps in Algorithm1, we find that the most computationally intensive step is the singular value shrinkage operation that performs SVD on G, which dominates the computational complexity of this algorithm. The time complexity of SVD for an m×n matrix is O(mn2) [24]. And for any ϵ>0, the iterative process in Algorithm 1 will terminate in O(L/ϵ) iterations with an ϵ-optimal solution [21, 25]. Consequently, the time complexity of our algorithm is O(KL/ϵmn2).We can further decrease the time complexity of the DRMC algorithm by applying Partial Reorthogonalization Package (PROPACK) [26] in the singular value shrinkage operation. PROPACK uses the Lanczos method [24] to compute only a partial SVD of G. However, it cannot a priori compute singular values that are greater than λ/L. Hence, we need to predetermine the number of singular values to be computed (denoted as svi) at the beginning of the ith iteration, and PROPACK can then compute the svi largest singular values and corresponding singular vectors. We adopt the prediction rule proposed in [27]:(32)svi+1=svpi+1,ifsvpi<svi.min⁡svpi+10,m,n,ifsvpi=svi,where svi is the predicted number of singular values, svpi is the actual number of singular values that are larger than λ/L, and sv0=10.The time complexity of the Lanczos method isO(rmn) for m×n matrix with rank of r [24]. Therefore, the time complexity of DRMC algorithm is O(KL/ϵrmn) if PROPACK is used. For fixed number of iterations, the complexity of DRMC can be simplified as O(rmn), while the state-of-the-art matrix completion based methods [11–13] require a complexity of O(r2mn). So, DRMC is more computationally efficient.


## 7. Error Analysis

In this section, we analyze the recovery error of the DRMC algorithm and present a theoretical upper bound.Before starting the analysis, we first introduce some assumptions and lemmas.Assumption 6.
The original data matrixX can be approximated by the first k DCT coefficients, with approximation error ξ:(33)ξ=X-D1TD1XF=D2TD2XF.Assumption 7.
LetA:Rm×n→Rm×n be the linear operator defined as(34)AX=2μL-1D2TD2X+L-1M∘Xand I be the identity operator.
Then, there exists a constant0≤η<1, such that(35)supAX≠0,XF=1⁡I-AXF≤η.Lemma 8.
Suppose thatSλ is the singular value shrinkage operator; then,(36)SλX1-SλX2F≤X1-X2F,∀X1,X2∈Rm×n.Proof.
The detailed proof of Lemma8 can be found in [28].Lemma 9.
Suppose thatX∈Rm×n with rank of r; then,(37)SλX-XF≤rλ.Proof.
Consider(38)SλX-XF=USλΣ-ΣVTF=UΣ-SλΣVTF=Udiagσi-σi-λ+1≤i≤r⁡VTF=Udiagdi1≤i≤rVTF=∑i=1rdi2,where(39)di=λ,ifσi≥λ;σi,ifσi<λ.Therefore, we have(40)SλX-XF≤rλ.The upper bound of the recovery error is then given in the following theorem.Theorem 10.
Suppose thatX^ is the estimate of X obtained by the DRMC algorithm; then, one has(41)X^-XF≤rλ¯+2ξμ1-η1+2μ.Proof.
When the iterative process in Algorithm1 has converged, Xnew will be equal to Xold. Hence, X^ will be the fixed point of the following:(42)X^=Sλ¯L-1I-2μL-1D2TD2X^-L-1M∘X^-X.Therefore, we have(43)X^-XF=Sλ¯L-1I-2μL-1D2TD2X^-L-1M∘X^-X-XF=Sλ¯L-1I-2μL-1D2TD2X^-L-1M∘X^-X-Sλ¯L-1I-2μL-1D2TD2X+Sλ¯L-1I-2μL-1D2TD2X-XF≤Sλ¯L-1I-2μL-1D2TD2X^-L-1M∘X^-X-Sλ¯L-1I-2μL-1D2TD2XF+Sλ¯L-1X-XF+2μL-1D2TD2XF.
Combining (43) and Lemma 8, we have(44)X^-XF≤I-2μL-1D2TD2X^-X-L-1M∘X^-XF+Sλ¯L-1X-XF+2μL-1D2TD2XF=I-AX^-XF+Sλ¯L-1X-XF+2μL-1D2TD2XF,where I is the identity operator and A is the operator defined in (34).
Then, applying Assumption6 and Lemma 9 to (44), we have(45)X^-XF≤I-AX^-XF+λ¯L-1r+2μL-1ξ.Combining Assumption 7, (24), and (45), we finally obtain the following error bound:(46)X^-XF≤rλ¯+2ξμ1-ηL=rλ¯+2ξμ1-η1+2μ.LetE represent the upper bound of the recovery error. Then, according to Theorem 10, E=(rλ¯+2ξμ)/(1-η)(1+2μ). Note that E(λ¯) is an increasing function of λ¯. So, we expect the actual recovery error of the DRMC algorithm to increase with λ¯, which is confirmed later by simulation results in Section 8.3.


## 8. Evaluation

We designed a data gathering scheme based on the proposed DRMC algorithm. The data gathering procedure is similar to [11]. Firstly, sink node broadcasts a sampling rate to all sensor nodes. Secondly, each sensor node randomly and independently decides whether to forward its readings to the sink according to the sampling rate. Finally, the sink node collects the incomplete data matrix and uses DRMC to retrieve the missing data. After implementing this data gathering scheme by Matlab, we carried out extensive experiments on three real-world datasets (as shown in Table 1) to evaluate the effectiveness of DRMC.


### 8.1. Baseline Methods

We select two state-of-the-art methods to compare with DRMC. The first method is Compressive Sensing (CS). We choose the DCT matrix defined in (9) to serve as the orthonormal basis in CS. The second method is Spatiotemporal Compressive Data Collection (STCDG). The parameters of STCDG are set to λ=0.5, r=10. Note that since our earlier work, namely, DCT-RPMC, depends on historical data while the proposed algorithm does not, we do not select DCT-RPMC as the baseline method.


### 8.2.  Recovery Accuracy

Firstly, we compared the recovery accuracy of the proposed algorithm with two baseline methods described above. The parameters of DRMC are listed in Table2.Table 2
Parameter settings for DRMC.
Parameter name
λ
-
μ
k
Default value
0.001
1
10Simulation experiments are carried out on three real-world datasets. Each simulation is conducted for 100 independent trials. The recovery errors are computed according to (6) and are averaged over the 100 trials.Comparison results are shown in Figures3–5. For experiments on Intel Temperature Trace, all methods achieve nearly the same recovery accuracy when the sampling rate is high. When the sampling rate is below a certain value (τ<0.1), recovery performance of baseline methods deteriorates quickly, while DRMC still achieves a good recovery accuracy. When the sampling rate is as low as 0.03, which means 97% of data loss, DRMC can reconstruct the lost data with recovery error less than 10%, while recovery error of CS and STCDG is close to 100%.Figure 3
Recovery accuracy on Intel Temperature Trace.Figure 4
Recovery accuracy on Intel Humidity Trace.Figure 5
Recovery accuracy on PARED Temperature Trace.Comparison results on Intel Humidity Trace are very similar to that on Intel Temperature Trace. Recovery error of DRMC is about 9% when the sampling rate is 0.03, which is noticeably better than that of baseline methods.For experiments on PARED Temperature Trace, DRMC still outperforms baseline methods for low sampling rate. The recovery error of DRMC is about16% when the sampling rate is 0.03, which is slightly worse than that on other two traces. This is because the low-rankness and DCT compactness features of PARED Temperature are not as good as that of other two traces, as shown in Figures 1 and 2.


### 8.3. Parameter Settings

The DRMC algorithm depends on several input parameters. Clearly, the choice of these parameters will affect the recovery performance of DRMC. In this subsection, we discuss how to choose the parameters for DRMC.The nuclear norm regularization parameterλ is an important parameter to ensure the low-rank feature of the reconstructed data matrix. In DRMC, we adopted a warm-start strategy for λ, in which λ is linearly reduced from λ1 to λK. In the implementation, λ1=10λ¯+1, λK=λ¯, and K=20. We tested DRMC on a range of values of λ¯ to investigate how λ¯ effects the performance of DRMC. Figure 6 shows the experimental results. The recovery errors of DRMC increase with λ¯, just as what we predicted in Section 7 by the theoretical error bound (41). Note that when λ¯<0.1, the recovery performance of DRMC is not sensitive to λ¯. So, in practice, we just set it to a small enough value, λ¯=0.001.Figure 6
Effect of parameterλ¯.Parameterμ is a regularization parameter that guarantees the DCT compactness feature of the recovered signal. Figure 7 shows the effects of μ on the recovery performance of DRMC. The recovery errors decline with μ and are stable when μ>0.1. So, we choose to use μ=1 for our experiments.Figure 7
Effect of parameterμ.Recall thatk represents the number of concentrated DCT coefficients. As discussed before in Section 4.3, the first 10 DCT coefficients concentrate 99% of the total energy. As expected, Figure 8 shows that the recovery errors are dropping fast with k and are stable when k>10. So, we choose to use k=10 for our experiments. Note that the recovery errors are slightly increasing with the growth of k when k>10. We explain this by considering the extreme case when k=m. If k=m, D1 is equal to D. As a result, the DCT regularization term D2XF2 in (15) is automatically equal to zero. Therefore, the DCT compactness property of the sensory data is not utilized and the recovery errors will increase, just as the case in Figure 7 when μ=0.Figure 8
Effect of parameterk.


### 8.4.  Energy Consumption and Network Lifespan

DRMC-based data gathering protocol is more energy efficient because it transmits less packets than the classic one (receiving and forwarding). As a result, DRMC-based protocol can save more energy and prolong the lifespan of wireless sensor networks. To verify this, simulation experiments are conducted and the simulation configuration is shown in Table3.Table 3
Simulation configuration for network lifespan.
Parameter name
Value
Number of nodes
1000
Initial energy
1 J
Sampling period
10 seconds
Data size
16 bits
E
T
x
100 nJ/bit
E
R
x
120 nJ/bit
E
Amp
0.01 nJ/(bit⋅m2)In the simulation, sensor nodes are randomly deployed in a 500 m× 500 m area and the sink node is deployed in the center. Each sensor node is equipped with 1 J energy. To evaluate the energy consumption, we adopt the following energy model [29]:(47)ETk,d=ETx+d2×EAmp×k,ifd<dThres,ETx+d4×EAmp×k,ifd≥dThres,ERk=kERx.E
T
(
k
,
d
) represents the energy consumption of transmitting k bits data with distance d. ER(k) denotes the energy consumption of receiving k bits data. ETx is the energy consumed by the transmitting circuit to process 1 bit data. ERx is the energy consumed by the receiving circuit to process 1 bit data. EAmp is the energy consumed by power amplifying circuit.Figure9 demonstrates the network lifespan of DRMC-based protocol and other baseline protocols under different sampling rate. Note that the network lifespan is defined as the time when the first energy exhausted node appears. Apparently, the sampling rate does not play a role in the classic data gathering, since it directly transmits all data without compression. Therefore, the lifespan curve of the classic protocol in Figure 9 is a straight line. For the CS method, the smaller the sampling rate is, the less measurements are taken. And as shown in Figure 9, the lifespan of CS is decreasing with the sampling rate. However, when the sampling rate is above a certain value, the lifespan of CS is even worse than the classic one. The reason why CS performs badly for large sampling rate is well analyzed in [30]. Figure 9 shows that DRMC-based protocol achieves the best lifespan. Similarly, the lifespan of DRMC is decreasing with the sampling rate. When the sampling rate decreases to 1, DRMC-based protocol is equivalent to the classic protocol and the lifespan of DRMC is equal to the classic one. Note that the lifespan of STCDG is exactly the same as DRMC, because both of the two methods are based on matrix completion. The lifespan of DRMC is longer than CS because the sampling matrix in DRMC is much sparser than that in CS.Figure 9
Relation of network lifespan to sampling rate.


## 8.1. Baseline Methods

We select two state-of-the-art methods to compare with DRMC. The first method is Compressive Sensing (CS). We choose the DCT matrix defined in (9) to serve as the orthonormal basis in CS. The second method is Spatiotemporal Compressive Data Collection (STCDG). The parameters of STCDG are set to λ=0.5, r=10. Note that since our earlier work, namely, DCT-RPMC, depends on historical data while the proposed algorithm does not, we do not select DCT-RPMC as the baseline method.


## 8.2.  Recovery Accuracy

Firstly, we compared the recovery accuracy of the proposed algorithm with two baseline methods described above. The parameters of DRMC are listed in Table2.Table 2
Parameter settings for DRMC.
Parameter name
λ
-
μ
k
Default value
0.001
1
10Simulation experiments are carried out on three real-world datasets. Each simulation is conducted for 100 independent trials. The recovery errors are computed according to (6) and are averaged over the 100 trials.Comparison results are shown in Figures3–5. For experiments on Intel Temperature Trace, all methods achieve nearly the same recovery accuracy when the sampling rate is high. When the sampling rate is below a certain value (τ<0.1), recovery performance of baseline methods deteriorates quickly, while DRMC still achieves a good recovery accuracy. When the sampling rate is as low as 0.03, which means 97% of data loss, DRMC can reconstruct the lost data with recovery error less than 10%, while recovery error of CS and STCDG is close to 100%.Figure 3
Recovery accuracy on Intel Temperature Trace.Figure 4
Recovery accuracy on Intel Humidity Trace.Figure 5
Recovery accuracy on PARED Temperature Trace.Comparison results on Intel Humidity Trace are very similar to that on Intel Temperature Trace. Recovery error of DRMC is about 9% when the sampling rate is 0.03, which is noticeably better than that of baseline methods.For experiments on PARED Temperature Trace, DRMC still outperforms baseline methods for low sampling rate. The recovery error of DRMC is about16% when the sampling rate is 0.03, which is slightly worse than that on other two traces. This is because the low-rankness and DCT compactness features of PARED Temperature are not as good as that of other two traces, as shown in Figures 1 and 2.


## 8.3. Parameter Settings

The DRMC algorithm depends on several input parameters. Clearly, the choice of these parameters will affect the recovery performance of DRMC. In this subsection, we discuss how to choose the parameters for DRMC.The nuclear norm regularization parameterλ is an important parameter to ensure the low-rank feature of the reconstructed data matrix. In DRMC, we adopted a warm-start strategy for λ, in which λ is linearly reduced from λ1 to λK. In the implementation, λ1=10λ¯+1, λK=λ¯, and K=20. We tested DRMC on a range of values of λ¯ to investigate how λ¯ effects the performance of DRMC. Figure 6 shows the experimental results. The recovery errors of DRMC increase with λ¯, just as what we predicted in Section 7 by the theoretical error bound (41). Note that when λ¯<0.1, the recovery performance of DRMC is not sensitive to λ¯. So, in practice, we just set it to a small enough value, λ¯=0.001.Figure 6
Effect of parameterλ¯.Parameterμ is a regularization parameter that guarantees the DCT compactness feature of the recovered signal. Figure 7 shows the effects of μ on the recovery performance of DRMC. The recovery errors decline with μ and are stable when μ>0.1. So, we choose to use μ=1 for our experiments.Figure 7
Effect of parameterμ.Recall thatk represents the number of concentrated DCT coefficients. As discussed before in Section 4.3, the first 10 DCT coefficients concentrate 99% of the total energy. As expected, Figure 8 shows that the recovery errors are dropping fast with k and are stable when k>10. So, we choose to use k=10 for our experiments. Note that the recovery errors are slightly increasing with the growth of k when k>10. We explain this by considering the extreme case when k=m. If k=m, D1 is equal to D. As a result, the DCT regularization term D2XF2 in (15) is automatically equal to zero. Therefore, the DCT compactness property of the sensory data is not utilized and the recovery errors will increase, just as the case in Figure 7 when μ=0.Figure 8
Effect of parameterk.


## 8.4.  Energy Consumption and Network Lifespan

DRMC-based data gathering protocol is more energy efficient because it transmits less packets than the classic one (receiving and forwarding). As a result, DRMC-based protocol can save more energy and prolong the lifespan of wireless sensor networks. To verify this, simulation experiments are conducted and the simulation configuration is shown in Table3.Table 3
Simulation configuration for network lifespan.
Parameter name
Value
Number of nodes
1000
Initial energy
1 J
Sampling period
10 seconds
Data size
16 bits
E
T
x
100 nJ/bit
E
R
x
120 nJ/bit
E
Amp
0.01 nJ/(bit⋅m2)In the simulation, sensor nodes are randomly deployed in a 500 m× 500 m area and the sink node is deployed in the center. Each sensor node is equipped with 1 J energy. To evaluate the energy consumption, we adopt the following energy model [29]:(47)ETk,d=ETx+d2×EAmp×k,ifd<dThres,ETx+d4×EAmp×k,ifd≥dThres,ERk=kERx.E
T
(
k
,
d
) represents the energy consumption of transmitting k bits data with distance d. ER(k) denotes the energy consumption of receiving k bits data. ETx is the energy consumed by the transmitting circuit to process 1 bit data. ERx is the energy consumed by the receiving circuit to process 1 bit data. EAmp is the energy consumed by power amplifying circuit.Figure9 demonstrates the network lifespan of DRMC-based protocol and other baseline protocols under different sampling rate. Note that the network lifespan is defined as the time when the first energy exhausted node appears. Apparently, the sampling rate does not play a role in the classic data gathering, since it directly transmits all data without compression. Therefore, the lifespan curve of the classic protocol in Figure 9 is a straight line. For the CS method, the smaller the sampling rate is, the less measurements are taken. And as shown in Figure 9, the lifespan of CS is decreasing with the sampling rate. However, when the sampling rate is above a certain value, the lifespan of CS is even worse than the classic one. The reason why CS performs badly for large sampling rate is well analyzed in [30]. Figure 9 shows that DRMC-based protocol achieves the best lifespan. Similarly, the lifespan of DRMC is decreasing with the sampling rate. When the sampling rate decreases to 1, DRMC-based protocol is equivalent to the classic protocol and the lifespan of DRMC is equal to the classic one. Note that the lifespan of STCDG is exactly the same as DRMC, because both of the two methods are based on matrix completion. The lifespan of DRMC is longer than CS because the sampling matrix in DRMC is much sparser than that in CS.Figure 9
Relation of network lifespan to sampling rate.


## 9. Conclusion

In this paper, we studied the data gathering and reconstruction problem in WSNs. We modeled the problem as matrix completion problem and investigated the data features in real WSN datasets. Then, by taking advantage of the low-rankness and DCT compactness features in WSNs, we proposed a DCT Regularized Matrix Completion (DRMC) algorithm to reconstruct the missing data. The recovery error of DRMC is carefully analyzed and a theoretical error upper bound is presented. Experimental results show that DRMC outperforms state-of-the-art methods for low sampling rate and achieves a good recovery accuracy even if the sampling rate is very low.



---

*Source: 272761-2015-07-14.xml*