Title :
Further Results on Performance Analysis for Compressive Sensing Using Expander Graphs
Author :
Xu, Weiyu ; Hassibi, Babak
Author_Institution :
California Inst. of Technol., Pasadena
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;
Conference_Titel :
Signals, Systems and Computers, 2007. ACSSC 2007. Conference Record of the Forty-First Asilomar Conference on
Conference_Location :
Pacific Grove, CA
Print_ISBN :
978-1-4244-2109-1
Electronic_ISBN :
1058-6393
DOI :
10.1109/ACSSC.2007.4487288