A Necessary and Sufficient Proximity Condition for Smoothness Equivalence of Nonlinear Subdivision Schemes

In the recent literature on subdivision methods for approximation of manifold-valued data, a certain “proximity condition” comparing a nonlinear subdivision scheme to a linear subdivision scheme has proved to be a key analytic tool for analyzing regularity properties of the scheme. This proximity condition is now well known to be a sufficient condition for the nonlinear scheme to inherit the regularity of the corresponding linear scheme (this is called smoothness equivalence). Necessity, however, has remained an open problem. This paper introduces a smooth compatibility condition together with a new proximity condition (the differential proximity condition). The smooth compatibility condition makes precise the relation between nonlinear and linear subdivision schemes. It is shown that under the smooth compatibility condition, the differential proximity condition is both necessary and sufficient for smoothness equivalence. It is shown that the failure of the proximity condition corresponds to the presence of resonance terms in a certain discrete dynamical system derived from the nonlinear scheme. Such resonance terms are then shown to slow down the convergence rate relative to the convergence rate of the corresponding linear scheme. Finally, a super-convergence property of nonlinear subdivision schemes is used to conclude that the slowed decay causes a breakdown of smoothness. The proof of sufficiency relies on certain properties of the Taylor expansion of nonlinear subdivision schemes, which, in addition, explain why the differential proximity condition implies the proximity conditions that appear in previous work.     

On multivariate subdivision schemes with nonnegative finite masks

We study the convergence of multivariate subdivision schemes with nonnegative finite masks. Consequently, the convergence problem for the multivariate subdivision schemes with nonnegative finite masks supported on centered zonotopes is solved. Roughly speaking, the subdivision schemes defined by these masks are always convergent, which gives an answer to a question raised by Cavaretta, Dahmen and Micchelli in 1991.

     

Hermite Subdivision Schemes and Taylor Polynomials

We propose a general study of the convergence of a Hermite subdivision scheme ℋ of degree d>0 in dimension 1. This is done by linking Hermite subdivision schemes and Taylor polynomials and by associating a so-called Taylor subdivision (vector) scheme . The main point of investigation is a spectral condition. If the subdivision scheme of the finite differences of is contractive, then is C ⁰ and ℋ is C ^d . We apply this result to two families of Hermite subdivision schemes. The first one is interpolatory; the second one is a kind of corner cutting. Both of them use the Tchakalov-Obreshkov interpolation polynomial.      

A family of non-oscillatory 6-point interpolatory subdivision schemes

In this paper we propose and analyze a new family of nonlinear subdivision schemes which can be considered non-oscillatory versions of the 6-point Deslauries-Dubuc (DD) interpolatory scheme, just as the Power _p schemes are considered nonlinear non-oscillatory versions of the 4-point DD interpolatory scheme. Their design principle may be related to that of the Power _p schemes and it is based on a weighted analog of the Power _p mean. We prove that the new schemes reproduce exactly polynomials of degree three and stay ’close’ to the 6-point DD scheme in smooth regions. In addition, we prove that the first and second difference schemes are well defined for each member of the family, which allows us to give a simple proof of the uniform convergence of these schemes and also to study their stability as in [19, 22]. However our theoretical study of stability is not conclusive and we perform a series of numerical experiments that seem to point out that only a few members of the new family of schemes are stable. On the other hand, extensive numerical testing reveals that, for smooth data, the approximation order and the regularity of the limit function may be similar to that of the 6-point DD scheme and larger than what is obtained with the Power _p schemes.     

Analysis of some bivariate non-linear interpolatory subdivision schemes

This paper is devoted to the convergence analysis of a class of bivariate subdivision schemes that can be defined as a specific perturbation of a linear subdivision scheme. We study successively the univariate and bivariate case and apply the analysis to the so called Powerp scheme (Serna and Marquina, J Comput Phys 194:632–658, 2004).     

Square root 3 -Subdivision Schemes: Maximal Sum Rule Orders

