A note on optimal support recovery in compressed sensing


Journal Article

Recovery of the support set (or sparsity pattern) of a sparse vector from a small number of noisy linear projections (or samples) is a "compressed sensing" problem that arises in signal processing and statistics. Although many computationally efficient recovery algorithms have been studied, the optimality (or gap from optimality) of these algorithms is, in general, not well understood. In this note, approximate support recovery under a Gaussian prior is considered, and it is shown that optimal estimation depends on the recovery metric in general. By contrast, it is shown that in the SNR limits, there exist uniformly near-optimal estimators, namely, the ML estimate in the high SNR case, and a computationally trivial thresholding algorithm in the low SNR case. © 2009 IEEE.

Full Text

Duke Authors

Cited Authors

  • Reeves, G; Gastpar, M

Published Date

  • December 1, 2009

Published In

Start / End Page

  • 1576 - 1580

International Standard Serial Number (ISSN)

  • 1058-6393

Digital Object Identifier (DOI)

  • 10.1109/ACSSC.2009.5470153

Citation Source

  • Scopus