Performance analysis of orthogonal matching pursuit under general perturbations

Jie Ding, Laming Chen, Yuantao Gu

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

3 Scopus citations

Abstract

As a canonical greedy algorithm, Orthogonal Matching Pursuit (OMP) is used for sparse approximation. Previous studies have mainly considered non-perturbed observations y = Φx, and focused on the exact recovery of x through y and Φ. Here, Φ is a matrix with more columns than rows, and x is a sparse signal to be recovered. This paper deals with performance of OMP under general perturbations - from both y and Φ. The main contribution shows that exact recovery of the support set of x can be guaranteed under suitable conditions. Such conditions are RIP-based, and involve the concept of sparsity, relative perturbation, and the smallest nonzero entry. In addition, certain conditions are given under which the support set of x can be reconstructed in the order of its entries' magnitude. In the end, it is pointed out that the conditions can be relaxed at the expense of a decrease in the accuracy of the recovery.

Original languageEnglish (US)
Title of host publication2012 International Conference on Computing, Networking and Communications, ICNC'12
Pages892-896
Number of pages5
DOIs
StatePublished - Apr 24 2012
Externally publishedYes
Event2012 International Conference on Computing, Networking and Communications, ICNC'12 - Maui, HI, United States
Duration: Jan 30 2012Feb 2 2012

Publication series

Name2012 International Conference on Computing, Networking and Communications, ICNC'12

Other

Other2012 International Conference on Computing, Networking and Communications, ICNC'12
CountryUnited States
CityMaui, HI
Period1/30/122/2/12

Keywords

  • Orthogonal Matching Pursuit (OMP)
  • Restricted Isometry Property (RIP)
  • general perturbations
  • support recovery

Fingerprint Dive into the research topics of 'Performance analysis of orthogonal matching pursuit under general perturbations'. Together they form a unique fingerprint.

Cite this