# An Adaptive Joint Sparsity Recovery for Compressive Sensing Based EEG System

Authors: Hamza Djelouat; Hamza Baali; Abbes Amira; Faycal Bensaali
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

The last decade has witnessed tremendous efforts to shape the Internet of things (IoT) platforms to be well suited for healthcare applications. These platforms are comprised of a network of wireless sensors to monitor several physical and physiological quantities. For instance, long-term monitoring of brain activities using wearable electroencephalogram (EEG) sensors is widely exploited in the clinical diagnosis of epileptic seizures and sleeping disorders. However, the deployment of such platforms is challenged by the high power consumption and system complexity. Energy efficiency can be achieved by exploring efficient compression techniques such as compressive sensing (CS). CS is an emerging theory that enables a compressed acquisition using well-designed sensing matrices. Moreover, system complexity can be optimized by using hardware friendly structured sensing matrices. This paper quantifies the performance of a CS-based multichannel EEG monitoring. In addition, the paper exploits the joint sparsity of multichannel EEG using subspace pursuit (SP) algorithm as well as a designed sparsifying basis in order to improve the reconstruction quality. Furthermore, the paper proposes a modification to the SP algorithm based on an adaptive selection approach to further improve the performance in terms of reconstruction quality, execution time, and the robustness of the recovery process.


---

## Body

## 1. Introduction

Nowadays, a huge interest has been dedicated to the development of Internet of things (IoT) based connected health platforms. These platforms are empowered by several wearable battery-driven sensors that collect and record different vital signs for a long period. The collected data is sent using low-power communication protocols to a nearby gateway. The gateway then delivers the data to the host cloud. At the cloud level, various signal processing and data analysis techniques are performed to provide computer-aided medical assistance. However, the performance of these platforms is bottlenecked mainly by the limited lifespan of wearable sensors. Therefore, exploring data compression techniques can reduce the number of the data transmitted from the sensors to the gateway, hence prolonging the sensor’s lifespan. Compressive sensing (CS) theory has proved to be a reliable compression technique which provides the best trade-off between reconstruction quality and low-power consumption compared to conventional compression approaches such as transform coding or segmentation and labeling techniques [1].CS is a novel data sampling paradigm that merges the acquisition and the compression processes into one operation. CS relies on the signal sparsity/compressibility in order to acquire a compressed form of the signal while maintaining its salient information. CS has been introduced in [2, 3]; the authors have proved that any sparse signal can be recovered exactly from a smaller set of measurements than its original dimension. Therefore, it is possible to acquire sparse signals by taking far fewer random measurements than what the famous Shannon-Nyquist theorem states using well-designed matrices. Despite the fact that CS is a relatively new theory, it has been incorporated in a wide range of emerging applications including image processing, radar, wireless communication, and monitoring-based applications.Furthermore, to cope with current monitoring systems, an extension to CS has been introduced in [4], namely, distributed compressive sensing (DCS). DCS aims to exploit both the signal intrastructure (the sparsity) and the interstructure of the acquisition system (correlation between the measurements of the different sensors) in order to acquire the information about the signals of interest using the minimum number of measurements.Subsequently, by leveraging the sparsity of most biosignals such as electrocardiogram (ECG) and electromyogram (EMG) [5, 6], many efforts have been dedicated to exploit CS and DCS in wireless body area network (WBAN) applications to enable CS-based IoT platforms for connected health. In such platforms, the compressed data is transmitted to a fusion node (gateway) that possesses enough computing and communication abilities. Afterwards, the data is routed to the cloud via the Internet for reconstruction, processing, and analysis. It is worth mentioning that data reconstruction can be performed on the gateway to empower an “IoT-based edge computing platform.”CS-based systems for EMG and ECG monitoring have been thoroughly investigated, where various aspects have been well analyzed, for instance, the comparison between CS and state-of-the-art compression techniques [7], the system design considerations [5], the effect of the sparsifying dictionaries [8], and the best algorithms in terms of quality of reconstruction [9]. In addition, authors in [10] further leveraged the biosignals structure, where, instead of only exploring the signal sparsity in one domain, the authors proposed using all the available structure such as low rank, piece-wise smoothness, and the sparsity in more than one domain. Subsequently, the authors in [10] proposed a reconstruction framework that aims to exploit any a priori information about the signals in order to enhance the reconstruction quality.Moreover, the application of CS in electroencephalogram (EEG) signals has been presented in the literature. The performance of such CS-based systems is controlled by two parameters, the sparsity of the signal, which depends mainly on the sparsifying basis, and the appropriate recovery algorithm adopted. Authors in [11] have shown the possibility of using CS for EEG compression as long as the EEG signal is recorded at least via 22 channels. The major limitation facing the deployment of CS in EEG compression is that it is very hard to find the transform domain where the EEG exhibits a sparse behavior. Therefore, different classes of sparsifying basis and dictionaries have been investigated to determine the best basis that provides the sparsest representation for EEG. Senay et al. have quantified the use of Slepian basis as sparsifying basis for EEG [12]; the obtained result shows a low error rate for the reconstructed EEG signal. In addition, Aviyente has presented a CS-based EEG compression system exploiting Gabor frame as dictionary for EEG signals [13], whereas Gangopadhyay et al. [14] have found that adopting a wavelet transform for EEG is more efficient in terms of quality of reconstruction. Zhang et al. presented in [15] a block sparse Bayesian learning (BSBL) approach to recover EEG raw data that enable both good reconstruction quality and low system complexity by using sparse sensing matrices and wavelet matrices as the sparsifying basis. More recently, authors in [16] introduced an optimization model based on l0 norm to enhance the cosparsity and to enforce the low-rank structure of the EEG signal. The authors proposed using a second-order difference matrix as the sparsifying dictionary to enhance the sparsity of the EEG signal as well as exploit the collaboration between the cosparsity and the low-rank structure to recover simultaneously a multichannel EEG signal.Besides selecting the optimum sparsifying matrix, adopting the appropriate reconstruction algorithm plays an important role in the recovery of the EEG data. Greedy algorithms have been widely explored in CS applications due to their low complexity and their superior performance compared to other recovery algorithms, such as convex relaxation approaches. The widely used greedy algorithms are orthogonal matching pursuits (OMP) [17], stage-wise OMP (StOMP) [18], compressive sampling matching pursuit (CoSaMP) [19], and subspace pursuit (SP) [20].The main task in greedy algorithms is to identify the locations of the largest coefficients in the estimated signal. Greedy algorithms adopt a signal proxy approach at each iteration to identify these locations. If the sensing matrix satisfies the restricted isometry property condition [21], then the signal proxy is very similar to the original signal and the locations of the nonzero elements can be easily identified. OMP and StOMP reconstruct the signal in an iterative approach by locating the largest coefficient at each time. On the other hand, SP and CoSaMP select more than one coefficient at each iteration which allows them to converge to the solution with a lower number of iterations. However, SP and CoSaMP require information about the signal sparsity which is not available a priori in many applications as the sparsity of the signal often changes over time. Moreover, the sparsity parameter k depends not only on the signal structure but also on the space where the data is sparse; hence, the same signal can exhibit different levels of sparsity depending on the sparsifying basis. The required knowledge of sparsity estimate parameter k presents a critical issue with the SP and CoSaMP, where a poor choice of k can remarkably degrade the reconstruction quality. Adaptive sparsity algorithms have been proposed in the literature; authors in [22, 23] have performed various modification to OMP, CoSaMP, and SP algorithms in order to provide an adaptive framework that estimates the best value for the sparsity parameter k. Sparsity adaptive matching pursuit (SAMP) proposed in [22] is considered as a generalization of both OMP and SP by updating k at each iteration until a certain condition is satisfied. The SAMP increases the value of sparsity parameter k using a two-stage verification process until the difference between the norms of the residual for every two successive iterations is below a certain threshold.In this paper, a CS-based scheme for EEG signal compression and recovery is presented. The contributions of the paper are as follows:(i)
Joint channel reconstruction using SP algorithm is presented. The proposed approach renders a better reconstruction quality than the conventional channel-per-channel recovery.(ii)
The concept of concatenated basis as the sparsifying basis for EEG signals is explored to tackle the problem of the nonsparsity, and the concatenated basis consists of a random selection of elements from both discrete cosine transform matrix (DCT) and discrete wavelet transform matrix (DWT).(iii)
A new adaptive approach is presented to reconstruct the EEG signal. The new algorithm is a modification of the SP algorithm to provide an algorithm that does not require the knowledge of the sparsity of the signal a priori. The new proposed dynamic selection subspace pursuit (DSSP) algorithm performs an adaptive selection at each iteration for the coefficients that capture most of the signal energy. The proposed algorithm promotes two improvements over SP: first, an enhancement of the data reconstruction quality and, second, an increased robustness compared with SP, as the latter would provide a bad reconstruction quality if the sparsity parameter is poorly estimated.The rest of the paper is organized as follows: CS fundamentals are briefly presented in Section2. Section 3 addresses the main issue of the paper where the description of joint reconstruction approach and the proposed recovery algorithm is provided. Simulation results and discussion are presented in Section 4. Section 5 concludes the paper.