Abstract. Subdivision with finitely supported masks is an efficient method to create discrete multiscale representations of smooth surfaces for CAGD applications. Recently a new subdivision scheme for triangular meshes, called $\sqrt 3$ -subdivision , has been studied. In comparison to dyadic subdivision, which is based on the dilation matrix 2I , $\sqrt 3$ -subdivision is based on a dilation M with det M=3 . This has certain advantages, for example, a slower growth for the number of control points. This paper concerns the problem of achieving maximal sum rule orders for stationary $\sqrt 3$ -subdivision schemes with given mask support, which is important because the sum rule order characterizes the order of the polynomial reproduction, and provides an upper bound on the Sobolev smoothness of the surface. We study both interpolating and approximating schemes for a natural family of symmetric mask support sets related to squares of sidelength 2n in Z ² , and obtain exact formulas for the maximal sum rule order for arbitrary n . For approximating schemes, the solution is simple, and schemes with maximal sum rule order are realized by an explicit family of schemes based on repeated averaging [15]. In the interpolating case, we use properties of multivariate Lagrange polynomial interpolation to prove the existence of interpolating schemes with maximal sum rule orders. These can be found by solving a linear system which can be reduced in size by using symmetries. From this, we construct some new examples of smooth (C ² ,C ³ ) interpolating $\sqrt 3$ -subdivision schemes with maximal sum rule order and symmetric masks. The construction of associated dual schemes is also discussed.     

Hermite subdivision on manifolds via parallel transport

We propose a new adaption of linear Hermite subdivision schemes to the manifold setting. Our construction is intrinsic, as it is based solely on geodesics and on the parallel transport operator of the manifold. The resulting nonlinear Hermite subdivision schemes are analyzed with respect to convergence and C ¹ smoothness. Similar to previous work on manifold-valued subdivision, this analysis is carried out by proving that a so-called proximity condition is fulfilled. This condition allows to conclude convergence and smoothness properties of the manifold-valued scheme from its linear counterpart, provided that the input data are dense enough. Therefore the main part of this paper is concerned with showing that our nonlinear Hermite scheme is “close enough”, i.e., in proximity, to the linear scheme it is derived from.     

Square root 3 -Subdivision Schemes: Maximal Sum Rule Orders

   Abstract. Subdivision with finitely supported masks is an efficient method to create discrete multiscale representations of smooth surfaces for CAGD applications. Recently a new subdivision scheme for triangular meshes, called

Smoothness Analysis of Nonlinear Subdivision Schemes of Homogeneous and Affine Invariant Type

Nonlinear subdivision schemes arise from, among other applications, nonlinear multiscale signal processing and shape preserving interpolation. For the univariate homogeneous subdivision operator $S:\ell(\bZ) \goto \ell(\bZ)$ we establish a set of commutation/recurrence relations which can be used to analyze the asymptotic decay rate of $\|\Delta^r S^j m\|_{\ell^\infty}$, $j=1,2,\ldots,$ the latter in turn determines the convergence and H\older regularity of $S$. We apply these results to prove that the critical H\older regularity exponent of a nonlinear subdivision scheme based on median-interpolation is equal to that of an approximating linear subdivision scheme, resolving a conjecture by Donoho and Yu. We also consider a family of nonlinear but affine invariant subdivision operators based on interpolation-imputation of $p$-mean (of which median corresponds to the special case $p=1$) as well as general continuous $M$-estimators. We propose a linearization principle which, when applied to $p$-mean subdivision operators, leads to a family of linear subdivision schemes. Numerical evidence indicates that in at least many cases the critical smoothness of a $p$-mean subdivision scheme is the same as that of the corresponding linear scheme. This suggests a more coherent view of the result obtained in this paper.     

Noninterpolatory Hermite subdivision schemes

Bivariate interpolatory Hermite subdivision schemes have recently been applied to build free-form subdivision surfaces. It is well known to geometric modelling practitioners that interpolatory schemes typically lead to ``unfair" surfaces--surfaces with unwanted wiggles or undulations--and noninterpolatory (a.k.a. approximating in the CAGD community) schemes are much preferred in geometric modelling applications. In this article, we introduce, analyze and construct noninterpolatory Hermite subdivision schemes, a class of vector subdivision schemes which can be applied to iteratively refine Hermite data in a not necessarily interpolatory fashion. We also study symmetry properties of such subdivision schemes which are crucial for application in free-form subdivision surfaces.

