Greedy Algorithms for Adaptive Approximation

Albert Cohen

Bollettino dell'Unione Matematica Italiana (2009)

  • Volume: 2, Issue: 2, page 391-402
  • ISSN: 0392-4041

Abstract

top
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.

How to cite

top

Cohen, Albert. "Greedy Algorithms for Adaptive Approximation." Bollettino dell'Unione Matematica Italiana 2.2 (2009): 391-402. <http://eudml.org/doc/290592>.

@article{Cohen2009,
abstract = {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.},
author = {Cohen, Albert},
journal = {Bollettino dell'Unione Matematica Italiana},
language = {eng},
month = {6},
number = {2},
pages = {391-402},
publisher = {Unione Matematica Italiana},
title = {Greedy Algorithms for Adaptive Approximation},
url = {http://eudml.org/doc/290592},
volume = {2},
year = {2009},
}

TY - JOUR
AU - Cohen, Albert
TI - Greedy Algorithms for Adaptive Approximation
JO - Bollettino dell'Unione Matematica Italiana
DA - 2009/6//
PB - Unione Matematica Italiana
VL - 2
IS - 2
SP - 391
EP - 402
AB - 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.
LA - eng
UR - http://eudml.org/doc/290592
ER -

References

top
  1. BABENKO, V. - BABENKO, Y. - LIGUN, A. - SHUMEIKO, A., On Asymptotical Behavior of the Optimal Linear Spline Interpolation Error of C 2 Functions, East J. Approx., 12(1) (2006), 71-101. MR2294672
  2. BARRON, A., Universal approximation bounds for superposition of n sigmoidal functions, IEEE Trans. Inf. Theory39 (1993), 930-945. Zbl0818.68126MR1237720DOI10.1109/18.256500
  3. BARRON, A. - COHEN, A. - DAHMEN, W. - DEVORE, R., Approximation and learning by greedy algorithms, to appear in Annals of Statistics (2007). MR2387964DOI10.1214/009053607000000631
  4. BERGH, J. - LÖFSTRÖM, J., Interpolation spaces, Springer Verlag, Berlin, 1976. 
  5. BINEV, P. - DAHMEN, W. - DEVORE, R., Adaptive Finite Element Methods with Convergence Rates, Numerische Mathematik97 (2004), 219-268. Zbl1063.65120MR2050077DOI10.1007/s00211-003-0492-7
  6. BOROUCHAKI, H. - FREY, P. J. - GEORGE, P. L. - LAUG, P. - SALTEL, E., Mesh generation and mesh adaptivity: theory, techniques, in Encyclopedia of computational mechanics, E. Stein, R. de Borst and T. J. R. Hughes ed., John Wiley & Sons Ltd., 2004. MR2288277DOI10.1002/0470091355
  7. CHEN, L. - SUN, P. - XU, J., Optimal anisotropic meshes for minimizing interpolation error in L p -norm, Math. of Comp., 76 (2007), 179-204. Zbl1106.41013MR2261017DOI10.1090/S0025-5718-06-01896-5
  8. COHEN, A. - DAHMEN, W. - DAUBECHIES, I. - DEVORE, R., Tree-structured approximation and optimal encoding, App. Comp. Harm. Anal., 11 (2001), 192-226. Zbl0992.65151MR1848303DOI10.1006/acha.2001.0336
  9. COHEN, A. - DYN, N. - HECHT, F. - MIREBEAU, J. M., Adaptive multiresolution analysis based on anisotropic triangulations, preprint, Laboratoire J.-L. Lions, 2008. MR3474490DOI10.1007/s00211-015-0732-7
  10. COHEN, A. - MIREBEAU, J. M., Greedy bisection generates optimally adapted triangulations, preprint, Laboratoire J.-L. Lions, 2008. Zbl1252.65043MR2869038DOI10.1090/S0025-5718-2011-02459-2
  11. DEVORE, R., Nonlinear approximation, Acta Numerica (1997), 51-150. MR1689432DOI10.1017/S0962492900002816
  12. DEVORE, R. - TEMLYAKOV, V., Some remarks on greedy algorithms, Advances in Computational Mathematics, 5 (1998), 173-187. Zbl0857.65016MR1399379DOI10.1007/BF02124742
  13. DÖRFLER, W., A convergent adaptive algorithm for Poisson's equation, SIAM J. Numer. Anal., 33 (1996), 1106-1124. Zbl0854.65090MR1393904DOI10.1137/0733054
  14. GILBERT, A. C. - TROPP, J. A., Signal recovery from random measurements via Orthogonal Matching Pursuit, IEEE Trans. Info. Theory, 53 (2007), 4655-4666. Zbl1288.94022MR2446929DOI10.1109/TIT.2007.909108
  15. JONES, L. K., 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. Zbl0746.62060MR1150368DOI10.1214/aos/1176348546
  16. KONYAGIN, S. V. - TEMLYAKOV, V. N., Rate of convergence of Pure greedy Algorithm, East J. Approx.5 (1999), 493-499. Zbl1101.41309MR1738484
  17. LIVSHITZ, E. D. - TEMLYAKOV, V. N., Two lower estimates in greedy approximation, Constr. Approx., 19 (2003), 509-524. Zbl1044.41010MR1998902DOI10.1007/s00365-003-0533-6
  18. MORIN, P. - NOCHETTO, R. - SIEBERT, K., Convergence of adaptive finite element methods, SIAM Review, 44 (2002), 631-658. Zbl1016.65074MR1980447DOI10.1137/S0036144502409093
  19. TEMLYAKOV, V., Nonlinear methods of approximation, Journal of FOCM, 3 (2003), 33-107. Zbl1039.41012MR1951502DOI10.1007/s102080010029
  20. TEMLYAKOV, V., Greedy algorithms, to appear in Acta Numerica. 
  21. VERFURTH, R., A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques, Wiley-Teubner, 1996. Zbl0853.65108

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.