DocumentCode :
3246741
Title :
Further Results on Performance Analysis for Compressive Sensing Using Expander Graphs
Author :
Xu, Weiyu ; Hassibi, Babak
Author_Institution :
California Inst. of Technol., Pasadena
fYear :
2007
fDate :
4-7 Nov. 2007
Firstpage :
621
Lastpage :
625
Abstract :
Compressive sensing is an emerging technology which can recover a sparse signal vector of dimension n via a much smaller number of measurements than n. In this paper, we will give further results on the performance bounds of compressive sensing. We consider the newly proposed expander graph based compressive sensing schemes and show that, similar to the l1 minimization case, we can exactly recover any k-sparse signal using only O(k log(n)) measurements, where k is the number of nonzero elements. The number of computational iterations is of order O(k log(n)), while each iteration involves very simple computational steps.
Keywords :
computational complexity; graph theory; iterative methods; signal sampling; compressive sensing; computational iterations; expander graphs; sparse signal vector; Current measurement; Graph theory; Mathematics; Noise robustness; Performance analysis; Signal processing; Signal sampling; Sparse matrices; Time measurement; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Signals, Systems and Computers, 2007. ACSSC 2007. Conference Record of the Forty-First Asilomar Conference on
Conference_Location :
Pacific Grove, CA
ISSN :
1058-6393
Print_ISBN :
978-1-4244-2109-1
Electronic_ISBN :
1058-6393
Type :
conf
DOI :
10.1109/ACSSC.2007.4487288
Filename :
4487288
Link To Document :
بازگشت