TY - JOUR
T1 - Subspace pursuit for compressive sensing signal reconstruction
AU - Dai, Wei
AU - Milenkovic, Olgica
N1 - Manuscript received March 10, 2008; revised October 30, 2008. Current version published April 22, 2009. This work is supported by the National Science Foundation (NSF) under Grants CCF 0644427, 0729216 and the DARPA Young Faculty Award of the second author. The authors are with the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801-2918 USA (e-mail: [email protected]; [email protected]). Communicated by H. Bölcskei, Associate Editor for Detection and Estimation. Color versions of Figures 2 and 4–6 in this paper are available online at http:// ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2009.2016006
PY - 2009
Y1 - 2009
N2 - We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques when applied to very sparse signals, and reconstruction accuracy of the same order as that of linear programming (LP) optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse, it can be shown that the mean-squared error of the reconstruction is upper-bounded by constant multiples of the measurement and signal perturbation energies.
AB - We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques when applied to very sparse signals, and reconstruction accuracy of the same order as that of linear programming (LP) optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse, it can be shown that the mean-squared error of the reconstruction is upper-bounded by constant multiples of the measurement and signal perturbation energies.
KW - Compressive sensing
KW - Orthogonal matching pursuit
KW - Reconstruction algorithms
KW - Restricted isometry property
KW - Sparse signal reconstruction
UR - http://www.scopus.com/inward/record.url?scp=65749110333&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=65749110333&partnerID=8YFLogxK
U2 - 10.1109/TIT.2009.2016006
DO - 10.1109/TIT.2009.2016006
M3 - Article
AN - SCOPUS:65749110333
SN - 0018-9448
VL - 55
SP - 2230
EP - 2249
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 5
ER -