Title :
Complex sparse projections for compressed sensing
Author :
Moghadam, Abdolreza Abdolhosseini ; Radha, Hayder
Author_Institution :
Dept. of Electr. & Comput. Eng., Michigan State Univ., East Lansing, MI, USA
Abstract :
Sparse projections for compressed sensing have been receiving some attention recently. In this paper, we consider the problem of recovering a k-sparse signal (x) in an n-dimensional space from a limited number (m) of linear, noiseless compressive samples (y) using complex sparse projections. Our approach is based on constructing complex sparse projections using strategies rooted in combinatorial design and expander graphs. We are able to recover the non-zero coefficients of the k-sparse signal (x) iteratively using a low-complexity algorithm that is reminiscent of well-known iterative channel decoding methods. We show that the proposed framework is optimal in terms of sample requirements for signal recovery (m = O (k log(n/k))) and has a decoding complexity of O (m log(n/m)), which represents a tangible improvement over recent solvers. Moreover we prove that using the proposed complex-sparse framework, on average 2k < m ¿ 4k real measurements (where each complex sample is counted as two real measurements) suffice to recover a k-sparse signal perfectly.
Keywords :
channel coding; combinatorial mathematics; computational complexity; graph theory; iterative decoding; signal reconstruction; combinatorial design; complex sparse projections; compressed sensing; decoding complexity; expander graphs; iterative channel decoding method; k-sparse signal recovery; low-complexity algorithm; noiseless compressive samples; nonzero coefficient recovery; Compressed sensing; Equations; Graph theory; Greedy algorithms; Iterative algorithms; Iterative decoding; Iterative methods; Minimization methods; Signal design; Sparse matrices; Compressed Sensing; channel decoding; sparse projections;
Conference_Titel :
Information Sciences and Systems (CISS), 2010 44th Annual Conference on
Conference_Location :
Princeton, NJ
Print_ISBN :
978-1-4244-7416-5
Electronic_ISBN :
978-1-4244-7417-2
DOI :
10.1109/CISS.2010.5464917