## 2. Compressed Sensing

### 2.1. Acquisition Model

The acquisition model of CS (1) is represented by an inner product between the input sparse signal x∈RN×1 and the sensing matrix Φ∈RM×N (such that m<N) to generate the compressed measured signal y∈RM×1.(1)y=Φx.In most cases, the input signalx is not sparse in time domain, yet it can exhibit a sparse behavior under the appropriate transform. Thus, given a set {Ψi}i=1N that spans R, x can be expressed as a linear combination between the elements of Ψ with a vector s∈RN such that x=∑i=1N‍ψisi. The input signal x is said to be k-sparse if s has only k≪N nonzero entries. The set of the indices corresponding to the positions of the nonzero entries of s is called the support of s and denoted as Σk.The sensing matrixΦ∈RM×N which maps the N-length input signal x to an M-length signal y has to enable a small number of samples to acquire the salient information in the input signal. Moreover, it should allow acceptable reconstruction quality. Therefore, Φ has to satisfy two conditions on the RIP and should be incoherent with sparsifying matrix Ψ [21].


### 2.2. Reconstruction Algorithms

Data reconstruction is the crucial task in any CS-based system. Thus, several approaches to recover the original signalx from the measured signal y have been proposed in literature. However, there are two main classes of reconstruction algorithms that have been widely explored, namely, convex optimization and greedy algorithms. Convex optimization approaches provide the exact solution if the input signal is completely sparse. Convex optimization algorithms are based on the l1 minimization operation; for instance, basis pursuit (BP) algorithm [24] considers the following solution:(2)x^=argminx1subject  toy=Φx.In the case where the acquisition process is contaminated with noise, two different techniques can be deployed; first, if the noise level is known a priori, basis pursuit denoising (BPDN) [25] can be applied. However, if there is no knowledge about the noise level, least absolute shrinkage and selection operator (LASSO) presents an efficient approach to recover the original signal.Greedy algorithms provide a suboptimal recovery for sparse signals, yet they outperform convex optimization approaches in the case where the signal of interest is highly sparse [17]. Greedy algorithms solve (1) iteratively by taking locally optimal decisions. These algorithms aim to find the locations of the nonzero coefficients to enable a fast recovery. Greedy algorithms include several variants such as gradient pursuit, matching pursuit (MP) [26], and OMP [17]. OMP offers a fast recovery compared to convex optimization approaches; however, it suffers from bad recovery quality for signals with a low degree of sparsity. Thus, several improved versions of OMP have been proposed, such as CoSaMP [19], SP [20], and StOMP [18].


