TY - GEN
T1 - Nearly optimal sparse group testing
AU - Gandikota, Venkata
AU - Grigorescu, Elena
AU - Jaggi, Sidharth
AU - Zhou, Samson
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2017/2/10
Y1 - 2017/2/10
N2 - Group testing is the process of pooling arbitrary subsets from a set of n items so as to identify, with a minimal number of disjunctive tests, a 'small' subset of d defective items. In 'classical' non-adaptive group testing, it is known that when d = o(n1-δ) for any δ > 0, θ(d log(n)) tests are both information-theoretically necessary, and sufficient to guarantee recovery with high probability. Group testing schemes in the literature meeting this bound require most items to be tested Ω(log(n)) times, and most tests to incorporate Ω(n/d) items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be 'sparse'. Specifically, we consider (separately) scenarios in which (a) items are finitely divisible and hence may participate in at most γ tests; and (b) tests are size-constrained to pool no more than ρ items per test. For both scenarios we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In particular, one of our main results shows that γ-finite divisibility of items forces any group testing algorithm with probability of recovery error at most ϵ to perform at least Ω(γ(n/d)(1-2ϵ)/((1+2ϵ)γ)) tests. Analogously, for ρ-sized constrained tests, we show an information-theoretic lower bound of Ω(n log(n/d)/(ρ log(n/ρd))). In both scenarios we provide both randomized constructions (under both ϵ-error and zero-error reconstruction guarantees) and explicit constructions of computationally efficient group-testing algorithms (under ϵ-error reconstruction guarantees) that require a number of tests that are optimal up to constant factors in some regimes of n, d, γ and ρ. We also investigate the effect of unreliability/noise in test outcomes.
AB - Group testing is the process of pooling arbitrary subsets from a set of n items so as to identify, with a minimal number of disjunctive tests, a 'small' subset of d defective items. In 'classical' non-adaptive group testing, it is known that when d = o(n1-δ) for any δ > 0, θ(d log(n)) tests are both information-theoretically necessary, and sufficient to guarantee recovery with high probability. Group testing schemes in the literature meeting this bound require most items to be tested Ω(log(n)) times, and most tests to incorporate Ω(n/d) items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be 'sparse'. Specifically, we consider (separately) scenarios in which (a) items are finitely divisible and hence may participate in at most γ tests; and (b) tests are size-constrained to pool no more than ρ items per test. For both scenarios we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In particular, one of our main results shows that γ-finite divisibility of items forces any group testing algorithm with probability of recovery error at most ϵ to perform at least Ω(γ(n/d)(1-2ϵ)/((1+2ϵ)γ)) tests. Analogously, for ρ-sized constrained tests, we show an information-theoretic lower bound of Ω(n log(n/d)/(ρ log(n/ρd))). In both scenarios we provide both randomized constructions (under both ϵ-error and zero-error reconstruction guarantees) and explicit constructions of computationally efficient group-testing algorithms (under ϵ-error reconstruction guarantees) that require a number of tests that are optimal up to constant factors in some regimes of n, d, γ and ρ. We also investigate the effect of unreliability/noise in test outcomes.
UR - http://www.scopus.com/inward/record.url?scp=85015185659&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85015185659&partnerID=8YFLogxK
U2 - 10.1109/ALLERTON.2016.7852259
DO - 10.1109/ALLERTON.2016.7852259
M3 - Conference contribution
AN - SCOPUS:85015185659
T3 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
SP - 401
EP - 408
BT - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
Y2 - 27 September 2016 through 30 September 2016
ER -