DocumentCode
3065165
Title
Sample complexity for 1-bit compressed sensing and sparse classification
Author
Gupta, Ankit ; Nowak, Robert ; Recht, Benjamin
Author_Institution
Samsung Telecommun. America, Richardson, TX, USA
fYear
2010
fDate
13-18 June 2010
Firstpage
1553
Lastpage
1557
Abstract
This paper considers the problem of identifying the support set of a high-dimensional sparse vector, from noise-corrupted 1-bit measurements. We present passive and adaptive algorithms for this problem, both requiring no more than O(d log(D)) measurements to recover the unknown support. The adaptive algorithm has the additional benefit of robustness to the dynamic range of the unknown signal.
Keywords
computational complexity; encoding; pattern classification; 1-bit compressed sensing; O(d log(D)) measurements; high-dimensional sparse vector; noise-corrupted 1-bit measurements; sample complexity; sparse classification; word length 1 bit; Adaptive algorithm; Compressed sensing; Dynamic range; Electric variables measurement; Gaussian noise; Noise measurement; Noise robustness; Signal processing; Signal to noise ratio; Telecommunication computing;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on
Conference_Location
Austin, TX
Print_ISBN
978-1-4244-7890-3
Electronic_ISBN
978-1-4244-7891-0
Type
conf
DOI
10.1109/ISIT.2010.5513510
Filename
5513510
Link To Document