A Sharp Bound on RIC in Generalized Orthogonal Matching Pursuit

Chen, Wengu ; Ge, Huanmin

Canadian mathematical bulletin, Tome 61 (2018) no. 1, pp. 40-54

Résumé

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.

Détail

DOI : 10.4153/CMB-2017-009-6

Mots-clés : 65D15, 65J22, 68W40, sensing matrix, generalized orthogonal matching pursuit, restricted isometry constant, sparse signal