On Finding a Set of Healthy Individuals From a Large Population

In this talk, we consider the problem of finding a given number of "healthy" items from a large population containing a small number of "defective" items using nonadaptive group testing. Such problems arise, for example, in the spectrum hole search problem for the cognitive radio (CR) networks. It is well-known that the primary user occupancy (active set) is sparse in the frequency domain over a wideband of interest. To setup a CR network, the secondary users need to find an appropriately wide unoccupied (inactive) frequency band. Thus, the main interest here is the identification of only a sub-band out of the total available unoccupied band, i.e., it is an inactive subset recovery problem. Another example is a product manufacturing plant, where a small shipment of non-defective (inactive) items has to be delivered at high priority. Once again, the interest here is in the identification of a subset of the non-defective items using as few tests as possible.

For this problem, we present mutual information based upper and lower bounds on the number of nonadaptive grouptests required to identify a given number of healthy items. We show that an impressive reduction in the number of testsis achievable compared to the approach of first identifying all the defective items and then picking the required number of healthy items from the complement set. Further, in the nonadaptive group testing setup, we obtain upper and lower bounds on the number of tests under both dilution and additive noise models, and show that the bounds are order-wise tight. Our results are derived using a general sparse signal model, by virtue of which, they are also applicable to other important sparse signal based applications such as compressive sensing (this is joint work with Abhay Sharma).