×

Simultaneous approximation by greedy algorithms. (English) Zbl 1096.41026

Authors’ abstract: We study nonlinear \(m\)-term approximation with regard to a redundant dictionary \(\mathcal D\) in a Hilbert space \(H\). It is known that the Pure Greedy Algorithm (or, more generally, the Weak Greedy Algorithm) provides for each \(f \in H\) and any dictionary \(\mathcal D\) an expansion into a series \[ f = \sum_{j=1}^\infty c_j(f) \varphi_j(f), \qquad \varphi(f) \in \mathcal D, \quad j=1,1,\ldots, \] with the Parseval property: \(\| f\|^{2} = \sum_{j} | c_j(f)|^2\). Following the paper of A. Lutoborski and the second author we study analogs of the above expansions for a given finite number of functions \(f^1,\ldots, f^N\) with a requirement that the dictionary elements \(\varphi_{j}\) of these expansions are the same for all \(f^i\), \(i =1,\ldots,N\). We study convergence and rate of convergence of such expansions which we call simultaneous expansions.
In the reviewer’s opinion, this paper is a major contribution on the subject.

MSC:

41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
41A25 Rate of convergence, degree of approximation
41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
46B20 Geometry and structure of normed linear spaces
41A28 Simultaneous approximation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.R. Barron, Universal approximation bounds for superposition of n sigmoidal functions, IEEE Trans. Inform. Theory 39 (1993) 930–945. · Zbl 0818.68126
[2] A. Cohen, R.A. DeVore and R. Hochmuth, Restricted nonlinear approximation, Constr. Approx. 16 (2000) 85–113. · Zbl 0947.41006
[3] G. Davis, S. Mallat and M. Avellaneda, Adaptive greedy approximations, Constr. Approx. 13 (1997) 57–98. · Zbl 0885.41006
[4] R.A. DeVore, Nonlinear approximation, Acta Numerica (1998) 51–150. · Zbl 0931.65007
[5] R. DeVore, B. Jawerth and V. Popov, Compression of wavelet decompositions, Amer. J. Math. 114 (1992) 737–785. · Zbl 0764.41024
[6] R.A. DeVore and V.N. Temlyakov, Nonlinear approximation by trigonometric sums, J. Fourier Anal. Appl. 2 (1995) 29–48. · Zbl 0886.42019
[7] R.A. DeVore and V.N. Temlyakov, Some remarks on Greedy Algorithms, Adv. Comput. Math. 5 (1996) 173–187. · Zbl 0857.65016
[8] R.A. DeVore and V.N. Temlyakov, Nonlinear approximation in finite-dimensional spaces, J. Complexity 13 (1997) 489–508. · Zbl 0892.41009
[9] S.J. Dilworth, N.J. Kalton, D. Kutzarova and V.N. Temlyakov, The tresholding greedy algorithm, greedy bases, and duality, IMI-Preprint Series 23 (2001) 1–23.
[10] D.L. Donoho, Unconditional bases are optimal bases for data compression and for statistical estimation, Appl. Comput. Harmon. Anal. 1 (1993) 100–115. · Zbl 0796.62083
[11] D.L. Donoho, CART and best-ortho-basis: A connection, Preprint (1995) 1–45.
[12] M. Donahue, L. Gurvits, C. Darken and E. Sontag, Rate of convex approximation in non-Hilbert spaces, Constr. Approx. 13 (1997) 187–220. · Zbl 0876.41016
[13] V.V. Dubinin, Greedy algorithms and applications, Ph.D. Thesis, University of South Carolina (1997). · Zbl 0932.31002
[14] J.H. Friedman and W. Stuetzle, Projection pursuit regression, J. Amer. Statist. Assoc. 76 (1981) 817–823.
[15] R. Gribonval and M. Nielsen, Some remarks on non-linear approximation with Schauder bases, East J. Approx. 7 (2001) 267–285. · Zbl 1090.41510
[16] P.J. Huber, Projection pursuit, Ann. Statist. 13 (1985) 435–475. · Zbl 0595.62059
[17] L. Jones, On a conjecture of Huber concerning the convergence of projection pursuit regression, Ann. Statist. 15 (1987) 880–882. · Zbl 0664.62061
[18] L. Jones, A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training, Ann. Statist. 20 (1992) 608–613. · Zbl 0746.62060
[19] A. Kamont and V.N. Temlyakov, Greedy approximation and the multivariate Haar system, IMI-Preprint Series 20 (2002) 1–24.
[20] B.S. Kashin and V.N. Temlyakov, On best m-terms approximations and the entropy of sets in the space L1, Math. Notes 56 (1994) 57–86. · Zbl 0836.41008
[21] B.S. Kashin and V.N. Temlyakov, On estimating approximative characteristics of classes of functions with bounded mixed derivative, Math. Notes 58 (1995) 922–925. · Zbl 0878.46023
[22] G. Kerkyacharian and D. Picard, Entropy, universal coding, approximation and bases properties, University of Paris 6 and 7, Preprint 663 (2001) 1–32. · Zbl 1055.41015
[23] S.V. Konyagin and V.N. Temlyakov, A remark on greedy approximation in Banach spaces, East J. Approx. 5 (1999) 1–15. · Zbl 1084.46509
[24] S.V. Konyagin and V.N. Temlyakov, Rate of convergence of pure greedy algorithm, East J. Approx. 5 (1999) 493–499. · Zbl 1101.41309
[25] S.V. Konyagin and V.N. Temlyakov, Convergence of greedy approximation I. General systems, IMI-Preprint Series 08 (2002) 1–19.
[26] S.V. Konyagin and V.N. Temlyakov, Convergence of greedy approximation II. The trigonometric system, IMI-Preprint Series 09 (2002) 1–25.
[27] S.V. Konyagin and V.N. Temlyakov, Greedy approximation with regard to bases and general minimal systems, Serdica Math. J. 28 (2002) 305–328. · Zbl 1040.41008
[28] E.D. Livshitz, On the rate of convergence of greedy algorithm, Manuscript (2000).
[29] E.D. Livshitz and V.N. Temlyakov, On convergence of weak greedy algorithms, IMI-Preprint 13 (2000) 1–9. · Zbl 1003.65011
[30] A. Lutoborski and V.N. Temlyakov, Vector greedy algorithms, J. Complexity 19 (2003) 458–473. · Zbl 1234.41024
[31] P. Oswald, Greedy algorithms and best m-term approximation with respect to biorthogonal systems, Preprint (2000) 1–22.
[32] L. Rejtö and G.G. Walter, Remarks on projection pursuit regression and density estimation, Stochastic Anal. Appl. 10 (1992) 213–222. · Zbl 0763.62034
[33] E. Schmidt, Zur Theorie der linearen und nichtlinearen Integralgleichungen. I, Math. Ann. 63 (1906–1907) 433–476. · JFM 38.0377.02
[34] V.N. Temlyakov, Greedy algorithm and m-term trigonometric approximation, Constr. Approx. 14 (1998) 569–587. · Zbl 0931.42002
[35] V.N. Temlyakov, The best m-term approximation and greedy algorithms, Adv. Comput. Math. 8 (1998) 249–265. · Zbl 0905.65063
[36] V.N. Temlyakov, Nonlinear m-term approximation with regard to the multivariate Haar system, East J. Approx. 4 (1998) 87–106. · Zbl 0978.41017
[37] V.N. Temlyakov, Greedy algorithms and m-term approximation with regard to redundant dictionaries, J. Approx. Theory 98 (1999) 117–145. · Zbl 0926.65050
[38] V.N. Temlyakov, Greedy algorithms with regard to the multivariate systems with a special structure, Constr. Approx. 16 (2000) 399–425. · Zbl 0962.41007
[39] V.N. Temlyakov, Weak greedy algorithms, Adv. Comput. Math. 12 (2000) 213–227. · Zbl 0964.65009
[40] V.N. Temlyakov, A criterion for convergence of weak greedy algorithms, Adv. Comput. Math. 17 (2002) 269–280. · Zbl 1128.41309
[41] V.N. Temlyakov, Two lower estimates in greedy approximation, IMI-Preprint Series 07 (2001) 1–12.
[42] V.N. Temlyakov, Nonlinear methods of approximation, IMI-Preprint Series 09 (2001) 1–57.
[43] P. Wojtaszczyk, Greedy algorithms for general systems, J. Approx. Theory 107 (2000) 293–314. · Zbl 0974.65053
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.