Robust support recovery using sparse compressive sensing matrices

This paper considers the task of recovering the support of a sparse, high-dimensional vector from a small number of measurements. The procedure proposed here, which we call the Sign-Sketch procedure, is shown to be a robust recovery method in settings where the measurements are corrupted by various forms of uncertainty, including additive Gaussian noise and (possibly unbounded) outliers, and even subsequent quantization of the measurements to a single bit. The Sign-Sketch procedure employs sparse random measurement matrices, and utilizes a computationally efficient support recovery procedure that is a variation of a technique from the sketching literature. We show here that O(max {k log(n - k), k log k}) non-adaptive linear measurements suffice to recover the support of any unknown n-dimensional vector having no more than k nonzero entries, and that our proposed procedure requires at most O(n log n) total operations for both acquisition and inference.