An improved RIP-based performance guarantee for sparse signal recovery via orthogonal matching pursuit

Ling Hua Chang, Jwo-Yuh Wu

Research output: Contribution to journalArticlepeer-review

60 Scopus citations

Abstract

A sufficient condition reported very recently for perfect recovery of a K-sparse vector via orthogonal matching pursuit (OMP) in K iterations (when there is no noise) is that the restricted isometry constant (RIC) of the sensing matrix satisfies δK+1 <(1K+1). In the noisy case, this RIC upper bound along with a requirement on the minimal signal entry magnitude is known to guarantee exact support identification. In this paper, we show that, in the presence of noise, a relaxed RIC upper bound δK+1 < 4K+1-1/2K together with a relaxed requirement on the minimal signal entry magnitude suffices to achieve perfect support identification using OMP. In the noiseless case, our result asserts that such a relaxed RIC upper bound can ensure exact support recovery in K iterations: this narrows the gap between the so far best known bound δK+1 <(1K+1) and the ultimate performance guarantee δK+1=(1/K). Our approach relies on a newly established near orthogonality condition, characterized via the achievable angles between two orthogonal sparse vectors upon compression, and, thus, better exploits the knowledge about the geometry of the compressed space. The proposed near orthogonality condition can be also exploited to derive less restricted sufficient conditions for signal reconstruction in two other compressive sensing problems, namely, compressive domain interference cancellation and support identification via the subspace pursuit algorithm.

Original languageEnglish
Article number6853372
Pages (from-to)5702-5715
Number of pages14
JournalIEEE Transactions on Information Theory
Volume60
Issue number9
DOIs
StatePublished - 1 Jan 2014

Keywords

  • Compressive sensing
  • interference cancellation
  • orthogonal matching pursuit
  • restricted isometry constant (RIC)
  • restricted isometry property (RIP)
  • subspace pursuit

Fingerprint Dive into the research topics of 'An improved RIP-based performance guarantee for sparse signal recovery via orthogonal matching pursuit'. Together they form a unique fingerprint.

Cite this