Generalized orthogonal matching pursuit

Jian Wang, Seokbeop Kwon, Byonghyo Shim

    Research output: Contribution to journalArticlepeer-review

    631 Citations (Scopus)

    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 δNK< √ N/√K+3√N. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to L1- minimization technique with fast processing speed and competitive computational complexity.

    Original languageEnglish
    Article number6302206
    Pages (from-to)6202-6216
    Number of pages15
    JournalIEEE Transactions on Signal Processing
    Volume60
    Issue number12
    DOIs
    Publication statusPublished - 2012

    Bibliographical note

    Funding Information:
    Manuscript received March 28, 2012; revised July 20, 2012; accepted September 06, 2012. Date of publication September 13, 2012; date of current version November 20, 2012. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Lawrence Carin. This work was supported by the KCC (Korea Communications Commission), Korea, under the R&D program supervised by the KCA (Korea Communication Agency) (KCA-12-911-01-110) and the NRF grant funded by the Korea government (MEST) (No. 2011-0012525). This paper was presented in part at the Asilomar Conference on Signals, Systems and Computers, November 2011.

    Keywords

    • Compressive sensing (CS)
    • orthogonal matching pursuit
    • restricted isometry property (RIP)
    • sparse recovery

    ASJC Scopus subject areas

    • Signal Processing
    • Electrical and Electronic Engineering

    Fingerprint

    Dive into the research topics of 'Generalized orthogonal matching pursuit'. Together they form a unique fingerprint.

    Cite this