Sure independence screening and compressed random sensing
- 24 May 2011
- journal article
- Published by Oxford University Press (OUP) in Biometrika
- Vol. 98 (2), 371-380
- https://doi.org/10.1093/biomet/asr010
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- Sure independence screening in generalized linear models with NP-dimensionalityThe Annals of Statistics, 2010
- New Bounds for Restricted Isometry ConstantsIEEE Transactions on Information Theory, 2010
- Necessary and Sufficient Conditions for Sparsity Pattern RecoveryIEEE Transactions on Information Theory, 2009
- Sure Independence Screening for Ultrahigh Dimensional Feature SpaceJournal of the Royal Statistical Society Series B: Statistical Methodology, 2008
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?IEEE Transactions on Information Theory, 2006
- Compressed sensingIEEE Transactions on Information Theory, 2006
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solutionCommunications on Pure and Applied Mathematics, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Uncertainty principles and ideal atomic decompositionIEEE Transactions on Information Theory, 2001