Active Search for Sparse Signals with Region Sensing
  Autonomous systems can be used to search for sparse signals in a large space;
e.g., aerial robots can be deployed to localize threats, detect gas leaks, or
respond to distress calls. Intuitively, search algorithms may increase
efficiency by collecting aggregate measurements summarizing large contiguous
regions. However, most existing search methods either ignore the possibility of
such region observations (e.g., Bayesian optimization and multi-armed bandits)
or make strong assumptions about the sensing mechanism that allow each
measurement to arbitrarily encode all signals in the entire environment (e.g.,
compressive sensing). We propose an algorithm that actively collects data to
search for sparse signals using only noisy measurements of the average values
on rectangular regions (including single points), based on the greedy
maximization of information gain. We analyze our algorithm in 1d and show that
it requires $\tilde{O}(\frac{n}{\mu^2}+k^2)$ measurements to recover all of $k$
signal locations with small Bayes error, where $\mu$ and $n$ are the signal
strength and the size of the search space, respectively. We also show that
active designs can be fundamentally more efficient than passive designs with
region sensing, contrasting with the results of Arias-Castro, Candes, and
Davenport (2013). We demonstrate the empirical performance of our algorithm on
a search problem using satellite image data and in high dimensions.
