×

On Lebesgue-type inequalities for greedy approximation. (English) Zbl 1120.41007

Lebesgue proved an inequality that relates the error of a particular method of approximation by the trigonometric polynomials of order n to the best possible error of approximation by the trigonometric polynomials of order n. In the case of approximation with regard to bases, the Lebesgue-type inequalities are known both in linear and in nonlinear settings. In this paper, the authors describe a pure greedy algorithm for a general dictionary. A general Lebesgue-type inequality for the pure greedy algorithm with regard to a m-coherent dictionary is proved, and an analogous inequality is established for the orthogonal greedy algorithm.

MSC:

41A10 Approximation by polynomials
42A10 Trigonometric approximation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Donoho, D. L.; Elad, M.; Temlyakov, V. N., Stable recovery of sparse overcomplete representations in the presence of noise, IMI-Preprints, 06, 1-42 (2004)
[2] DeVore, R. A.; Temlyakov, V. N., Some remarks on Greedy Algorithms, Adv. Comp. Math., 5, 173-187 (1996) · Zbl 0857.65016
[3] A.C. Gilbert, S. Muthukrishnan, M.J. Strauss, Approximation of functions over redundant dictionaries using coherence, The 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003.; A.C. Gilbert, S. Muthukrishnan, M.J. Strauss, Approximation of functions over redundant dictionaries using coherence, The 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003. · Zbl 1094.41500
[4] Konyagin, S. V.; Temlyakov, V. N., Greedy approximation with regard to bases and general minimal systems, Serdica Math. J., 28, 305-328 (2002) · Zbl 1040.41008
[5] Temlyakov, V. N., Greedy Algorithms and \(m\)-term approximation with regard to redundant dictionaries, J. Approx. Theory, 98, 117-145 (1999) · Zbl 0926.65050
[6] Temlyakov, V. N., Weak greedy algorithms, Adv. Comp. Math., 12, 213-227 (2000) · Zbl 0964.65009
[7] Temlyakov, V. N., Nonlinear methods of approximation, Found. Comput. Math., 3, 33-107 (2003) · Zbl 1039.41012
[8] Tropp, J. A., Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, 50, 2231-2242 (2004) · Zbl 1288.94019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.