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 .