Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
复制标题
嘈杂的非自适应组测试：（近）确定缺陷方法
DOI：
10.1109/tit.2020.2970184
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
O. Johnson
中科院分区：
文献类型：
--
作者：
J. Scarlett;O. Johnson
组测试问题包括根据许多可能有噪声的测试从较大的项目集中确定一小组有缺陷的项目，并且在诸如医学测试、通信协议、模式匹配等应用中相关。我们研究了该问题的噪声版本，其中每个标准无噪声组测试的结果都受到独立噪声的影响，对应于将无噪声结果通过二进制通道传递。我们引入了一类近似确定缺陷（NDD）算法，并研究了在伯努利随机检验设计下误差概率渐近消失所需检验次数的界。此外，我们还研究了与算法无关的反向结果，给出了伯努利测试设计下所需测试次数的下界。在反向z通道噪声下，可实现速率和反向结果在广泛的稀疏范围内匹配，而在z通道噪声下，两者在较窄的密集/低噪声范围内匹配。我们观察到，虽然这两个通道在作为通信通道时具有相同的Shannon容量，但在进行组测试时，它们的表现却截然不同。最后，我们将这些噪声模型的分析扩展到一般的二进制噪声模型（包括对称噪声），并在广泛的尺度下展示了对已知现有边界的改进。
The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly-noisy tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and more. We study the noisy version of this problem, where the outcome of each standard noiseless group test is subject to independent noise, corresponding to passing the noiseless result through a binary channel. We introduce a class of algorithms that we refer to as Near-Definite Defectives (NDD), and study bounds on the required number of tests for asymptotically vanishing error probability under Bernoulli random test designs. In addition, we study algorithm-independent converse results, giving lower bounds on the required number of tests under Bernoulli test designs. Under reverse Z-channel noise, the achievable rates and converse results match in a broad range of sparsity regimes, and under Z-channel noise, the two match in a narrower range of dense/low-noise regimes. We observe that although these two channels have the same Shannon capacity when viewed as a communication channel, they can behave quite differently when it comes to group testing. Finally, we extend our analysis of these noise models to a general binary noise model (including symmetric noise), and show improvements over known existing bounds in broad scaling regimes.
概率群检验中Kautz-Singleton构造的最优性
影响因子：
2.5
作者：
Inan, Huseyin A.;Kairouz, Peter;Wootters, Mary;Ozgur, Ayfer
通讯作者：
Ozgur, Ayfer