Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals → CMB
Abstract view

# A sharp bound on RIC in generalized orthogonal matching pursuit

 Read article[PDF: 662KB]
Published:2017-04-17
Printed: Mar 2018
• Wengu Chen,
Institute of Applied Physics and Computational Mathematics, Beijing, 100088, China
• Huanmin Ge,
Graduate School, China Academy of Engineering Physics, Beijing, 100088, China
 Format: LaTeX MathJax PDF

## Abstract

Generalized orthogonal matching pursuit (gOMP) algorithm has received much attention in recent years as a natural extension of orthogonal matching pursuit (OMP). 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 gOMP algorithm in the noiseless case. That is, if the restricted isometry constant (RIC) $\delta_{NK+1}$ of the sensing matrix $A$ satisfies $\delta_{NK+1}\lt \frac{1}{\sqrt{\frac{K}{N}+1}}$, then the 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 RIC combining with an extra condition on the minimum magnitude of the nonzero components of $K$-sparse signals can guarantee that the gOMP selects all of support indices of the $K$-sparse signals.
 Keywords: sensing matrix, generalized orthogonal matching pursuit, restricted isometry constant, sparse signal
 MSC Classifications: 65D15 - Algorithms for functional approximation 65J22 - Inverse problems 68W40 - Analysis of algorithms [See also 68Q25]

 top of page | contact us | privacy | site map |

© Canadian Mathematical Society, 2018 : https://cms.math.ca/