Improved Bounds on the Restricted Isometry Constant for Orthogonal Matching Pursuit

In this letter, we first construct a counter example to show that for any given positive integer $K\ge 2$ and for any $\frac{1}{\sqrt{K+1}}\le t<1$, there always exist a $K-$sparse $\text{x}$ and a matrix $\text{A}$ with the restricted isometry constant ${\delta }_{K+1}=t$ such that the OMP algorithm fails in $K$ iterations. Secondly, we show that even when ${\delta }_{K+1}=\frac{1}{\sqrt{K}+1}$, the OMP algorithm can also perfectly recover every $K-$sparse vector $\text{x}$ from $\text{y}=\text{A}\text{x}$ in $K$ iteration. This improves the best existing results which were independently given by Mo et al. and Wang et al.