Friday, December 30, 2011

Compressed Sensing: An Overview #2 (Group Testing)

Here we will consider a situation where N number of soldiers have to be tested for a particular disease using a sensitive but an expensive blood test. If blood samples from different soldiers were grouped together, the test would be sensitive enough to declare a positive if any of the soldier was infected. If there are K soldiers and where K>> then M = N measurement is to be done. If K=1 (priori) then M=log2 (N) is possible. Here global measurement is taken which is then followed by a reasoning algorithm. This was proposed by two economist during the Second World war for the screening of soldiers infected with syphilis. The proposal was to put the blood samples together as few people were likely to be infected by Syphilis, this saves tests on average. Though test was not put into practice the discussions on the subject is still being continued!! A similar principle is applied in compressive sensing.

The signal is projected onto a random signal of equal length. Each projection refers to a measurement. Each random signal used for measurement in the view of Fourier Series is a linear combination of several frequency component thus is equivalent to the extraction of information regarding several frequencies of the original signal. With adequate measurement the signal can be reconstructed using the L-1 norm optimization algorithm. The accuracy obtained by this is remarkable but is limited to a very strict condition. The signal should be sparse in terms of 'Information content'. Mathematically the number coefficients representing the signal must be small. Luckily most of the signals in nature satisfy this requirement and that is the reason why signals are compressible. 

No comments:

Post a Comment