Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Optimal $ N$-term approximation by linear splines over anisotropic Delaunay triangulations


Authors: Laurent Demaret and Armin Iske
Journal: Math. Comp. 84 (2015), 1241-1264
MSC (2010): Primary 41A25, 42C40; Secondary 68U10, 94A08
DOI: https://doi.org/10.1090/S0025-5718-2014-02908-6
Published electronically: October 17, 2014
MathSciNet review: 3315507
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Anisotropic triangulations provide efficient geometrical methods for sparse representations of bivariate functions from discrete data, in particular from image data. In previous work, we have proposed a locally adaptive method for efficient image approximation, called adaptive thinning, which relies on linear splines over anisotropic Delaunay triangulations. In this paper, we prove asymptotically optimal $ N$-term approximation rates for linear splines over anisotropic Delaunay triangulations, where our analysis applies to relevant classes of target functions: (a) piecewise linear horizon functions across $ \alpha $-Hölder smooth boundaries, (b) functions of $ W^{\alpha ,p}$ regularity, where $ \alpha > 2/p-1$, (c) piecewise regular horizon functions of $ W^{\alpha ,2}$ regularity, where $ \alpha > 1$.


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

  • [1] Robert A. Adams and John J. F. Fournier, Sobolev Spaces, 2nd ed., Pure and Applied Mathematics (Amsterdam), vol. 140, Elsevier/Academic Press, Amsterdam, 2003. MR 2424078 (2009e:46025)
  • [2] 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 (2009b:94007), https://doi.org/10.1016/j.acha.2007.06.009
  • [3] C. Benett and R. Sharpley: Interpolation of Operators, Academic Press, 1998.
  • [4] M. Š. Birman and M. Z. Solomjak, Piecewise polynomial approximations of functions of classes $ W_{p}^{\alpha }$, Mat. Sb. (N.S.) 73 (115) (1967), 331-355 (Russian). MR 0217487 (36 #576)
  • [5] S. Bougleux, G. Peyré, and L. Cohen, Image compression with anisotropic geodesic triangulations, Proceedings of ICCV'09, Oct. 2009.
  • [6] Emmanuel Candès, Laurent Demanet, David Donoho, and Lexing Ying, Fast discrete curvelet transforms, Multiscale Model. Simul. 5 (2006), no. 3, 861-899. MR 2257238 (2007h:65161), https://doi.org/10.1137/05064182X
  • [7] Emmanuel J. Candès and David L. Donoho, New tight frames of curvelets and optimal representations of objects with piecewise $ C^2$ singularities, Comm. Pure Appl. Math. 57 (2004), no. 2, 219-266. MR 2012649 (2004k:42052), https://doi.org/10.1002/cpa.10116
  • [8] Albert Cohen, Nira Dyn, Frédéric Hecht, and Jean-Marie Mirebeau, Adaptive multiresolution analysis based on anisotropic triangulations, Math. Comp. 81 (2012), no. 278, 789-810. MR 2869037 (2012j:94051), https://doi.org/10.1090/S0025-5718-2011-02495-6
  • [9] Jean-Marie Mirebeau and Albert Cohen, Greedy bisection generates optimally adapted triangulations, Math. Comp. 81 (2012), no. 278, 811-837. MR 2869038, https://doi.org/10.1090/S0025-5718-2011-02459-2
  • [10] 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 (2006g:41037), https://doi.org/10.1137/040604649
  • [11] L. Demaret, N. Dyn, and A. Iske, Image compression by linear splines over adaptive triangulations, Signal Processing Journal 86(7), July 2006, 1604-1616.
  • [12] Laurent Demaret and Armin Iske, Anisotropic triangulation methods in adaptive image approximation, Approximation algorithms for complex systems, Springer Proc. Math., vol. 3, Springer, Heidelberg, 2011, pp. 47-68. MR 3026158, https://doi.org/10.1007/978-3-642-16876-5_3
  • [13] L. Demaret and A. Iske, Adaptive image approximation by linear splines, over locally optimal Delaunay triangulations, IEEE Signal Processing Letters 13(5), May 2006, 281-284.
  • [14] Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51-150. MR 1689432 (2001a:41034), https://doi.org/10.1017/S0962492900002816
  • [15] Ronald A. DeVore, Björn Jawerth, and Bradley J. Lucier, Image compression through wavelet transform coding, IEEE Trans. Inform. Theory 38 (1992), no. 2, 719-746. MR 1162221 (97h:68139), https://doi.org/10.1109/18.119733
  • [16] M.N. Do and M. Vetterli, The contourlet transform: an efficient directional multiresolution image representation, IEEE Transactions on Image Processing 14(12), December 2005, 2091-2106.
  • [17] David L. Donoho, Wedgelets: nearly minimax estimation of edges, Ann. Statist. 27 (1999), no. 3, 859-897. MR 1724034 (2001g:62026), https://doi.org/10.1214/aos/1018031261
  • [18] D. L. Donoho, Sparse components of images and optimal atomic decompositions, Constr. Approx. 17 (2001), no. 3, 353-382. MR 1828917 (2002i:94003), https://doi.org/10.1007/s003650010032
  • [19] Herbert Edelsbrunner and Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, (Urbana, IL, 1988) ACM, New York, 1988, pp. 118-133. MR 1213465, https://doi.org/10.1145/73393.73406
  • [20] D. E. Edmunds and H. Triebel, Function Spaces, Entropy Numbers, Differential Operators, Cambridge Tracts in Mathematics, vol. 120, Cambridge University Press, Cambridge, 1996. MR 1410258 (97h:46045)
  • [21] Kanghui Guo and Demetrio Labate, Optimally sparse multidimensional representation using shearlets, SIAM J. Math. Anal. 39 (2007), no. 1, 298-318. MR 2318387 (2008k:42097), https://doi.org/10.1137/060649781
  • [22] Kanghui Guo, Demetrio Labate, Wang-Q Lim, Guido Weiss, and Edward Wilson, Wavelets with composite dilations, Electron. Res. Announc. Amer. Math. Soc. 10 (2004), 78-87 (electronic). MR 2075899 (2005e:42119), https://doi.org/10.1090/S1079-6762-04-00132-5
  • [23] Laurent Jacques and Jean-Pierre Antoine, Multiselective pyramidal decomposition of images: wavelets with adaptive angular selectivity, Int. J. Wavelets Multiresolut. Inf. Process. 5 (2007), no. 5, 785-814. MR 2445428 (2009e:42078), https://doi.org/10.1142/S0219691307002051
  • [24] A. P. Korostelëv and A. B. Tsybakov, Minimax Theory of Image Reconstruction, Lecture Notes in Statistics, vol. 82, Springer-Verlag, New York, 1993. MR 1226450 (95a:62028)
  • [25] B. Lehner, G. Umlauf, and B. Hamann, Image compression using data-dependent triangulations, In: Advances in Visual Computing, G. Bebis et al. (eds.), Springer, LNCS 4841, 2007, 351-362.
  • [26] E. Le Pennec and S. Mallat, Bandelet image approximation and compression, Multiscale Model. Simul. 4 (2005), no. 3, 992-1039 (electronic). MR 2203949 (2006k:42082), https://doi.org/10.1137/040619454
  • [27] Stéphane Mallat, A Wavelet Tour of Signal Processing, Academic Press Inc., San Diego, CA, 1998. MR 1614527 (99m:94012)
  • [28] Stéphane Mallat, Geometrical grouplets, Appl. Comput. Harmon. Anal. 26 (2009), no. 2, 161-180. MR 2490212 (2010a:42148), https://doi.org/10.1016/j.acha.2008.03.004
  • [29] Gerlind Plonka, The easy path wavelet transform: a new adaptive wavelet transform for sparse representation of two-dimensional data, Multiscale Model. Simul. 7 (2008), no. 3, 1474-1496. MR 2496710 (2010d:65394), https://doi.org/10.1137/080719248
  • [30] Duncan D.-Y. Po and Minh N. Do, Directional multiscale modeling of images using the contourlet transform, IEEE Trans. Image Process. 15 (2006), no. 6, 1610-1620. MR 2478998, https://doi.org/10.1109/TIP.2006.873450
  • [31] Franco P. Preparata and Michael Ian Shamos, Computational Geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR 805539 (87d:68102)
  • [32] Rahul Shukla, Pier Luigi Dragotti, Minh N. Do, and Martin Vetterli, Rate-distortion optimized tree-structured compression algorithms for piecewise polynomial images, IEEE Trans. Image Process. 14 (2005), no. 3, 343-359. MR 2120667, https://doi.org/10.1109/TIP.2004.840710
  • [33] M.B. Wakin, J.K. Romberg, H. Choi, and R.G. Baraniuk, Wavelet-domain approximation and compression of piecewise smooth images, IEEE Trans. Image Process. 15, 2006, 1071-108.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 41A25, 42C40, 68U10, 94A08

Retrieve articles in all journals with MSC (2010): 41A25, 42C40, 68U10, 94A08


Additional Information

Laurent Demaret
Affiliation: German Research Center for Environmental Health, Institute of Computational Biology, Ingolstädter Landstrasse 1, 85764 Neuherberg, Germany
Email: laurent.demaret@helmholtz-muenchen.de

Armin Iske
Affiliation: Department of Mathematics, University of Hamburg, Bundesstrasse 55, 20146 Hamburg, Germany
Email: iske@math.uni-hamburg.de

DOI: https://doi.org/10.1090/S0025-5718-2014-02908-6
Received by editor(s): March 28, 2012
Received by editor(s) in revised form: August 22, 2013
Published electronically: October 17, 2014
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society