Subspace Pursuit for Compressive Sensing Signal Reconstruction

By Wei Dai, Olgica Milenkovic. IEEE Transactions on Information Theory, 2008

911 citations recorded by the source corpus.

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.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e365b81006034225e4eb089d682e0b3f01330245

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Fast and Efficient Compressive Sensing Using Structurally Random Matrices (2011, background): “Furthermore, there also exists a family of gr eedy pursuit algorithms [6], [7], [8], [9], [10] offering anothe r promising option for sparse reconstruction.”
Spectral compressive sensing (2013, background): “Other examples include orthogonal matching pursuit, CoSaMP, and subspace pursuit [46, 54, 55].”
The Cosparse Analysis Model and Algorithms (2011, neutral): “…the focus of many papers, studying its core theoretical properties by exploring practical numerical algorithms for using it in practice (e.g. [10, 32, 7, 11]), evaluating theoretically these algorithms’ performance guarantees (e.g. [25, 16, 41, 42, 2]), addressing ways to obtain the dictionary…”
Compressed Sensing for Wireless Communications: Useful Tips and Tricks (2015, methodology): “CoSaMp [88], SP [21] More thank indices of the nonzero elements ofs are found and then candidates of poor quality are pruned afterwards.”
Structured Compressed Sensing: From Theory to Applications (2011, methodology): “Other greedy techniques that have a similar ﬂavor to OMP include CoSaMP [56], detailed as Algorithm 2, and subspace pursuit (SP) [57].”
A Systematic Review of Compressive Sensing: Concepts, Implementations and Applications (2018, background): “[41] W. Dai and O. Milenkovic, ‘‘Subspace pursuit for compressive sensing signal reconstruction,’’ IEEE Trans.”
Distributed Compressive CSIT Estimation and Feedback for FDD Multi-User Massive MIMO Systems (2014, methodology): “works [29]–[32], many later works [33]–[38] have considered structured sparse signals and looked for approaches to exploit the structured sparsity properties.”
A non-adapted sparse approximation of PDEs with stochastic inputs (2010, methodology): “Some of the standard greedy pursuit algorithms are Orthogonal Marching Pursuit (OMP) [55,27], Regularized OMP (ROMP)[49], Stagewise OMP (StOMP) [31], Compressive Sampling MP (CoSaMP) [48], Subspace Pursuit [24], and Iterative Hard Thresholding (IHT) [26].”
Message-passing algorithms for compressed sensing (2009, methodology): “Even improvements over iterative thresholding such as CoSaMP and Subspace Pursuit (13, 14) did not achieve the transitions of LP-based methods (see also Fig.”
Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing (2009, neutral): “In the case of TST there are even more choices to be made than with IST/IHT.”
ADMiRA: Atomic Decomposition for Minimum Rank Approximation (2009, background): “Furthermore, ADMiRA provides a strong performance guarantee for P2 that covers th general case whereX0 is only approximately low-rank andb contains noise.”
Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective (2021, methodology): “Using de-bias steps in Automated Accelerated IHT: Based on pursuit methods for sparse optimization (Needell & Tropp, 2009; Dai & Milenkovic, 2009; Kyrillidis & Cevher, 2014), we propose a modiﬁcation that improves upon Algorithm 2 both in speed and accuracy in empirical evaluation.”
Compressive sensing: From theory to applications, a survey (2013, background): “Since rank determines the order, dimension and complexity of the system, low rank matrices correspond to low order statistical models.”
Fast L1-Minimization Algorithms For Robust Face Recognition (2010, neutral): “Also, in the literature, there exist greedy algorithms to estimate sparse signals, such as Orthogonal Matching Pursuit (OMP) [30] and its many variants and extensions [4], [31], [32].”