Generalized orthogonal matching pursuit

Jian Wang; Seokbeop Kwon; Byonghyo Shim

doi:10.1109/TSP.2012.2218810

Generalized orthogonal matching pursuit

Jian Wang, Seokbeop Kwon, Byonghyo Shim

Department of Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

524 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 L₁- minimization technique with fast processing speed and competitive computational complexity.

Original language	English
Article number	6302206
Pages (from-to)	6202-6216
Number of pages	15
Journal	IEEE Transactions on Signal Processing
Volume	60
Issue number	12
DOIs	https://doi.org/10.1109/TSP.2012.2218810
Publication status	Published - 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

Access to Document

10.1109/TSP.2012.2218810

Cite this

@article{3a46adc4aacc4f0583ca0e9a7d4a262f,

title = "Generalized orthogonal matching pursuit",

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.",

keywords = "Compressive sensing (CS), orthogonal matching pursuit, restricted isometry property (RIP), sparse recovery",

author = "Jian Wang and Seokbeop Kwon and Byonghyo Shim",

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.",

year = "2012",

doi = "10.1109/TSP.2012.2218810",

language = "English",

volume = "60",

pages = "6202--6216",

journal = "IEEE Transactions on Signal Processing",

issn = "1053-587X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "12",

}

TY - JOUR

T1 - Generalized orthogonal matching pursuit

AU - Wang, Jian

AU - Kwon, Seokbeop

AU - Shim, Byonghyo

N1 - 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.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Compressive sensing (CS)

KW - orthogonal matching pursuit

KW - restricted isometry property (RIP)

KW - sparse recovery

UR - http://www.scopus.com/inward/record.url?scp=84870506486&partnerID=8YFLogxK

U2 - 10.1109/TSP.2012.2218810

DO - 10.1109/TSP.2012.2218810

M3 - Article

AN - SCOPUS:84870506486

SN - 1053-587X

VL - 60

SP - 6202

EP - 6216

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

IS - 12

M1 - 6302206

ER -

Generalized orthogonal matching pursuit

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this