Ben Champion
2
2
Ben Champion has not written any posts yet.
Ben Champion has not written any posts yet.
[EDIT:
I see the monograph in gwern's post below makes the observation that group testing is a Boolean version of compressed sensing and references Gilbert et al. 2008 which I'm just reading - found a freely available version on Google Scholar. And more importantly, the monograph contains algorithms with similar bounds to CS.
READ GWERN'S POST BELOW FIRST
]
Some ideas...
This is can be seen as a nonlinear version of a compressed sensing problem (see here for a good "25 minute" intro to compressed sensing, or the Wikipedia article).
The nonlinearity comes from the fact that the pooled test seems to behave like an approximate OR-gate: if any sample is positive the pooled sample will be... (read more)
Would you be able to post this under answers? It seems to describe algorithms and their performance bounds in quite some detail and definitely deserves to be the top answer.