An Efficient Algorithm for Capacity-Approaching Noisy Adaptive Group Testing
An Efficient Algorithm for Capacity-Approaching Noisy Adaptive Group Testing
复制标题
容量逼近噪声自适应组测试的有效算法
DOI：
10.1109/isit.2019.8849310
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
J. Scarlett
中科院分区：
文献类型：
--
作者：
J. Scarlett
在本文中，我们考虑具有自适应测试设计和噪声结果的组测试问题。我们提出了一种计算高效的四阶段过程，其组件包括随机分箱、识别包含缺陷项目的箱、通过通道代码进行 1 稀疏恢复，以及纠正早期阶段中的任何错误的“清理”步骤。我们证明，渐进所需的测试数量非常接近最著名的信息论可实现性界限（基于计算上难以处理的解码），并接近低稀疏状态下基于容量的逆界限。
In this paper, we consider the group testing problem with adaptive test designs and noisy outcomes. We propose a computationally efficient four-stage procedure with components including random binning, identification of bins containing defective items, 1-sparse recovery via channel codes, and a "clean-up" step to correct any errors from the earlier stages. We prove that the asymptotic required number of tests comes very close to the best known information-theoretic achievability bound (which is based on computationally intractable decoding), and approaches a capacity-based converse bound in the low-sparsity regime.