SAFFRON: A Fast, Efficient, and Robust Framework for Group Testing Based on Sparse-Graph Codes
SAFFRON: A Fast, Efficient, and Robust Framework for Group Testing Based on Sparse-Graph Codes
复制标题
DOI：
10.1109/tsp.2019.2929938
复制
发表时间：
2019-09-01
影响因子：
5.4
通讯作者：
Ramchandran, Kannan
中科院分区：
文献类型：
--
作者：
Lee, Kangwook;Chandrasekher, Kabir;Ramchandran, Kannan
小组测试是通过汇总项目组中识别n项中k个缺陷项目的问题。在本文中，我们通过利用现代稀疏图形编码理论的设计和分析工具来设计小组测试，以通过订单 - 最佳样本复杂性进行近似恢复。我们的算法，藏红花，至少恢复（1 -Epsilon）K有缺陷的物品W.P. 1 -k/n（r）具有m = 2（1 + r）c（epsilon）k log（2）n测试，其中epsilon是一个任意的小常数，c（epsilon）是一个准确特征的常数，r是任何积极的整数。解码复杂性是theta（k log n）。我们还提出了藏红花的变体，这些变体对噪声和未知的偏移量很强。例如，对于n相似或等于4.3 x 10（9）和k = 128结果。此外，用2 GHz Intel Core i7和8 GB内存的笔记本电脑上的解码时间不到4秒。
Group testing is the problem of identifying K defective items among n items by pooling groups of items. In this paper, we design group testing algorithms for approximate recovery with order-optimal sample complexity by leveraging design and analysis tools from modern sparse-graph coding theory. Our algorithm, SAFFRON, recovers at least (1 - epsilon)K defective items w.p. 1 - K/n(r) with m = 2(1 + r)C(epsilon)K log(2) n tests, where epsilon is an arbitrarily small constant, C(epsilon) is a precisely characterizable constant, and r is any positive integer. The decoding complexity is Theta(K log n). We also propose variations of SAFFRON, which are robust to noise and unknown offsets. For example, for n similar or equal to 4.3 x 10(9) and K = 128, our algorithm is observed to recover all defective items with m similar or equal to 8.3 x 10(5) tests, even in the presence of noisy test results. Moreover, the decoding time takes less than 4 seconds on a laptop with a 2 GHz Intel Core i7 and 8 GB memory.