### 2.3. Distributed Compressive Sensing

Conventional CS exploits only the sparsity of the data. However, if the same data is collected using different sensing nodes or different channels, their measurements would be highly correlated. In such scenario, the measurements exhibit the same behavior, such as being sparse in a particular domain.Therefore, in a multichannel CS-based data acquisition system, each sensing node collects and compresses its data individually without taking any considerations about the other nodes. For the recovery, two approaches can be considered to reconstruct the data; first, data reconstruction can be performed on each sensing node individually, this approach ignores the dependency between the measurements of different sensors, and, hence, the quality of the reconstruction depends only on the sparsity of each recording. The second approach exploits the collaboration between all measurements to obtain more information about the data; thus, a better reconstruction quality can be achieved. This process is called joint measurement setting and it has motivated the introduction of the DCS concept.DCS presents a new distributed coding framework that exploits both the sparsity of the signal and the correlation between the different signals in multisensing architectures. In the DCS acquisition stage, each sensor collects its measurements by taking random projections of the signal without any consideration about the states of the other sensors in the network. However, the reconstruction phase exploits the intersignal correlation by using all of the obtained measurements to recover all the signals simultaneously.


## 2.1. Acquisition Model

The acquisition model of CS (1) is represented by an inner product between the input sparse signal x∈RN×1 and the sensing matrix Φ∈RM×N (such that m<N) to generate the compressed measured signal y∈RM×1.(1)y=Φx.In most cases, the input signalx is not sparse in time domain, yet it can exhibit a sparse behavior under the appropriate transform. Thus, given a set {Ψi}i=1N that spans R, x can be expressed as a linear combination between the elements of Ψ with a vector s∈RN such that x=∑i=1N‍ψisi. The input signal x is said to be k-sparse if s has only k≪N nonzero entries. The set of the indices corresponding to the positions of the nonzero entries of s is called the support of s and denoted as Σk.The sensing matrixΦ∈RM×N which maps the N-length input signal x to an M-length signal y has to enable a small number of samples to acquire the salient information in the input signal. Moreover, it should allow acceptable reconstruction quality. Therefore, Φ has to satisfy two conditions on the RIP and should be incoherent with sparsifying matrix Ψ [21].


## 2.2. Reconstruction Algorithms

Data reconstruction is the crucial task in any CS-based system. Thus, several approaches to recover the original signalx from the measured signal y have been proposed in literature. However, there are two main classes of reconstruction algorithms that have been widely explored, namely, convex optimization and greedy algorithms. Convex optimization approaches provide the exact solution if the input signal is completely sparse. Convex optimization algorithms are based on the l1 minimization operation; for instance, basis pursuit (BP) algorithm [24] considers the following solution:(2)x^=argminx1subject  toy=Φx.In the case where the acquisition process is contaminated with noise, two different techniques can be deployed; first, if the noise level is known a priori, basis pursuit denoising (BPDN) [25] can be applied. However, if there is no knowledge about the noise level, least absolute shrinkage and selection operator (LASSO) presents an efficient approach to recover the original signal.Greedy algorithms provide a suboptimal recovery for sparse signals, yet they outperform convex optimization approaches in the case where the signal of interest is highly sparse [17]. Greedy algorithms solve (1) iteratively by taking locally optimal decisions. These algorithms aim to find the locations of the nonzero coefficients to enable a fast recovery. Greedy algorithms include several variants such as gradient pursuit, matching pursuit (MP) [26], and OMP [17]. OMP offers a fast recovery compared to convex optimization approaches; however, it suffers from bad recovery quality for signals with a low degree of sparsity. Thus, several improved versions of OMP have been proposed, such as CoSaMP [19], SP [20], and StOMP [18].


## 2.3. Distributed Compressive Sensing

Conventional CS exploits only the sparsity of the data. However, if the same data is collected using different sensing nodes or different channels, their measurements would be highly correlated. In such scenario, the measurements exhibit the same behavior, such as being sparse in a particular domain.Therefore, in a multichannel CS-based data acquisition system, each sensing node collects and compresses its data individually without taking any considerations about the other nodes. For the recovery, two approaches can be considered to reconstruct the data; first, data reconstruction can be performed on each sensing node individually, this approach ignores the dependency between the measurements of different sensors, and, hence, the quality of the reconstruction depends only on the sparsity of each recording. The second approach exploits the collaboration between all measurements to obtain more information about the data; thus, a better reconstruction quality can be achieved. This process is called joint measurement setting and it has motivated the introduction of the DCS concept.DCS presents a new distributed coding framework that exploits both the sparsity of the signal and the correlation between the different signals in multisensing architectures. In the DCS acquisition stage, each sensor collects its measurements by taking random projections of the signal without any consideration about the states of the other sensors in the network. However, the reconstruction phase exploits the intersignal correlation by using all of the obtained measurements to recover all the signals simultaneously.


## 3. CS-Based EEG Compression

EEG is a well-considered framework to measure the electrical activity of the brain; EEG signals are widely used to detect different types of neurological disorders such as comas, epilepsy, and sleep disorders. Moreover, EEG can also be used for nonmedical applications such as brain-computer interface. EEG signals are recorded over a long period of time using a set of electrodes placed over the head of the subject. EEG signals are considered as a multivariate signal acquired via multiple channels which results in the generation of big EEG data that need to be stored and transmitted. However, several studies have highlighted the limitation of such approach in terms of high energy consumption due to massive raw data streaming. Thus, EEG monitoring platforms would benefit from more power efficient sampling and compression prior to wireless transmission. These limitations motivate the incorporation of CS and DCS to the EEG acquisition and compression.


### 3.1. Related Work

CS-based EEG monitoring has been investigated in the literature. First, the feasibility of applying CS to EEG acquisition has been addressed in [11, 27]. The authors quantified CS-based EEG monitoring, where CS has been used as a compression technique to reduce both the storage and the processing load. The obtained results revealed that CS does not provide a good reconstruction quality unless an appropriate acquisition scheme is deployed. CS can be applied only if at least 22 channels are deployed to collect the EEG data.The low sparsity of the EEG raw data in both time and frequency domains presents the main challenge in the design of CS-based EEG monitoring systems. Thus, a great attention was dedicated to providing dictionaries and basis that render a high sparse representation of EEG signals. Subsequently, several dictionaries have been investigated in the literature such as Slepian basis, Gabor frames, and DWT matrices [12–15, 28]. In [12], Senay et al. quantified a CS framework for EEG compression using Slepian functions as a sparsifying dictionary. By projecting the EEG signal into the Slepian basis, a sparse representation is achieved; hence, the EEG can be efficiently compressed with CS at a very low error rate. In addition, Aviyente analyzed a CS framework for EEG compression in terms of the mean square error (MSE) using Gabor frame method as sparsifying basis [13]. The author argued that chirped Gabor dictionary would be very efficient and it can increase the sparsity of the signals; hence, it improves the performance of CS-based EEG monitoring. On the other hand, Gangopadhyay et al. claimed in [14] that wavelet-based dictionaries are more suitable for CS-based EEG compression than the previously mentioned approaches. Author in [11] have provided a detailed performance study for six different sparsifying dictionaries, namely, Gabor, Mexican Hat, cubic Spline, linear Spline, cubic B-Spline, and linear B-Spline. In the paper, intensive sets of simulations were carried out for different reconstruction algorithms in 18 different test conditions. The B-Spline dictionaries proved to be the most promising, yielding best reconstruction quality and achieving the lowest error rates. Furthermore, Liu et al. proposed in [16] a new framework for EEG monitoring based on sparse signal recovery method and simultaneous cosparsity and low-rank (SCLR) optimization approaches. The proposed approach utilizes second-order difference matrix as the sparsifying basis and l0 minimization for data reconstruction. Nevertheless, Zhang et al. explored the BSBL which was initially developed in [29] to empower ECG signal monitoring for EEG reconstruction [15]. The idea of the paper is that, instead of finding the optimal sparsifying dictionary, the authors used general dictionary matrices (DWT and DCT) to represent the EEG signal. Yet, they explored BSBL to take advantage of the block structure of the EEG signal. The results revealed an acceptable reconstruction quality for particular sets of applications.Besides evaluating the sparsity, the metrics for EEG data reconstruction have been investigated as well. For instance, root-mean-squared difference (PRD) has been used to evaluate the reconstruction quality of EEG reconstruction in [30]. However, different thresholds have been established based on the targeted application. In [31], based on energy preservation criterion, authors determined that the maximum PRD which provides an acceptable recovery is 7%. Such PRD value can guarantee that 99.5% of the signal energy is persevered, whereas Higgins et al. demonstrated in [32] that up to 30% PRD is tolerable with EEG compression for applications of automated seizure detection.Table1 expatiates on the comparative results between several works presented in the literature on the integration of CS in context of EEG monitoring.Table 1
Summary of CS-based EEG monitoring approaches presented in the literature.
References
Sparsifying basis
Reconstruction algorithm
CR
PRD
MSE
Abdulghani et al. [11]
B-Spline
BP
0.33
18.61
—
Casson and Rodriguez-Villegas [33]
DWT
BP
0.4
25
—
Zhang et al. [15]
DWT
BSBL
0.5
—
0.078
Liu et al. [16]
Second-order difference matrix
l0
0.5
—
0.045


### 3.2. Joint Channel Reconstruction

In a multichannel acquisition scenario, the joint sparsity of the signal ensemble is often smaller than the aggregate over individual signals sparsities [4]. Therefore, if the signal of interest is characterized by a weak sparsity, such as EEG signals, it is possible to explore the joint sparsity of the ensemble. In addition, exploiting joint sparsity would result in a remarkable reduction in the number of measurements required to achieve an acceptable recovery.The corresponding CS model CS-based EEG compression system for theJ channels can be written as follows:(3)Y=ΦX, where X=[x1,x2,…,xJ]∈RN×J denotes the original EEG raw data and N is the number of samples in each channel, whereas Y=[y1,y2,…,yJ]∈RM×J denotes the compressed form of the EEG data.The proposed method represents the multichannel signal data by stacking, column-wise, the measurement vectors of the different channels into a single vector. This approach allows the recovery of a multiple channel recording simultaneously by exploring their joint sparsity in order to reduce the number of the required measurements for each channel as well as achieve a better reconstruction quality than the conventional CS recovery which recovers each of the channel measurements individually.The joint-measurements acquisition model can be expressed as(4)Yj=ΦXjj=1,2,…,l,where l is an integer number such that l=J/Λ and Λ denotes the number of channels to be recovered simultaneously. The vector [X]j∈RΛ×N is the column-wise stacking of the elements of X such that [X]j=[xj-1Λ+1T,xj-1Λ+2T,…,x(j-1)Λ+ΛT]T.For EEG data recovery, each[X]j is reconstructed individually by applying the SP algorithm. The pseudocode for SP algorithm is presented in Algorithm 1.Algorithm 1:Subspace pursuit algorithm.
Input:
[
Y
]
j: measurement vector
Φ: sensing matrix
ϵ: stopping criterion
k: sparsity estimate
Initialization:
Ω=[]
r[0]=[Y]j
current iterationi=0
Procedure: While  ri-ri-12≥ϵ  and  ri2≤ri-12
(1) i=i+1
(2) G[i-1]=Φ∗r[i]
(3) Ω[i]={k indices corresponding to the largest absolute value of G[i]}
(4) Ω=Ω∪Ω[i]
(5) [X]jΩ[i]=ΦΩ†[Y]j
(6) r[i]=[Y]j-ΦΩ[X]j[i]
Output:
X
j
^: reconstructed EEG signal that satisfies Xj^{1,...,N}-Ω=0 and XjΩ[i]=ΦΩ†Yj


### 3.3. Proposed DSSP Algorithm

Unlike SAMP, this paper proposes the DSSP algorithm, which follows a straightforward modification to the SP algorithm by exploring the key idea of CS. That is, if the signal is highly compressible, then only a small number of the coefficients capture most of the signal’s energy. Subsequently, by locating these coefficients at each iteration, the true support of the signal (the locations of the largest nonzero coefficients) can be identified.Moreover, as the signal structure often changes with time, its sparsity changes as well. Thus, to cope with this variation in the signal structure, the algorithm should exhibit a dynamic selection approach; that is, the number of selected coefficients at each iteration should be updated depending on the changes in the signal structure. Hence, the proposed DSSP algorithm follows an energy-based selection approach that updates the number of selected coefficients depending on the acquired signal at any given time.Therefore, in the DSSP algorithm, rather than selecting a fixed number of coefficients at each iteration, the algorithm locates the indices of the minimum number of coefficients that capture the most of the signal’s energy. This approach expands the true support of the signal stage by stage. In addition, DSSP refines the estimated signal at each iteration, where the columns of the sensing matrix corresponding to the locations of the selected coefficients are used to solve a least square problem. This process is repeated until an acceptable quality of reconstruction is achieved based on error minimization condition.In order to select the appropriate number of coefficients that capture most of the signal proxy energy at each iteration, the parameter0<λ<1 is defined as the rate between the energy of the selected coefficient and the energy of the signal proxy at each iteration. Therefore, in order to select the appropriate set of coefficients that holds most of the signal proxy energy, the parameter λ can be selected as high as possible as long as it allows the selection of at least one coefficient at each iteration.The pseudocode of the DSSP is listed in Algorithm2.Algorithm 2:Dynamic selection subspace pursuit (DSSP) algorithm.
Input:
[Y]j: measurement vector
Φ: sensing matrix
ϵ: stopping criterion
λ: Energy parameter, 0<λ<1
Ω=[]
r[0]=[Y]j
current iterationi=0
Procedure: While  r[i]-r[i-1]2≥ϵ
and ri2≤r[i-1]2
(1) i=i+1
(2) Calculate the signal proxy G[n][i-1]=Φ∗r[i]
(3) Calculate the energy of the signal proxy
E
=
1
N
∑
n
=
1
N
G
n
2
(4) Sort G[n][i-1] in an ascending order
(5) Ω[i] = minimum k indices corresponding to the largest
absolute that satisfies
P
|
Ω
=
1
k
∑
n
=
1
k
|
G
[
n
]
|
2
≥
λ
E
(6) Ω=Ω∪Ω[i]
(7) [X]jΩ[i]=ΦΩ†[Y]j
(8)r[i]=[Y]j-ΦΩ[X]j[i]
Output:
X
j
^: reconstructed EEG signal that satisfies Xj^{1,...,N}-Ω=0
andXjΩ[i]=ΦΩ†Yj


## 3.1. Related Work

