Subspace Pursuit for Compressive Sensing Signal Reconstruction

Abstract

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 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.

The first version was submitted on Mar. 6th, 2008. The 2nd version was updated on Mar. 10th, 2008. The 3rd version was submitted on Jan 8th, 2009

Cited by in corpus (17)

• A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework
• A framework to characterize performance of LASSO algorithms
• On the Iterative Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing
• Combining geometry and combinatorics: A unified approach to sparse signal recovery
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• Compressed Remote Sensing of Sparse Objects
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• Compressive Sensing Using Low Density Frames
• A rigorous geometry-probability equivalence in characterization of ${\ell }_1$-optimization
• Improved Bounds on Restricted Isometry Constants for Gaussian Matrices
• A performance analysis framework for SOCP algorithms in noisy compressed sensing
• Efficient and Guaranteed Rank Minimization by Atomic Decomposition
• Bounds on restricted isometry constants of random matrices
• Towards a better compressed sensing
• Linear under-determined systems with sparse solutions: Redirecting a challenge?
• A problem dependent analysis of SOCP algorithms in noisy compressed sensing
• Compressive Imaging of Subwavelength Structures