We propose a framework for compressive sensing of images with geometric features. Specifically, let x ∈ RN be an N-pixel image, where each pixel p has value xp. The image is acquired by computing the measurement vector Ax, where A is an m x N measurement matrix for some m l N. The goal is then to design the matrix A and recovery algorithm which, given Ax, returns an approximation to x.In this paper we investigate this problem for the case where x consists of a small number (k) of local geometric objects (e.g., stars in an image of a sky), plus noise. We construct a matrix A and recovery algorithm with the following features: (i) the number of measurements m is O(k logk N), which undercuts currently known schemes that achieve m=O(k log (N/k)) (ii) the matrix A is ultra-sparse, which is important for hardware considerations (iii) the recovery algorithm is fast and runs in time sub-linear in N. We also present a comprehensive study of an application of our algorithm to a problem in satellite navigation.

This paper demonstrates fundamental limits of sensor networks for detection problems where the number of hypotheses is exponentially large. Such problems characterize many important applications including detection and classification of targets in a geographical area using a network of seismic sensors, and detecting complex substances with a chemical sensor array. We refer to such applications as large-scale detection problems. Using the insight that these problems share fundamental similarities with the problem of communicating over a noisy channel, we define the “sensing capacity” and lower bound it for a number of sensor network models. The sensing capacity expression differs significantly from the channel capacity due to the fact that for a fixed sensor configuration, codewords are dependent and nonidentically distributed. The sensing capacity provides a bound on the minimal number of sensors required to detect the state of an environment to within a desired accuracy. The results differ significantly from classical detection theory, and provide an intriguing connection between sensor networks and communications. In addition, we discuss the insight that sensing capacity provides for the problem of sensor selection.

Prior work motivated the use of sequential decoding for the problem of large-scale detection in sensor networks. In this paper we develop the metric for sequential decoding from first principles, different from the Fano metric which is conventionally used in sequential decoding. The difference in the metric arises due to the dependence between codewords, which is inherent in sensing problems. We analyze the behavior of this metric and show that it has the requisite properties for use in sequential decoding, i.e., the metric is, 1) expected to increase if decoding proceeds correctly, and 2) expected to decrease if more than a certain number of decoding errors are made. Through simulations, we show that the metric behaves according to theory and results in much higher accuracies than the Fano metric. We also show that due to an empirically-observed computational cutoff rate, we can perform accurate detection in large scale sensor networks, even when the optimal Viterbi decoding is not computationally feasible.

Computing the exact maximum likelihood or maximum a posteriori estimate of the environment is computationally expensive in many practical distributed sensing settings. We argue that this computational difficulty can be overcome by increasing the number of sensor measurements. Based on our work on the connection between error correcting codes and sensor networks, we propose a new algorithm which extends the idea of sequential decoding used to decode convolutional codes to estimation in a sensor network. In a simulated distributed sensing application, this algorithm provides accurate estimates at a modest computational cost given a sufficient number of sensor measurements. Above a certain number of sensor measurements this algorithm exhibits a sharp transition in the number of steps it requires in order to converge, leading to the potentially counter-intuitive observation that the computational burden of estimation can be reduced by taking additional sensor measurements.

We bound the number of sensors required to achieve a desired level of sensing accuracy in a discrete sensor network application (e.g. distributed detection). We model the state of nature being sensed as a discrete vector, and the sensor network as an encoder. Our model assumes that each sensor observes only a subset of the state of nature, that sensor observations are localized and dependent, and that sensor network output across different states of nature is neither identical nor independently distributed. Using a random coding argument we prove a lower bound on the 'sensing capacity' of a sensor network, which characterizes the ability of a sensor network to distinguish among all states of nature. We compute this lower bound for sensors of varying range, noise models, and sensing functions. We compare this lower bound to the empirical performance of a belief propagation based sensor network decoder for a simple seismic sensor network scenario. The key contribution of this paper is to introduce the idea of a sharp cut-off function in the number of required sensors, to the sensor network community.

Occupancy grid mapping algorithms assume that grid block values are independently distributed. However, most environments of interest contain spatial patterns that are better characterized by models that capture dependencies among grid blocks. To account for such dependencies, we model the environment as a pairwise Markov random field. We specify a belief propagation-based mapping algorithm that takes these dependencies into account when estimating a map. To demonstrate the potential benefits of this approach, we simulate a simple multi-robot minefield mapping scenario. Minefields contain spatial dependencies since some landmine configurations are more likely than others, and since clutter, which causes false alarms, can be concentrated in certain regions and completely absent in others. Our belief propagation-based approach outperforms conventional occupancy grid mapping algorithms in the sense that better maps can be obtained with significantly fewer robot measurements. The belief propagation algorithm requires a modest amount of increased computation, but we contend that in applications where significant energy and time expenditure is associated with robot movement and active sensing, the reduction in the required number of samples justified the increased computation.

This paper computes the sensing capacity of a sensor network, with sensors of limited range, sensing a two-dimensional Markov random field, by modeling the sensing operation as an encoder. Sensor observations are dependent across sensors, and the sensor network output across different states of the environment is neither identically nor independently distributed. Using a random coding argument, based on the theory of types, we prove a lower bound on the sensing capacity of the network, which characterizes the ability of the sensor network to distinguish among environments with Markov structure, to within a desired accuracy

We define a notion of 'sensing capacity' that characterizes the ability of a sensor network to successfully distinguish among a discrete set of targets. Sensing capacity is defined as the maximum ratio of target positions to sensors for which inference of targets within a certain distortion is achievable. We demonstrate a lower bound on this capacity. Unlike previous work on 'sensor network capacity', our notion of sensing capacity is defined by the sensing task itself, as opposed to external resource constraints such as power, communications, and processing.

Deployed vision systems often encounter image variations poorly represented in their training data. While observing their environment, such vision systems obtain unlabeled data that could be used to compensate for incomplete training. In order to exploit these relatively cheap and abundant unlabeled data we present a family of algorithms called /spl lambda/MEEM. Using these algorithms, we train an appearance-based people detection model. In contrast to approaches that rely on a large number of manually labeled training points, we use a partially labeled data set to capture appearance variation. One can both avoid the tedium of additional manual labeling and obtain improved detection performance by augmenting a labeled training set with unlabeled data. Further, enlarging the original training set with new unlabeled points enables the update of detection models after deployment without human intervention. To support these claim we show people detection results, and compare our performance to a purely generative expectation maximization-based approach to learning over partially labeled data.