A Sharp Bound on RIC in Generalized Orthogonal Matching Pursuit. Issue 1 (1st March 2018)

• Record Type: Journal Article
• Authors: Chen, Wengu; Ge, Huanmin
• Is Part Of: Canadian mathematical bulletin =. Volume 61:Issue 1(2018)
• Page Start: 40
• Page End: 54
• Publication Date: 2018-03-01
• Subjects: 65D15 -- 65J22 -- 68W40; sensing matrix -- generalized orthogonal matching pursuit -- restricted isometry constant -- sparse signal; Mathematics -- Periodicals; Mathematics; Periodicals; 510.5
• DOI: 10.4153/CMB-2017-009-6
• Languages: English
• ISSNs: 0008-4395

Abstract

Abstract: The generalized orthogonal matching pursuit $\left( \text{gOMP} \right)$ algorithm has received much attention in recent years as a natural extension of the orthogonal matching pursuit $\left( \text{OMP} \right)$ . It is used to recover sparse signals in compressive sensing. In this paper, a new bound is obtained for the exact reconstruction of every $K$ -sparse signal via the $\text{gOMP}$ algorithm in the noiseless case. That is, if the restricted isometry constant $\left( \text{RIC} \right)$ ${{\delta }_{NK+1}}$ of the sensing matrix $A$ satisfies ${{\delta }_{NK+1}}\, <\frac{1}{\sqrt{\frac{K}{N}+\, 1}}, $ then the $\text{gOMP}$ can perfectly recover every $K$ -sparse signal $x$ from $y\, =\, Ax$ . Furthermore, the bound is proved to be sharp. In the noisy case, the above bound on $\text{RIC}$ combining with an extra condition on the minimum magnitude of the nonzero components of $K$ -sparse signals can guarantee that the $\text{gOMP}$ selects all of the support indices of the $K$ -sparse signals.