ICT-2011.9.8 - FET ProactivePHIDIAS
Deliverable report for
P H I D I A S
"Ultra-Low-Power Holistic Design for Smart Biosignals Computing
Platforms"
Grant Agreement Number 318013
Deliverable D 1.4
Report describing the set of software optimization methods for best sparse recovery
Due date of deliverable: 30/09/2014
Actual submission date: 30/09/2014
Lead beneficiary for this deliverable: UNIBO
Contributors:
- EPFL: main effort
-UNIBO:review
Dissemination Level:PU / Public / X
PP / Restricted to other program participants (including the Commission Services)
RE / Restricted to a group specified by the consortium (including the Commission Services)
CO / Confidential, only for members of the consortium (including the Commission Services)
Version:1
Draft of the WP Leader
Commented version for amendment
Version accepted by the Steering Board / X
1.Abstract
Within previous deliverable (D 1.2), the partner EPFL has discussed the model based reconstruction technique to use additional structural information from underlying signal to improve the reconstruction quality. Exploiting this additional structural information is crucial for any state-of-the-art compression techniques, and it will result in much more optimized and robust compression techniques. In continuation of the structural sparsity models, here we extend our work to joint compression of multi-lead ECG signals.
Herein, we build on our findings by extending the recovery algorithm to use the group sparsity priors. Using group sparsity priors help to exploitthe strong correlation and to reduce even further amount of data to be transmitted wirelessly, thus addressing the important challenge of ultra-low-power embedded monitoring of multi-lead ECG signals.
2.Multi-lead Compressed Sensing and joint reconstruction
Capitalizing on sparsity, the Phidias consortium aims to apply the emerging CS approach(Donoho 2006) for a low-complexity, real-time and energy-efficient bio-signalsignal compression on WBSN motes.
In D1.1we have shown show that CS represents a competitive alternative to state-of-the- compression methodsfor monitoring systems based on Wireless Body Sensor Nodes (WBSNs), especially in the case of ECG acquisitions. The results validate the suitability of compressed sensing for real-time energy-aware ECG compression on resource-constrained WBSN motes. The results shown in D1.2 highlight thathaving additional information from sparsity structure over multiple signals could potentially lead to much optimized and robust recovery algorithms.
Figure 1 15-lead ECG recording
In these cases, sampling, compressing and reconstructing each signal individually is clearly sub-optimal, because leads are not independent sources, and are in fact strongly correlated. In the case of the multi-lead ECG acquisitions, all signals can be considered as different projections of a single multidimensional source, which in-fact is due to the electrical activity of the heart.
Figure 1 is an example window of 15-lead ECG recording, which shows presence of strong correlation among the leads.
The mutual information between the leads of bio-signals can be exploited to optimize CS-based compression, considering the example of multi-lead ECG acquisitions. We also propose techniques to exploit this information for optimized recovery of the joint compressed sensing. This optimization will directly translate to less measurement needed for the recovery, leading to reduction in transmission bandwidth (and ultimately, power consumption) without quality degradation.
1.1.Background on Multi-lead Compressed Sensing
The CS sampling and reconstruction steps are described in Deliverable 1.1 and 1.2. In this section we will discuss the problem of the multi-leads ECG signals and their joint compression. Letbe the real valued matrix ofECG signals where each column corresponds to a single ECG lead.
Wherecorresponds to lead number in -dimensional ECGmatrix . In general one can write the CS sensing as
whereis the sensing matrix and is vector representation of the matrix . The construction of the sensing matrix depends on the sampling strategy and the underlying structure of multi-lead signals . However, three main structures of the sensing matrix could be described as:
Distinct Distributed Sampling that is referred to the case where each lead is sampled by a distinct sensing matrix. Then this corresponds to a block diagonal general matrix :
where and is the sensing matrix applied to the column of the , and refers to the number of measurements collected from each lead . Here, we have a scenario where the number of measurements from each lead ( for all) is equal to the others, but same notation could be used if they are not, without loss of generality. This gives more freedom in designing the sensing matrix for each individual lead, in case there is a distinct structural sparsity within each lead.
Uniform Distributed Sampling is called to a sampling strategy where there is a unique sensing matrix for all leads. This model is also referred as Multiple Measurement Vectors (MMV) in literature(Cotter 2005) (Chen 2006). Then the general sensing matrix is:
where is unique sensing matrix for all the leads. This scenario is very well suited for the cases with a strong correlation between the leads.
Dense Sampling is the general sensing strategy where the sensing matrix does not have any specific structure and all the measurements convey some information from other leads. In two previous techniques, measurement vector has a group structure, where each group conveys information from a specific lead, for example first number of vector is the linear measurement collected from lead , and the second block of m in corresponds to the second lead and so on. In contrast to such a sensing strategy, if sensing matrix considered as a dense matrix, then all measurement entries have global information from all the leads.
This sensing strategy gives a maximum flexibility in designing the sensing matrix, but at a price of huge computational cost in implementation(Golbabaee and Vandergheynst, 2012).
3.Joint Reconstruction of Multi-lead compressed sensing
In this section, we will discuss the problem of the multi-lead ECG signals and their joint compression. Here since the sensing is done on a node with limited resources, we are using a uniform sensing matrix for multi-lead compressed sensing. Choosing such a uniform sensing matrix gives the minimum computational cost for implementation of encoder and decoder (since the main step in both involves the matrix multiplication). It is also more efficient choice in terms of required memory space for the storage, because it should be known in both encoding and decoding. Both these characteristics are of paramount importance when design a practical low-power sensing scheme. With this assumption, then the problem could be written as:
whereis our uniform sensing matrix and is our measurement matrix. Similar to single lead case, let us imagine that is the matrix of the wavelet representation of the original ECG matrix:
and , is the vector of wavelet coefficients of each ECG lead which is spars. Given the sparsity assumption of the matrix , similar to the single lead compressed sensing, one can try to solve the BPDN problem to recover the original data.
Equation 1
which very similar bound on recovery error could be obtained. The recovery algorithm, which here we call it normal CS does not consider the correlation among the leads. It is shown that for multi-lead signal recovery has a weak performance. Additionally, we have used two techniques for recovery exploiting the strong correlation among the leads, which are describes in following.
1.2.Joint support selection
As mentioned before, we propose to leverage the similarities between multiple channels to obtain a high-performance CS-based methodology. Following this intuition, we propose and evaluate a novel algorithm for joint reconstruction of multi-lead bio-signal acquisitions. Figure 2 shows the support of the best -term approximation of the investigated multi-lead ECG recordings. As detailed in D1.2, it shows that support set of the -term approximation for leads are very similar, so that a joint sparse support selection can be performed in the reconstruction algorithm.
Figure 2 - Support of the best -term approximation of multi-lead ECG signals.
As discussed before, sparsity support is given by an “oracle”, then solving the CS problem is reduced to a least square problem and could be solved very efficiently. Here, with some approximation we could consider that all the leads share the same sparse support. In literature, few greedy techniques are proposed to select such a joint-sparsity support(Duarte 2005) (Tropp 2006) (Golbabaee and Vandergheynst 2009). Very similar to these approaches, here we are also using a greedy technique to select the set of the highest possible candidate from all the lead as our support. However, we need to fix the sparsity before.
Compression Ratio and Best s-term Approximation
We have discussed before that ECG signals are compressible, but they are not exact sparse. This means that their expansion of the proper transformation domain, like the discrete wavelet domain, results in a compressible representation.
In case of exact sparse signals, the number of required measurements for the sensing matrix, which holds RIP is while for compressible signal the number of measurements depends on the level of sparsity and the desired reconstruction quality, which is essentially bigger than this number.
Moreover, in the illustrated scenario of joint support selection, the amount of similarity between the best -term approximation support of each lead and the reference one plays an important role, and must be investigated. To do so, we employed a similar strategy to the one proposed in D1.2, defining a constant value as the fraction of sparsity level over the number of measurements : . In our simulations for each number of measurements , different values for corresponding to different values of -term approximations of other leads are investigated. Figure 3 shows the results of output SNR over all records of the database. Different curves for each values of are plotted. The plot shows that how for different values of acquired number of the measurements the best -term approximation will change.
Figure 3 - Averaged SNR for fixed number of measurements over different selection of the cardinality of the support, normalized over
Based on the results shown on the Figure 3, the best value of for each number of is extracted. Figure 4 shows these values for different number of measurements.The results show that for small number of measurements, strong similarity exist between the support set of leads, so that a small cardinality in the support is required to reach the best results. Instead, for higher values of the , similarity between the support set of the leads could not add any additional information. In other words, in case of higher number of measurements, since signals are not exact sparse, even coefficients with small values impact the quality of the input reconstruction.
Figure 4- Best value for s corresponding to different values of measurements’ number (m).
1.3.Group sparsity and joint reconstruction
The second approach is to use convex relaxation by replacing the sparsity-inducingnorm with some other matrix norm to promote a joint sparsity selection in the solution.
We could rewrite the problem of Equation 1 in the form:
whereis a convex differentiable function and is a sparsity-inducing norm. Here, our data-fitting function is and usually in context of the CS reconstruction norm is used to enforce sparsity.
In case of the multi-lead ECG compression, where there is a strong correlation between the sparsity structures among the leads, the model of sparse coefficients should be refined to take this into account.
In such a situation, where nonzero coefficients are naturally partitioned into subsets or groups, the best choice could be using a group-sparsity inducing term (Kowalski 2009). Figure 2shows the support of the best -term approximation of the investigated multi-lead ECG recordings. It shows that support set of the -term approximation for leads are very similar, so that a joint sparse support selection can be performed in the reconstruction algorithm.
We propose to achieve this by replacing the traditional norm with the following group prior:
whereis a partition of and denotes the vector in recording the coefficient of indexed by in . This is known as a mixed -norm. It behaves like a-norm on the vector in , and therefore, induces group sparsity.
The CS problem (Equation 1) can be cast as a second order cone-programming problem and thus could be solved via interior point methods(Nesterov 1994). However, it involves dense matrices, which often preclude the use and potential advantage of sophisticated interior point methods. Here, we use the class of proximal methods, which involves very cheap computational effort compared to interior point methods. This class of methods could be applied to solve a problem of the form (Equation 1), where the problem is as the sum of a generic smooth differentiable function with Lipschitz-continuous gradient, and a non-differentiable function . Here we use the Fast Iterative soft thresholding algorithm (FISTA) for reconstruction, where the proximal step is replaced by soft thresholding and mixed -norm for normal CS and joint reconstruction respectively(Beck 2009).
4.Experimental Results
To validate the performance of the proposed joint compression scheme, we use the PTB Diagnostic ECG Database (Goldberger 2000), available on the physionet website. The database contains 549 records of 15-lead ECG from 290 subjects. Signals are sampled at 1KHz with 16-bit resolution. This database has been described in subsection Deliverable 1.
1.4.Joint Support selection
Here in this section, we present the results for the “Joint Support” selection algorithm where the best sparsity support is selected. For each given number of measurements, we fix the sparsity level , and we find the best set of sparse support.
Figure 5- Averaged SNR for Joint sparse selection and normal CS.
Figure 5 shows the comparison between the performance quality of normal CS reconstruction and the joint support selection technique in terms of averaged output SNR. The results show that exploiting these similarities between the support sets among different leads could reach to a significant gain, when a small number of measurements are considered; but for larger number of measurements it fails to improve reconstruction.
The results show that by applying the joint reconstruction even a very small number (20%) of measurements would suffice to reach a good signal reconstruction. Moreover, even for very small number of measurements (like 5%) where normal CS reconstruction fails, by using the joint CS it is still possible to recover the signals and reach to the performance quality of about 10 dB.
1.5.Joint CS reconstruction with mixed -norm
Here, in this section we present the results for both normal CS reconstructions with regularization per channel and joint group reconstruction with -norm. In all our experiments ECG matrix is a window of size and .
For sensing matrix , sparse random binary matrix is used, where each column contain only nonzero elements (Mamaghanian, Khaled, et al, 2011). The results are averaged over 100 packets randomly selected from all the database records.
Figure 6- Output averaged SNR (top) and PRD (bottom) overall records for different compression ratios
Figure 6 compares the output SNR and PRD, averaged over all database records, for both algorithms and different compression ratios. The “Normal reconstruction” and “Joint reconstruction” correspond to convex minimization with and constrains respectively. This figure shows the average PRD and SNR, but there is a large variance across individual records.
Alternatively, Figure 7 shows the box plots for both algorithms. On each box, the central mark is the median, the edges of the box are the 25th and 75th percentiles, and the whiskers extend to the most extreme.
In both figures the level corresponding to the “good” (corresponding to PRD level between 2% and 9%) and “very good” (PRD level below than 2% reconstruction qualities are indicated. It shows that the joint reconstruction clearly outperforms the normal CS reconstruction for all compression ratios: “good” reconstruction quality for Normal CS can be reached with 65.9% of compression, while for joint reconstruction this number could increase close to 7% to reach up to 72.7%.
As noted in our previous work (Mamaghanian, Khaled, et al., 2010), compression can be further enhanced by removing inter-packet redundancy and performing Huffman coding. The results of our work indicate that the compression level could be enhanced by close to 50% by removing the inter-packet redundancy and Huffman coding without impacting the reconstruction quality.
Figure 7Box plots for all database records for Normal reconstruction (top) and Joint reconstruction (bottom)
Figure 8 and Figure 9 compare the averaged SNR for each lead for different compressions. The output SNR iscolor-coded. These figures also show that joint reconstruction enhances the quality of all leads at the same time. The weak behavior for leads number 4 and 7, compared to other leads are because these leads are very noisy compared the rest of the leads. This is also shown on the Normal reconstruction in Figure 8.
Figure 8Averaged SNR for all the leads for different compression levels for normal CS
Figure 9Averaged SNR for all the leads for different compression levels for joint reconstruction (bottom)
1.6.Energy Consumption Analysis
In this section, we further investigate the power consumption of both algorithms. Our experimental setup consists of a Shimmer wireless node( embedded ECG compression by CS and wirelessly transmitting the compressed data using its IEEE 802.15.4-compliant radio to a remote base station. A simple medium access control (MAC) scheme is implemented between the node and the base station in FreeRTOS: the base station periodically sends a beacon to maintain node synchronization, and the ECG sensing node sends its data in its guaranteed time slots (GTS), which is assigned by the base station and notified in the beacon. This simple MAC is in fact compatible with the beacon-enabled mode of the IEEE 802.15.4 MAC protocol (IEEE 2003).