Multidimensional Interpolatory Subdivision Schemes.
This paper presents a general construction of multidimensional interpolatory subdivision schemes. In particular, we provide a concrete method for the construction of bivariate interpolatory subdivision schemes of increasing smoothness by finding an appropriate mask to convolve with the mask of a three-direction box spline Br,r,r of equal multiplicities. The resulting mask for the interpolatory subdivision exhibits all the symmetries of the three-direction box spline and with this increased symmetry comes increased smoothness. Several examples are computed (for in terms of the refinement mask are established and applied to the examples to estimate their smoothness.
iii. The function ' is in some H-older class C ff for suitable ff.
The function ' is fundamental, if i holds, and it is refinable, if ii holds. The sequence h is
called the refinement mask of the function '.
In that sense the paper is a continuation of [25] where we considered compactly supported
fundamental solutions given as linear combination of B-splines in the univariate setting and of
box splines in the multivariate setting. While those fundamental solutions exhibit nice symmetry,
regularity and approximation properties, they fail to satisfy a refinement relation, which precludes
their use in subdivision schemes. In fact, it was proven in [19] for the univariate case that there
are no compactly supported piecewise polynomial functions (splines) which are refinable and fundamental
except for piecewise constant or piecewise linear with integer knots. On the otherhand,
the univariate refinable and fundamental functions given in [7] and [8] are convolutions of B-splines
with some distributions. Univariate refinable and fundamental functions can be derived also as the
autocorrelations of refinable functions constructed in [5] in the context of wavelets; again these functions
have the form of convolutions of B-splines with distributions. This indicates that multivariate
functions satisfying i-iii may not necessarily be splines, but they could be convolutions of box
splines with some distributions. It is our goal here to provide in the multivariate setting compactly
supported and refinable fundamental solutions with the nice properties of symmetry, regularity and
approximation. The functions given here are convolutions of box splines with distributions.
Some compactly supported interpolatory subdivision schemes have already been given in the
literature. In particular, we mention the work of [9], [12], [13] and [14]. The butterfly subdivision
scheme given by [12] was the first example of bivariate C 1 refinable and fundamental function '.
An improvement of the smoothness analysis of the scheme can be found in [14]. Several continuous
bivariate refinable and fundamental functions are also given in [9]. Applications of interpolatory
subdivision schemes to the generation of surfaces can be found in [9], [12], [13], [14] and [23], and
applications to wavelets decompositions and image compression can be found in [10] and [11]. The
use of fundamental solutions for cardinal interpolation to obtain fundamental solutions for Hermite
interpolation on the lattice was discussed in [15]. Connections of fundamental and refinable functions
to refinable functions having orthogonal shifts was discussed in [20] and [22].
We first establish some notation and some consequences of the refinement relation (1.1). For
a finite sequence a, the symbol of a is the trigonometric polynomial ea on IR s with extension to a
Laurent polynomial, e
A, on C s as defined by the equations
For a compactly supported continuous function ' on IR s , the symbol takes the form
Introduction and Method
the last equality by the Poisson summation formula. In other words, it is the symbol of the sequence
restricted to ZZ s .
Upon taking Fourier transforms, the refinement relation (1.1) is equivalent to
When ZZ s
represents the vertices of the unit cube in IR s , a standard argument yields
-2ZZ se h(
or, in terms of the symbols,
se
Before we apply relation (1.5) to the problem at hand, we introduce another set of polynomials
e
2 , for a sequence a and relate them to the polynomials e
A
. We can decompose
e
A modulo ZZ s
2 as follows:
se
A - (z) :=
Then
e
A
Hence, we see that the polynomials e
A
2 , are obtained from the polynomials
2 g under the action of the unitary matrix U := f(\Gamma1) - 2 ZZ s
A
z - e
s:
Now, if the function ' is a fundamental solution for cardinal interpolation so that i. holds,
then from (1.2) and (1.3), e
se
se
Multidimensional Interpolatory Subdivision Schemes 3
Thus, the equation
is necessary in order that the function ' be a compactly supported and refinable fundamental
solution for cardinal interpolation.
Our point of view will be to try to define an appropriate polynomial e
H satisfying (1.8) and so
that the subdivision mask derived from the coefficients of e h will converge to the desired fundamental
function '. We hope to do this with good estimates on the smoothness of the resulting fundamental
solution as well. To this end we take our cue from the construction of compactly supported refinable
functions in the univariate case in [5] where the function e h takes the factored form
The left hand factor is the symbol of the refinement mask for the cardinal B-spline of order N .
It is this left hand factor that gives the smoothness to the resulting refinable functions while the
contribution of the trigonometric polynomial factor G(y) takes away from that smoothness. An
appropriately chosen G not only gives the basic orthogonality properties of the refinable functions,
but also does not lessen the smoothness too much.
For several variables, the appropriate generalization of the cardinal B-splines are the box splines
defined for a given s \Theta n matrix \Xi of full rank with integer entries. The basic facts and much of the
notation concerning box splines are taken from [2]; the reader is referred to [2] for the appropriate
references. In the case of the univariate cardinal spline, the number N plays several roles: it is the
order of the spline (one more than the degree of its polynomial pieces); the interval [0 : :N ] is the
support of the spline; and, the spline belongs to C N \Gamma2 , or even finer, its 1st derivative is in
For the multivariate box splines, these three things are encoded in the direction matrix \Xi,
but in more complicated ways. The (total) degree of the polynomial pieces of the box spline does
not exceed n \Gamma s. The support of the box spline is the polyhedron
where the summation runs over the columns of the matrix \Xi and as the notation indicates, we shall
apply set notation to \Xi as a set of its columns. Finally, the box spline belongs to C
is the minimum number of columns that can be discarded from \Xi to obtain a
matrix of rank ! s.
A box spline B \Xi satisfies the refinement equation
e
Y
In what follows, we shall drop the subscript indication of dependence on the direction set \Xi unless
it is needed to resolve ambiguities.
In the univariate case, the shifts of any cardinal B-spline form a Riesz basis, but this is no
longer the case for box splines in higher dimensions. However, there is an easy to check criterion
for when the shifts of a box spline do form a Riesz basis; namely, when the direction set \Xi is
4 1. Introduction and Method
a unimodular matrix (all bases of columns from \Xi have determinant \Sigma1). The last condition is
equivalent to there being no y 2 IR s at which all of the functions b
vanish. The
latter fact in turn implies that the symbol for the autocorrelation function B au := B   B(\Gamma \Delta ) is
positive for . In this case, (1.5) reads
where e
B, e
M are the symbols associated with the box spline B, its autocorrelation and
its refinement mask m respectively. That observation is the basic step in the proof of
Proposition(1.11). If the direction matrix \Xi defining the box spline
neither set of Laurent polynomials
2 g and
have common zeros in (Cnf0g) s . Here f
M is the symbol for the refinement mask m of the box spline.
Proof. Since e
B au is positive for implies that the
first set of Laurent polynomials in the Proposition have no common zeros for
The relation (1.7) then implies that the second set of Laurent polynomials in the Proposition have
no common zeros for . But from (1.6) and (1.9) it follows that the second set
of Laurent polynomials can only have common zeros where z = exp(\Gammaiy). Hence, again by (1.7),
the first set of Laurent polynomials can only have common zeros where one of the components of
z is zero. -
We shall use this Proposition to find candidates for e
H that satisfy (1.8). By Bezout's theorem,
there exist Laurent polynomials e
such that
We set Q :=
-2ZZ sz \Gamma- e
m(y); or e
In that case,
e
se
so that
e
se
and (1.8) is satisfied.
The proceeding paragraph outlines a general construction of the mask. There are many possibilities
for the polynomials e
and choices of ff 2 IN s in (1.12). Which ones give rise to the
refinement mask of a regular fundamental solution for cardinal interpolation with the properties
we desire? We present the two dimensional case in detail in the next section.
Multidimensional Interpolatory Subdivision Schemes 5
Once a construction of the mask is carried out, the Fourier transform of the corresponding
refinable function ' with mask h can be represented by
If e the infinite product converges in the sense of distributions. In this case the function
' is a compactly supported distribution.
The function ' can be constructed iteratively. Begin with one of the simplest continuous
examples of a ', say the hat function ' 0 := B 1;1;1 (the piecewise linear box spline having value 1
at (1; 1)) and define recursively
h(j)'
This is called the cascade algorithm. If ' n converges to ' uniformly, the function ' can be obtained
through this interative process and ' is a compactly supported L1 (IR s ) function. If ' is stable,
converges to ' uniformly. Recall that a compactly supported continuous function ' is stable,
if there is C ? 0, so that
With the refinement mask h satisfying e we have a function ', at least in the distributional
sense, which satisfies equation (1.1). It is still a matter to check whether the obtained
refinement mask defines a continuous function ', whether the resulting refinable function is the
fundamental solution for cardinal interpolation and whether the corresponding subdivision scheme
converges uniformly. Since only the mask is at hand, all criteria used to test the above properties
should be in terms of the refinement mask h and it should be possible to implement the criteria for
reasonable examples.
We first of all require that ' be continuous. Regularity or smoothness criteria that can be
applied to our case are discussed in the x3. All the examples we shall construct in x4 will be better
than C 1 .
Once we know that the resulting function ' is continuous, then we must show that it is
fundamental. As a corollary of the characterization of the stability and orthonormality of refinable
functions in terms of refinement mask, the results in [20] provide necessary and sufficient conditions
to test whether a mask that determines a continuous compactly supported ' is also fundamental:
Theorem(1.16). ([20] Proposition 4.1) Suppose ' is a compactly supported continuous function
satisfying the refinement equation (1.1) with the mask sequence h supported in [\Gamma(N \Gamma1) : :(N \Gamma1)] s .
Then ' is fundamental if and only if the ffi sequence is the unique eigenvector (up to constant
multiples) of the matrix
IH :=
corresponding to a simple eigenvalue 1.
For the examples of our construction given in Section 4, the task of determining the eigenvalues
and eigenvectors can be carried out numerically; for example, using MATLAB. Once we know that
' is fundamental, then it is automatically stable, since there is C ? 0 so that
6 2. The Bivariate Construction
(see [17]). Consequently ' n converges to ' uniformly (e.g. see [3]).
Suppose that the mask h defines a fundamental and refinable continuous function '. An interpolatory
subdivision scheme is defined as follows: Let c := fc ff : ff 2 ZZ s g be a sequence of control
points. The subdivision operator S is defined by
This gives us new control points,
The new control point sequence c 1 is determined linearly from c by 2 s different convolution
rules, and sequence c 1 consists of 2 s different copies of the original control point sequence c which
are mixed together. Since the scaling factor is 2, the new control polygon is parameterized, so that
the points c 1
ff correspond to the finer grid 2
c(fi), the new control
point sequence interpolates the previous one. Continuing this process, we get the control point
sequences c corresponding to the grids 2 \Gamman ZZ s . This process is called an interpolatory
subdivision scheme. The subdivision scheme is said to converge for an arbitrary control point
sequence c 2 ' 1 (ZZ s ), if there exists a continuous function f so that
lim
ck
The limit function f is
c ff '(
In particular, if c then the limit function is '.
It was shown in [3] that if ' is stable, the subdivision scheme converges. Therefore, the interpolatory
subdivision schemes discussed in this paper converge. Interested readers should consult
[3] for details.
Finally, we remark that since the refinable functions constructed here
possible to construct prewavelets from them. Interested readers should consult [17], [18] and [24]
for details of the construction of prewavelets.
2. The Bivariate Construction
Here we detail a construction in the two-dimensional case. The box splines that have stable
shifts are those defined for direction matrices based on the three directions
1). We shall take these directions to be given with equal multiplicities r. These
box splines will be denoted by B r;r;r . The symbol of the mask in this case takes the form
The box spline B r;r;r belongs to C 2r\Gamma2 . In case r = 1, the box spline B 1;1;1 is itself interpolatory
so there is no need to find a suitable multiplier e
Q for the symbol. Hence, we assume that r - 2 in
the sequel.
Multidimensional Interpolatory Subdivision Schemes 7
It has been our experience [25] that out of the many possible fundamental solutions that one
can obtain through the use of Bezout's theorem, most do not have practical (or aesthetic) value
because they have large variation (and often large max norm) over their support. The method of
construction here leads to examples of fundamental solutions of increasing smoothness with the
classic shape: centrally symmetric with value equal 1 at the origin. In fact, from the cases we have
computed, it appears that with greater symmetry comes greater smoothness. Our object in the end
will be to preserve the well-known symmetry structure of the box spline [1].
The existence of a function e
Q implies that there is some square that will contain the support of
the mask h for e
H. A smaller square means smaller support for the mask h and consequently, smaller
support for the refinable function. Initially, we try to fit the support of the mask h for e
H into a
square of side length 4r \Gamma 1. It turns out that for our examples this is possible. Later, we will impose
further conditions to make its support look like that of (twice) the support of the box spline within
that square. We consider the even lattice in the somewhat smaller square S
central point 2). Choosing this central point for the ff in (1.12), we find polynomials
e
such that
The idea of the construction is simply this: The masks of f
each occupy a smaller rectangle
S - in the lower right hand corner of S. The mask rectangle S - (with its values) is permitted to
shift in the three directions long as the shifted rectangles remain within
S. Each of the distinct such shifts are assigned an unknown coefficient which multiplies each of the
entries in the mask. In this way, the points in 2ZZ are assigned values which are a
linear combination of the values of the masks for the f
(the values in ZZ 2 n2ZZ 2 are
automatically zero). This leads to a linear system of equations when we ask that the resulting mask
be zero everywhere except at should be equal 1.
Our first goal is to analyze this system, even when some additional symmetry conditions
inherited from f
are imposed. First, we observe from (2.1) and the definition of f
M - that
2:
Therefore, the upper right corner of the rectangle S 0;0 can be shifted to the even lattice points in
the rectangle [2r . There are (r \Gamma 1) 2 such shifts. The new mask formed when these shifts
are added together will be the mask for the polynomial@ X
a 0;0 (j)z 2jA f
and the candidate for e
Q 0;0 is the first factor. Similar reasoning applies to the other rectangles S -
8 2. The Bivariate Construction
and we find that the candidates for the e
are:
e
a 0;0 (j)z 2j
e
a 1;0 (j)z 2j
e
a 0;1 (j)z 2j
e
a 1;1 (j)z 2j :
There are (r \Gamma unknowns in the above equations which equals
precisely the number of even lattice points in [0 . Thus, the resulting system of equations
has a solution if it is consistent and then each such solution satisfies (2.2).
In general, there may be infinitely many solutions because of the symmetries inherent in the
masks of the f
First, observe that f
M is invariant under the interchange of z(1) and z(2). Thus,
f
f
For any given set of solutions e
to (2.2), we define
e
e
Then the e
- also provide solutions for (2.2) as does the combination e
- )=2 and the
latter also satisfy
e
e
Next we observe that f
also satisfies the reciprocal relation
z
M(z
This implies that
Again, given any set of solutions e
Multidimensional Interpolatory Subdivision Schemes 9
Observe that if the e
then so do the e
- . Furthermore,
-2ZZ 2z 4r\Gamma2 z \Gamma2-\Gamma2-   f
so that the e
- also satisfy (2.2). Moreover, the monomials comprising e
still correspond to shifts
of S - that would remain in S. Finally, the combinations e
with the property that
Assume now that the e
are solutions of (2.2) that satisfy both (2.7) and (2.10). We have
shown that they can be obtained from any solution by the above procedure. Define
Then the relations e
e
Q(z
follow from (2.7) and (2.10).
We are now in a position to define a suitable e
With this definition, e
H is symmetric in the components of the variable z = (z(1); z(2)) and is
reciprocal
H(z
These two properties imply immediately that the associated mask of coefficients h is symmetric
through the direction and is symmetric through the origin:
Furthermore,
e
so that the necessary condition (1.8) is fulfilled. Moreover, since
we find that
2. The Bivariate Construction
The maximum support square for the mask of any f
while that for the
mask of any e
. Thus, the support of the mask for f
Q is in
and
We now restrict ourselves to consider the periodic symbol e h :=
The reciprocal relation (2.13) implies that e h is a real cosine polynomial. From (2.14) we have
2 nf0g, we also have
This gives four linear equations for the
, from which easily follows
In particular, since e
implies that
The above construction does lead to solutions that provide fairly smooth convergent interpolatory
subdivision schemes. But as it stands, the solutions are not uniquely determined since we
have not taken into account the full symmetries of the box spline. Here we use the symmetries of
the "centered" form of the box spline B r;r;r (see [1]), translated to our setting. The symmetries of
the mask f
M will be generated by the two matrices
and G 2 :=
acting on the exponents of z through the two relations
M(z); and z(2) r f
For later purposes, we note that the complete set of symmetries are embodied in the matrices
G :=
'oe
The symmetries for the box spline were derived by mapping the three directions into permutations
of themselves. This has significance for the problem at hand because the three directions are in fact
the non-zero elements of ZZ 2
2 n0; for all G 2 G:
Multidimensional Interpolatory Subdivision Schemes 11
The first of relations (2.17) just combines the interchange of z(1) and z(2) and the reciprocal
relation and so has already been taken into account in our construction above. The second relation
is a much stronger requirement that will restrict further the shifts of the S - that will be permitted,
thus reducing the number of unknowns. The restrictions will depend on the parity of r.
We first check how the second relation in (2.17) translates to the f
r even:
r odd:
The symmetry on e
H imposed by the matrix G 2 acting on its exponents is
This, together with the definition of e
H , (2.12), and the second relation in (2.17), makes the following
requirement of e
Q:
As was the case with f
places restrictions on the e
r even:
re
r odd:
If we require that the e
retain the form (2.4), then substituting that form into the right
hand side of (2.22) places further restrictions on which monomials may have non-zero coefficients.
Carrying this out, we find that the e
should have the form:
r even:
e
\Gamma( r
a 0;0 (j)z 2j ;
e
\Gamma( r
e
a 0;1 (j)z 2j ;
e
\Gamma( r
a 1;1 (j)z 2j ;
r odd:
e
e
e
e
12 2. The Bivariate Construction
First observe that in either case there are coefficients in (2.23).
Next, we note that the relations (2.19) put similar restrictions on the possible nonzero coefficients
of z(1) 2j(1) z(2) 2j(2) for the f
f
is even, or
f
r is even, or
f
is even, or
f
is even, or
Thus, under these restrictions the monomials z(1) 2j(1) z(2) 2j(2) in
coefficients have indices that satisfy
Hence, there are equations when these coefficients are compared in (2.2) with
the e
Once again, a solution exists if the system is consistent.
The two operations (2.6) and (2.9) both produce functions of the type (2.23) if the original
functions are of that type. Hence as before, there exist solutions e
of (2.2) that satisfy both (2.7)
and (2.10). It is possible to make the solution satisfy (2.21) as well by making use of
r even:
e
e
e
e
r odd:
e
e
e
e
If the e
have the form (2.23) and already satisfy (2.7), (2.10), and (2.2), then the functions
e
e
e
e
will be of the form (2.23) and satisfy (2.2), (2.7), (2.10) and (2.22).
We summarize the findings so far in the following theorem:
Multidimensional Interpolatory Subdivision Schemes 13
Theorem(2.25). Among the solution sets f e
-2ZZ 2, of
having the form (2.23), there is one that satisfies (2.7), (2.10) and (2.22). For that solution set the
Laurent polynomial
e
Q(z) with e
is invariant under the action of the group G acting on its exponents:
e
G:
The mask sequence h corresponding to e
H is supported in
and satisfies
G:
The relation (2.27) together with (2.18) gives a very strong symmetry on the mask h. (The
reader may find it very helpful to consult the masks of section 4 while reading this.) Since
G;
as a set, the numbers fh(2j are the same for each - 2 ZZ 2
2 nf0g. These numbers are
arranged symmetrically in the six cones generated by the lines
on hexagonal rings of lattice points about the origin:
A consequence of this is that the mask h is symmetric on its support along any of the lines
const. For example, if const - 0, then
The relations (2.16) were a result of f
f
which implies e
e
Comparing coefficients in these equations and taking into account
ffi(j), we arrive at further relations for the mask h on the lines
j(2)=const
j(2)=2const
j(1)=const
j(1)=2const
j(1)\Gammaj(2)=const
j(1)\Gammaj(2)=2const
14 3. Regularity of refinable functions
In particular, the sum of entries in the interior of each of the 6 cones is 0.
The final symmetry comes from the fact that f
e
3. Regularity of refinable functions
In this section we will provide some criteria for the regularity of refinable functions in terms of
their masks. These criteria are useful for the estimation of the regularity of the refinable functions
derived from interpolatory subdivision schemes constructed in the next section.
Unvariate counterparts of our regularity theorems and more can be found in [6, x7.1.3], [16],
[4] and references cited therein. The proofs of some of these results is carried to the multivariate
case and the dilation matrix 2I in order to provide estimates for our examples. This can be done
without encountering many difficulties; however, we include the proofs for the sake of completeness.
The function
for some constant independent of x.
The number ff is related to weighted L p exponents - p defined as
Z
In this paper, we only use - 1 and - 2 . The regularity order ff is related to - 1 and - 2 by the inequality
The idea here is the usual Littlewood-Paley technique. The domain of the Fourier transform
of ' is broken into the pieces C n := 2 n TT s
Z
then Z
Hence, log 2, or when
To estimate
R
'(w)j p dw, we consider the operator on L 2 (TT s ) defined in terms of a eg with
the symbol of a finite mask
Wf :=
This is the Fourier transform of the transition operator W for the mask g as defined in [20]:
Wa :=
Multidimensional Interpolatory Subdivision Schemes 15
As discussed in [20], if g is supported on [\Gamma(N the space of all
sequences supported on [\Gamma(N is an invariant subspace of W . The restriction of W
to ' N is called the restricted transition operator. The restricted transition operator W on ' N can
be represented by the matrix
G :=
(cf. Theorem 1.16). We only use the restricted operator in this section and assume that g is supported
on . Similarly, the space b
the space of Fourier transforms
of all sequences in ' N , is an invariant subspace of c W .
Proposition (3.2). Let b
' n be defined inductively by
Then for any f 2 L 2 (TT s ), we have
and
Z
Z
\Gamman w)b' n
Z
\Gamman w)\Pi n
with equality whenever both f - 0 and eg - 0.
Proof. For
For general n, using the fact that
3. Regularity of refinable functions
we fiind that
c
-2ZZ se g(w=2
\Gamman (w
Inequality, (3.4) follows directly by (3.3), since
Z
Z
\Gamman (w
Z
\Gamman w)b' n (w)jdw:
A similar result was proved in [21].
Suppose that eg satisfies
Define the space of trigonometric polynomials
Since D fi
2 nf0g, we have that
ae and for all jfij - ae.
Hence, the space V ae is an invariant subspace of the restricted transition operator c W defined by
(3.1).
Proposition(3.6). Suppose e
satisfies conditions (3.5) and eg - 0. Let - be the spectral radius of
c
. For the function ' g defined by
there is a constant C such that
Z
Multidimensional Interpolatory Subdivision Schemes 17
Proof. For any given ffi ? 0, there exists a norm k \Delta k on V ae so that for any f 2 V ae ,
Hence
Z
Since all the choices of the constants in this proof do not depend on n, for simplicity, we denote all
the constants by C even though the value of C may change with each occurance.
Cjwj, the function b
' g is bounded on TT s . Hence,
Z
Z
ae, we have f 2 V ae . Note that
Z
Z
\Gamman w)b' n (w)jdw
Z
\Gamman w)b' n (w)jdw
Z
It was proved in [20] that if ' g is fundamental, then - ! 1. Hence, the condition
whenever the mask g is the mask for a convergent interpolatory subdivision scheme.
Theorem(3.7). Suppose e g satisfies conditions (3.5) where e g is derived from an interpolatory
subdivision scheme with mask h as follows:
eg :=
fails to hold.
Let - be the spectral radius of c W j V ae
, then the fundamental solution ' for the interpolatory subdivision
scheme is in C ff\Gammaffl for any ffl ? 0 and
log -= log 2; if e h - 0 or;
log -=2 log fails to hold.
Proof. If e h - 0, then ' Proposition 3.6 and the result follows from the Littlewood-
Paley technique mentioned at the beginning of this section with
Similarly, if e h - 0 fails, then we use the autocorrelation function ' au := '( \Delta )   '(\Gamma \Delta ) of '. The
function ' au is refinable with the refinement mask h au := 2 \Gammas h( \Delta )   h(\Gamma \Delta ). Hence e h
nonnegative. Thus, ' Proposition 3.6 and the result follows from the Littlewood-Paley
technique mentioned at the beginning of this section with 2. -
The above regularity results only depended on the property (3.5) and the nonnegativity of the
mask eg and did not require any factorization of the mask eg. However, factorization can be useful
3. Regularity of refinable functions
both to establish (3.5) in some cases and to isolate a nonnegative part. This is the case for the
bivariate construction discussed in the last section where we have the factorization
and b
' is the product of the box spline B r;r;r 2 C 2r\Gamma2 with the Fourier transform of a distribution.
Since D fi e
2 nf0g, we have that
e h, and
Hence, the space V 2r\Gamma1 is an invariant subspace of the restricted transition operator c
W defined by
(3.1) with e
e h, while V 4r\Gamma1 is an invariant subspace of c
W if the autocorrelation function is
used.
In applications, we use either the matrix IH defined in Theorem 1.16 or the matrix
IH au :=
as an operator on the restricted sequence spaces to check the regularity of '. Since c W is the
Fourier transform of the operator IH (respectively, IH au ) on the restricted sequence space, the
eigenvalues of IH (respectively, IH au ) are the eigenvalues of c
W and the Fourier transform of the
eigenvectors of IH (respectively, IH au ) are the corresponding eigenvectors of c
W . This observation
together with Theorem 3.7 allows the following procedure to estimate the regularity of '. First find
all eigenvalues and eigenvectors of IH (respectively, IH au ), then throw out all those eignvalues whose
Fourier transform of the corresponding eigenvectors are not in V ae , where
. Note that the Fourier transform of the eigenvector v := (v fi ) of IH (respectively,
IH au ) is not in V ae if and only if
0-j-j-ae
The maximum absolute value of the remaining eigenvalues is the - to be used in Theorem 3.7.
For the examples of our construction in the next section, the task of determining which of
the largest eigenvectors are definitely NOT in V ae can be carried out numerically using MATLAB;
simply order the eigenvalues according to decreasing modulus and proceed down the list checking
(3.8) until a numerically significant drop in value occurs.
The problem with this procedure is that as the matrices get large, it becomes quite difficult
to carry out the numerical procedures. The complexity of using IH au is substantially more than in
using IH, yet we are forced to use it since e h will fail to be positive for odd r. The next observation
will be useful for our particular examples.
In the case e
mjeq, where e
m is the mask of a box spline B \Xi and e
is a finitely supported mask of some distribution with e , we can define an operator, c W 2 \Gammas eq ,
as in (3.1) but using q. If the support of the mask q is in
consider the operator c W 2 \Gammas eq restricted to b ' N .
Multidimensional Interpolatory Subdivision Schemes 19
mjeq where e
m is the refinement mask of a box spline B \Xi , and the
trigonometric polynomial e q is nonnegative,
e g satisfies (3.5). Let - be the spectral
radius of the restricted transition operator c W 2 \Gammas eq , i.e. the spectral radius of the matrix
restricted to V ae . Then ' 2 C m(\Xi)+s\Gamma1\Gammalog -= log 2\Gammaffl , where ffl ? 0 is arbitrary.
Proof. We note that
e q
e q
(cf. [2, p. 102]). Hence, just as in the proof of Proposition 3.6 and using Theorem 3.7, we have
Z
Z
Y
e
dw
Z
(recall that the value of C may change with each occurance). Hence, that ' 2 C m(\Xi)+s\Gamma1\Gammalog -= log 2\Gammaffl
follows from the Littlewood-Paley technique. -
The factorization in Corollary 3.9 does not require that we take the largest box spline factor,
just that the remaining factor be nonnegative.
4. Examples
We present the bivariate examples corresponding to decreasing
detail) and discuss their regularity. We note that we have chosen the three direction mesh used in
box spline theory. It is an easy transformation to convert this to the hexagonal mesh used by several
people in wavelet analysis. One should realize that the three-direction symmetry of our examples
would transform to a beautiful hexagonal symmetry in the hexagonal mesh.
2. The box spline B 2;2;2 has continuous second partial derivatives and its third partial
derivatives are in L1 (IR 2 ). If we apply our method to obtain e h, then the support of the mask
h 2;2;2 is expected to be in the square [\Gamma3 : Indeed, we obtain a mask exhibiting the full
symmetries of the box spline
4. Examples
where the entry at the origin is distinguished by boldface type. Here we note that there are only
nonzero entries and only the 6 nonzero entries in the cone are required since the rest
follow from the symmetries. If we use Theorem 1.16 on the 49 \Theta 49 matrix IH 2;2;2 determined by
h 2;2;2 we find that it has 1 as a simple eigenvalue with ffi as its eigenvector. Hence, the function
defined via (1.14) is a fundamental solution for cardinal interpolation. That ' 2;2;2 enjoys
the classic shape of a fundamental solution and the symmetries of the tree direction box spline is
clearly seen in Figure 4.1.

Figure

(4.1). The function ' 2;2;2 on [\Gamma3 : :3] 2 and its level lines \Gamma:1
3. The box spline B 3;3;3 belongs to C 4 (IR 2 ). The support of the mask h 3;3;3 will be in
the square Again we obtain a mask exhibiting the full symmetries of the box spline
Multidimensional Interpolatory Subdivision Schemes 21
where the entry at the origin is distinguished by boldface type. Only the entries in the cone
are needed to describe the matrix with the symmetries are taken into consideration. The eigenvalues
and eigenvectors of the 121 \Theta 121 sparse matrix IH 3;3;3 are easily determined by MATLAB. Again,
1 is a simple eigenvalue with ffi as its eigenvector. Hence, the function ' 3;3;3 defined via (1.14) is a
fundamental solution for cardinal interpolation by Theorem 1.16(see Figure 4.2).
-5 -4 -3 -2
-5

Figure

(4.2). The function ' 3;3;3 on [\Gamma5 : :5] 2 and its level curves \Gamma:1
4. The box spline B 4;4;4 belongs to C 6 (IR 2 ). The support of the mask h 4;4;4 will be in
the square [\Gamma7 : . Again, the mask exhibits the full symmetries of the box spline
22 4. Examples6 6
\Gamma350 12950 \Gamma48650 36050 \Gamma48650 12950 \Gamma350 0
where the entry at the origin is distinguished by boldface type. Again, analysing the matrix IH 4;4;4 ,
we find that the resulting function ' 4;4;4 is fundamental (see, Figure 4.3).
-226
-226

Figure

(4.3). The function ' 4;4;4 on [\Gamma7 : :7] 2 and its level lines [\Gamma:1
Multidimensional Interpolatory Subdivision Schemes 23
8. As is already apparent in the case 4, the masks soon become too large to
give fully in the text. We have given the three cases full so that the symmetries alluded
to in Section 2 can be firmly established in the minds of the reader. We give the masks of the four
remaining cases in a more compact form, using the cones of symmetry. We use the first quadrant
with 1 in the lower left corner sitting at the origin, the rest of the diagonal is left blank and one
mask is given in the cone and the other in 0 - k ! j. The two included tables give the
masks for 8. While the mask for 8 is a 31 \Theta 31 matrix which is quite large
for numerical purposes, it does compare favorably with using a fundamental box spline interpolant
of comparable smoothness (for example, the fundamental solution corresponding to B 3;3;3 ) which
has exponential decay and so must be truncated appropriately for use.
The matrices IH grow more quickly and for is already an 941 \Theta 941 matrix. The
computations still show that the eigenvalue 1 is simple with ffi as its eigenvector. The computations
of the sums (3.8) do show the effects of the added complexity, but are none-the-less useful for the
estimation of regularity.
Regularity. The examples for sufficient variety to test various smoothness
criteria. We use Theorem 3.7 and Corollary 3.9 to estimate the regularity of our examples. We have
computed three separate quantities.
The first quantity is the spectral radius of c W j V
for e in all cases, even though by
Theorem 3.7 it applies only in the cases when e h - 0. It turns out that e h - 0 holds if and only if r is
even, since exp(i(r \Gamma 2) \Delta )eq - 4 in each case. We suspect that this quantity gives the best estimate
for regularity even in the case of odd r when it has not been shown to apply.
The second computation yields an estimate for the spectral radius of c
for
the size of the matrix IH au quickly impedes the computation and we were successful in carrying it
out only for 4. In every case, the estimate for the smoothness is smaller than that obtained
using the first quantity, although this estimate is valid in all cases.
Finally, we use the factorization e
in Corollary 3.9. In this
case, is the spectral radius of c W j V 2r\Gamma3
for
qj.
The results of the computations are listed in the following table: Recall that ' r;r;r belongs to
C ff\Gammaffl where ff is estimated by \Gamma log(-)= log(2) when r is even, by \Gamma log(-)=(2
and by 2 \Gamma log(-)= log(2) for r odd.
e
qj
3 2.8301e+00 2.1751e+00 2.6100e+00
6 4.7767e+00 ?? NA



--R

Bivariate cardinal interpolation by splines on a three-direction mesh
splines

A new technique to estimate the regularity of a refinable function
Orthonormal bases of compactly supported wavelets
Ten Lectures on Wavelets
Interpolation through an iterative scheme
Symmetric iterative interpolation processes



A butterfly subdivision scheme for surface interpolation with tension control
"Multivariate Approximation and Interpolation,"
Using parameters to increase smoothness of curves and surfaces generated by subdivision
Hermite interpolation on the lattice hZZ d
Subdivision schemes in L p spaces
Using the refinement equation for the construction of pre- wavelets II: Powers of two
Multiresolution and wavelets
Complete characterization of refinable splines
Stability and orthonormality of multivariate refinable functions
Biorthogonal wavelet bases on IR d
Interpolatory subdivision schemes and wavelets
Smooth surface interpolation over arbitrary triangulations by subdivision algorithms
Wavelets and pre-wavelets in low dimensions

--TR

--CTR
Yun-Zhang Li, On the holes of a class of bidimensional nonseparable wavelets, Journal of Approximation Theory, v.125 n.2, p.151-168, December
Guiqing Li , Weiyin Ma, Interpolatory ternary subdivision surfaces, Computer Aided Geometric Design, v.23 n.1, p.45-77, January 2005
Bin Han , Rong-Qing Jia, Quincunx fundamental refinable functions and Quincunx biorthogonal wavelets, Mathematics of Computation, v.71 n.237, p.165-196, January 2002
Bin Dong , Zuowei Shen, Construction of biorthogonal wavelets from pseudo-splines, Journal of Approximation Theory, v.138 n.2, p.211-231, February 2006
subdivision schemes;box splines;wavelets;interpolatory subdivision schemes;interpolation