CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Publications        
Abstract view

A sharp bound on RIC in generalized orthogonal matching pursuit

  • 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 sensing matrix, generalized orthogonal matching pursuit, restricted isometry constant, sparse signal
MSC Classifications: 65D15, 65J22, 68W40 show english descriptions Algorithms for functional approximation
Inverse problems
Analysis of algorithms [See also 68Q25]
65D15 - Algorithms for functional approximation
65J22 - Inverse problems
68W40 - Analysis of algorithms [See also 68Q25]
 

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