Nearly optimal sparse group testing
Nearly optimal sparse group testing
复制标题
接近最优的稀疏组测试
DOI：
10.1109/allerton.2016.7852259
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Samson Zhou
中科院分区：
文献类型：
--
作者：
V. Gandikota;Elena Grigorescu;S. Jaggi;Samson Zhou
成组测试是从一组n个项目中汇集任意子集的过程，以便用最少数量的析取测试来识别d个缺陷项目的“小”子集。在“经典”非自适应组测试中，已知当d = o（n<sup>1−δ</sup>）且δ > 0时，θ（d log（n））测试是信息理论上必要的，并且足以保证高概率的恢复。文献中满足此界的分组检验方案要求大多数项被检验Ω（log（n））次，并且大多数检验包含Ω（n/d）项。出于物理上的考虑，我们研究组测试模型，其中的测试程序被限制为“稀疏”。具体来说，我们（单独）考虑以下场景：（a）项目是可分的，因此最多可以参与γ检验;（B）检验的大小受到限制，每个检验的样本池不超过ρ个项目。对于这两种情况下，我们提供了信息理论的下限，以保证高概率恢复所需的测试数量。特别地，我们的一个主要结果表明，项目的γ-有限整除性迫使任何恢复错误概率最多为1/2的组测试算法至少执行Ω（γ（n/d）<sup>（1−2 <$）/（（1+2 <$）γ）</sup>）测试。类似地，对于ρ-尺寸的约束测试，我们给出了Ω（n log（n/d）/（ρ log（n/ρd）））的信息论下界。在这两种情况下，我们都提供了随机化的结构（在无误差和零误差重建保证下）和显式的计算有效的组测试算法的结构（在无误差重建保证下），这些算法需要一些测试，这些测试在n，d，γ和ρ的某些制度中是最佳的。我们还研究了不可靠性/噪声对测试结果的影响。
Group testing is the process of pooling arbitrary subsets from a set of n items so as to identify, with a minimal number of disjunctive tests, a “small” subset of d defective items. In “classical” non-adaptive group testing, it is known that when d = o(n<sup>1−δ</sup>) for any δ > 0, θ(d log(n)) tests are both information-theoretically necessary, and sufficient to guarantee recovery with high probability. Group testing schemes in the literature meeting this bound require most items to be tested Ω(log(n)) times, and most tests to incorporate Ω(n/d) items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be “sparse”. Specifically, we consider (separately) scenarios in which (a) items are finitely divisible and hence may participate in at most γ tests; and (b) tests are size-constrained to pool no more than ρ items per test. For both scenarios we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In particular, one of our main results shows that γ-finite divisibility of items forces any group testing algorithm with probability of recovery error at most ϵ to perform at least Ω(γ(n/d)<sup>(1−2ϵ)/((1+2ϵ)γ)</sup>) tests. Analogously, for ρ-sized constrained tests, we show an information-theoretic lower bound of Ω(n log(n/d)/(ρ log(n/ρd))). In both scenarios we provide both randomized constructions (under both ϵ-error and zero-error reconstruction guarantees) and explicit constructions of computationally efficient group-testing algorithms (under ϵ-error reconstruction guarantees) that require a number of tests that are optimal up to constant factors in some regimes of n, d, γ and ρ. We also investigate the effect of unreliability/noise in test outcomes.