Bound-Optimization based Block Space Bayesian Learning - implementation -

Zhilin just wrote the provocative Is compressed sensing really useful for wireless telemonitoring of non-sparse physiological signals (Part 1)? where he makes the case that in most physiological signals the small stuff is sometimes as important as the large ones and that in effect in most conditions these signals are not sparse or barely compressible. This is exactly what Yonina Eldar was saying at the MIA 2012 meeting when she was talking about compressed beamformining [1] additonal work into sub-Nyquist sampling can be found in [2] and [3]. Zhilin  however takes a different route it seems, i.e. more in line with structured sparsity. Going back to Zhilin's argument:

.....Clearly, we can see, if a compressed sensing algorithm can be widely used in wireless telemonitoring, it must has the ability to recover non-sparse physiological signals, which completely contradicts the sparsity assumption in all the compressed sensing algorithms.

One may ask, there is another way for compressed sensing of non-sparse signals: suppose a non-sparse signal can be represented in a transform domain (e.g. wavelet domains, DCT domains, etc), such that the representation coefficients are sparse, i.e., x = Bz,

where x is the signal, B is the basis of the transform domain, and z is the representation coefficients. Then, the signal x is compressed by, y = Ax,

where y is the compressed signal, and A is the sensing matrix. In the remote terminal, the compressed data y and the matrix product AB are used to recover the sparse coefficients z according to the relation: y = (AB) z. And then the original signal x is recovered by the relation x = Bz.

However, the success of this method relies on the sparsity of the representation coefficients z. Unfortunately, for most physiological signals, z is not sparse enough, and completely recovering z is still a challenge for most compressed sensing algorithms (especially the sensing matrix A is a binary sparse matrix, a requirement of telemonitoring with low energy consumption)....

The paper introducing the Bound-Optimization based Block Space Bayesian Learning is: Low Energy Wireless Body-Area Networks for Fetal ECG Telemonitoring via the Framework of Block Sparse Bayesian Learning by Zhilin Zhang, Tzyy-Ping Jung. , Scott Makeig , Bhaskar D. Rao . The abstract reads:

Fetal ECG (FECG) telemonitoring is an important branch in telemedicine. The design of a telemonitoring system via a low-power wireless body-area network for ambulatory use is highly desirable. As an emerging technique, compressed sensing (CS) shows great promise in compressing data with low power consumption. However, due to some specific characteristics of FECG recordings such as non-sparsity and strong noise contamination, current CS algorithms generally fail in this application. In this work we utilize the block sparse Bayesian learning (bSBL) framework, a recently developed framework solving the CS problems. To illustrate the ability of the bSBL methods, we apply it to two representative FECG datasets. In one dataset the fetal heartbeat signals are visible, while in the other dataset are barely visible. The experiment results show that the bSBL framework is capable of compressing FECG raw recordings and successfully reconstructing them. These successes rely on two unique features of the bSBL framework; one is the ability to reconstruct less-sparse but structured signals, and the other is the ability to learn and exploit correlation structure of signals to improve performance. These two abilities of the framework greatly enhance the potential use of bSBL in telemonitoring of other physiological signals.

The BSBL-BO algorithm to break through the bottleneck in wireless telemonitoring using compressed sensing is here. Stay tuned to part 2 of this argument: 

[1] Compressed Beamforming in Ultrasound Imaging by Noam Wagner, Yonina C. Eldar, Arie Feuer, Zvi Friedman.

[2]  Innovation Rate Sampling of Pulse Streams with Application to Ultrasound Imaging by Ronen Tur,  Yonina C. Eldar, Zvi Friedman. 

[3] Sub-Nyquist Radar, Omer Bar-Ilan and Yonina C. Eldar





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.

Around the blog in 80 hours: Compressive Sensing and Advanced Matrix Factorization Edition

Since the last "around the blogs in 80 hours" blog entry, I had to answer a pretty common beginner's question in  The answer is still No. We then had a large  Compressive Sensing This Week entry and eventually a stream of papers and implementation on Analysis Operators that started with an implementation featured in Noise Aware Analysis Operator Learning for Approximately Cosparse Signals. Then the subject slided into inpainting with  90% missing pixels and you reconstructed that ?! Analysis Operator Learning and Its Application to Image Reconstruction and  Inpainting Algorithm on GitHub (TV-L2 denoising and inpainting). I ended having to comment on Learning Analysis Operators. In the meantime, there is an implementation available for  Incremented Rank PowerFactorization algorithm. Other entries/tweets that caught my attention included the following:

