We discuss the performances of greedy algorithms for two problems of numerical approximation. The first one is the best approximation of an arbitrary function by an N-terms linear combination of simple functions adaptively picked within a large dictionary. The second one is the approximation of an arbitrary function by a piecewise polynomial function on an optimally adapted triangulation of cardinality N. Performance is measured in terms of convergence rate with respect to the number of element in the dictionary in the first case and of triangles in the second case.
@article{BUMI_2009_9_2_2_391_0,
author = {Albert Cohen},
title = {Greedy Algorithms for Adaptive Approximation},
journal = {Bollettino dell'Unione Matematica Italiana},
volume = {2},
year = {2009},
pages = {391-402},
zbl = {1171.65009},
mrnumber = {2537277},
language = {en},
url = {http://dml.mathdoc.fr/item/BUMI_2009_9_2_2_391_0}
}
Cohen, Albert. Greedy Algorithms for Adaptive Approximation. Bollettino dell'Unione Matematica Italiana, Tome 2 (2009) pp. 391-402. http://gdmltest.u-ga.fr/item/BUMI_2009_9_2_2_391_0/
[1] - - - , On Asymptotical Behavior of the Optimal Linear Spline Interpolation Error of Functions, East J. Approx., 12(1) (2006), 71-101. | MR 2294672
[2] , Universal approximation bounds for superposition of n sigmoidal functions, IEEE Trans. Inf. Theory39 (1993), 930-945. | MR 1237720 | Zbl 0818.68126
[3] - - - , Approximation and learning by greedy algorithms, to appear in Annals of Statistics (2007). | MR 2387964
[4] - , Interpolation spaces, Springer Verlag, Berlin, 1976.
[5] - - , Adaptive Finite Element Methods with Convergence Rates, Numerische Mathematik 97 (2004), 219-268. | MR 2050077 | Zbl 1063.65120
[6] - - - - , Mesh generation and mesh adaptivity: theory, techniques, in Encyclopedia of computational mechanics, , and ed., John Wiley & Sons Ltd., 2004. | MR 2288277
[7] - - , Optimal anisotropic meshes for minimizing interpolation error in -norm, Math. of Comp., 76 (2007), 179-204. | MR 2261017 | Zbl 1106.41013
[8] - - - , Tree-structured approximation and optimal encoding, App. Comp. Harm. Anal., 11 (2001), 192-226. | MR 1848303 | Zbl 0992.65151
[9] - - - , Adaptive multiresolution analysis based on anisotropic triangulations, preprint, Laboratoire J.-L. Lions, 2008. | MR 3474490
[10] - , Greedy bisection generates optimally adapted triangulations, preprint, Laboratoire J.-L. Lions, 2008. | MR 2869038 | Zbl 1252.65043
[11] , Nonlinear approximation, Acta Numerica (1997), 51-150. | MR 1689432
[12] - , Some remarks on greedy algorithms, Advances in Computational Mathematics, 5 (1998), 173-187. | MR 1399379 | Zbl 0857.65016
[13] , A convergent adaptive algorithm for Poisson's equation, SIAM J. Numer. Anal., 33 (1996), 1106-1124. | MR 1393904 | Zbl 0854.65090
[14] - , Signal recovery from random measurements via Orthogonal Matching Pursuit, IEEE Trans. Info. Theory, 53 (2007), 4655-4666. | MR 2446929 | Zbl 1288.94022
[15] , A simple lemma on greedy approximation in Hilbert spaces and convergence rates for projection pursuit regression and neural network training, Ann. Stat., 20 (1992), 608-613. | MR 1150368 | Zbl 0746.62060
[16] - , Rate of convergence of Pure greedy Algorithm, East J. Approx. 5 (1999), 493-499. | MR 1738484 | Zbl 1101.41309
[17] - , Two lower estimates in greedy approximation, Constr. Approx., 19 (2003), 509-524. | MR 1998902 | Zbl 1044.41010
[18] - - , Convergence of adaptive finite element methods, SIAM Review, 44 (2002), 631-658. | MR 1980447 | Zbl 1016.65074
[19] , Nonlinear methods of approximation, Journal of FOCM, 3 (2003), 33-107. | MR 1951502 | Zbl 1039.41012
[20] , Greedy algorithms, to appear in Acta Numerica.
[21] , A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques, Wiley-Teubner, 1996. | Zbl 0853.65108