This article is cited in 22 papers

Sparse approximation and recovery by greedy algorithms

E. D. Livshits^ab, V. N. Temlyakov<sup>cd

a</sup> Lomonosov Moscow State University
^b Evernote Corp, Moscow 121087, Russia
^c Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
^d University of South Carolina

Abstract: We study sparse approximation by greedy algorithms. Our contribution is twofold. First, we prove exact recovery with high probability of random $K$-sparse signals within $[K(1+ \epsilon)]$ 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 Lebesgue-type inequalities for the restricted isometry property dictionaries. Our technique is a development of the recent technique created by Zhang.

Language: English

DOI: 10.1109/TIT.2014.2320932

Bibliographic databases:

• 
• 
• 
•