Our work on compressed sensing of fetal ECG has been accepted by IEEE T-BME

Our work on compressed sensing of fetal ECG has been accepted by IEEE Trans. Biomedical Engineering. The details are as follows:

Compressed Sensing for Energy-Efficient Wireless Telemonitoring of Non-Invasive Fetal ECG via Block Sparse Bayesian Learning,  
by Zhilin Zhang, Tzyy-Ping Jung, Scott Makeig, Bhaskar D. Rao, accepted by IEEE Trans. Biomedical Engineering.   
Available at:  http://arxiv.org/abs/1205.1287, Codes can be downloaded at: http://dsp.ucsd.edu/~zhilin/BSBL.html, or  https://sites.google.com/site/researchbyzhang/bsbl


Note that there are two groups of works on compressed sensing of ECG. One is the ECG compression (just like video compression, image compression, etc). Most works actually belong to this group. They generally use some MIT-BIH datasets, which are very clean (noise is removed).

Another group is compressed sensing of ECG for energy-efficient wireless telemonitoring. There are only few works in this group. Our work belongs to this group. In this group the ECG data is always contaminated by noise and artifacts ('signal noise'). This is because the goal of telemonitoring is to allow people to walk and even exercise freely, and thus strong noise and artifacts caused by muscle and electrode movement are inevitable. Furthermore, artifacts caused by battery power level also cannot be ignored. Consequently, the raw ECG recordings are not sparse in the time domain and also not sparse in the transformed domains (e.g. the wavelet domain, the DCT domain). However, the strict constraint on energy consumption (and design issues, etc) of telemonitoring systems does not encourage filtering or other preprocessing before compression. Or, put in another way, if energy consumption and design issues are not problems, CS may have no advantages over traditional methods. Thus, CS algorithms have to recover non-sparse signals for this application. It turns out that the problem is very challenging.

Our work not only solves this challenging problem, but also has some interesting mathematical meanings:

By linear algebra, there are infinite solutions to the underdetermined problem y=Ax. When the true solution x0 is sparse, using CS algorithms it is possible to find it. But when the true solution x0 is non-sparse, finding it is more challenging and new constraints/assumptions are called for. This work shows that when exploiting the unknown block structure and the intra-block correlation of x0, it is possible to find a solution x_est which is very close to the true solution x0. These findings raise new and interesting possibilities for signal compression as well as theoretical questions in the subject of sparse and non-sparse signal recovery from a small number of measurements y.

Below is the paper's Abstract:
Fetal ECG (FECG) telemonitoring is an important branch in telemedicine. The design of a telemonitoring system via a wireless body-area network with low energy consumption for ambulatory use is highly desirable. As an emerging technique, compressed sensing (CS) shows great promise in compressing/reconstructing data with low energy consumption. However, due to some specific characteristics of raw FECG recordings such as non-sparsity and strong noise contamination, current CS algorithms generally fail in this application.

This work proposes to use the block sparse Bayesian learning (BSBL) framework to compress/reconstruct non-sparse raw FECG recordings. Experimental results show that the framework can reconstruct the raw recordings with high quality. Especially, the reconstruction does not destroy the interdependence relation among the multichannel recordings. This ensures that the independent component analysis decomposition of the reconstructed recordings has high fidelity. Furthermore, the framework allows the use of a sparse binary sensing matrix with much fewer nonzero entries to compress recordings. Particularly, each column of the matrix can contain only two nonzero entries. This shows the framework, compared to other algorithms such as current CS algorithms and wavelet algorithms, can greatly reduce code execution in CPU in the data compression stage.


PS: When I wrote this paper, I was in my wife's delivery room. My wife was lying on the bed, resting and waiting for her midwife. I was sitting beside her, writing the paper in my laptop (and trying to finish the main framework before the miracle moment). Now the baby is 8-month.

Yes, let's Move From Sparsity to Structured Sparsity

Igor wrote a cool post in Nuit Blanche yesterday: Pushing the Boundaries in Compressive Sensing by proposing the following questions (quoted below):

