Robust support recovery using sparse compressive sensing matrices

Jarvis Haupt, Richard Baraniuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2011 45th Annual Conference on Information Sciences and Systems, CISS 2011
DOIs
StatePublished - 2011
Event2011 45th Annual Conference on Information Sciences and Systems, CISS 2011 - Baltimore, MD, United States
Duration: Mar 23 2011Mar 25 2011

Publication series

Name2011 45th Annual Conference on Information Sciences and Systems, CISS 2011

Other

Other2011 45th Annual Conference on Information Sciences and Systems, CISS 2011
Country/TerritoryUnited States
CityBaltimore, MD
Period3/23/113/25/11

Keywords

  • Support recovery
  • compressive sensing
  • feature selection
  • model selection
  • robust inference
  • sketching
  • sparse recovery
  • sparsity pattern recovery

Fingerprint

Dive into the research topics of 'Robust support recovery using sparse compressive sensing matrices'. Together they form a unique fingerprint.

Cite this