Improved Sufficient Conditions for Support Recovery of Sparse Signals Via Orthogonal Matching Pursuit

Abstract

The orthogonal matching pursuit (OMP) algorithm is a standard greedy algorithm in the context of compressed sensing. Due to its high efficiency and effectiveness, OMP has drawn much attention in the recent decade. The goal of this paper is to study different conditions for stable recovery of sparse signals with OMP from a limited number of linear measurements for noisy signals. Specifically, two new sufficient conditions on the minimum magnitude of nonzero elements of sparse signals under which OMP can precisely recover the support of sparse signals are presented under the 1∞-Gaussian and bounded noise, respectively. Our conditions are much weaker when compared with the existing ones.

Keywords

• Support recovery
• compressed sensing
• orthogonal matching pursuit
• restricted isometry constant