Exact reconstruction of sparse signals via generalized orthogonal matching pursuit

Jian Wang, Byonghyo Shim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationConference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011
Number of pages4
Publication statusPublished - 2011
Event45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011 - Pacific Grove, CA, United States
Duration: 2011 Nov 62011 Nov 9

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393


Other45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011
Country/TerritoryUnited States
CityPacific Grove, CA


  • Compressed sensing (CS)
  • generalized orthogonal matching pursuit (gOMP)
  • restricted isometric property (RIP)

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications

Cite this