1Compressive Distilled Sensing: Sparse Recovery Using Adaptivity in Compressive Measurements

Abstract—The recently-proposed theory of distilled sensing establishes that adaptivity in sampling can dramatically improve the performance of sparse recovery in noisy settings. In par-ticular, it is now known that adaptive point sampling enables the detection and/or support recovery of sparse signals that are otherwise too weak to be recovered using any method based on non-adaptive point sampling. In this paper the theory of dis-tilled sensing is extended to highly-undersampled regimes, as in compressive sensing. A simple adaptive sampling-and-refinement procedure called compressive distilled sensing is proposed, where each step of the procedure utilizes information from previous observations to focus subsequent measurements into the proper signal subspace, resulting in a significant improvement in effective measurement SNR on the signal subspace. As a result, for the same budget of sensing resources, compressive distilled sensing can result in significantly improved error bounds compared to those for traditional compressive sensing. I