Multilevel group testing via sparse-graph codes

摘要: In this paper, we consider the problem of multi-level group testing, where goal is to recover a set K defective items in n by pooling groups and observing result each test. The main difference multilevel testing with classical non-adaptive that test an integer [L] = {0,1, • •, L}: if there are i < L pool, i, more than L. We develop algorithm using sparse-graph codes has low sample computational complexity. More precisely, high probability, our provably recovers (1 — ∊) fraction C(∊, L)K log(n) tests, L) constant only depends on ∊ number levels L, it can be precisely characterized for arbitrary e. Furthermore, complexity O(K log(n)). As example, able 10−3) 13.8K measurements 2. also provide numerical results show tight agreement theoretical results.