Adaptive multiresolution analysis based on anisotropic triangulations

Cohen, Albert; Dyn, Nira; Hecht, Frédéric; Mirebeau, Jean-Marie

doi:10.1090/S0025-5718-2011-02495-6

Adaptive multiresolution analysis based on anisotropic triangulations
HTML articles powered by AMS MathViewer

by Albert Cohen, Nira Dyn, Frédéric Hecht and Jean-Marie Mirebeau PDF

Math. Comp. 81 (2012), 789-810 Request permission

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

Francesc Arandiga, Albert Cohen, Rosa Donat, Nira Dyn, and Basarab Matei, Approximation of piecewise smooth functions and images by edge-adapted (ENO-EA) nonlinear multiresolution techniques, Appl. Comput. Harmon. Anal. 24 (2008), no. 2, 225–250. MR 2393984, DOI 10.1016/j.acha.2007.06.009
Bradley K. Alpert, A class of bases in $L^2$ for the sparse representation of integral operators, SIAM J. Math. Anal. 24 (1993), no. 1, 246–262. MR 1199538, DOI 10.1137/0524016
Thomas Apel, Anisotropic finite elements: local estimates and applications, Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1999. MR 1716824
Vladislav Babenko, Yuliya Babenko, Anatoliy Ligun, and Alexander Shumeiko, On asymptotical behavior of the optimal linear spline interpolation error of $C^2$ functions, East J. Approx. 12 (2006), no. 1, 71–101. MR 2294672
Peter Binev, Wolfgang Dahmen, and Ron DeVore, Adaptive finite element methods with convergence rates, Numer. Math. 97 (2004), no. 2, 219–268. MR 2050077, DOI 10.1007/s00211-003-0492-7
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.
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.
Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone, Classification and regression trees, Wadsworth Statistics/Probability Series, Wadsworth Advanced Books and Software, Belmont, CA, 1984. MR 726392
Emmanuel J. Candès and David L. Donoho, Curvelets and curvilinear integrals, J. Approx. Theory 113 (2001), no. 1, 59–90. MR 1866248, DOI 10.1006/jath.2001.3624
Long Chen, Pengtao Sun, and Jinchao Xu, Optimal anisotropic meshes for minimizing interpolation errors in $L^p$-norm, Math. Comp. 76 (2007), no. 257, 179–204. MR 2261017, DOI 10.1090/S0025-5718-06-01896-5
Albert Cohen, Wolfgang Dahmen, Ingrid Daubechies, and Ronald DeVore, Tree approximation and optimal encoding, Appl. Comput. Harmon. Anal. 11 (2001), no. 2, 192–226. MR 1848303, DOI 10.1006/acha.2001.0336
A. Cohen and J.M. Mirebeau, Greedy bisection generates optimally adapted triangulations, Math. of Comp. 81, 811-837, 2012.
S. Dekel and D. Leviatan, Adaptive multivariate approximation using binary space partitions and geometric wavelets, SIAM J. Numer. Anal. 43 (2005), no. 2, 707–732. MR 2177887, DOI 10.1137/040604649
Laurent Demaret, Nira Dyn, Michael S. Floater, and Armin Iske, Adaptive thinning for terrain modelling and image compression, Advances in multiresolution for geometric modelling, Math. Vis., Springer, Berlin, 2005, pp. 319–338. MR 2112359, DOI 10.1007/3-540-26808-1_{1}8
David L. Donoho, Wedgelets: nearly minimax estimation of edges, Ann. Statist. 27 (1999), no. 3, 859–897. MR 1724034, DOI 10.1214/aos/1018031261
David L. Donoho, CART and best-ortho-basis: a connection, Ann. Statist. 25 (1997), no. 5, 1870–1911. MR 1474073, DOI 10.1214/aos/1069362377
Willy Dörfler, A convergent adaptive algorithm for Poisson’s equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106–1124. MR 1393904, DOI 10.1137/0733054
Borislav Karaivanov and Pencho Petrushev, Nonlinear piecewise polynomial approximation beyond Besov spaces, Appl. Comput. Harmon. Anal. 15 (2003), no. 3, 177–223. MR 2010943, DOI 10.1016/j.acha.2003.08.002
B. S. Kashin and A. A. Saakyan, Orthogonal series, Translations of Mathematical Monographs, vol. 75, American Mathematical Society, Providence, RI, 1989. Translated from the Russian by Ralph P. Boas; Translation edited by Ben Silver. MR 1007141, DOI 10.1090/mmono/075
E. Le Pennec and S. Mallat, Bandelet image approximation and compression, Multiscale Model. Simul. 4 (2005), no. 3, 992–1039. MR 2203949, DOI 10.1137/040619454
Pedro Morin, Ricardo H. Nochetto, and Kunibert G. Siebert, Convergence of adaptive finite element methods, SIAM Rev. 44 (2002), no. 4, 631–658 (2003). Revised reprint of “Data oscillation and convergence of adaptive FEM” [SIAM J. Numer. Anal. 38 (2000), no. 2, 466–488 (electronic); MR1770058 (2001g:65157)]. MR 1980447, DOI 10.1137/S0036144502409093
Rob Stevenson, An optimal adaptive finite element method, SIAM J. Numer. Anal. 42 (2005), no. 5, 2188–2217. MR 2139244, DOI 10.1137/S0036142903425082
R. Verfurth, A review of a posteriori error estimation and adaptive mesh-refinement techniques, Wiley-Teubner, 1996.