Tata Institute of Fundamental Research
On Finding a Set of Healthy Individuals From a Large Population
Seminar
Speaker:
Dr. Chandra R. Murthy (Indian Institute of Science
Electrical Communication Engineering Department
Bangalore 560012)
Organiser:
Rahul Vaze
Date:
Tuesday, 19 Nov 2013, 11:00 to 12:00
Venue:
AG-80
(Scan to add to calendar)
Abstract:
Abstract: 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).
| Speaker: | Dr. Chandra R. Murthy (Indian Institute of Science Electrical Communication Engineering Department Bangalore 560012) |
| Organiser: | Rahul Vaze |
| Date: | Tuesday, 19 Nov 2013, 11:00 to 12:00 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
Abstract: 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).
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).