×

Universal bases and greedy algorithms for anisotropic function classes. (English) Zbl 1025.41009

We suggest a three-step strategy to find a good basis (dictionary) for nonlinear \(m\)-term approximation. The first step consists of solving an optimization problem of finding a near best basis for a given function class \(F\), when we optimize over a collection \({\mathbf D}\) of bases (dictionaries). The second step is devoted to finding a universal basis (dictionary) \({\mathcal D}_u\in {\mathbf D}\) for a given pair \(({\mathcal F},{\mathbf D})\) of collections: \({\mathcal F}\) of function classes and \({\mathbf D}\) of bases (dictionaries). This means that \({\mathcal D}_u\) provides near optimal approximation for each class \(F\) from a collection \({\mathcal F}\). The third step deals with constructing a theoretical algorithm that realizes near best \(m\)-term approximation with regard to \({\mathcal D}_u\) for function classes from \({\mathcal F}\). In this paper we work this strategy out in the model case of anisotropic function classes and the set of orthogonal bases. The results are positive. We construct a natural tensor-product-wavelet-type basis and prove that it is universal. Moreover, we prove that a greedy algorithm realizes near best \(m\)-term approximation with regard to this basis for all anisotropic function classes.

MSC:

41A25 Rate of convergence, degree of approximation
41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bernstein, S. N., On the best approximation of functions of several variables by means of polynomials of trigonometric sums, Trudy Mat. Inst. Steklov, 38, 24-29 (1951)
[2] R. A. DeVore (1998): Nonlinear approximation. Acta Numerica, 51-150. · Zbl 0931.65007
[3] DeVore, R. A.; Konyagin, S. V.; Temlyakov, V. N., Hyperbolic wavelet approximation, Constr. Approx., 14, 1-26 (1998) · Zbl 0895.41016
[4] Dung, Dihn, On best continuous methods in n-term approximation, Vietnam J. Math., 26, 367-371 (1998) · Zbl 0964.41015
[5] Kashin, B. S., On approximation properties of complete orthonormal systems, Trudy Mat. Inst. Steklov, 172, 187-191 (1985) · Zbl 0581.42018
[6] Kashin, B. S.; Temlyakov, V. N., On best m-term approximation and the entropy of sets in the space L^1, Mat. Zametki, 56, 57-86 (1994) · Zbl 0836.41008
[7] Konyagin, S. V.; Temlyakov, V. N., A remark on greedy approximation in Banach spaces, East J. Approx., 5, 1-15 (1999) · Zbl 1084.46509
[8] Lindenstrauss, J.; Tzafriri, L., Classical Banach Spaces I (1977), Berlin: Springer-Verlag, Berlin · Zbl 0362.46013
[9] Potapov, M. K., Imbedding theorems for analytic functions of several variables, Dokl. Akad. Nauk SSSR, 112, 591-594 (1957) · Zbl 0133.33201
[10] Schütt, C., Entropy numbers of diagonal operators between symmetric Banach spaces, J. Approx. Theory, 40, 121-128 (1984) · Zbl 0497.41017
[11] Temlyakov, V. N., Approximation of functions with bounded mixed difference by trigonometric polynomials, and the widths of some classes of functions, Math. USSR-Izv., 46, 171-186 (1982) · Zbl 0499.42002
[12] Temlyakov, V. N., Approximation by elements of a finite-dimensional subspace of functions from various Sobolev or Nikol’skii spaces, Mat. Zametki, 43, 770-786 (1988)
[13] Temlyakov, V. N., Approximation of Periodic Functions (1993), New York: Nova Science, New York · Zbl 0899.41001
[14] Temlyakov, V. N., Nonlinear Kolmogorov’s widths, Mat. Zametki, 63, 891-902 (1998) · Zbl 0917.41016
[15] Temlyakov, V. N., Greedy algorithms with regard to multivariate systems with special structure, Constr. Approx., 16, 399-425 (2000) · Zbl 0962.41007
[16] Timan, M. F., Interrelation between total and partial best approximation in the mean of functions of several variables, Dokl. Akad. Nauk SSSR, 112, 24-26 (1957) · Zbl 0083.05003
[17] Wojtaszczyk, P., On unconditional polynomial bases in L_p and Bergman spaces, Constr. Approx., 13, 1-15 (1997) · Zbl 0863.41004
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.