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.

Original languageEnglish (US)
Pages (from-to)2230-2249
Number of pages20
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - May 27 2009


  • Compressive sensing
  • Orthogonal matching pursuit
  • Reconstruction algorithms
  • Restricted isometry property
  • Sparse signal reconstruction

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Subspace pursuit for compressive sensing signal reconstruction'. Together they form a unique fingerprint.

  • Cite this