Near-Optimal Noisy Group Testing via Separate Decoding of Items
Near-Optimal Noisy Group Testing via Separate Decoding of Items
复制标题
通过项目的单独解码进行近乎最优的噪声组测试
DOI：
10.1109/jstsp.2018.2844818
复制
发表时间：
2017
影响因子：
7.5
通讯作者：
V. Cevher
中科院分区：
文献类型：
--
作者：
J. Scarlett;V. Cevher
组测试问题包括根据大量测试从较大的一组项目中确定一小组有缺陷的项目，并且与医学测试、通信协议、模式匹配等应用相关。在本文中，我们重新审视了一种用于噪声组测试的有效算法，其中每个项目都单独解码（Malyutov 和 Mateev，1980），并通过通用噪声模型的信息理论框架开发新颖的性能保证。对于无噪声和对称噪声的特殊情况，我们发现误差消失概率所需的渐进测试次数在低稀疏性水平下信息论最优值的 $\log 2 \approx 0.7$ 范围内，并且在允许错误解码项的一小部分的情况下，这种保证扩展到所有次线性稀疏性水平。此外，我们提供了一个逆界，表明如果尝试使用单独的项目解码和独立的同分布随机测试稍微超出我们的低稀疏性可实现性阈值，则错误解码的平均项目数会接近普通解码器的平均数量。
The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and more. In this paper, we revisit an efficient algorithm for noisy group testing in which each item is decoded separately (Malyutov and Mateev, 1980), and develop novel performance guarantees via an information-theoretic framework for general noise models. For the special cases of no noise and symmetric noise, we find that the asymptotic number of tests required for vanishing error probability is within a factor $\log 2 \approx 0.7$ of the information-theoretic optimum at low-sparsity levels, and that with a small fraction of allowed incorrectly decoded items, this guarantee extends to all sublinear sparsity levels. In addition, we provide a converse bound showing that if one tries to move slightly beyond our low-sparsity achievability threshold using separate decoding of items and independent identically distributed randomized testing, the average number of items decoded incorrectly approaches that of a trivial decoder.