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.
|