Recovering Graph-Structured Activations using Adaptive Compressive Measurements
This addresses graph signal processing for applications like sensor networks or biological networks, representing an incremental improvement over existing compressive sensing approaches.
The paper tackles the problem of localizing clusters of activated vertices in graphs using adaptively designed compressive measurements, achieving localization guarantees at weaker signal-to-noise ratios than unstructured methods and providing matching information-theoretic lower bounds.
We study the localization of a cluster of activated vertices in a graph, from adaptively designed compressive measurements. We propose a hierarchical partitioning of the graph that groups the activated vertices into few partitions, so that a top-down sensing procedure can identify these partitions, and hence the activations, using few measurements. By exploiting the cluster structure, we are able to provide localization guarantees at weaker signal to noise ratios than in the unstructured setting. We complement this performance guarantee with an information theoretic lower bound, providing a necessary signal-to-noise ratio for any algorithm to successfully localize the cluster. We verify our analysis with some simulations, demonstrating the practicality of our algorithm.