Non-adaptive Group Testing: Explicit Bounds and Novel Algorithms
Non-adaptive Group Testing: Explicit Bounds and Novel Algorithms
复制标题
DOI：
10.1109/tit.2014.2310477
复制
发表时间：
2014-05-01
影响因子：
2.5
通讯作者：
Agnihotri, Samar
中科院分区：
文献类型：
--
作者：
Chan, Chun Lam;Jaggi, Sidharth;Agnihotri, Samar
我们考虑一些计算效率和可证明正确的算法与接近最佳的样本复杂度的问题，嘈杂的非自适应组测试。分组测试涉及将项目的任意子集分组到池中。然后对每个池进行测试，以识别缺陷项目，这些项目通常被认为是稀疏的。我们考虑非自适应随机汇集测量，其中池是随机选择的，独立于测试结果。我们还考虑了一个模型，其中噪声测量允许一些假阴性和一些假阳性测试结果（并且还允许不对称噪声和激活噪声）。我们考虑三类算法的组测试问题（我们称之为专门的优惠券收集器算法，列匹配算法，和LP解码算法的最后两类算法（其中一些版本已被认为是以前在文献中）的启发压缩感知文献中的相应算法。这些算法中的第二和第三种有几种口味，分别处理无噪声和有噪声的测量场景。我们的贡献是新颖的分析，以获得明确的样本复杂性的界限，明确计算的所有常数，这些算法作为所需的错误概率，噪声参数，项目的数量，和大小的缺陷集（或上限）的函数。我们还比较了信息理论的样本复杂性的下界的基础上Fano的不等式的界限，并表明，上界和下界是相等的一个明确的可计算的通用常数因子（独立的问题参数）。
We consider some computationally efficient and provably correct algorithms with near-optimal sample complexity for the problem of noisy nonadaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be sparse. We consider nonadaptive randomly pooling measurements, where pools are selected randomly and independently of the test outcomes. We also consider a model where noisy measurements allow for both some false negative and some false positive test outcomes (and also allow for asymmetric noise, and activation noise). We consider three classes of algorithms for the group testing problem (we call them specifically the coupon collector algorithm, the column matching algorithms, and the LP decoding algorithms-the last two classes of algorithms (versions of some of which had been considered before in the literature) were inspired by corresponding algorithms in the compressive sensing literature. The second and third of these algorithms have several flavors, dealing separately with the noiseless and noisy measurement scenarios. Our contribution is novel analysis to derive explicit sample-complexity bounds-with all constants expressly computed-for these algorithms as a function of the desired error probability, the noise parameters, the number of items, and the size of the defective set (or an upper bound on it). We also compare the bounds to information-theoretic lower bounds for sample complexity based on Fano's inequality and show that the upper and lower bounds are equal up to an explicitly computable universal constant factor (independent of problem parameters).