2021/02/20 by Cheng, Xiwei, Jaggi, Sidharth, Zhou, Qiaoqiao
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2102.10256
In the problem of classical group testing one aims to identify a small subset (of size d) 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, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting, which subsumes as special cases a variety of noiseless and noisy group-testing models in the literature, the test outcome is positive with probability f(x), where x is the number of defectives tested in a pool, and f(⋅) is an arbitrary monotonically increasing (stochastic) test function. Our main contributions are as follows. 1. We present a non-adaptive scheme that with probability 1-ε identifies all defective items. Our scheme requires at most \cal O( H(f) dlog((n)/(ε))) tests, where H(f) is a suitably defined "sensitivity parameter" of f(⋅), and is never larger than \cal O(d1+o(1)), but may be substantially smaller for many f(⋅). 2. We argue that any non-adaptive group testing scheme needs at least Ω((1-ε)h(f) dlog(\frac n d)) tests to ensure reliable recovery. Here h(f) ≥ 1 is a suitably defined "concentration parameter" of f(⋅). 3. We prove that (H(f))/(h(f))∈Θ(1) for a variety of sparse-recovery group-testing models in the literature, and \frac H(f) h(f) ∈ \cal O(d1+o(1)) for any other test function.