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.