Note on noisy group testing: Asymptotic bounds and belief propagation reconstruction
Note on noisy group testing: Asymptotic bounds and belief propagation reconstruction
复制标题
关于噪声组测试的注意事项：渐近边界和置信传播重建
DOI：
10.1109/allerton.2010.5707018
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
O. Johnson
中科院分区：
文献类型：
--
作者：
D. Sejdinovic;O. Johnson
最近Atia和Saligrama提出了一种基于信息论的分组测试问题的观点，以确定最优测试次数。他们的结果在无噪声的情况下成立，只有假阳性发生，只有假阴性发生。我们将他们的结果扩展到一个包含假阳性和假阴性的模型，开发了所需测试数量的简单信息理论界限。基于这些界限，我们得到了改进的收敛阶的情况下，假阴性。由于这些结果是基于（计算上不可行的）联合典型性解码，我们提出了一个信念传播算法检测有缺陷的项目，并比较其实际性能的理论界。
An information theoretic perspective on group testing problems has recently been proposed by Atia and Saligrama, in order to characterise the optimal number of tests. Their results hold in the noiseless case, where only false positives occur, and where only false negatives occur. We extend their results to a model containing both false positives and false negatives, developing simple information theoretic bounds on the number of tests required. Based on these bounds, we obtain an improved order of convergence in the case of false negatives only. Since these results are based on (computationally infeasible) joint typicality decoding, we propose a belief propagation algorithm for the detection of defective items and compare its actual performance to the theoretical bounds.