Sunday, March 17, 2013

Sunday Morning Insight: How to spot a compressive sensing system: the case of the Randomized MALDI TOF MS/MS system

Every once in while, one wonders if and how a specific sensing system could be transformed into a compressive one. Sometimes, there is no need for hardware change, sometimes everything has to change. Is there a middle ground ? I have found that most often one can target sensing systems for a compressive architecture when there is already some work or publication using a multiplexing scheme such as the Hadamard Transform. Let us take the example of MALDI TOF MS/MS, a technique of mass spectrometry using several stages to detect different proteins and is heavily used in proteomics. As you all know the hot subject these days is genomics but it is only part of the story. Once the genome is known we have seldom data on the types of proteins that are produced by particular genes. In effect, without saying it aloud, the genomics revolution cares deeply about the end products such as proteins to make headways in medicine etc....

The first hint that something might match a compressive sensing system is the several stages of transformation from the initial signal to what the final detector sees. One can foresee that if the several stages of transformation are actionable, then some programmable multiplexing can occur.  That directly opens the door to a randomized multiplexing provided that the signal is sparse. Which brings us to the next question: Is the signal sparse ? Here is a typical output:

It looks sparse enough to me. Now, when you read about the system, you notice that the sensing system seems to be sampling in a raster mode (one item at a time). Is there a way to do it some other way ? is there a way to make the matrix shown above denser and shorter ? in other words, is there a way to make this sensing system compressive ?

One should then look for work or publications that have used some simple convolution schemes. One of the obvious one is the Hadamard Transform. 

Why focus on Hadamard ? In the Hadamard case, the measurement matrix is a square matrix made of zeros and ones and the recovery scheme is a linear one i.e. multiply the results with the transpose of that same Hadamard matrix (since H* H = I). In compressive sensing, the measurement matrices are short and fat (yielding fewer measurements) and can be instances of Bernouilli or Random Hadamard ensembles. The recovery, however, is non-linear and requires solvers such as the ones listed in section 4 of the Big Picture in Compressive Sensing.

It so happens that a publication using the Hadamard transform already exists [1] so we don't have to go too far and that publication has all the elements that makes you think a compressive approach will work. Here are the clues: First the authors have to educate their peers about group testing of Bananas:

This is good sign because as we all know group testing is a subset of compressive sensing. Then comes the most interesting observation of the paper [Emphasis is mine]
The SNR gain is also a function of spectrum sparsity, and the best results are obtained for spectra with very few, strong mass peaks
Bingo !

As a first step one could directly use data (no need to go into the lab for new experimental data) and pick only a subset of measurements obtained from the Hadamard modulation. Use that randomized transformation and any of the solvers listed here, "et voila" have a publication and much to play with to see if there are particular measurement matrices that are more effective than others. In particular, one might want to investigate the recent seeded measurement matrices of Krzakala et al as the number of non zero unknowns (i.e. peaks in the spectrum) scale directly as the number of measurements....

P.S.: I'll just add this Randomized MALDI TOF MS/MS or Mass spectrometry technique to the list of technologies that do not exist

P.S 2: This blog entry was triggered by a discussion with Sujithra Raviselvam on the Google+ group and stemmed from a 2005 blog entry which featured the thesis of Earle Stone [2]

1. Hadamard Transform Time-of-Flight Mass Spectrometry: More Signal, More of the Time Richard N. Zare, Facundo M. Fernµndez, and Joel R. Kimmel


No comments: