Recovery of sparse signals via generalized orthogonal matching pursuit: A new analysis

Jian Wang, Suhyuk Kwon, Ping Li, Byonghyo Shim

Research output: Contribution to journalArticlepeer-review

94 Citations (Scopus)


As an extension of orthogonal matching pursuit (OMP) for improving the recovery performance of sparse signals, generalized OMP (gOMP) has recently been studied in the literature. In this paper, we present a new analysis of the gOMP algorithm using the restricted isometry property (RIP). We show that if a measurement matrix Φ ∈ Rm×n satisfies the RIP with isometry constant δmax{9,S+1}K ≤ 1/8, then gOMP performs stable reconstruction of all K-sparse signals x ∈ Rn from the noisy measurements y=Φ x+ v, within {K,⌊8K/S⌋ iterations, where v is the noise vector and S is the number of indices chosen in each iteration of the gOMP algorithm. For Gaussian random measurements, our result indicates that the number of required measurements is essentially m= O(K log n/K), which is a significant improvement over the existing result m= O(K2 log n/K), especially for large K.

Original languageEnglish
Article number7321045
Pages (from-to)1076-1089
Number of pages14
JournalIEEE Transactions on Signal Processing
Issue number4
Publication statusPublished - 2016 Feb 15

Bibliographical note

Funding Information:
The work of J. Wang and P. Li were supported in part by NSF-III-1360971, NSF-Bigdata-1419210, ONRN00014-13-1-0764, and AFOSR-FA9550-13-1-0137. The work of J. Wang was also supported in part by Grant NSFC 61532009 and Grant 15KJA520001 of Jiangsu Province. The work of B. Shim was supported in part by ICT R&D program of MSIP/IITP, B0126-15-1017, Spectrum Sensing and Future Radio Communication Platforms and the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIP) (2014R1A5A1011478).

Publisher Copyright:
© 2015 IEEE.


  • Compressed Sensing (CS)
  • Generalized Orthogonal Matching Pursuit (gOMP)
  • Mean Square Error (MSE)
  • Restricted Isometry Property (RIP)
  • sparse recovery
  • stability

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Recovery of sparse signals via generalized orthogonal matching pursuit: A new analysis'. Together they form a unique fingerprint.

Cite this