2014/10/30 by Ganesan, Abhinav, Ebrahimi, Javad, Jaggi, Sidharth +1
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1410.8440
Group testing with inhibitors (GTI) introduced by Farach at al. is studied in this paper. There are three types of items, d defectives, r inhibitors and n-d-r normal items in a population of n items. The presence of any inhibitor in a test can prevent the expression of a defective. For this model, we propose a probabilistic non-adaptive pooling design with a low complexity decoding algorithm. We show that the sample complexity of the number of tests required for guaranteed recovery with vanishing error probability using the proposed algorithm scales as T=O(d log n) and T=O((r2)/(d)log n) in the regimes r=O(d) and d=o(r) respectively. In the former regime, the number of tests meets the lower bound order while in the latter regime, the number of tests is shown to exceed the lower bound order by a log (r)/(d) multiplicative factor. When only upper bounds on the number of defectives D and the number of inhibitors R are given instead of their exact values, the sample complexity of the number of tests using the proposed algorithm scales as T=O(D log n) and T=O(R2 log n) in the regimes R2=O(D) and D=o(R2) respectively. In the former regime, the number of tests meets the lower bound order while in the latter regime, the number of tests exceeds the lower bound order by a log R multiplicative factor. The time complexity of the proposed decoding algorithms scale as O(nT).