Optimal 𝑁-term approximation by linear splines over anisotropic Delaunay triangulations

Demaret, Laurent; Iske, Armin

doi:10.1090/S0025-5718-2014-02908-6

Optimal $N$-term approximation by linear splines over anisotropic Delaunay triangulations
HTML articles powered by AMS MathViewer

by Laurent Demaret and Armin Iske PDF

Math. Comp. 84 (2015), 1241-1264 Request permission

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

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
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
C. Benett and R. Sharpley: Interpolation of Operators, Academic Press, 1998.
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
S. Bougleux, G. Peyré, and L. Cohen, Image compression with anisotropic geodesic triangulations, Proceedings of ICCV’09, Oct. 2009.
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, DOI 10.1137/05064182X
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, DOI 10.1002/cpa.10116
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, DOI 10.1090/S0025-5718-2011-02495-6
Jean-Marie Mirebeau and Albert Cohen, Greedy bisection generates optimally adapted triangulations, Math. Comp. 81 (2012), no. 278, 811–837. MR 2869038, DOI 10.1090/S0025-5718-2011-02459-2
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
L. Demaret, N. Dyn, and A. Iske, Image compression by linear splines over adaptive triangulations, Signal Processing Journal 86(7), July 2006, 1604–1616.
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, DOI 10.1007/978-3-642-16876-5_{3}
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.
Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51–150. MR 1689432, DOI 10.1017/S0962492900002816
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, DOI 10.1109/18.119733
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.
David L. Donoho, Wedgelets: nearly minimax estimation of edges, Ann. Statist. 27 (1999), no. 3, 859–897. MR 1724034, DOI 10.1214/aos/1018031261
D. L. Donoho, Sparse components of images and optimal atomic decompositions, Constr. Approx. 17 (2001), no. 3, 353–382. MR 1828917, DOI 10.1007/s003650010032
Herbert Edelsbrunner and Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Proceedings of the Fourth Annual Symposium on Computational Geometry (Urbana, IL, 1988) ACM, New York, 1988, pp. 118–133. MR 1213465, DOI 10.1145/73393.73406
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, DOI 10.1017/CBO9780511662201
Kanghui Guo and Demetrio Labate, Optimally sparse multidimensional representation using shearlets, SIAM J. Math. Anal. 39 (2007), no. 1, 298–318. MR 2318387, DOI 10.1137/060649781
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. MR 2075899, DOI 10.1090/S1079-6762-04-00132-5
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, DOI 10.1142/S0219691307002051
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, DOI 10.1007/978-1-4612-2712-0
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.
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
Stéphane Mallat, A wavelet tour of signal processing, Academic Press, Inc., San Diego, CA, 1998. MR 1614527
Stéphane Mallat, Geometrical grouplets, Appl. Comput. Harmon. Anal. 26 (2009), no. 2, 161–180. MR 2490212, DOI 10.1016/j.acha.2008.03.004
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, DOI 10.1137/080719248
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, DOI 10.1109/TIP.2006.873450
Franco P. Preparata and Michael Ian Shamos, Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR 805539, DOI 10.1007/978-1-4612-1098-6
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, DOI 10.1109/TIP.2004.840710
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.