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

Jian Wang; Suhyuk Kwon; Ping Li; Byonghyo Shim

doi:10.1109/TSP.2015.2498132

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

Jian Wang, Suhyuk Kwon, Ping Li, Byonghyo Shim

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

100 Citations (Scopus)

Abstract

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 Φ ∈ R^m×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 ∈ Rⁿ 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(K² log n/K), especially for large K.

Original language	English
Article number	7321045
Pages (from-to)	1076-1089
Number of pages	14
Journal	IEEE Transactions on Signal Processing
Volume	64
Issue number	4
DOIs	https://doi.org/10.1109/TSP.2015.2498132
Publication status	Published - 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.

Keywords

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

Access to Document

10.1109/TSP.2015.2498132

Cite this

@article{51d96d0ef46a480ab2c973d7d0b0e48a,

title = "Recovery of sparse signals via generalized orthogonal matching pursuit: A new analysis",

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

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

author = "Jian Wang and Suhyuk Kwon and Ping Li and Byonghyo Shim",

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: {\textcopyright} 2015 IEEE.",

year = "2016",

month = feb,

day = "15",

doi = "10.1109/TSP.2015.2498132",

language = "English",

volume = "64",

pages = "1076--1089",

journal = "IEEE Transactions on Signal Processing",

issn = "1053-587X",

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

number = "4",

}

TY - JOUR

T1 - Recovery of sparse signals via generalized orthogonal matching pursuit

T2 - A new analysis

AU - Wang, Jian

AU - Kwon, Suhyuk

AU - Li, Ping

AU - Shim, Byonghyo

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

PY - 2016/2/15

Y1 - 2016/2/15

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

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

KW - Compressed Sensing (CS)

KW - Generalized Orthogonal Matching Pursuit (gOMP)

KW - Mean Square Error (MSE)

KW - Restricted Isometry Property (RIP)

KW - sparse recovery

KW - stability

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

U2 - 10.1109/TSP.2015.2498132

DO - 10.1109/TSP.2015.2498132

M3 - Article

AN - SCOPUS:84961999658

SN - 1053-587X

VL - 64

SP - 1076

EP - 1089

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

IS - 4

M1 - 7321045

ER -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this