On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit
Authors:
- 6 June 2012
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 60 (9) , 4973-4976
Abstract
Orthogonal matching pursuit (OMP) is a greedy search algorithm popularly being used for the recovery of compressive sensed sparse signals. In this correspondence, we show that if the isometry constant δK+1 of the sensing matrix Φ satisfies δK+1 <; 1/(1/√K+1) then the OMP algorithm can perfectly recover K-sparse signals from the compressed measurements y=Φx. Our bound offers a substantial improvement over the recent result of Davenport and Wakin and also closes gap between the recovery bound and fundamental limit over which the perfect recovery of the OMP cannot be guaranteed.Keywords
This publication has 12 references indexed in Scilit:
- Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching PursuitIEEE Transactions on Information Theory, 2012
- Near optimal bound of orthogonal matching pursuit using restricted isometric constantEURASIP Journal on Advances in Signal Processing, 2012
- The Orthogonal Super Greedy Algorithm and Applications in Compressed SensingIEEE Transactions on Information Theory, 2011
- 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
- Shifting Inequality and Recovery of Sparse SignalsIEEE Transactions on Signal Processing, 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
- A Simple Proof of the Restricted Isometry Property for Random MatricesConstructive Approximation, 2008
- A generalized uncertainty principle and sparse representation in pairs of basesIEEE Transactions on Information Theory, 2002