×

Adaptive multiresolution analysis based on anisotropic triangulations. (English) Zbl 1242.65293

This interesting paper continues the research of J.-M. Mirebeau and A. Cohen [ibid. 81, No. 278, 811–837 (2012; Zbl 1252.65043)]. The authors study a greedy refinement procedure for the generation of data-adapted triangulations. Let \(f\in L^p(\Omega)\) \((1\leq p\leq \infty)\) be a given bivariate function. Then the algorithm produces a hierarchy of triangulations \({\mathcal D}_j\) (\(j=0,1,\ldots\)) of \(\Omega\) and piecewise polynomial approximations of \(f\) on these triangulations. Starting from an initial triangulation \({\mathcal D}_0\) of \(\Omega\), the procedure bisects every triangle from one of its vertices to the mid-point of the opposite segment. The choice of the vertex is typically the one which minimizes the new approximation error after bisection among the three options. Thus the data-adapted triangulations are anisotropic (i.e., without any constraints on the size and shape of the triangles).
The hierarchical structure of the triangulations allows 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. The \(L^p\)-convergence of all these approximations is shown. For \(p=2\), the authors present numerical tests for piecewise linear approximations of special functions and a numerical image.

MSC:

65T60 Numerical methods for wavelets
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65M55 Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
65D07 Numerical computation using splines
41A15 Spline approximation
41A63 Multidimensional problems
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Citations:

Zbl 1252.65043
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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. · Zbl 1168.68592 · doi:10.1016/j.acha.2007.06.009
[2] Bradley K. Alpert, A class of bases in \?² for the sparse representation of integral operators, SIAM J. Math. Anal. 24 (1993), no. 1, 246 – 262. · Zbl 0764.42017 · doi:10.1137/0524016
[3] Thomas Apel, Anisotropic finite elements: local estimates and applications, Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1999. · Zbl 0917.65090
[4] Vladislav Babenko, Yuliya Babenko, Anatoliy Ligun, and Alexander Shumeiko, On asymptotical behavior of the optimal linear spline interpolation error of \?² functions, East J. Approx. 12 (2006), no. 1, 71 – 101.
[5] Peter Binev, Wolfgang Dahmen, and Ron DeVore, Adaptive finite element methods with convergence rates, Numer. Math. 97 (2004), no. 2, 219 – 268. · Zbl 1063.65120 · doi:10.1007/s00211-003-0492-7
[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] 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. · Zbl 0541.62042
[9] Emmanuel J. Candès and David L. Donoho, Curvelets and curvilinear integrals, J. Approx. Theory 113 (2001), no. 1, 59 – 90. · Zbl 0989.42020 · doi:10.1006/jath.2001.3624
[10] Long Chen, Pengtao Sun, and Jinchao Xu, Optimal anisotropic meshes for minimizing interpolation errors in \?^{\?}-norm, Math. Comp. 76 (2007), no. 257, 179 – 204. · Zbl 1106.41013
[11] Albert Cohen, Wolfgang Dahmen, Ingrid Daubechies, and Ronald DeVore, Tree approximation and optimal encoding, Appl. Comput. Harmon. Anal. 11 (2001), no. 2, 192 – 226. · Zbl 0992.65151 · doi:10.1006/acha.2001.0336
[12] A. Cohen and J.M. Mirebeau, Greedy bisection generates optimally adapted triangulations, Math. of Comp. 81 (2012), no. 278, 811-837. · Zbl 1252.65043
[13] 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. · Zbl 1089.41011 · doi:10.1137/040604649
[14] 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. · Zbl 1066.94504 · doi:10.1007/3-540-26808-1_18
[15] David L. Donoho, Wedgelets: nearly minimax estimation of edges, Ann. Statist. 27 (1999), no. 3, 859 – 897. · Zbl 0957.62029 · doi:10.1214/aos/1018031261
[16] David L. Donoho, CART and best-ortho-basis: a connection, Ann. Statist. 25 (1997), no. 5, 1870 – 1911. · Zbl 0942.62044 · doi:10.1214/aos/1069362377
[17] Willy Dörfler, A convergent adaptive algorithm for Poisson’s equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106 – 1124. · Zbl 0854.65090 · doi:10.1137/0733054
[18] Borislav Karaivanov and Pencho Petrushev, Nonlinear piecewise polynomial approximation beyond Besov spaces, Appl. Comput. Harmon. Anal. 15 (2003), no. 3, 177 – 223. · Zbl 1032.41018 · doi:10.1016/j.acha.2003.08.002
[19] 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. · Zbl 0668.42011
[20] E. Le Pennec and S. Mallat, Bandelet image approximation and compression, Multiscale Model. Simul. 4 (2005), no. 3, 992 – 1039. · Zbl 1091.94006 · doi:10.1137/040619454
[21] 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)]. · Zbl 1016.65074 · doi:10.1137/S0036144502409093
[22] Rob Stevenson, An optimal adaptive finite element method, SIAM J. Numer. Anal. 42 (2005), no. 5, 2188 – 2217. · Zbl 1081.65112 · doi:10.1137/S0036142903425082
[23] R. Verfurth, A review of a posteriori error estimation and adaptive mesh-refinement techniques, Wiley-Teubner, 1996. · Zbl 1189.76394
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.