On the interdependence of sensing, accuracy, and complexity in large-scale detection applications

This thesis presents fundamental limits and practical algorithms for multi-sensor systems in 'large-scale detection' applications. Multi-sensor systems combine multiple sensor observations to detect or estimate the state of an environment. We define 'large-scale detection' as a detection problem where sensors are used to detect the state of a discrete grid or vector. Such problems characterize many important applications, including detection and classification of targets in a geographical area using a sensor network, and detecting complex chemicals using a chemical sensor array.; While multi-sensor systems have been deployed in large-scale detection applications, many basic theoretical questions regarding sensor allocation and sensor selection have not been addressed in earlier work. To understand the performance limits of such systems, recent work proposed the idea of a 'sensing capacity.' While a definition was provided, the existence of a strictly positive sensing capacity, and therefore the practical value of this idea, remained an open question. One of the main contributions of this thesis is to define a sensing capacity that allows for a tolerable detection error. For this definition, we prove the existence of a positive sensing capacity for a number of multi-sensor system models.; The sensing capacity provides fundamental limits on the number of sensor measurements required to detect the state of an environment. We obtain our theoretical results by using the insight that large-scale detection problems bear a striking resemblance to the problem of communicating over a noisy channel. In communications, Shannon's celebrated channel capacity results bound the maximum rate of transmission below which coding schemes with error probability arbitrarily close to zero are feasible. For a large-scale detection application, our results bound the minimum number of sensors required to achieve a desired detection accuracy with arbitrarily small probability of error.; We analyze the sensing capacity for several multi-sensor system models, and extend this analysis to account for spatial and temporal dependence in the environment being sensed. Sensing capacity differs significantly from channel capacity, since it is not a mutual information. This has practical implications for the problem of sensor selection. In addition, our results differ significantly from classical detection theory, where the probability of error approaches zero as the ratio of hypotheses to sensor measurements goes to zero. In contrast, we show that there exists a positive ratio of the size of the grid or vector being detected to the number of sensor measurements below which error can be made arbitrarily close to zero.; An important implication of our theoretical results is the connection provided by the sensing capacity between multi-sensor systems and the large number of coding ideas used to build communications systems. To demonstrate the benefit of this insight, we extend the idea of sequential decoding from convolutional codes to multi-sensor systems. Sequential decoding is a low-complexity decoding heuristic for convolutional codes that works well at rates sufficiently below the channel capacity. In simulations of robot mapping, we show that this idea can be applied to sensor fusion in multi-sensor systems, as an alternative to complex algorithms such as the belief propagation algorithm.; To demonstrate the impact of the ideas presented in this thesis in a practical application, we show how a simple IR thermometer can be used to detect multiple targets. In practice, such sensors are used to estimate the temperature of a specific object. To enable the use of such sensors in target detection, we develop a realistic physics-based sensor model that accounts for the interaction of multiple hot targets with the sensor. In simulation, we demonstrate that for a sufficient number of IR sensor measurements, sequential decoding algorithms have sharp empirical performance...