Adaptive Sensing for Sparse Signal Recovery

The theory of compressed sensing shows that sparse signals in high-dimensional spaces can be recovered from a relatively small number of samples in the form of random projections. However, in severely resource-constrained settings even CS techniques may fail, and thus, a less aggressive goal of partial signal recovery is reasonable. This paper describes a simple data-adaptive procedure that efficiently utilizes information from previous observations to focus subsequent measurements into subspaces that are increasingly likely to contain true signal components. The procedure is analyzed in a simple setting, and more generally, shown experimentally to be more effective than methods based on traditional (non-adaptive) random projections for partial signal recovery.