CS-based EEG monitoring has been investigated in the literature. First, the feasibility of applying CS to EEG acquisition has been addressed in [11, 27]. The authors quantified CS-based EEG monitoring, where CS has been used as a compression technique to reduce both the storage and the processing load. The obtained results revealed that CS does not provide a good reconstruction quality unless an appropriate acquisition scheme is deployed. CS can be applied only if at least 22 channels are deployed to collect the EEG data.The low sparsity of the EEG raw data in both time and frequency domains presents the main challenge in the design of CS-based EEG monitoring systems. Thus, a great attention was dedicated to providing dictionaries and basis that render a high sparse representation of EEG signals. Subsequently, several dictionaries have been investigated in the literature such as Slepian basis, Gabor frames, and DWT matrices [12–15, 28]. In [12], Senay et al. quantified a CS framework for EEG compression using Slepian functions as a sparsifying dictionary. By projecting the EEG signal into the Slepian basis, a sparse representation is achieved; hence, the EEG can be efficiently compressed with CS at a very low error rate. In addition, Aviyente analyzed a CS framework for EEG compression in terms of the mean square error (MSE) using Gabor frame method as sparsifying basis [13]. The author argued that chirped Gabor dictionary would be very efficient and it can increase the sparsity of the signals; hence, it improves the performance of CS-based EEG monitoring. On the other hand, Gangopadhyay et al. claimed in [14] that wavelet-based dictionaries are more suitable for CS-based EEG compression than the previously mentioned approaches. Author in [11] have provided a detailed performance study for six different sparsifying dictionaries, namely, Gabor, Mexican Hat, cubic Spline, linear Spline, cubic B-Spline, and linear B-Spline. In the paper, intensive sets of simulations were carried out for different reconstruction algorithms in 18 different test conditions. The B-Spline dictionaries proved to be the most promising, yielding best reconstruction quality and achieving the lowest error rates. Furthermore, Liu et al. proposed in [16] a new framework for EEG monitoring based on sparse signal recovery method and simultaneous cosparsity and low-rank (SCLR) optimization approaches. The proposed approach utilizes second-order difference matrix as the sparsifying basis and l0 minimization for data reconstruction. Nevertheless, Zhang et al. explored the BSBL which was initially developed in [29] to empower ECG signal monitoring for EEG reconstruction [15]. The idea of the paper is that, instead of finding the optimal sparsifying dictionary, the authors used general dictionary matrices (DWT and DCT) to represent the EEG signal. Yet, they explored BSBL to take advantage of the block structure of the EEG signal. The results revealed an acceptable reconstruction quality for particular sets of applications.Besides evaluating the sparsity, the metrics for EEG data reconstruction have been investigated as well. For instance, root-mean-squared difference (PRD) has been used to evaluate the reconstruction quality of EEG reconstruction in [30]. However, different thresholds have been established based on the targeted application. In [31], based on energy preservation criterion, authors determined that the maximum PRD which provides an acceptable recovery is 7%. Such PRD value can guarantee that 99.5% of the signal energy is persevered, whereas Higgins et al. demonstrated in [32] that up to 30% PRD is tolerable with EEG compression for applications of automated seizure detection.Table1 expatiates on the comparative results between several works presented in the literature on the integration of CS in context of EEG monitoring.Table 1
Summary of CS-based EEG monitoring approaches presented in the literature.
References
Sparsifying basis
Reconstruction algorithm
CR
PRD
MSE
Abdulghani et al. [11]
B-Spline
BP
0.33
18.61
—
Casson and Rodriguez-Villegas [33]
DWT
BP
0.4
25
—
Zhang et al. [15]
DWT
BSBL
0.5
—
0.078
Liu et al. [16]
Second-order difference matrix
l0
0.5
—
0.045


## 3.2. Joint Channel Reconstruction

In a multichannel acquisition scenario, the joint sparsity of the signal ensemble is often smaller than the aggregate over individual signals sparsities [4]. Therefore, if the signal of interest is characterized by a weak sparsity, such as EEG signals, it is possible to explore the joint sparsity of the ensemble. In addition, exploiting joint sparsity would result in a remarkable reduction in the number of measurements required to achieve an acceptable recovery.The corresponding CS model CS-based EEG compression system for theJ channels can be written as follows:(3)Y=ΦX, where X=[x1,x2,…,xJ]∈RN×J denotes the original EEG raw data and N is the number of samples in each channel, whereas Y=[y1,y2,…,yJ]∈RM×J denotes the compressed form of the EEG data.The proposed method represents the multichannel signal data by stacking, column-wise, the measurement vectors of the different channels into a single vector. This approach allows the recovery of a multiple channel recording simultaneously by exploring their joint sparsity in order to reduce the number of the required measurements for each channel as well as achieve a better reconstruction quality than the conventional CS recovery which recovers each of the channel measurements individually.The joint-measurements acquisition model can be expressed as(4)Yj=ΦXjj=1,2,…,l,where l is an integer number such that l=J/Λ and Λ denotes the number of channels to be recovered simultaneously. The vector [X]j∈RΛ×N is the column-wise stacking of the elements of X such that [X]j=[xj-1Λ+1T,xj-1Λ+2T,…,x(j-1)Λ+ΛT]T.For EEG data recovery, each[X]j is reconstructed individually by applying the SP algorithm. The pseudocode for SP algorithm is presented in Algorithm 1.Algorithm 1:Subspace pursuit algorithm.
Input:
[
Y
]
j: measurement vector
Φ: sensing matrix
ϵ: stopping criterion
k: sparsity estimate
Initialization:
Ω=[]
r[0]=[Y]j
current iterationi=0
Procedure: While  ri-ri-12≥ϵ  and  ri2≤ri-12
(1) i=i+1
(2) G[i-1]=Φ∗r[i]
(3) Ω[i]={k indices corresponding to the largest absolute value of G[i]}
(4) Ω=Ω∪Ω[i]
(5) [X]jΩ[i]=ΦΩ†[Y]j
(6) r[i]=[Y]j-ΦΩ[X]j[i]
Output:
X
j
^: reconstructed EEG signal that satisfies Xj^{1,...,N}-Ω=0 and XjΩ[i]=ΦΩ†Yj


## 3.3. Proposed DSSP Algorithm