A key step in our mathematical analysis of Hermite type subdivision schemes is that we make use of the strong convergence theory of refinement equations to convert a prescribed geometric condition on the subdivision scheme--namely, the subdivision scheme is of Hermite type--to an algebraic condition on the subdivision mask. The latter algebraic condition can then be used in a computational framework to construct specific schemes.

     

Low Regularity Exponential-Type Integrators for Semilinear Schrödinger Equations

We introduce low regularity exponential-type integrators for nonlinear Schrödinger equations for which first-order convergence only requires the boundedness of one additional derivative of the solution. More precisely, we will prove first-order convergence in \(H^r\) for solutions in \(H^{r+1}\) (with \(r > d/2\)) of the derived schemes. This allows us lower regularity assumptions on the data than for instance required for classical splitting or exponential integration schemes. For one-dimensional quadratic Schrödinger equations, we can even prove first-order convergence without any loss of regularity. Numerical experiments underline the favorable error behavior of the newly introduced exponential-type integrators for low regularity solutions compared to classical splitting and exponential integration schemes.     

Smoothing nonlinear subdivision schemes by averaging

In the theory of linear subdivision algorithms, it is well-known that the regularity of a linear subdivision scheme can be elevated by one order (say, from C ^k to C ^k+1) by composing it with an averaging step (equivalently, by multiplying to the subdivision mask a(z) a (1 + z) factor. In this paper, we show that the same can be done to nonlinear subdivision schemes: by composing with it any nonlinear, smooth, 2-point averaging step, the lifted nonlinear subdivision scheme has an extra order of regularity than the original scheme. A notable application of this result shows that the classical Lane-Riesenfeld algorithm for uniform B-Spline, when extended to Riemannian manifolds based on geodesic midpoint, produces curves with the same regularity as their linear counterparts. (In particular, curvature does not obstruct the nonlinear Lane-Riesenfeld algorithm to inherit regularity from the linear algorithm.) Our main result uses the recently developed technique of differential proximity conditions.     

Convergent Vector and Hermite Subdivision Schemes

Hermite subdivision schemes have been studied by Merrien, Dyn, and Levin and they appear to be very different from subdivision schemes analyzed before since the rules depend on the subdivision level. As suggested by Dyn and Levin, it is possible to transform the initial scheme into a uniform stationary vector subdivision scheme which can be handled more easily.With this transformation, the study of convergence of Hermite subdivision schemes is reduced to that of vector stationary subdivision schemes. We propose a first criterion for C⁰-convergence for a large class of vector subdivision schemes. This gives a criterion for C¹-convergence of Hermite subdivision schemes. It can be noticed that these schemes do not have to be interpolatory. We conclude by investigating spectral properties of Hermite schemes and other necessary/sufficient conditions of convergence.     

Analysis of stationary subdivision schemes for curve design based on radial basis function interpolation

This paper provides a large family of interpolatory stationary subdivision schemes based on radial basis functions (RBFs) which are positive definite or conditionally positive definite. A radial basis function considered in this study has a tension parameter λ>0 such that it provides design flexibility. We prove that for a sufficiently large , the proposed 2L-point (L∈N) scheme has the same smoothness as the well-known 2L-point Deslauriers-Dubuc scheme, which is based on 2L-1 degree polynomial interpolation. Some numerical examples are presented to illustrate the performance of the new schemes, adapting subdivision rules on bounded intervals in a way of keeping the same smoothness and accuracy of the pre-existing schemes on R. We observe that, with proper tension parameters, the new scheme can alleviate undesirable artifacts near boundaries, which usually appear to interpolatory schemes with irregularly distributed control points.     

Regularity of multivariate vector subdivision schemes

In this paper we discuss methods for investigating the convergence of multivariate vector subdivision schemes and the regularity of the associated limit functions. Specifically, we consider difference vector subdivision schemes whose restricted contractivity determines the convergence of the original scheme and describes the connection between the regularity of the limit functions of the difference subdivision scheme and the original subdivision scheme.