Sure independence screening and compressed random sensing

Lingzhou Xue, Hui Zou

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


Compressed sensing is a very powerful and popular tool for sparse recovery of high dimensional signals. Random sensing matrices are often employed in compressed sensing. In this paper we introduce a new method named aggressive betting using sure independence screening for sparse noiseless signal recovery. The proposal exploits the randomness structure of random sensing matrices to greatly boost computation speed. When using sub-Gaussian sensing matrices, which include the Gaussian and Bernoulli sensing matrices as special cases, our proposal has the exact recovery property with overwhelming probability. We also consider sparse recovery with noise and explicitly reveal the impact of noise-to-signal ratio on the probability of sure screening.

Original languageEnglish (US)
Pages (from-to)371-380
Number of pages10
Issue number2
StatePublished - Jun 2011

Bibliographical note

Funding Information:
The authors thank the editor and referees for their helpful comments. This work was supported by a grant from the National Science Foundation, U.S.A.


  • Compressed sensing
  • Random matrix
  • Sparse recovery
  • Sub-Gaussian random variable
  • Sure independence screening


Dive into the research topics of 'Sure independence screening and compressed random sensing'. Together they form a unique fingerprint.

Cite this