Unlike SAMP, this paper proposes the DSSP algorithm, which follows a straightforward modification to the SP algorithm by exploring the key idea of CS. That is, if the signal is highly compressible, then only a small number of the coefficients capture most of the signal’s energy. Subsequently, by locating these coefficients at each iteration, the true support of the signal (the locations of the largest nonzero coefficients) can be identified.Moreover, as the signal structure often changes with time, its sparsity changes as well. Thus, to cope with this variation in the signal structure, the algorithm should exhibit a dynamic selection approach; that is, the number of selected coefficients at each iteration should be updated depending on the changes in the signal structure. Hence, the proposed DSSP algorithm follows an energy-based selection approach that updates the number of selected coefficients depending on the acquired signal at any given time.Therefore, in the DSSP algorithm, rather than selecting a fixed number of coefficients at each iteration, the algorithm locates the indices of the minimum number of coefficients that capture the most of the signal’s energy. This approach expands the true support of the signal stage by stage. In addition, DSSP refines the estimated signal at each iteration, where the columns of the sensing matrix corresponding to the locations of the selected coefficients are used to solve a least square problem. This process is repeated until an acceptable quality of reconstruction is achieved based on error minimization condition.In order to select the appropriate number of coefficients that capture most of the signal proxy energy at each iteration, the parameter0<λ<1 is defined as the rate between the energy of the selected coefficient and the energy of the signal proxy at each iteration. Therefore, in order to select the appropriate set of coefficients that holds most of the signal proxy energy, the parameter λ can be selected as high as possible as long as it allows the selection of at least one coefficient at each iteration.The pseudocode of the DSSP is listed in Algorithm2.Algorithm 2:Dynamic selection subspace pursuit (DSSP) algorithm.
Input:
[Y]j: measurement vector
Φ: sensing matrix
ϵ: stopping criterion
λ: Energy parameter, 0<λ<1
Ω=[]
r[0]=[Y]j
current iterationi=0
Procedure: While  r[i]-r[i-1]2≥ϵ
and ri2≤r[i-1]2
(1) i=i+1
(2) Calculate the signal proxy G[n][i-1]=Φ∗r[i]
(3) Calculate the energy of the signal proxy
E
=
1
N
∑
n
=
1
N
G
n
2
(4) Sort G[n][i-1] in an ascending order
(5) Ω[i] = minimum k indices corresponding to the largest
absolute that satisfies
P
|
Ω
=
1
k
∑
n
=
1
k
|
G
[
n
]
|
2
≥
λ
E
(6) Ω=Ω∪Ω[i]
(7) [X]jΩ[i]=ΦΩ†[Y]j
(8)r[i]=[Y]j-ΦΩ[X]j[i]
Output:
X
j
^: reconstructed EEG signal that satisfies Xj^{1,...,N}-Ω=0
andXjΩ[i]=ΦΩ†Yj


## 4. Results and Discussion

