Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity

Preprint
Publisher Website
Google Scholar
  • 6 March 2008
Abstract
We propose a new algorithm, termed subspace pursuit, for signal reconstruction of sparse and compressible signals with and without noisy perturbations. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques, and reconstruction capability of the same order as that of $l_{1}$-norm optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm is capable of exactly reconstructing an arbitrary sparse signals, provided that the linear measurements satisfy the restricted isometry property with a constant parameter which can be described in a closed form. In the noisy setting and the case where the signal is not exactly sparse, it can be shown that the mean squared error of the reconstruction is upper bounded by a constant multiple of the measurement and signal pertubation energy.

This publication has 0 references indexed in Scilit: