Non-adaptive Quantitative Group Testing Using Irregular Sparse Graph Codes
Non-adaptive Quantitative Group Testing Using Irregular Sparse Graph Codes
复制标题
DOI：
10.1109/allerton.2019.8919896
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Esmaeil Karimi;Fatemeh Kazemi;A. Heidarzadeh;K. Narayanan;A. Sprintson
中科院分区：
文献类型：
--
作者：
Esmaeil Karimi;Fatemeh Kazemi;A. Heidarzadeh;K. Narayanan;A. Sprintson
本文研究了N个大群体中存在缺陷项目的定量群检验问题。我们考虑这样一个场景，其中每个项目都以$K/N$的概率存在缺陷，独立于其他项目。在QGT问题中，目标是用尽可能少的测试次数，通过测试项目组来识别所有或足够大的缺陷项目。特别是，每次测试的结果是一个非负整数，表示测试组中有缺陷的项目的数量。在这项工作中，我们提出了一种非自适应QGT方案，用于潜在的缺陷项目随机化模型，该方案利用不规则二部图上的稀疏图码，在图的左节点上优化度轮廓，以及二进制t-纠错BCH码。我们证明了在次线性区域，即当比率$K/N$随着N无界增长而消失时，所提出的方案具有$m=c(t, d) K\left(t \log \left(\frac{\ell N}{c(t, d) K}+1\right)+1\right)$检验可以识别出概率接近1的所有缺陷项，其中d和$\ell$分别是最大左度和平均左度，并且$c(t,\ d)$仅依赖于t和d（而不依赖于K和N）。对于任意$t \leq 4$，所提出方案的测试和恢复算法的计算复杂度分别为$O\left(N\log\frac{N}{K}\right)$和$O\left(K\log\frac{N}{K}\right)$。在以高概率识别所有缺陷项目所需的测试次数方面，所提出的方案优于最近提出的两种用于亚线性区域的非自适应QGT方案，包括我们基于正则二部图的方案和Gebhard等人的方案。
This paper considers the problem of Quantitative Group Testing (QGT) where there are some defective items among a large population of N items. We consider the scenario in which each item is defective with probability $K/N$, independently from the other items. In the QGT problem, the goal is to identify all or a sufficiently large fraction of the defective items by testing groups of items, with the minimum possible number of tests. In particular, the outcome of each test is a non-negative integer which indicates the number of defective items in the tested group. In this work, we propose a non-adaptive QGT scheme for the underlying randomized model for defective items, which utilizes sparse graph codes over irregular bipartite graphs with optimized degree profiles on the left nodes of the graph as well as binary t-error-correcting BCH codes. We show that in the sub-linear regime, i.e., when the ratio $K/N$ vanishes as N grows unbounded, the proposed scheme with $m=c(t, d) K\left(t \log \left(\frac{\ell N}{c(t, d) K}+1\right)+1\right)$ tests can identify all the defective items with probability approaching 1, where d and $\ell$ are the maximum and average left degree, respectively, and $c(t,\ d)$ depends only on t and d (and does not depend on K and N). For any $t \leq 4$, the testing and recovery algorithms of the proposed scheme have the computational complexity of $O\left(N\log\frac{N}{K}\right)$ and $O\left(K\log\frac{N}{K}\right)$, respectively. The proposed scheme outperforms two recently proposed non-adaptive QGT schemes for the sub-linear regime, including our scheme based on regular bipartite graphs and the scheme of Gebhard et al., in terms of the number of tests required to identify all defective items with high probability.