Wednesday, December 17, 2008

CS: Group Testing and Sparse Signal Recovery, A linear solution to the 12-balls problem


The first time I became aware of Group Testing was when I was confronted to the problem described here by Robert H. Thouless in a paper entitled "The 12-Balls Problem as an Illustration of the Application of Information Theory" [1]:
You have 12 balls of the same size. 11 of these balls are the same weight, one is different; you do not know whether this ball is heavier or lighter than the others. You have also a balance on which any group of the balls can be weighed against any other group. How can you discover by means of three weighings which is the different ball and whether it is heavier or lighter than the other balls ?
I was slow and young (I am now slow and older:-)) and it took me a whole day to figure it out. Ever since I have been looking into compressed sensing, I have been looking for an introductory paper connecting group testing and compressed sensing. That paper has come out and is entitled: Group Testing and Sparse Signal Recovery by Anna GilbertMark Iwen and  Martin Strauss. The abstract reads:
Traditionally, group testing is a design problem. The goal is to design an optimally efficient set of tests of items such that the test results contain enough information to determine a small subset of items of interest. It has its roots in the statistics community and was originally designed for the Selective Service during World War II to remove men with syphilis from the draft [5]. It appears in many forms, including coin-weighing problems, experimental designs, and public health. We are interested in both the design of tests and the design of an efficient algorithm that works with the tests to determine the group of interest because many of the same techniques that are useful for designing tests are also used to solve algorithmic problems in compressive sensing, as well as to analyze and recover statistical quantities from streaming data. This article is an expository article, with the purpose of examining the relationship between group testing and compressive sensing, along with their applications and connections to sparse function learning.
Until today, I thought that the solution to the 12-ball problem was an adaptative one as my solution had the second weighing dependent on the results of the first weighing. It turns out that there is also a non-adaptive solution to it, as described here (my solution is the tree-like solution below the non-adaptive solution. Ain't the interwebs great ?) In other words, a CS-like linear measurement technique seems to be doing as well as a nonlinear one!


Reference:
[1] The 12-Balls Problem as an Illustration of the Application of Information Theory, Robert H. Thouless, The Mathematical Gazette, Vol. 54, No. 389 (Oct., 1970), pp. 246-249

Credit: NASA/JPL/Space Science Institute, Enceladus

4 comments:

Bilbo said...

This took me the better part of a day to figure out as well. Was about to give up when I stumbled on the trick. Better late than never.

Thanks for the link to the article, since I was wondering the same thing: How does a puzzle like this relate to Compressed Sensing? Given that my BSEE was a long time ago I doubt that I will be able to understand it, but will do my best. (A shoutout to Steve Hsu's Information Processing blog for stimulating my interest in this topic.)

A bientôt.

Igor said...

Hi Kevin,

Maybe this explanation will help ( https://www.quora.com/What-is-compressed-sensing-compressive-sampling-in-laymans-terms/answer/Igor-Carron ) . The number of defective items (1 ball) is small (sparse) compared to the total number of balls (12).

Hope this helps,

Igor.

Bilbo said...

Thanks Igor,

I actually did take a look at that page. Your page here (https://nuit-blanche.blogspot.com/p/teaching-compressed-sensing.html) is an excellent resource for approaching this topic, providing further reading for people of all levels of mathematical sophistication. Will poke around on that page to see if there is something that I can sink my teeth into. Although I remember a bit of linear algebra, probability, and signal processing from my electrical engineering college days, that was a long time ago (Rice '78).

Best,
Kevin

Igor said...

Kevin,

The videos of either Mark Davenport or Emmanuel Candes do a pretty good job I think.

Cheers,

Igor.

Printfriendly