Skip to main content
SpringerLink
Log in

Stability of Nonlinear Subdivision and Multiscale Transforms

  • Published:
Constructive Approximation Aims and scope

Abstract

Extending upon the work of Cohen, Dyn, and Matei (Appl. Comput. Harmon. Anal. 15:89–116, 2003) and of Amat and Liandrat (Appl. Comput. Harmon. Anal. 18:198–206, 2005), we present a new general sufficient condition for the Lipschitz stability of nonlinear subdivision schemes and multiscale transforms in the univariate case. It covers the special cases (weighted essentially nonoscillatory scheme, piecewise polynomial harmonic transform) considered so far but also implies the stability in some new cases (median interpolating transform, power-p schemes, etc.). Although the investigation concentrates on multiscale transforms

$$\bigl\{v^0,d^1,\ldots,d^J\bigr\}\longmapsto v^J,\quad J\ge1,$$

in ℓ ∞(ℤ) given by a stationary recursion of the form

$$v^{j}=Sv^{j-1}+d^{j},\quad j\ge1,$$

involving a nonlinear subdivision operator S acting on ℓ ∞(ℤ), the approach is extendable to other nonlinear multiscale transforms and norms, as well.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Amat, S., Arandiga, F., Cohen, A., Donat, R., Garcia, G., von Oehsen, M.: Data compression with ENO schemes: A case study. Appl. Comput. Harmon. Anal. 11, 273–288 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  2. Amat, S., Donat, R., Liandrat, J., Trillo, J.C.: Analysis of a new nonlinear subdivision scheme applications in image processing. Found. Comput. Math. 6(2), 193–225 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  3. Amat, S., Liandrat, J.: On the stability of the PPH nonlinear multiresolution. Appl. Comput. Harmon. Anal. 18, 198–206 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  4. Baraniuk, R., Janssen, M., Lavu, S.: Multiscale approximation of piecewise smooth two-dimensional functions using normal triangulated meshes. Appl. Comput. Harmon. Anal. 19, 92–130 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  5. Cavaretta, A.S., Dahmen, W., Micchelli, C.A.: Stationary Subdivision, vol. 93. American Mathematical Society, Providence (1991)

    Google Scholar 

  6. Cohen, A., Dyn, N., Matei, B.: Quasilinear subdivision schemes with applications to ENO interpolation. Appl. Comput. Harmon. Anal. 15, 89–116 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  7. Coifman, R.R., Lafon, S.: Diffusion maps. Appl. Comput. Harmon. Anal. 21, 5–30 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  8. Dadourian, K., Liandrat, J.: Analysis of some bivariate non-linear interpolatory subdivision schemes. Numer. Algorithms 48(1–3), 261–278 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  9. Daubechies, I., Runborg, O., Sweldens, W.: Normal multiresolution approximation of curves. Constr. Approx. 20, 399–463 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  10. Donoho, D.L., Yu, T.P.-Y.: Nonlinear pyramid transforms based on median-interpolation. SIAM J. Math. Anal. 31(5), 1030–1061 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  11. Dyn, N.: Subdivision schemes in CAGD. In: Light, W.A. (ed.) Advances in Numerical Analysis, vol. II, pp. 36–104. Oxford University Press, London (1992)

    Google Scholar 

  12. Dyn, N., Grohs, P., Wallner, J.: Approximation order of interpolatory nonlinear subdivision schemes. J. Comput. Appl. Math. 223, 1697–1703 (2010)

    Article  MathSciNet  Google Scholar 

  13. Dyn, N., Levin, D.: Subdivision schemes in geometric modelling. Acta Numer. 11, 73–144 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  14. Floater, M.S., Micchelli, C.A.: Nonlinear stationary subdivision. In: Govil, N.K., Mohapatra, R.N., Nashed, Z., Sharma, A., Szabados, J. (eds.) Approximation Theory: in Memory of A.K. Varma, pp. 209–224. Dekker, New York (1998)

    Google Scholar 

  15. Grohs, P.: Smoothness analysis of subdivision schemes on regular grids by proximity. SIAM J. Numer. Anal. 46, 2169–2182 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  16. Grohs, P.: Smoothness equivalence properties of univariate subdivision schemes and their projection analogues. Numer. Math. 113(2), 163–180 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  17. Guskov, I., Vidimce, K., Sweldens, W., Schröder, P.: Normal meshes. In: Akeley, K. (ed.) Computer Graphics (SIGGRAPH ’00: Proceedings), pp. 95–102. ACM, New York (2000)

    Google Scholar 

  18. Harizanov, S.: Stability of nonlinear multiresolution analysis. PAMM 8(1), 10933–10934 (2008)

    Article  Google Scholar 

  19. Harizanov, S.: Stability of nonlinear subdivision schemes and multiresolutions. Master’s Thesis, Jacobs University Bremen (2008)

  20. Harten, A., Engquist, B., Osher, S., Chakravarthy, S.: Uniformly high order essentially non-oscillatory schemes. J. Comput. Phys. 71, 231–303 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  21. Heijmans, H.J.A.M., Goutsias, J.K.: Nonlinear multiresolution signal decomposition schemes. I. Morphological pyramids. IEEE Trans. Image Process. 9(11), 1862–1876 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  22. Heijmans, H.J.A.M., Goutsias, J.K.: Nonlinear multiresolution signal decomposition schemes. ii. Morphological wavelets. IEEE Trans. Image Process. 9(11), 1897–1913 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  23. Khodakovsky, A., Guskov, I.: Compression of normal meshes. In: Brunnett, G., Hamann, B., Müller, H., Linsen, L. (eds.) Geometric Modeling for Scientific Visualization, pp. 189–207. Springer, Berlin (2003)

    Google Scholar 

  24. Khodakovsky, A., Schröder, P., Sweldens, W.: Progressive geometry compression. In: Akeley, K. (ed.) Computer Graphics (SIGGRAPH ’00: Proceedings), pp. 271–278. ACM, New York (2000)

    Google Scholar 

  25. Kuijt, F., van Damme, R.: Convexity preserving interpolatory subdivision schemes. Constr. Approx. 14, 609–630 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  26. Kuijt, F., van Damme, R.: Stability of subdivision schemes. TW Memorandum 1469, Faculty of Applied Mathematics, University of Twente, The Netherlands (1998)

  27. Kuijt, F., van Damme, R.: Monotonicity preserving interpolatory subdivision schemes. J. Comput. Appl. Math. 101(1–2), 203–229 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  28. Liu, X.-D., Osher, S., Chan, T.: Weighted essentially non-oscillatory schemes. J. Comput. Phys. 115, 200–212 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  29. Marinov, M., Dyn, N., Levin, D.: Geometrically controlled 4-point interpolatory schemes. In: Advances in Multiresolution for Geometric Modelling, pp. 301–317. Springer, Berlin (2004)

    Google Scholar 

  30. Matei, B.: Smoothness characterization and stability in nonlinear multiscale framework: theoretical results. Asymptot. Anal. 41(3–4), 277–309 (2005)

    MATH  MathSciNet  Google Scholar 

  31. Oswald, P.: Smoothness of a nonlinear subdivision scheme. In: Cohen, A., Merrien, J.-L., Schumaker, L.L. (eds.) Curve and Surface Fitting: Saint-Malo 2002, pp. 323–332. Nashboro Press, Brentwood (2003)

    Google Scholar 

  32. Oswald, P.: Smoothness of nonlinear median-interpolation subdivision. Adv. Comput. Math. 20, 401–423 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  33. Serna, S., Marquina, A.: Power ENO methods: a fifth-order accurate weighted power ENO method. J. Comput. Phys. 194, 632–658 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  34. Ur Rahman, I., Drori, I., Stodden, V.C., Donoho, D.L., Schröder, P.: Multiscale representations for manifold-valued data. Multiscale Model. Simul. 4(4), 1201–1232 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  35. Wallner, J.: Smoothness analysis of subdivision schemes by proximity. Constr. Approx. 24, 289–318 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  36. Wallner, J., Dyn, N.: Convergence and C 1 analysis of subdivision schemes on manifolds by proximity. Comput. Aided Geom. Des. 22, 593–622 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  37. Wallner, J., Nava Yazdani, E., Grohs, P.: Smoothness properties of Lie group subdivision schemes. Multiscale Model. Simul. 6, 493–505 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  38. Xie, G., Yu, T.P.-Y.: Smoothness analysis of nonlinear subdivision schemes of homogeneous and affine invariant type. Constr. Approx. 22(2), 219–254 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  39. Xie, G., Yu, T.P.-Y.: Smoothness equivalence properties of manifold-valued data subdivision schemes based on the projection approach. SIAM J. Numer. Anal. 45(3), 1200–1225 (2007)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Jacobs University, SES, Campusring 1, 29759, Bremen, Germany

    S. Harizanov & P. Oswald

Authors
  1. S. Harizanov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. Oswald
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to P. Oswald.

Additional information

Communicated by Wolfgang Dahmen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Harizanov, S., Oswald, P. Stability of Nonlinear Subdivision and Multiscale Transforms. Constr Approx 31, 359–393 (2010). https://doi.org/10.1007/s00365-010-9082-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00365-010-9082-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation