Efficient Algorithms for Noisy Group Testing
Efficient Algorithms for Noisy Group Testing
复制标题
DOI：
10.1109/tit.2017.2659619
复制
发表时间：
2017-04-01
影响因子：
2.5
通讯作者：
Jaggi, Sidharth
中科院分区：
文献类型：
--
作者：
Cai, Sheng;Jahangoshahi, Mohammad;Jaggi, Sidharth
小组测试是指通过“小”数量的“合并”测试（即具有阳性的测试）从（大）n个项目中识别（较小的）D缺陷的问题（较小的）d缺陷子集的问题结果，如果至少在池中测试的项目中至少有一个有缺陷，则会产生负面结果）。为了易于表达，我们将重点放在d = o（n1-delta）的某些delta> 0时。测试可能是无嘈杂的或嘈杂的，并且测试过程可能是适应性的（定义测试的池可能可以取决于先前测试的结果）或非自适应（每个测试都独立于其他测试的结果）。丰富的文献表明，theta（d log（n））测试在理论上是必要的，对于小组测试问题是必要的，并且足以实现这一性能。但是，直到最近才开始研究具有n次线性计算复杂性的重建算法。在带有嘈杂结果的自适应测试的情况下，我们提出了第一个方案，该方案在测试的数量和解码复杂性（O（d log（n）））中同时均具有最佳序列（最多恒定因子）性能指标）。我们自适应算法的阶段总数为“小”（o（log（d）））。同样，在具有嘈杂结果的非自适应测试的情况下，我们提出了第一个方案，该方案在测试数量和解码复杂性（通过需要O（D log（D）log（D）log（d）log（D）的算法（D））中同时近乎最佳的方案（D） n）测试，并具有O（log n+log（2）d）的解码复杂性。仅需要两个阶段，对于所有三个设置，测试的数量和解码复杂度刻度都为O（d（log n+log（2）d））。 1/（pol y（d））。我们的定理语句。
Group-testing refers to the problem of identifying (with high probability) a (small) subset of D defectives from a (large) set of N items via a "small" number of "pooled" tests (i.e., tests that have a positive outcome if at least one of the items being tested in the pool is defective, else have a negative outcome). For ease of presentation in this paper, we focus on the regime when D = O(N1-delta) for some delta > 0. The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of the literature demonstrates that Theta (D log(N)) tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexities that are sub-linear in N have started being investigated. In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity (O (D log(N)) in both the performance metrics). The total number of stages of our adaptive algorithm is "small" (O(log(D))). Similarly, in the scenario with non-adaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires O(D log(D) log(N)) tests and has a decoding complexity of O(D(log N+log(2) D)). Finally, we present an adaptive algorithm that only requires two stages, and for which both the number of tests and the decoding complexity scale as O(D(log N+log(2) D)). For all three settings, the probability of error of our algorithms scales as O (1/(pol y(D)). For each of the statements mentioned earlier about the order of the number of measurements, decoding complexity, and probability of error, we provide explicitly computed "small" universal factors in our theorem statements.