Improved Bounds on the Restricted Isometry Constant for Orthogonal Matching Pursuit

Abstract

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 $\x$ and a matrix $\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 $\x$ from $\y=\A\x$ in $K$ iteration. This improves the best existing results which were independently given by Mo et al. and Wang et al.

Electronic Letters, 2013