Sparse Measurement Systems: Applications, Analysis, Algorithms and Design

This thesis deals with 'large-scale' detection problems that arise in many real world applications such as sensor networks, mapping with mobile robots and group testing for biological screening and drug discovery. These are problems where the values of a large number of inputs need to be inferred from noisy observations and where the transformation from input to measurement occurs because of a physical process.;In particular, we focus on sparse measurement systems. We use the term sparse measurement system to refer to applications where every observation is a (stochastic) function of a small number of inputs. Here, small is relative to the total input size. Such a system can conveniently be represented by a (sparse) structured graphical model. We study the fundamental limits of performance of these sparse measurement systems through an information theoretic lens and analyze robustness to noise, model mismatch and parameter uncertainty. We also look at these problems from an algorithmic point of view and develop practical algorithms, aided by the representation of the system as a graphical model. We analyze how the computational cost of detection with sparse measurements changes with various system parameters. Finally, we will show how to use both these analyses to design sparse measurement systems.;We show that, in addition to sensor parameters such as the measurement function and the noise model, which describe how the physical measurement transforms the inputs, the structure of the measurements critically effects the information theoretic and computational properties associated with a measurement system. The term 'structure' here refers to properties such as the number of times each input is measured and the pattern in which inputs are sensed---parameters that become important when information from many measurements has to be fused to reconstruct the input. The measurement 'system' extends beyond the inputs and the measurements to include other factors such as how the inputs were generated, and how the measurements are fused to detect the input. We will show in this thesis that looking at a measurement system as a whole, in this way, leads to insights that can be used to improve system performance and to design better systems. The way we handle the correlations introduced by the fixed, sparse measurement structure and given measurement function, is what differentiates our use of the probabilistic method from other work in coding theory.;The aim of this thesis is to develop tools for designers and users of sparse measurement systems. Given the characteristics of the inputs to be detected and constrained choices of measurement types and structures, we help answer the following types of questions for sparse measurement systems: (1) How many measurements are required to detect the input? (2) What algorithms can be used for detection? (3) How can the algorithm be modified to suit a particular application? (4) How should the system design be changed to improve performance and robustness? (5) How do these answers change with different sensing functions, measurement structures, application requirements and detection algorithms? Providing an answer to these questions allows an engineer to design a sparse measurement system that meets specified performance objectives while respecting various physical constraints.;To demonstrate the impact of the ideas presented in this thesis we show results on two distinct real-world applications, by a combination of data driven modeling and simulation. We study two algorithms in some detail, the Cross Entropy (CE) method developed for rare event simulation and the Sequential Decoding (SD) algorithm from coding theory. In the first experiment we show how to use a sparse measurement system for a group testing based drug discovery application. We demonstrate how group testing with CE decoding can reduce the amount of noise while limiting the number of tests. In the second experiment we show that a simple Infra-Red sensor can be used to detect multiple hot targets---motivated by the important problem of finding people in disaster areas or in collapsed buildings. We validate the feasibility of our SD approach in an experiment using an actual Infra-Red temperature sensor.