Generalized Group Testing

In the problem of classical group testing one aims to identify a small subset (of size d ) of diseased individuals/defective items in a large population (of size n ). This process is based on a minimal number of suitably-designed group tests on subsets of items, where the test outcome is positive iff the given test contains at least one defective item. Motivated by physical considerations, such as scenarios with imperfect test apparatus, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting the test outcome is governed by an arbitrary monotonically increasing (stochastic) test function f , with the test outcome being positive with probability f(x) , where x is the number of defectives tested in that pool. This formulation subsumes as special cases a variety of noiseless and noisy group-testing models in the literature. Our main contributions are as follows. Firstly, for any monotone test function f(c) we present a non-adaptive scheme that with probability 1- identifies all defective items. Our scheme requires at most O} ((f)} d({n}) tests, where {(f) is a suitably defined 'sensitivity parameter' of f, and is never larger than Od1+o(1) , but indeed can be substantially smaller for a variety of f. Secondly, we argue that any non-adaptive group testing scheme needs at least ((1- (f)} d ({n} d}) tests to ensure high reliability recovery. Here f is a suitably defined 'concentration parameter' of f, and 1. Thirdly, we prove that our sample-complexity bounds for generalized group testing are information-theoretically near-optimal for a variety of sparse-recovery group-testing models in the literature. That is, for any 'noisy' test function F (i.e., 0 < f(0) < f(d) < 1), and for a variety of '(one-sided) noiseless' test functions f (i.e., either f(0)=0 , or f(d)=1 , or both) studied in the literature we show that (f) (f) (1). As a by-product we tightly characterize the heretofore open information-theoretic order-wise sample-complexity for the well-studied model of threshold group-testing. For general (near)-noiseless test functions f we show that (f) (d1+o(1)). We also demonstrate a 'natural' test-function f whose sample complexity scales 'extremally' as d2n , rather than (dn) as in the case of classical group-testing. Some of our techniques may be of independent interest - in particular our achievability requires a delicate saddle-point approximation, our impossibility proof relies on a novel bound relating the mutual information of pair of random variables with the mean and variance of a specific function, and as a by-product of our proof showing that our sample-complexity upper and lower bounds are close we derive novel structural results about monotone functions.