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 Gilbert, Mark 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