Speaker: Yifei Ma

Abstract: Many real-world applications require searching for sparse signals on a large search domain, looking for needles in a haystack. Motivated by unmanned aerial vehicle surveillance for gas leaks or human survivors of disasters, we study optimal search designs when the observations are limited to taking average values in physically contiguous regions. In contrast to the popular argument that in unconstrained domains, an active design may not be necessary to achieve the optimal sampling complexity (up to logarithmic factors), we find compressive sensing infeasible in our constrained problem. Therefore, we use an information theoretic approach and demonstrate its optimality in 1d domains despite its greedy nature. Simulation studies and demonstrations of our method on real satellite images are provided.