Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Adaptive multiresolution analysis based on anisotropic triangulations

Authors: Albert Cohen, Nira Dyn, Frédéric Hecht and Jean-Marie Mirebeau
Journal: Math. Comp. 81 (2012), 789-810
MSC (2010): Primary 65-XX; Secondary 41-XX
Published electronically: September 28, 2011
MathSciNet review: 2869037
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A simple greedy refinement procedure for the generation of data-adapted triangulations is proposed and studied. Given a function $ f$ of two variables, the algorithm produces a hierarchy of triangulations $ (\mathcal {D}_j)_{j\geq 0}$ and piecewise polynomial approximations of $ f$ on these triangulations. The refinement procedure consists in bisecting a triangle $ T$ in a direction which is chosen so as to minimize the local approximation error in some prescribed norm between $ f$ and its piecewise polynomial approximation after $ T$ is bisected. The hierarchical structure allows us to derive various approximation tools such as multiresolution analysis, wavelet bases, adaptive triangulations based either on greedy or optimal CART trees, as well as a simple encoding of the corresponding triangulations. We give a general proof of convergence in the $ L^p$ norm of all these approximations. Numerical tests performed in the case of piecewise linear approximation of functions with analytic expressions or of numerical images illustrate the fact that the refinement procedure generates triangles with an optimal aspect ratio (which is dictated by the local Hessian of $ f$ in the case of $ C^2$ functions).

References [Enhancements On Off] (What's this?)

  • 1. F. Arandiga, A. Cohen, R. Donat, N. Dyn and B. Matei, Approximation of piecewise smooth images by edge-adapted techniques, ACHA 24, 225-250, 2008. MR 2393984 (2009b:94007)
  • 2. B. Alpert, A class of bases in $ L^2$ for the sparse representation of integral operators, SIAM J. Math. Anal. 24, 246-262, 1993. MR 1199538 (93k:65104)
  • 3. T. Apel, Anisotropic finite elements: Local estimates and applications, Series ``Advances in Numerical Mathematics'', Teubner, Stuttgart, 1999. MR 1716824 (2000k:65002)
  • 4. V. Babenko, Y. Babenko, A. Ligun and A. Shumeiko, On asymptotical behavior of the optimal linear spline interpolation error of $ C^2$ functions, East J. Approx. 12(1), 71-101, 2006. MR 2294672 (2007m:41008)
  • 5. P. Binev, W. Dahmen and R. DeVore, Adaptive finite element methods with convergence rates, Numerische Mathematik 97, 219-268, 2004. MR 2050077 (2005d:65222)
  • 6. R. Baraniuk, H. Choi, J. Romberg and M. Wakin, Wavelet-domain approximation and compression of piecewise smooth images, IEEE Transactions on Image Processing, 15(5), 1071-1087, 2006.
  • 7. H. Borouchaki, P.J. Frey, P.L. George, P. Laug and E. Saltel, 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.
  • 8. L. Breiman, J.H. Friedman, R.A. Olshen and C.J. Stone, Classification and regression trees, Wadsworth international, Belmont, CA, 1984. MR 726392 (86b:62101)
  • 9. E. Candes and D. L. Donoho, Curvelets and curvilinear integrals, J. Approx. Theory. 113, 59-90, 2000. MR 1866248 (2002j:41012)
  • 10. L. Chen, P. Sun and J. Xu, Optimal anisotropic meshes for minimizing interpolation error in $ L^p$-norm, Math. of Comp. 76, 179-204, 2007. MR 2261017 (2008e:65385)
  • 11. A. Cohen, W. Dahmen, I. Daubechies and R. DeVore, Tree-structured approximation and optimal encoding, App. Comp. Harm. Anal. 11, 192-226, 2001. MR 1848303 (2002g:42048)
  • 12. A. Cohen and J.M. Mirebeau, Greedy bisection generates optimally adapted triangulations, Math. of Comp. 81 (2012), no. 278, 811-837.
  • 13. S. Dekel and D. Leviathan, Adaptive multivariate approximation using binary space partitions and geometric wavelets, SIAM Journal on Numerical Analysis 43, 707-732, 2005. MR 2177887 (2006g:41037)
  • 14. L. Demaret, N. Dyn, M. Floater and A. Iske, Adaptive thinning for terrain modelling and image compression, in Advances in Multiresolution for Geometric Modelling, N.A. Dodgson, M.S. Floater, and M.A. Sabin (eds.), Springer-Verlag, Heidelberg, 321-340, 2005. MR 2112359
  • 15. D. Donoho, Wedgelets: nearly minimax estimation of edges, Ann. Statist. 27(3), 859-897, 1999. MR 1724034 (2001g:62026)
  • 16. D. Donoho, CART and best basis: a connexion, Ann. Statist. 25(5), 1870-1911, 1997. MR 1474073 (98k:62052)
  • 17. W. Dörfler, A convergent adaptive algorithm for Poisson's equation, SIAM J. Numer. Anal. 33, 1106-1124, 1996. MR 1393904 (97e:65139)
  • 18. B. Karaivanov and P. Petrushev, Nonlinear piecewise polynomial approximation beyond Besov spaces, Appl. Comput. Harmon. Anal. 15(3), 177-223, 2003. MR 2010943 (2005g:41021)
  • 19. B. S. Kashin and A. A. Saakian, Orthogonal series, Amer. Math. Soc., Providence, 1989. MR 1007141 (90g:42001)
  • 20. E. Le Pennec and S. Mallat, Bandelet image approximation and compression, SIAM Journal of Multiscale Modeling. and Simulation, 4(3), 992-1039, 2005. MR 2203949 (2006k:42082)
  • 21. P. Morin, R. Nochetto and K. Siebert, Convergence of adaptive finite element methods, SIAM Review 44, 631-658, 2002. MR 1980447
  • 22. R. Stevenson, An optimal adaptive finite element method, SIAM J. Numer. Anal., 42(5), 2188-2217, 2005. MR 2139244 (2006e:65226)
  • 23. R. Verfurth, A review of a posteriori error estimation and adaptive mesh-refinement techniques, Wiley-Teubner, 1996.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65-XX, 41-XX

Retrieve articles in all journals with MSC (2010): 65-XX, 41-XX

Additional Information

Albert Cohen
Affiliation: Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie, 4, Place Jussieu, 75005 Paris, France

Nira Dyn
Affiliation: School of Mathematics, Tel Aviv University, Ramat Aviv, Israel

Frédéric Hecht
Affiliation: Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie, 4, Place Jussieu, 75005 Paris, France

Jean-Marie Mirebeau
Affiliation: Laboratoire Jacques Louis Lions, Université Pierre et Marie Curie, 4, Place Jussieu, 75005 Paris, France

Received by editor(s): October 20, 2008
Received by editor(s) in revised form: October 20, 2010
Published electronically: September 28, 2011
Additional Notes: This research was supported by the P2R French-Israeli program “Nonlinear multiscale methods—applications to image and terrain data”
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society