  Orthogonal Matching pursuit (OMP) is a popular algorithm to estimate an
unknown sparse vector from multiple linear measurements of it. Assuming exact
sparsity and that the measurements are corrupted by additive Gaussian noise,
the success of OMP is often formulated as exactly recovering the support of the
sparse vector. Several authors derived a sufficient condition for exact support
recovery by OMP with high probability depending on the signal-to-noise ratio,
defined as the magnitude of the smallest non-zero coefficient of the vector
divided by the noise level. We make two contributions. First, we derive a
slightly sharper sufficient condition for two variants of OMP, in which either
the sparsity level or the noise level is known. Next, we show that this sharper
sufficient condition is tight, in the following sense: for a wide range of
problem parameters, there exist a dictionary of linear measurements and a
sparse vector with a signal-to-noise ratio slightly below that of the
sufficient condition, for which with high probability OMP fails to recover its
support. Finally, we present simulations which illustrate that our condition is
tight for a much broader range of dictionaries.
