Affordable Access

Sparse approximation and recovery by greedy algorithms

Authors
  • Livshitz, Eugene
  • Temlyakov, Vladimir
Type
Preprint
Publication Date
Apr 01, 2013
Submission Date
Mar 14, 2013
Identifiers
arXiv ID: 1303.3595
Source
arXiv
License
Yellow
External links

Abstract

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.

Report this publication

Statistics

Seen <100 times