Greedy Algorithms andM-Term Approximation with Regard to Redundant Dictionaries
✍ Scribed by V.N. Temlyakov
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 198 KB
- Volume
- 98
- Category
- Article
- ISSN
- 0021-9045
No coin nor oath required. For personal study only.
✦ Synopsis
We study the efficiency of greedy type algorithms with regard to redundant dictionaries in Hilbert space and we prove a general result which gives a sufficient condition on a dictionary to guarantee that the pure greedy algorithm is near best in the sense of power decay of error of approximation. We discuss also some important examples. It is already known (see DeVore and Temlyakov, Adv. Comput. Math. 5 (1996), 173 187) that the Pure Greedy Algorithm for some dictionaries has a saturation property. We construct an example which shows that a natural generalization of the Pure Greedy Algorithm also has a saturation property. Next we discuss some new phenomena which occur in approximation by a greedy type algorithm with regards to a highly redundant dictionary.