×

Vector greedy algorithms. (English) Zbl 1234.41024

A dictionary is a subset \(\mathcal D\) of a Hilbert space \((H,\langle\cdot,\cdot\rangle)\) such that \(\|g\|=1\) for all \(g\in \mathcal D\) and cl-span\((\mathcal D)=H.\) The objective of greedy algorithms is to construct a sequence \(\{g_k\}\) in \(\mathcal D\) and a sequence of approximants \(G_k\in\mathcal D_k=\) span\(\{g_1,\dots,g_k\}\) such that \(\lim_{k\to\infty}\|f-G_k\|=0.\) With the dictionary \(\mathcal D\) one associates a norm defined by \(\|f\|_{\mathcal D}=\sup_{g\in \mathcal D}|\langle f,g\rangle|.\) The construction proceeds inductively by adding to existing \(g_1,\dots,g_n\) an element \(g_{n+1}\in\mathcal D.\) The specific optimization criterium used for constructing \(G_k\) will define specific greedy algorithms. The first two algorithms considered by the authors, the pure greedy algorithm (PGA) and the orthogonal greedy algorithm (OGA), are based on the hypothesis that there exists a selection \(S:H\to\mathcal D\) such that \(\langle f,S(f)\rangle ==\|f\|_{\mathcal D}\). In this case one defines \(G(f)=\langle f,S(f)\rangle S(f)\) and \(R(f)=f-G(f)\).
The PGA is based on the recurrence formulae \(G_m(f)=G_{m-1}(f)+G(R_{m-1}(f)),\, R_m(f):=f-G_m(f)= G(R_{m-1}(f))\). The OGA is defined in a similar way taking \[ H_m(f)=\text{ span}\{G(R^o_0(f)),\dots,G(R^o_{m-1}(f))\},\, G_m^o(f)=P_{H_m}(f) \] (the metric (= orthogonal) projection on \(H_m=H_m(f)\)), and \(R^o(f)=f-G_m^o(f)\).
The authors consider also four greedy algorithms of weak type, where instead of the selection \(S\) one uses elements \(\varphi\in \mathcal D\) such that \(|\langle f,\varphi\rangle|\geq t\|f\|_{\mathcal D},\) for some \(t\in (0,1),\) where \(t\) can be different at each step. They give some necessary and sufficient conditions for the convergence of these algorithms as well as evaluations of the rates of convergence. The obtained results extend some previous results of the second author, see [Adv. Comput. Math. 12, 213–227 (2000; Zbl 0964.65009)], the survey [Acta Numerica 17, 235–409 (2008; Zbl 1178.65050) and the recent book [V. Temlyakov, Greedy approximation. Cambridge Monographs on Applied and Computational Mathematics 20. Cambridge: Cambridge University Press. (2011; Zbl 1279.41001)].

MSC:

41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
41A25 Rate of convergence, degree of approximation
41A45 Approximation by arbitrary linear expressions
65D15 Algorithms for approximation of functions
65J05 General theory of numerical analysis in abstract spaces
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barron, A. R., Universal approximation bounds for superposition of \(n\) sigmoidal functions, IEEE Trans. Inform. Theory, 39, 930-945 (1993) · Zbl 0818.68126
[2] Davis, G.; Mallat, S.; Avellaneda, M., Adaptive greedy approximations, Constr. Approx., 13, 57-98 (1997) · Zbl 0885.41006
[3] R.A. DeVore, Nonlinear approximation, Acta Numer. (1998) 51-150.; R.A. DeVore, Nonlinear approximation, Acta Numer. (1998) 51-150. · Zbl 0931.65007
[4] DeVore, R.; Jawerth, B.; Popov, V., Compression of wavelet decompositions, Amer. J. Math., 114, 737-785 (1992) · Zbl 0764.41024
[5] DeVore, R. A.; Temlyakov, V. N., Nonlinear approximation by trigonometric sums, J. Fourier Anal. Appl., 2, 29-48 (1995) · Zbl 0886.42019
[6] DeVore, R. A.; Temlyakov, V. N., Some remarks on greedy algorithms, Adv. Comput. Math., 5, 173-187 (1996) · Zbl 0857.65016
[7] DeVore, R. A.; Temlyakov, V. N., Nonlinear approximation in finite-dimensional spaces, J. Complexity, 13, 489-508 (1997) · Zbl 0892.41009
[8] Donahue, M.; Gurvits, L.; Darken, C.; Sontag, E., Rate of convex approximation in non-Hilbert spaces, Constr. Approx., 13, 187-220 (1997) · Zbl 0876.41016
[9] Donoho, D. L., Unconditional bases are optimal bases for data compression and for statistical estimation, Appl. Comput. Harmon. Anal., 1, 100-115 (1993) · Zbl 0796.62083
[10] Donoho, D. L., CART and best-ortho-basisa connection, Ann. Statist., 25, 1870-1911 (1997) · Zbl 0942.62044
[11] V.V. Dubinin, Greedy algorithms and applications, Ph.D. Thesis, University of South Carolina, 1997.; V.V. Dubinin, Greedy algorithms and applications, Ph.D. Thesis, University of South Carolina, 1997. · Zbl 0932.31002
[12] Friedman, J. H.; Stuetzle, W., Projection pursuit regression, J. Amer. Statist. Assoc., 76, 817-823 (1981)
[13] Huber, P. J., Projection pursuit, Ann. Statist., 13, 435-475 (1985) · Zbl 0595.62059
[14] Jones, L., On a conjecture of Huber concerning the convergence of projection pursuit regression, Ann. Statist., 15, 880-882 (1987) · Zbl 0664.62061
[15] Jones, L., A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training, Ann. Statist., 20, 608-613 (1992) · Zbl 0746.62060
[16] Kashin, B. S.; Temlyakov, V. N., On best \(m\)-terms approximations and the entropy of sets in the space \(L^1\), Math. Notes, 56, 57-86 (1994) · Zbl 0836.41008
[17] Kashin, B. S.; Temlyakov, V. N., On estimating approximative characteristics of classes of functions with bounded mixed derivative, Math. Notes, 58, 922-925 (1995) · Zbl 0878.46023
[18] Rejtö, L.; Walter, G. G., Remarks on projection pursuit regression and density estimation, Stochastic Anal. Appl., 10, 213-222 (1992) · Zbl 0763.62034
[19] Schmidt, E., Zur Theorie der linearen und nichtlinearen Integralgleichungen. I, Math. Annalen, 63, 433-476 (1906 1907)
[20] Temlyakov, V. N., Greedy algorithm and \(m\)-term trigonometric approximation, Constr. Approx., 14, 569-587 (1998) · Zbl 0931.42002
[21] Temlyakov, V. N., The best \(m\)-term approximation and greedy algorithms, Adv. Comput. Math., 8, 249-265 (1998) · Zbl 0905.65063
[22] Temlyakov, V. N., Nonlinear \(m\)-term approximation with regard to the multivariate Haar system, East J. Approx., 4, 87-106 (1998) · Zbl 0978.41017
[23] V.N. Temlyakov, Greedy algorithms with regard to the multivariate systems with a special structure, preprint, 1998, pp. 1-26.; V.N. Temlyakov, Greedy algorithms with regard to the multivariate systems with a special structure, preprint, 1998, pp. 1-26.
[24] Temlyakov, V. N., Greedy algorithms and \(m\)-term approximation with regard to redundant dictionaries, J. Approx. Theory, 98, 117-145 (1999) · Zbl 0926.65050
[25] Temlyakov, V. N., Weak greedy algorithms, Adv. Comput. Math., 12, 213-227 (2000) · Zbl 0964.65009
[26] Temlyakov, V. N., A criterion for convergence of weak greedy algorithm, Adv. Comput. Math., 17, 269-280 (2002) · Zbl 1128.41309
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.