In order to quantify the performance of CS-based scheme for EEG compression, intensive experiments have been carried out using MATLAB computing software. The EEG signals were taken from the database of the EEGLab [34]. The EEG database considered contains 80 channel recordings, each with 384 samples.In order to set up the simulations, Symlets wavelet-based transform [35] is used as sparsifying basis for the EEG signal. Symlets have been selected after several empirical simulations to determine the best wavelet class that provides the best reconstruction quality.In the design of the sensing matrix, two approaches have been adopted. In the first one, the entries of the sensing matrix are drawn from a normal distribution such thatΦ~(0,1/M). Whereas, in the second one, the entries are drawn form a Bernoulli distribution with entries {1,-1}. The experiments results are averaged on 100 trials.The signal reconstruction quality is evaluated in terms of the normalized mean square error (NMSE). NMSE calculates the 2-norm of the difference between the original ECG signal[X]j and the reconstructed one Xj^ as follows:(5)NMSE=Xj-Xj^22Xj22.Furthermore, the term compression ratio (CR) is defined as the ratio betweenM, the number of samples in the compressed signal, and N, the number of samples in the original ECG signal:(6)CR=MN.First, the adopted algorithm for EEG signal reconstruction is SP. As shown in Algorithm1, the SP algorithm requires the sparsity estimate as an input; however, there is no established rule to select the best sparsity parameter k. Thus, in order to determine the optimum value of k, intensive empirical simulations have been performed. The obtained results indicate that the optimal value of k for channel-per-channel reconstruction (EEG signal with 384 samples) is k=55±3. Subsequently, for joint channel reconstruction the best sparsity estimate value is k=Λ×55.Table2 presents performance comparison in terms of NMSE between the reconstruction quality of the proposed approach and the result presented in [15] where the same EEG data has been used. To this end, the number of samples to be transmitted M=N/2 is equal to the number of samples used in [15]. Moreover, in order to quantify the performance of our proposed approach, different values of Λ have been selected, such that Λ={1,2,4,8}. Λ=1 represents the case where each channel is recovered individually and no joint sparsity is explored. The results show clearly that exploiting the joint sparsity improves the reconstruction quality, where the latter increases with the increase of the number of channels recovered simultaneously. In addition, the choice of the sensing matrix does not have a great impact on the reconstruction quality except for the case where CR = 0.5, in which a better performance is obtained using Bernoulli matrix. Nevertheless, the reconstruction quality obtained in [15] still outperforms the quality achieved by the proposed approach.Table 2
Averaged reconstruction performance.
[15]
Λ=1
Λ
=
2
Λ=4
Λ
=
8
Random matrix
N/A
0.156
0.14
0.1056
0.092
Bernoulli matrix
0.078
0.157
0.1423
0.1051
0.0844The low quality of reconstruction obtained can be explained by the fact that the wavelet basis does not provide a good sparse representation to EEG data. Therefore, by using the concept of dictionary concatenation [36] which has been investigated for ECG signals in [8], a sparsifying basis for EEG has been proposed. The basis is constructed by selecting random elements from DCT and wavelet families, namely, Daubechies and Symlets.Figures1 and 2 present the reconstruction quality in terms of NMSE for different values of CR using random and binary sensing matrix, respectively. The obtained results consolidate the previous results where exploiting joint-recovery with Λ=4,8 enhances remarkably the reconstruction quality. Moreover, using the proposed dictionary renders a better reconstruction than using a DWT as sparsifying basis. Furthermore, the same reconstruction quality obtained in [15] by taking CR = 0.5 can be obtained by exploring joint-recovery combined with the proposed basis using only a CR = 0.3 for the case where Λ=8. On the other hand, with Λ=2, an inferior reconstruction quality is achieved compared to channel-per-channel recovery for CR value higher than 0.4. One reason for such inferior performance is the poor selection of the sparsity estimate for the SP algorithm; hence, SP is not robust to sparsity change within the different signal blocks.Figure 1
Recovery quality in terms of NMSE for different values of compression ratio (CR) using a random matrix.Figure 2
Recovery quality in terms of NMSE for different values of compression ratio (CR) using a binary matrix.Secondly, in order to quantify the performance of the proposed algorithm (DSSP), intensive numerical simulations have been carried out in order to determine the best approach to select the parameterλ. Figures 3 and 4 quantify the performance of the DDSP algorithm for different values of λ. Figure 3 presents the reconstruction quality in terms of NMSE for channel-per-channel recovery method. λ values have been selected such that λ={0.5,0.7,0.8,0.85,0.9,0.95}. The obtained results show that the NMSE decrease constantly with increasing the value of CR, which leads to a better reconstruction quality. In addition, the results show that, with value of λ=0.9, the signal true support is very well located at each iteration which provides a better reconstructing quality.Figure 3
Comparison between reconstruction quality of DSSP with SP for channel-per-channel recovery.Figure 4
Comparison between reconstruction quality of DSSP with SP for joint-recovery withΛ=2.Figure4 illustrates the performance for joint channel recovery with Λ=2, and the obtained results consolidate with the results presented in Figure 3 which shows the superiority of DDSP using λ=0.9 over the SP algorithm. However, when the value of λ approaches 1, the DDSP selects more coefficients at each iteration; subsequently, the coefficients which do not belong to the true support of the signal are more likely to be selected, which can degrade the quality of the reconstruction such as the case where λ=0.95.Figure5 presents the execution time for the SP with DSSP using different values of λ. The reported results are averaged over the reconstruction time for 80 channels. As the reconstruction time of the implemented algorithms is controlled by the speed of the processor and the number of tasks handled by the processor, all the algorithms have been implemented on the same program in a single PC to reduce the effect of this dependency. It is worth mentioning that the results are obtained using a PC equipped with an Intel Core i7-3770 @ 3.4 Ghz CPU and a RAM of 16.0 GB. The obtained execution time illustrates that, for CR values less than 0.4, SP converges faster compared to the proposed algorithm. However, it is worth mentioning that, for such low CR, SP does not guarantee an acceptable recovery quality. On the other hand, for CR higher than 0.4, although the proposed algorithm includes more steps in order to determine the best sparsity estimate at each iteration, the obtained results show that the proposed algorithm outperforms the SP algorithm in terms of the reconstruction time in case of λ=0.8. This can be explained by the fact that the proposed selection approach is more likely to determine the true support of the signal which will lead to a lower number of iterations to converge to the desired reconstruction quality. However, as DSSP achieves its best performance with λ=0.9 for a CR = 0.45 as shown previously in Figure 4, increasing the number of samples transmitted would result in an additional information about the signal which renders a faster recovery as illustrated by the decrease of the execution time from CR = 0.5 to CR = 0.6.Figure 5
Averaged Reconstruction Time (sec) for different CR values.


## 5. Conclusion

Biosignal compression represents a hot topic to be addressed in order to enable IoT-based connected health platforms that offer low-power consumption, simple system design, and efficient performance.Efficient EEG compression schemes using CS have not achieved the desired performance yet. This is mainly due to the nonsparse nature of EEG signals. This paper investigates the concept of joint-recovery to improve the reconstruction quality of EEG signals by exploiting the collaboration between the multichannel measurements. Moreover, the paper explores the idea of basis concatenation to tackle the issue of EEG nonsparsity. The experimental results have been compared to the state-of-the-art BSBL algorithm using the same database as well as similar system setup. Thus, by adopting SP-based joint channel recovery, the achieved reconstruction quality outperforms the one obtained BSBL algorithm. In addition, the paper quantifies the use of both Bernoulli and random matrices as sensing matrix; the obtained results reveal that both classes provide a similar performance in terms of quality of reconstruction. However, Bernoulli matrices have proved in the literature to be hardware friendly and offer a low system complexity.Furthermore, an adaptive reconstruction algorithm has been proposed to tackle the problem of the variation of the signal sparsity over time. The most prominent advantage of the proposed DSSP is the ability to provide a good reconstruction quality without prior knowledge of the signal sparsity which can be very useful in several applications.In conclusion, the obtained results are very promising and their hardware implementation for remote monitoring in IoT applications can be further investigated as future work.



---

*Source: 9823684-2017-11-29.xml*