• Given that compressive sensing is based on an argument of sparsity 
• Given that sparsity is all around us because most data seem to be sparse or compressible in a wavelet basis
• Given that wavelet decomposition not only shows not just simple compressibility but structured compressibility of most datasets
• Given that we now have some results showing better compressive sensing with a structured sparsity argument

Isn't it time we stopped talking about RIP ? the Donoho-Tanner phase transition ? L_1 recovery ?

My answer is "YES"! There are a lot of practical scenarios where signals (or the regression coefficients) have rich structure. Merely exploiting sparsity without exploiting structure is far from enough! Even in some cases where structure information is not obvious and generally traditional L1 recovery algorithms are used, we can still find a way to use structured-sparsity-based algorithms.

In the following I'll give an example on the recovery of compressed audio signals, which is a typical application. I've seen a number of work which used traditional L1 algorithms to do the job. Let's see how a block-structure-exploited algorithm can improve the result.

Below is an audio signal with the length of 81920. 

In the compression stage, it was evenly divided into T segments x_i (i=1,2,...,T). We considered five cases, i.e., T choosing 160, 80, 40, 20, and 10. Accordingly, the segments had the length of N = 512, 1024, 2048, 4096, and 8192.  Each segment, x_i, was compressed into y_i. The sensing matrix A was a random Gaussian matrix with the dimension N/2 by N.

In the recovery stage, we first recovered the DCT coefficients of each segment, and then recovered the original segment. This is a tradition method used by most L1 algorithms for this task, since audio signals are believed to be more sparse than in the time domain.

We used six algorithms which do not consider any structure information. They were: Smooth L0 (SL0), EM-BG-AMP, SPGL-1, BCS, OMP, and SP. Their recovery performance was measured by total speed and the normalized MSE (calculated in dB). The results are given in the following table:

Table: Performance of all algorithms measured in terms of normalized MSE in dB (and speed in second).

From the Table, we can see if we want to obtain good quality, we need to increase the segment length. However, the cost is that the recovery time is significantly increased. For example, to achieve the quality of MSE = -21dB, SL0 needed to recover segments of the length 8192, and the total time was 2725 seconds!

Now let's perform the BSBL-BO algorithm, a sparse Bayesian learning algorithm exploiting block structure and intra-block correlation,  to do the same task. As I have said in many places, BSBL-BO needs users to define a block partition, and the block partition is not needed to be consistent with the true block structure of signals. So, we defined the block partition as (in Matlab language): [1:16:N]. The complete command for recovering the i-th segment was:

Result = BSBL_BO(A,  y_i, [1:16:N], 0, 'prune_gamma',-1, 'max_iters',15);

The recovery result for the case N=512 is given in the above Table. Clearly, by exploiting the structure information, BSBL-BO achieved -23.3 dB but only cost 82 seconds! The quality was 2 dB higher than that of SL0 but cost only 3% of the time cost by SL0.

What this result tells us? 

First, exploiting both structure and sparsity is very important; merely exploiting sparsity is outdated in many practical applications.

Second, conclusions on which algorithms are fast or slow are weakened if not mentioning which practical task is finished by these algorithms. Based on specific tasks, the answer could be varied case by case. For example, in the above experiment SL0 was very faster than BSBL-BO given the same segment length N. However, if the goal is to achieve a good quality, it took much longer time than BSBL-BO (even could not achieve the same quality as BSBL-BO, no matter how large the N was).

Note, I was not trying to compare BSBL-BO with the other algorithms. The comparison was not meaningful, since BSBL-BO exploits structure while the other algorithms do not. The point here is, even for some traditional applications where L1 algorithms were often used, exploiting structure information can provide you a better result!

PS: Recently we have an invited short review paper on SBL algorithms exploiting intra- and inter-vector correlation,
Bhaskar D. Rao, Zhilin Zhang, Yuzhe Jin, Sparse Signal Recovery in the Presence of Intra-Vector and Inter-Vector Correlation, SPCOM 2012
which can be accessed at: http://arxiv.org/pdf/1205.4471v1

Besides, several months ago we have another review paper on SBL algorithms exploiting structure, titled "From Sparsity to Structured Sparsity: Bayesian Perspective", in the Chinese journal Signal Processing. Those who can read Chinese can access the paper from here.