Intra-Block Correlation and Sparse Sensing Matrices

In The Cost of Not Knowing, I stated at the very end that 

When solving for x in dimension N, you have to sample  x a few times if you have some knowledge of the deeper inter-dependencies between the elements of x. It's been shown to work recently. 

With this knowledge,  your cost for discovering x can be pretty low.

How low ? we're not sure yet

Zhilin sent me an email this morning alluding to this issue of "we're not sure yet". His empirical answer for x with a certain sparsity and some knowledge of the intra-correlation between the non zero elements seems to be close to that of last year's result (more recently here) from Florent Krzakala, Marc Mézard, François Sausset,Yifan Sun, Lenka Zdeborová.

This is fascinating but in return it begs other questions that seem to be furthered by the second half of his e-mail. I shall shall return to those issues later. In the meantime, here is Zhilin's e-mail

Hi.... Igor,

....

We recently updated our two papers, and some new features/results were added, which you may be interested in.

One is the paper on block sparse Bayesian learning: "Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation". The arXiv link is here: http://arxiv.org/pdf/1201.0862v2.pdf. You may be interested in Fig.1 and Fig.2 in the revised version, which show the phase transition curves of BSBL algorithms and other block sparse algorithms. You can see that the BSBL algorithms' phase transition curves show some interesting phenomenon: in many situations BSBL algorithms can recover a block sparse signals with K non-zero elements from only K measurements.

The second paper is, "Low Energy Wireless Body-Area Networks for Fetal ECG Telemonitoring via the Framework of Block Sparse Bayesian Learning". The arXiv link is here: http://arxiv.org/pdf/1205.1287v3.

In the revised version, we used another dataset (the OSET dataset), which contains much strong noise (e.g. baseline wanders), and the fetal hearbeat signals are completely buried in the noise (in our previous version the baseline wanders were very small). This dataset is a better representative to practical scenarios, since strong baseline wanders are often seen in raw fetal ECG recordings (and other physiological signal recordings), especially in wireless telemonitoring scenarios. Another interesting result is Fig.15, which shows the used BSBL algorithm's performance is not affected by the number of non-zero elements in each column of the sensing matrix. In other words, when each column of the sensing matrix contains only two non-zero elements, the BSBL algorithm still has the same performance.

This is probably different from some existing results using other algorithms, whose performance is sensitive to the number of non-zero elements in each column of the sensing matrix. And this result indicates that the BSBL algorithm can further reduce energy consumption in the signal compression stage.

If you have any comments, please feel free to let me know.

Best regards,

Zhilin

Thanks Zhilin !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.