Generalized Orthogonal Matching Pursuit
Authors:
- Jian WangJWJian Wang
- Seokbeop KwonSKSeokbeop Kwon
- Byonghyo ShimBSByonghyo Shim
Preprint
Abstract
As a greedy algorithm to recover sparse signals from compressed measurements, orthogonal matching pursuit (OMP) algorithm has received much attention in recent years. In this paper, we introduce an extension of the OMP for pursuing efficiency in reconstructing sparse signals. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple $N$ indices are identified per iteration. Owing to the selection of multiple ''correct'' indices, the gOMP algorithm is finished with much smaller number of iterations when compared to the OMP. We show that the gOMP can perfectly reconstruct any $K$-sparse signals ($K > 1$), provided that the sensing matrix satisfies the RIP with $\delta_{NK} < \frac{\sqrt{N}}{\sqrt{K} + 3 \sqrt{N}}$. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to $\ell_1$-minimization technique with fast processing speed and competitive computational complexity.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Stability and Robustness of Weak Orthogonal Matching Pursuits2012
- Signal Recovery From Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching PursuitIEEE Journal of Selected Topics in Signal Processing, 2010
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching PursuitFoundations of Computational Mathematics, 2008
- The restricted isometry property and its implications for compressed sensingComptes Rendus Mathématique, 2008
- A Simple Proof of the Restricted Isometry Property for Random MatricesConstructive Approximation, 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
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Uncertainty principles and ideal atomic decompositionIEEE Transactions on Information Theory, 2001