Date Added: Feb 2012
The authors present computationally efficient and provably correct algorithms with near-optimal sample-complexity for noisy non-adaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be sparsely distributed. They consider random non-adaptive pooling where pools are selected randomly and independently of the test outcomes. Their noisy scenario accounts for both false negatives and false positives for the test outcomes. Inspired by compressive sensing algorithms they introduce four novel computationally efficient decoding algorithms for group testing, CBP via Linear Programming (CBP-LP), NCBP-LP (Noisy CBPLP), and the two related algorithms NCBP-SLP+ and NCBPSLP- ("Simple" NCBP-LP).