• Suresh mentions the Summer School on Massive Data Mining in August in Copenhagen.
• Emmanuel has a full entry on his release of an OpenCV/C++ implementation of TV-inpainting capability I mentioned here. It's in French but here is a Google translation.
• Vladimir points to Brandywine's 1 Gigapixel Hyperspectral CMOS Sensor
• Djalil mentions Simulating random walks bridges
• Roberto looks deeper in Particle Sketches / 2 - Working Around The Central Limit Theorem
• Bob talks about the Paper of the Day (Po'D): Semantic gap?? Schemantic Schmap!! Edition
• Laurent and Petros pointed to this piece entitled "A World Without Referees" by Larry Wasserman

And then some comments:

One of Vladimir Ignatovich's work in ultra-cold neutrons has been trying to figure out why some neutrons at very low energy get absorbed. He has done some analysis on the cross section needed to account for this loss but to my knowledge has never been able to figure it out experimetnally. It remains an open problem it seems. The arxiv blog points to a paper that computes the probability these neutrons go into other worlds. Sigh....How is this Science ? Ok let's imagine they go to to other worlds,.how do you prove that experimentally ? is this reproducible ? after they have disappeared you wait for neutrons to come back ? But if they leak out, there should be some leaking in ? I am shaking my head as I am writing this.

What happened to shoddy journalism ? you don't have to look too far this week.

Finally, The astronauts on the ISS caught a Dragon

Credit photo: ESA/NASA. Opening the SpaceX Dragon's hatch.

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.

A Comment on Learning Analysis Operators

In the blog entry Inpainting Algorithm on GitHub (TV-L2 denoising and inpainting),  Martin Kleinsteuber commented:

Hi everyone, "The first approach may yield better results in the inpainting stage but requires a learning phase." This sentence suggests that an operator has to be learned for every individual inpainting task. However, the operator is learned offline and universal, a replacement for the TV, so to speak. It would be interesting to see how a combination of both approaches would perform

I wholeheartedly agree with Martin, if I gave the impression it was an unsurmountable issue then clearly it is not (if you have the time and inclination to perform this calibration). I also agree with him that given the learned analysis operator, one can use verbatim the methods used by Emmanuel to get similar results and it would be great to eventually compare these two approaches. But, to me, one of the most important aspect of Analysis Operator Learning and Its Application to Image Reconstruction by Simon Hawe, Martin Kleinsteuber, Klaus Diepold is.the following: interesting line of thoughts triggered by this:

"...We want to point out that this choice of parameters leads to a suitable general analysis operator, i.e. an operator with sparsifying property for the class of all natural images. It is thinkable that for more specific classes of images, for example medical imagery, other parameters may lead to a more suitable operator. .."

And indeed where would the learning of the analysis operator be of further interest ? How is the analysis operator different from say the TV if it is learned from samples taken 

• from the same camera with the same lens ? 
• The same cameras with different lenses ? or different setting for those lenses ?
• with widely differing specific natural images ?

Most synthetic experiments perform a calibration of the analysis operator with stock (2d) images, how is the analysis operator different

• with a 3d physical natural scene ? 
• with scenes taken different kind of sensors like SEM or a random lens imager ? 

In the end , how do we compare those different analysis operators ? What sort of information does it bring to the hardware maker ? to the sensor designer ? to the calibration process ?

  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.

Inpainting Algorithm on GitHub (TV-L2 denoising and inpainting)

In light of the recent entry showing the results of an inpainting algorithm within an Analysis Operator Learning approach, Emmanuel d'Angelo let me know that he made available his  TV-L2 denoising and inpainting code on Github. The photo above represents another 90% missing pixel reconstruction of Lena. The two approaches are very different in that the analysis operator approach is first learned in the first paper whereas in the case of Emmanuel's code, the analysis operator is given ( Finite Difference/TV). The first approach may yield better results in the inpainting stage but requires a learning phase. 

Emmanuel is still writing up his thesis so he is pretty busy for the moment, hence only the inpainting component of the more general algorithm is available. The general algorithm will include a fast version that can deal with the speed of video streams. According to him 

" The TV-L2 denoising is exactly what is described in the Chambolle-Pock [1], Alg. 1 of the primal-dual paper (no acceleration). The inpainting procedure is not described as is in the paper, but can be considered as a straightforward deduction from this same paper"

On his blog he describes the algorithm in more detail, it is in French however, so let me translate the remarks:

• The functional used here is nothing remarkable: it is the famous ROF, namely argmin 1/2 ∥ Ax-y∥^2_2 + λ ∥ x ∥ TV, where A is a random mask and TV is Total Variation.
• The implementation is slightly modified to simulate an infinite parameter λ where the mask is nonzero, and 0 otherwise.
• The algorithm used is called primal-dual and is described this paper [1].
• For the Open Lab dys et EPFL, I wrote a demo that used the video stream from a webcam on the Mac, which made quite an impression  (and not just among the general public). It is used by my boss regularly when he wants to impress visitors. The algorithm was FISTA this time (Ref. 2), which converges fast..
• The demo was initially written in the days of Mac OS X 1.5 Leopard withOpenCV version 1.0. Changes to QuickTime and OpenCV made that demo almost obsolete, so I invite you instead to go to the version of the code on Github.

He added in a follow-up e-mail on the state of the current code on Github

The code is C++ only, and targeted to work with OpenCV 2.4 and later. My optical flow code will be both OpenCV/C++ and GPGPU/OpenCL (it will be a bug free version of the one I presented at ICIP). I also want to add multithreading with Grand Central Dispatch (aka libdispatch), which is an Apple equivalent of Intel TBB. GCD is open sourced and available for Mac OS, iOS, and FreeBSD.

If I have the time to implement a "good" wavelet transform, I will submit it top the main OpenCV module.

Let us stay tuned for the optical flow algorithm on the Github repository that will run at 30 fps. In the meantime, Emmanuel's publications are listed here.

[1] A first-order primal-dual algorithm for convex problems with applications to imaging, Antonin Chambolle et Thomas Pock Journal of Mathematical Imaging and Vision, 2011, Volume 40, Number 1, Pages 120-145
[2] A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. Amir Beck and Marc Teboulle, SIAM J. Imaging Sci. 2, 183 (2009), DOI:10.1137/080716542



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.

To Catch a Dragon

Awesome. Congrats to the ISS crew and SpaceX!

More on NASA TV.


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.