Sparse approximation and recovery by greedy algorithms

Eugene Livshitz, Vladimir Temlyakov

Published 2013-03-14, updated 2013-04-01Version 2

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.