Research Projects

Sampling Limits for Detection and Identification in Sensor Networks

Galen Reeves and Michael Gastpar

ONR/MURI

Sensor networks perform a spatio-temporal sampling of the environment, and a natural question concerns the relationship between the sampling density and the resulting insight one can gain into the environment. Such questions are often considered from the perspective of recovering the underlying signal of interest, either perfectly or within a small squared error. However, many of the most interesting sensor network applications will not require such a reconstruction. Rather, for tasks such as detection and identification, only certain basic facts about the environment are of interest. Under different models of the environment and the measurement uncertainty, what are the limits on the sampling density to guarantee a certain level of fidelity in detection and identification?

Results in compressed sensing have shown that the support of a high dimensional sparse signal can be accurately determined from a relatively small number of linear measurement. We investigate the sampling rate (i.e. the ratio of measurements to signal dimension) needed to detect the support. Although this sampling rate can be very small in the noiseless setting, we have shown that in the SNR regimes inspired by communication models, the rate must increase with the dimension of the signal. Ultimately, this means that the compressed sensing gains are lost as dimensions of interest become very large. We investigate bounds on how well the support can be estimated for fixed sampling rates, and show that a bounded fraction of errors is attainable using maximum likelihood estimation. While ML estimation is computationally impractical for large signals, we also show efficient estimation schemes can attain the same basic scaling results at the price of slightly worse distortion.