Group Testing: An Information Theory Perspective
Group Testing: An Information Theory Perspective
复制标题
DOI：
10.1561/0100000099
复制
发表时间：
2019-01-01
影响因子：
2.4
通讯作者：
Scarlett, Jonathan
中科院分区：
文献类型：
--
作者：
Aldridge, Matthew;Johnson, Oliver;Scarlett, Jonathan
组测试问题涉及通过对项目池进行测试来发现大量人群中的少量缺陷项目。如果池包含至少一个缺陷，则测试为阳性，如果不包含缺陷，则为阴性。这是一个稀疏推理问题，具有组合的味道，在医学测试，生物学，电信，信息技术，数据science，和更多的应用程序，在这本专著中，我们调查最近的发展，在组测试问题从信息理论的角度来看。我们涵盖了几个相关的发展：有效的算法与实际的存储和计算要求，最佳解码方法的可扩展性界限，算法独立的匡威界。我们不仅根据标度律，而且根据常数因子来评估理论保证，从而产生了组测试速率的概念，表明每次测试学到的信息量。考虑到无噪声和嘈杂的设置，我们确定了几个制度，现有的算法是可证明的最优或接近最优，以及制度，那里仍然有更大的改进潜力。此外，我们调查的结果有关的一些变化的标准组测试问题，包括部分恢复标准，自适应算法与有限数量的阶段，约束测试设计，和sublineartime算法。
The group testing problem concerns discovering a small number of defective items within a large population by performing tests on pools of items. A test is positive if the pool contains at least one defective, and negative if it contains no defectives. This is a sparse inference problem with a combinatorial flavour, with applications in medical testing, biology, telecommunications, information technology, data science, and more.In this monograph, we survey recent developments in the group testing problem from an information-theoretic perspective. We cover several related developments: efficient algorithms with practical storage and computation requirements, achievability bounds for optimal decoding methods, and algorithm-independent converse bounds. We assess the theoretical guarantees not only in terms of scaling laws, but also in terms of the constant factors, leading to the notion of the rate of group testing, indicating the amount of information learned per test. Considering both noiseless and noisy settings, we identify several regimes where existing algorithms are provably optimal or near-optimal, as well as regimes where there remains greater potential for improvement.In addition, we survey results concerning a number of variations on the standard group testing problem, including partial recovery criteria, adaptive algorithms with a limited number of stages, constrained test designs, and sublineartime algorithms.