  We study sparse approximation by greedy algorithms. Our contribution is
two-fold. First, we prove exact recovery with high probability of random
$K$-sparse signals within $\lceil K(1+\e)\rceil$ iterations of the Orthogonal
Matching Pursuit (OMP). This result shows that in a probabilistic sense the OMP
is almost optimal for exact recovery. Second, we prove the Lebesgue-type
inequalities for the Weak Chebyshev Greedy Algorithm, a generalization of the
Weak Orthogonal Matching Pursuit to the case of a Banach space. The main
novelty of these results is a Banach space setting instead of a Hilbert space
setting. However, even in the case of a Hilbert space our results add some new
elements to known results on the Lebesque-type inequalities for the RIP
dictionaries. Our technique is a development of the recent technique created by
Zhang.
