Lebesgue-Type Inequalities for Greedy Approximation in Banach Spaces

We study sparse representations and sparse approximations with respect to incoherent dictionaries. We address the problem of designing and analyzing greedy methods of approximation. A key question in this regard is: How to measure efficiency of a specific algorithm? Answering this question, we prove the Lebesgue-type inequalities for algorithms under consideration. A very important new ingredient of the paper is that we perform our analysis in a Banach space instead of a Hilbert space. It is known that in many numerical problems, users are satisfied with a Hilbert space setting and do not consider a more general setting in a Banach space. There are known arguments that justify interest in Banach spaces. In this paper, we give one more argument in favor of consideration of greedy approximation in Banach spaces. We introduce a concept of