Exact reconstruction of sparse signals via generalized orthogonal matching pursuit
Authors:
- 1 November 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1139-1142
Abstract
As a greedy algorithm recovering sparse signal from compressed measurements, orthogonal matching pursuit (OMP) algorithm have received much attention in recent years. The OMP selects at each step one index corresponding to the column that is most correlated with the current residual. In this paper, we present an extension of OMP for pursuing efficiency of the index selection. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple (N ∈ ℕ) columns are identified per step. We derive rigorous condition demonstrating that exact reconstruction of K-sparse (K >; 1) signals is guaranteed for the gOMP algorithm if the sensing matrix satisfies the restricted isometric property (RIP) of order NK with isometric constant δ NK <; √n/(√K+2√N). In addition, empirical results demonstrate that the gOMP algorithm has very competitive reconstruction performance that is comparable to the ℓ 1 -minimization technique.Keywords
This publication has 11 references indexed in Scilit:
- Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry PropertyIEEE Transactions on Information Theory, 2010
- Signal Recovery From Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching PursuitIEEE Journal of Selected Topics in Signal Processing, 2010
- On Recovery of Sparse Signals Via $\ell _{1}$ MinimizationIEEE Transactions on Information Theory, 2009
- Subspace Pursuit for Compressive Sensing Signal ReconstructionIEEE Transactions on Information Theory, 2009
- The restricted isometry property and its implications for compressed sensingComptes Rendus Mathématique, 2008
- Sparsity and incoherence in compressive samplingInverse Problems, 2007
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationIEEE Transactions on Information Theory, 2006
- Error correction via linear programming2005
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimizationProceedings of the National Academy of Sciences, 2003
- Signal representation using adaptive normalized Gaussian functionsSignal Processing, 1994