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.     

Nonlinear Subdivision Schemes on Irregular Meshes

The present article deals with convergence and smoothness analysis of geometric, nonlinear subdivision schemes in the presence of extraordinary points. We discuss when the existence of a proximity condition between a linear scheme and its nonlinear analogue implies convergence of the nonlinear scheme (for dense enough input data). Furthermore, we obtain C ¹ smoothness of the nonlinear limit function in the vicinity of an extraordinary point over Reif’s characteristic parametrization. The results apply to the geometric analogues of well-known subdivision schemes such as Doo–Sabin or Catmull–Clark schemes.     

Stability of Manifold-Valued Subdivision Schemes and Multiscale Transformations

Linear subdivision schemes can be adapted in various ways so as to operate in nonlinear geometries such as Lie groups or Riemannian manifolds. It is well known that along with a linear subdivision scheme a multiscale transformation is defined. Such transformations can also be defined in a nonlinear setting. We show the stability of such nonlinear multiscale transforms. To do this we introduce a new kind of proximity condition which bounds the difference of the differential of a nonlinear subdivision scheme and a linear one. It turns out that—unlike the generic nonlinear case and modulo some minor technical assumptions—in the manifold-valued setting, convergence implies stability of the nonlinear subdivision scheme and associated nonlinear multiscale transformations.     

Smoothness Analysis of Subdivision Schemes by Proximity

Linear curve subdivision schemes may be perturbed in various ways, for example, by modifying them such as to work in a manifold, surface, or group. The analysis of such perturbed and often nonlinear schemes "T" is based on their proximity to the linear schemes "S" which they are derived from. This paper considers two aspects of this problem: One is to find proximity inequalities which together with C^k smoothness of S imply C^k smoothness of T. The other is to verify these proximity inequalities for several ways to construct the nonlinear scheme T analogous to the linear scheme S. The first question is treated for general k, whereas the second one is treated only in the case k = 2. The main result of the paper is that convergent geodesic/projection/Lie group analogues of a certain class of factorizable linear schemes have C² limit curves.     

Invariance property of proximity conditions in nonlinear subdivision

Proximity conditions are used extensively in the analysis of smoothness and approximation order properties of subdivision schemes for manifold-valued data. While these properties under question are independent of choice of coordinates on the manifold, it is not known whether the proximity condition itself is invariant under arbitrary change of coordinates. In this note, we answer this question to the affirmative, i.e. we prove that the proximity condition is satisfied in one coordinate system if and only if it is satisfied in any other coordinate system. In passing, we prove a connection between the general proximity condition and an alternate proximity condition used in the interpolatory case. This interpolatory proximity condition also enjoys the same invariance under change of coordinates.     

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.     

Single Basepoint Subdivision Schemes for Manifold-valued Data: Time-Symmetry Without Space-Symmetry

This paper establishes smoothness results for a class of nonlinear subdivision schemes, known as the single basepoint manifold-valued subdivision schemes, which shows up in the construction of wavelet-like transform for manifold-valued data. This class includes the (single basepoint) Log–Exp subdivision scheme as a special case. In these schemes, the exponential map is replaced by a so-called retraction map f from the tangent bundle of a manifold to the manifold. It is known that any choice of retraction map yields a C ² scheme, provided the underlying linear scheme is C ² (this is called “C ² equivalence”). But when the underlying linear scheme is C ³, Navayazdani and Yu have shown that to guarantee C ³ equivalence, a certain tensor P _f associated to f must vanish. They also show that P _f vanishes when the underlying manifold is a symmetric space and f is the exponential map. Their analysis is based on certain “C ^k  proximity conditions” which are known to be sufficient for C ^k  equivalence. In the present paper, a geometric interpretation of the tensor P _f is given. Associated to the retraction map f is a torsion-free affine connection, which in turn defines an exponential map. The condition P _f =0 is shown to be equivalent to the condition that f agrees with the exponential map of the connection up to the third order. In particular, when f is the exponential map of a connection, one recovers the original connection and P _f vanishes. It then follows that the condition P _f =0 is satisfied by a wider class of manifolds than was previously known. Under the additional assumption that the subdivision rule satisfies a time-symmetry, it is shown that the vanishing of P _f implies that the C ⁴ proximity conditions hold, thus guaranteeing C ⁴ equivalence. Finally, the analysis in the paper shows that for k≥5, the C ^k  proximity conditions imply vanishing curvature. This suggests that vanishing curvature of the connection associated to f is likely to be a necessary condition for C ^k equivalence for k≥5.     

Analysis of subdivision schemes for nets of functions by proximity and controllability

