Multilevel group testing via sparse-graph codes
Multilevel group testing via sparse-graph codes
复制标题
通过稀疏图代码进行多级组测试
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Ramtin Pedarsani
中科院分区：
文献类型：
--
作者：
Pedro Abdalla;Amirhossein Reisizadeh;Ramtin Pedarsani
在本文中，我们考虑了多级分组测试问题，其目标是通过集合项目组并观察每个测试的结果来恢复n个项目集合中的K个缺陷项目。多级组织测试的主要区别与经典的非自适应的集团测试问题是每个测试的结果是一个整数的集合[L] ={0 1•••L}:如果有我< L池中有缺陷的项目,测试的结果是我,如果有超过L条目池中,测试的结果是L .我们开发一个多级群检测算法使用稀疏图代码示例和计算复杂度低。更准确地说，我们的算法可以高概率地通过C（， L）K log(n)检验证明恢复（1 -）部分缺陷项，其中C（， L）是一个常数，它只依赖于和层数L，并且可以精确地表征任意L和e。我们的算法的计算复杂度为O（K log(n)）。作为一个例子，我们的算法能够恢复（1 - 10−3）次品的部分，只有13.8K log(n)测量的L = 2。我们还提供了与理论结果非常吻合的数值结果。
In this paper, we consider the problem of multi-level group testing, where the goal is to recover a set of K defective items in a set of n items by pooling groups of items and observing the result of each test. The main difference of multilevel group testing with the classical non-adaptive group testing problem is that the result of each test is an integer in the set [L] = {0,1, • • •, L}: if there are i < L defective items in the pool, the result of the test is i, and if there are more than L items in the pool, the result of the test is L. We develop a multilevel group testing algorithm using sparse-graph codes that has low sample and computational complexity. More precisely, with high probability, our algorithm provably recovers (1 — ∊) fraction of the defective items using C(∊, L)K log(n) tests, where C(∊, L) is a constant that only depends on ∊ and the number of levels L, and it can be precisely characterized for arbitrary L and e. Furthermore, the computational complexity of our algorithm is O(K log(n)). As an example, our algorithm is able to recover (1 — 10−3) fraction of the defective items with only 13.8K log(n) measurements for L = 2. We also provide numerical results that show tight agreement with our theoretical results.
影响因子：
5.4
作者：
Lee, Kangwook;Chandrasekher, Kabir;Ramchandran, Kannan
通讯作者：
Ramchandran, Kannan