Recovering Block-structured Activations Using Compressive Measurements

We consider the problems of detection and support recovery of a contiguous block of weak activation in a large matrix, from a small number of noisy, possibly adaptive, compressive (linear) measurements. We characterize the tradeoffs between the various problem dimensions, the signal strength and the number of measurements required to reliably detect and recover the support of the signal. In each case sufficient conditions are complemented with information theoretic lower bounds. This is closely related to the problem of (noisy) compressed sensing, where the anal-ogous task is to detect or recover the support of a sparse vector using a small number of linear measurements. In compressed sensing, it has been shown that, at least in a mini-max sense, for both detection and support recovery, adaptivity and contiguous structure only reduce signal strength requirements by logarithmic factors. On the contrary, we show that while for detection neither adaptivity nor structure reduce the signal strength requirement, for support recovery the signal strength requirement is strongly influenced by both structure and the ability to choose measurements adaptively