Improved bounds on restricted isometry constant for orthogonal matching pursuit

First, a counter example is constructed to show that for any given positive integer K ≥ 2 and for any (1/√K + 1) ≤ t < 1, there always exists a K-sparse x and a matrix A with the restricted isometry constant δK +1 = t such that the orthogonal matching pursuit (OMP) algorithm fails in K iterations. Secondly, it is shown that even when δ K + 1 = (1/(√K + 1)), the OMP algorithm can also perfectly recover every K-sparse vector x from y = Ax in K iterations. This improves the best existing results which were independently given by Mo and Shen and Wang and Shim.