In this paper we develop tools for the analysis of net subdivision schemes, schemes which recursively refine nets of bivariate continuous functions defined on grids of lines, and generate denser and denser nets. Sufficient conditions for the convergence of such a sequence of refined nets, and for the smoothness of the limit function, are derived in terms of proximity to a bivariate linear subdivision scheme refining points, under conditions controlling some aspects of the univariate functions of the generated nets. Approximation orders of net subdivision schemes, which are in proximity with positive schemes refining points are also derived. The paper concludes with the construction of a family of blending spline-type net subdivision schemes, and with their analysis by the tools presented in the paper. This family is a new example of net subdivision schemes generating C¹ limits with approximation order 2.     

A generalized Taylor factorization for Hermite subdivision schemes

In a recent paper, we investigated factorization properties of Hermite subdivision schemes by means of the so-called Taylor factorization. This decomposition is based on a spectral condition which is satisfied for example by all interpolatory Hermite schemes. Nevertheless, there exist examples of Hermite schemes, especially some based on cardinal splines, which fail the spectral condition. For these schemes (and others) we provide the concept of a generalized Taylor factorization and show how it can be used to obtain convergence criteria for the Hermite scheme by means of factorization and contractivity.     

A generalized Taylor factorization for Hermite subdivision schemes

In a recent paper, we investigated factorization properties of Hermite subdivision schemes by means of the so-called Taylor factorization. This decomposition is based on a spectral condition which is satisfied for example by all interpolatory Hermite schemes. Nevertheless, there exist examples of Hermite schemes, especially some based on cardinal splines, which fail the spectral condition. For these schemes (and others) we provide the concept of a generalized Taylor factorization and show how it can be used to obtain convergence criteria for the Hermite scheme by means of factorization and contractivity.     

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.

     

Subdivision schemes with general dilation in the geometric and nonlinear setting

We establish results on convergence and smoothness of subdivision rules operating on manifold-valued data which are based on a general dilation matrix. In particular we cover irregular combinatorics. For the regular grid case results are not restricted to isotropic dilation matrices. The nature of the results is that intrinsic subdivision rules which operate on geometric data inherit smoothness properties of their linear counterparts.     

From Hermite to stationary subdivision schemes in one and several variables

Vector and Hermite subdivision schemes both act on vector data, but since the latter one interprets the vectors as function values and consecutive derivatives they differ by the “renormalization” of the Hermite scheme in any step. In this paper we give an algebraic factorization method in one and several variables to relate any Hermite subdivision scheme that satisfies the so–called spectral condition to a vector subdivision scheme. These factorizations are natural extensions of the “zero at π” condition known for the masks of refinable functions. Moreover, we show how this factorization can be used to investigate different forms of convergence of the Hermite scheme and why the multivariate situation is conceptionally more intricate than the univariate one. Finally, we give some examples of such factorizations.     

Subdivision Schemes and Irregular Grids

The present paper deals with subdivision schemes associated with irregular grids. We first give a sufficient condition concerning the difference scheme to obtain convergence. This condition generalizes a necessary and sufficient condition for convergence known in the case of uniform and stationary schemes associated with a regular grid. Through this sufficient condition, convergence of a given subdivision scheme can be proved by comparison with another scheme. Indeed, when two schemes are equivalent in some sense, and when one satisfies the sufficient condition for convergence, the other also satisfies it and it therefore converges too. We also study the smoothness of the limit functions produced by a scheme which satisfies the sufficient condition. Finally, the results are applied to the study of Lagrange interpolating subdivision schemes of any degree, with respect to particular irregular grids.     

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.      

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.     

Approximation order of interpolatory nonlinear subdivision schemes

Linear interpolatory subdivision schemes of C^r smoothness have approximation order at least r+1. The present paper extends this result to nonlinear univariate schemes which are in proximity with linear schemes in a certain specific sense. The results apply to nonlinear subdivision schemes in Lie groups and in surfaces which are obtained from linear subdivision schemes. We indicate how to extend the results to the multivariate case.     

Scalar and Hermite subdivision schemes

A criterion of convergence for stationary nonuniform subdivision schemes is provided. For periodic subdivision schemes, this criterion is optimal and can be applied to Hermite subdivision schemes which are not necessarily interpolatory. For the Merrien family of Hermite subdivision schemes which involve two parameters, we are able to describe explicitly the values of the parameters for which the Hermite subdivision scheme is convergent.     

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.     

Convergence and smoothness analysis of subdivision rules in Riemannian and symmetric spaces

After a discussion on definability of invariant subdivision rules we discuss rules for sequential data living in Riemannian manifolds and in symmetric spaces, having in mind the space of positive definite matrices as a major example. We show that subdivision rules defined with intrinsic means in Cartan-Hadamard manifolds converge for all input data, which is a much stronger result than those usually available for manifold subdivision rules. We also show weaker convergence results which are true in general but apply only to dense enough input data. Finally we discuss C ¹ and C ² smoothness of limit curves.