TY - GEN
T1 - Pooled testing with compressive sensing
AU - Yang, Jing
AU - Prater-Bennette, Ashley
N1 - Publisher Copyright:
© 2021 SPIE
PY - 2021
Y1 - 2021
N2 - In this work, we consider compressed sensing based pooled testing, where k out of n items are defective (with a non-zero state). Each time, a subset of items are mixed together, and a real-valued quantitative measurement is obtained, where the measurement equals a random linear combination of the states of the mixed items. Our objective is to detect the k defective items based on the quantitative measurements. This problem arises in a variety of applications, including viral infection diagnosis, network state inference, etc. We assume that each item can be mixed in a limited number of tests, and the mixing coefficients are drawn independently according to a standard Gaussian distribution. We obtain sufficient conditions on the number of tests required for the exact detection of the defective items using an exhaustive search decoder. Our result indicates that the sample complexity scales in the order of O(k? log(nk)), where ? is approximately the minimum of the n proportions of tests that include individual items. Our result recovers the optimal sample complexity in compressive sensing when ? = 1. The performance of the exhaustive search decoder is evaluated numerically under various assumptions on the mixing constraints, signal to noise ratio, and sparsity level.
AB - In this work, we consider compressed sensing based pooled testing, where k out of n items are defective (with a non-zero state). Each time, a subset of items are mixed together, and a real-valued quantitative measurement is obtained, where the measurement equals a random linear combination of the states of the mixed items. Our objective is to detect the k defective items based on the quantitative measurements. This problem arises in a variety of applications, including viral infection diagnosis, network state inference, etc. We assume that each item can be mixed in a limited number of tests, and the mixing coefficients are drawn independently according to a standard Gaussian distribution. We obtain sufficient conditions on the number of tests required for the exact detection of the defective items using an exhaustive search decoder. Our result indicates that the sample complexity scales in the order of O(k? log(nk)), where ? is approximately the minimum of the n proportions of tests that include individual items. Our result recovers the optimal sample complexity in compressive sensing when ? = 1. The performance of the exhaustive search decoder is evaluated numerically under various assumptions on the mixing constraints, signal to noise ratio, and sparsity level.
UR - http://www.scopus.com/inward/record.url?scp=85108847419&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85108847419&partnerID=8YFLogxK
U2 - 10.1117/12.2587732
DO - 10.1117/12.2587732
M3 - Conference contribution
AN - SCOPUS:85108847419
T3 - Proceedings of SPIE - The International Society for Optical Engineering
BT - Big Data III
A2 - Ahmad, Fauzia
A2 - Markopoulos, Panos P.
A2 - Ouyang, Bing
PB - SPIE
T2 - Big Data III: Learning, Analytics, and Applications 2021
Y2 - 12 April 2021 through 16 April 2021
ER -