Nuit Blanche: Group Testing and SAFFRON

Monday, September 07, 2015

Group Testing and SAFFRON

A few days ago, we featured this preprint entitled " SAFFRON: A Fast, Efficient, and Robust Framework for Group Testing based on Sparse-Graph Codes", I wondered then why I did not see a reference to some other similar work in that area featured here back two years ago. ". One of the authors, Kannan Ramchandran kindly responded to my interrogation: outstanding ! Here is what Kannan sent me:

Dear Igor,

We recently read your blog article introducing our new arxived paper on group testing.
http://nuit-blanche.blogspot.fr/2015/08/saffron-fast-efficient-and-robust.html

We would like to first thank you for sharing our paper on your well-read blog! In your post, you referred to a paper from two years ago (by Mezart et al.), which we didn’t cite in our new paper. We didn't know about this prior work, and thank you for pointing this out. We read it, and found that our papers are very different. While apparently related at the surface, perhaps due to the confusing common use of spatial-coupled codes to tackle some group testing problem, we would like to clarify that the two works are indeed very different. FYI, we would like to describe some clear distinctions between our works.

First, and most important, the two papers are working on different problems: the paper by Mezart et al. is on linear group testing, while our work is on boolean group testing. In linear group testing, a test result of a pool reveals the number of defective items in the pool, while in boolean group testing, a test result is simply a Boolean OR operator, i.e. it is a boolean 1 if there is one or more defective items, 0 otherwise. It is clear that boolean group testing is a strictly harder problem than the linear group testing problem since in our case, the test gives only one bit of information that is also a non-linear function of the components of the sparse input vector.

Further, our use of spatially coupled LDPC codes is completely different form the way they use spatially coupled LDPC codes. The use of LDPC codes for the linear problem is not that surprising as the problem is linear. However, the non-linear nature of our Boolean problem makes the use of spatial LDPC codes somewhat challenging. Specifically, we design our pooling matrix using a 2-layer approach. The upper layer is designed based on simple left-regular random bipartite graphs. The lower layer can be designed based on any error correcting codes. We mentioned spatially coupled LDPC in our work because it is a good candidate of error-correcting codes that can be used for this lower layer. However, our scheme is very general, and it is not limited to spatially coupled LDPC. On the other hand, Mezart’s paper uses a pooling matrix that is entirely based on a spatially coupled code. Further, we were able to achieve the optimal computational complexity with this layered pooling design, while Mezart’s paper uses a standard belief propagation algorithm, which has a suboptimal computational complexity.

Though different, now that we are aware of this work, we will reference Mezart’s paper in our revised version as they proposed the use of spatially coupled codes to tackle a linear variant of the group testing problem that we address. We will also add a reference to the Cheraghchi paper on group testing with thresholds that you point out in your blog in our revised version.

Again, thank you for sharing our paper on your blog and pointing out a useful reference that we were unaware of.

Regards,
Kannan

Thank you Kannan !

As a reminder, all the preprints/papers mentioned on this blog related to Group Testing are listed under the GroupTesting tag. There are 48 blog entries using that tag. A while ago, I explained how compressive sensing works on Quora using the concepts behind group testing: What is compressed sensing (compressive sampling) in layman's terms?

Potentially relevant