Computing the Smoothness Exponent of a Symmetric Multivariate Refinable Function.
Smoothness and symmetry are two important properties of a refinable function. It is known that the Sobolev smoothness exponent of a refinable function can be estimated by computing the spectral radius of a certain finite matrix which is generated from a mask. However, the increase of dimension and the support of a mask tremendously increase the size of the matrix and therefore make the computation very expensive. In this paper, we shall present a simple and efficient algorithm for the numerical computation of the smoothness exponent of a symmetric refinable function with a general dilation matrix. By taking into account the symmetry of a refinable function, our algorithm greatly reduces the size of the matrix and enables us to numerically compute the Sobolev smoothness exponents of a large class of symmetric refinable functions. Step-by-step numerically stable algorithms are given. To illustrate our results by performing some numerical experiments, we construct a family of dyadic interpolatory masks in any dimension, and we compute the smoothness exponents of their refinable functions in dimension three. Several examples will also be presented for computing smoothness exponents of symmetric refinable functions on the quincunx lattice and on the hexagonal lattice.
Introduction
. A d  d integer matrix M is called a dilation matrix if the
condition holds. A dilation matrix M is isotropic if all the eigen-values
of M have the same modulus. We say that a is a mask on Z d if a is a nitely
supported sequence on Z d such that
1. Wavelets are derived from
renable functions via a standard multiresolution technique. A renable function
is a solution to the following renement equation
2Z d
where a is a mask and M is a dilation matrix. For a mask a on Z d and a dd dilation
matrix M , it is known ([2]) that there exists a unique compactly supported distributional
solution, denoted by  M
a throughout the paper, to the renement equation
(1.1) such that ^
a where the Fourier transform of f 2 L 1 (R d ) is dened to
be
Z
R d
f(x)e ix dx;  2 R d
and can be naturally extended to tempered distributions. When the mask a and
dilation matrix M are clear from the context, we write  instead of  M
a for simplicity.
Symmetric multivariate wavelets and renable functions have proved to be very useful
in many applications. For example, 2D renable functions and wavelets have been
widely used in subdivision surfaces and image/mesh compression while 3D renable
functions have been used in subdivision volumes, animation and video processing, etc.
The research was supported by NSERC Canada under Grant G121210654 and by Alberta
Innovation and Science REE under Grant G227120136.
y Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta,
Canada T6G 2G1. E-mail: bhan@math.ualberta.ca, URL: http://www.ualberta.ca/bhan
Han
For a compactly supported function  in R d , we say that the shifts of  are stable
if for every  2 R d , b
. For a function  2 L 2 (R d ), its
smoothness exponent is dened to be
Z
R d
Smoothness is one of the most important properties of a wavelet system. Therefore,
it is of great importance to have algorithms for the numerical computation of the
smoothness exponent of a renable function. Let a be a mask and M be a dilation
matrix. We denote  k 1 the set of all polynomials of total degree less than k. By
convention,  1 is the empty set. We say that a satises the sum rules of order k
with respect to the lattice MZ d if
2MZ d
2MZ d
Dene a new sequence b from the mask a by
2Z d
the linear space of all nitely supported sequences on Z d . For a
subset K of Z d , by '(K) we denote the linear space of all nitely supported sequences
on Z d that vanish outside the set K.
The transition operator T b;M associated with the sequence b and the dilation
matrix M is dened by
2Z d
(R d ) be a renable function with a nitely supported mask a and a
dilation matrix M such that the shifts of  are stable and a satises the sum rules of
order k but not k + 1. Dene the
set
by
\Z d and
and dene the slightly smaller subspace V 2k 1 of
'(
b;M ) to be
'(
2Z d
When M is isotropic, it was demonstrated in [4, 5, 6, 10, 21, 23, 24, 26, 27, 33, 35] in
various forms under various conditions that
) is the spectral radius of the operator T b;M acting on the nite
dimensional T b;M -invariant subspace V 2k 1 of
'(
However, from the point of view of numerical computation, there are some diculties
in obtaining the Sobolev smoothness exponent of a renable function via (1.7)
by computing the quantity (T b;M
due to the following considerations:
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 3
D1. It is not easy to nd a simple basis for the space V 2k 1 by a numerically
stable procedure to obtain a representation matrix of T b;M under such a basis.
Theoretically speaking, if some elements in a numerically found basis of V 2k 1
cannot satisfy the equality in (1.6) exactly, then it will dramatically change
the spectral radius since in general T b;M has signicantly larger eigenvalues
outside the subspace V 2k 1 .
D2. When the dimension is greater than one and even when the mask has a relatively
small support, in general, the dimensions of the spaces V 2k 1 and
'(
b;M are
very large. For example, for a 3D mask with support [ 7; 7] 3 and sum rules
of order 4, we have dim(V 7
dim('(
This makes
the numerical computation using (1.7) very expensive or even impossible.
D3. In order to obtain the exact Sobolev smoothness exponent by (1.7), we have
to check the assumption that the shifts of  M
a are stable which is a far from
trivial condition to be veried.
Fortunately, the di-culty in D1 was successfully overcome in Jia and Zhang [25],
where they demonstrated that (T b;M
) is the largest value in modulus in the
set consisting of all the eigenvalues of T b;M j
'(
excluding some known special
eigenvalues. Note that
'(
b;M ) has a simple basis f-  : b;M g, where -
and -  nfg.
On the other hand, both symmetry and smoothness of a wavelet basis are very
important and much desired properties in many applications. It is one of the purposes
in this paper to try to overcome the di-culty in D2 for a symmetric renable function.
We shall demonstrate in Algorithm 2.1 in Section 2 that we can compute the Sobolev
smoothness exponent of a symmetric renable function by using a much smaller space
than using the space
'(
b;M ). In Section 3, we shall see that for many renable
functions, it is not necessary to directly verify the stability assumption since they are
already implicitly implied by the computation. Therefore, the di-culty in D3 does
not exist at all for many renable functions (almost all interesting known examples
fall into this class).
To give the reader some idea about how symmetry can be of help in computing the
smoothness exponents of symmetric renable functions, we give the following
comparison result in Table 1. See Section 2 for more detail and explanation of Table 1.

Table
The last two rows indicate the matrix sizes in computing the Sobolev smoothness exponents of
symmetric renable functions using both the method in [25] and the method in Algorithm 2.1 in
Section 2 in this paper. This table demonstrates that Algorithm 2.1 can greatly reduce the size of
the matrix in computing the Sobolev smoothness exponent of a symmetric renable function.
Mask 4D mask 3D mask 2D mask 2D mask 2D mask
Symmetry full axes full axes hexagonal full axes hexagonal
Dilation matrix 2I 4 2I 3 2I 2
Method in [25] 194481 24389 8911 5601 > 3241
Algorithm 2.1 715 560 756 707 294
Masks and renable functions with extremely large supports may be rarely used in
real world applications. For a given mask which is of interest in applications, very often
there are some free parameters in the mask and one needs to optimize the smoothness
exponent of its renable function ([9, 12, 15, 17, 28, 30]). The e-cient algorithms
4 Bin Han
proposed in this paper will be of help for such a smoothness optimization problem. On
the other hand, a renable function vector satises the renement equation (1.1) with
a matrix mask of multiplicity r. A matrix mask of multiplicity r is a sequence of r r
matrices on Z d (Masks discussed in this paper correspond to are called scalar
masks). Very recently, as demonstrated in [17], multivariate renable function vectors
with short support and symmetry are of interest in computer aided geometric design
(CAGD) and in numerical solutions to partial dierential equations. Let M be the
quincunx dilation matrix (the fourth dilation matrix in Table 1) and let a be a matrix
mask of multiplicity 3 with support [ masks of order 1
discussed in [17] are examples of such masks which often have many free parameters
and are useful in CAGD). In order to compute the Sobolev smoothness exponent of its
renable function vector with such a small mask, without using symmetry, we found
that one has to deal with a 1161  1161 matrix (also see [23]). As a consequence,
even in low dimensions and for masks with small supports, it is very important to
take into account the symmetry of a renable function (vector) in algorithms for the
numerical computation of its smoothness exponent. Though for simplicity we only
consider scalar masks here, results in this paper can be generalized to matrix masks
and renable function vectors which will be discussed elsewhere.
The structure of the paper is as follows. In Section 2, we shall present step
by step numerically stable and e-cient algorithms for the numerical computation of
the Sobolev smoothness exponent of a symmetric renable function. In addition, an
algorithm for computing the Holder smoothness exponent of a symmetric renable
function will be given in Section 2 provided that the symbol of its mask is nonnegative.
In Section 3, we shall study the relation of the spectral radius of a certain operator
acting on dierent spaces. Such analysis enables us to overcome the di-culty in D3
for a large class of masks. In Section 4, we shall apply the results in Sections 2 and 3
to several examples including renable functions on quincunx lattice and hexagonal
lattice. We shall also present a C 2
3-interpolatory subdivision scheme in Section 4.
Next, we shall generalize the well known univariate interpolatory masks in Deslauriers
and Dubuc [8] and the bivariate interpolatory masks in [15] to any dimension.
Finally, we shall use the results in Sections 2 and 3 to compute Sobolev smoothness
exponents of interpolating renable functions associated with such interpolatory
masks in dimension three.
Programs for computing the Sobolev and Holder smoothness exponents of symmetric
renable functions based on the Algorithms 2.1 and 2.5 in Section 2, which
come without warranty and are not yet optimized with respect to user interface, can
be downloaded at http://www.ualberta.ca/bhan.
2. Computing smoothness exponent using symmetry. In this section, taking
into account the symmetry, we shall present an e-cient algorithm for the numerical
computation of the Sobolev smoothness exponent of a symmetric multivariate
renable function with a general dilation matrix. As the main result in this section,
Algorithms 2.1 and 2.5 are quite simple and can be easily implemented, though their
proofs and some notation are relatively technical.
Before proceeding further, let us introduce some notation and necessary back-
ground. Let N 0 denote all the nonnegative integers. For
d for
For
(R d
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 5
For
ed , where e j is the jth coordinate unit
vector in R d . Let - 0 denote the sequence such that
nf0g. For norm is dened to be kuk p := (
Let M be a d  d dilation matrix and a be a mask on Z d . Dene the subdivision
operator
2Z d
lim
kr  S n
do
Let M be a dilation matrix and max be the spectral radius of M (When M is
isotropic, then When a mask a satises the sum rules of order k
but not k + 1, we dene the following important quantity:
The above quantity  p (a; M) plays a very important role in characterizing the convergence
of a subdivision scheme in a Sobolev space and in characterizing the L p
smoothness exponent of a renable function.
The L p smoothness of f 2 L p (R d ) is measured by its L p smoothness exponent:
constant C and for large enough positive integer n
When 2, the above denition of  2 (f) agrees with the denition in (1.2). By
generalizing the results in [4, 5, 6, 10, 12, 21, 24, 26, 27, 32, 33, 35] and references
therein, we have
a
and the equality holds when the shifts of  M
a are stable and M is an isotropic dilation
matrix. When M is a general dilation matrix and the shifts of  M
a are stable, as
demonstrated in [5] for the case only have the estimate
log
a
where min := min 16j6d being
all the eigenvalues of M . As pointed out in [5], the usual Sobolev smoothness dened
in (1.2) and (2.3) is closely related to isotropic dilations and anisotropic Sobolev spaces
are needed in the case of an anisotropic dilation matrix. See [5] for more detail on
this issue.
So, to compute the Sobolev smoothness exponent of a renable function, we need
to compute  2 (a; M) and therefore, to compute  k (a; M; 2). It is the purpose of this
section to discuss how to e-ciently compute  k (a; M; 2) when a is a symmetric mask.
Let  be a nite subset of integer matrices whose determinants are 1. We say
that  is a symmetry group with respect to a dilation matrix M (see [13]) if  forms
a group under matrix multiplication and MM 1 2  for all  2 . Obviously, each
element in a symmetry group induces a linear isomorphism on Z d .
6 Bin Han
Let  A
d denote the set of all linear transforms on Z d which are given by
and  is a permutation on
d is called
the full axes symmetry group. Obviously,  A
d is a symmetry group with respect to
the dilation matrix 2I d . It is also easy to check that  A
2 is a symmetry group with
respect to the quincunx dilation matrices
and
Another symmetry group with respect to 2I 2 is the following group which is called
the hexagonal symmetry group:
Such a group  H can be used to obtain wavelets on the hexagonal planar lattice (that
is, the triangular mesh). For a symmetry group  and a sequence u on Z d , we dene
a new sequence (u) as follows:
where # denotes the cardinality of the set . We say that a mask a is invariant
under  if (a) = a. Obviously, for any sequence u, (u) is invariant under  since
When  is a symmetry group with respect to a dilation matrix M ,
then a is invariant under  implies that the renable function  M
a is also invariant
under ; that is,  M
a
a for all  2 . See Han [13] for detailed discussion on
symmetry property of multivariate renable functions. We caution the reader that
the condition MM 1 2  for all  2  cannot be removed in the denition of a
symmetry group with respect to a dilation matrix M . For example, as a subgroup of
A
is not a symmetry group with respect to the quincunx dilation matrices,though it is
a symmetry group with respect to the dilation matrix 2I 2 . So even when a mask a is
invariant under such a group , the renable function  M
a with the quincunx dilation
matrices may not be invariant under .
Let Z d
denote a subset of Z d such that for every  2 Z d , there exists a unique
satisfying In other words, Z d
is a complete set of
representatives of the distinct cosets of Z d under the equivalence relation induced by
on Z d .
Taking into account the symmetry of a mask, now we have the following algorithm
for the numerical computation of the important quantity  2 (a; M ).
Algorithm 2.1. Let M be a d  d isotropic dilation matrix and let  be a
symmetry group with respect to the dilation matrix M . Let a be a mask on Z d such
that
1. Dene the sequence b as in (1.3). Suppose that b is invariant
under the symmetry group  and a satises the sum rules of order k but not k+1. The
quantity  2 (a; M), or equivalently,  k (a; M; 2), is obtained via the following procedure:
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 7
(a) Find a nite subset K of Z d
such that
and
(b) Obtain a (#K )  (#K ) matrix T as follows:
(c) Let (T ) consist of the absolute values of all the eigenvalues of the square matrix T
counting multiplicity of its eigenvalues. Then  2 (a; M) is the smallest number
in the following set
o/
with positive multiplicity
where by default log j det Mj 0 := 1 and
Before we give a proof to Algorithm 2.1, let us make some remarks and discuss
how to compute the set K and the quantities m (j) in Algorithm 2.1. Since the
matrix T in Algorithm 2.1 has a simple structure, it is not necessary to store the whole
matrix T in order to compute its eigenvalues and many techniques from numerical
analysis (such as the subspace iteration method and Arnoldi's method as discussed in
[34]) can be exploited to further improve the e-ciency in computing the eigenvalues
of T . We shall not discuss such an issue here. One satisfactory set K can be easily
obtained as follows:
Proposition 2.2. Let K 0
0g. Recursively compute
\ Z d
. Then K satises all the
conditions in (a) of Algorithm 2.1.
Proof. Note that K j  (
integer r. Therefore, there must exist j 2 N such that K
Consequently,
jg. The set O j can be ordered according to the
lexicographic order. That is,
8 Bin Han
order if  For a d  d matrix A and
which is uniquely determined
by
x
It is easy to verify that S(AB; are all the eigen-values
of A, then   ;  2 O j are all the eigenvalues of S(A;
since S(A; j) is similar to S(B; when A is similar to B. Moreover,
by comparing the Taylor series of the same
function e x T Ay and e y T A T x .
The quantities m (j); j 2 N 0 can be computed as follows.
Proposition 2.3. Let  be a symmetry group. Then
In particular, when I d 2 , then m (2j
Proof. For  2 N d
be the sequence given by q
that
(#)[(q
are linearly independent, we have
When I d 2 , we observe that
Therefore, since
Note that m (j) depends only on the symmetry group  and is independent of
the dilation matrix M . When  is a subgroup of the full axes symmetry group  A
d ,
then m (j) can be easily determined since the matrix S(; j) is very simple for every
d . For example,
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 9
For the convenience of the reader, we list the quantities m (j) in Algorithm 2.1
for some well known symmetry groups in Table 2. In Table 2, the symmetry groups
2 and  2
are dened to be

Table
The quantities m (j); j 2 N 0 in Algorithm 2.1 for some known symmetry groups. Note that
N in this table.
26 28
A
A
A
A
For a sequence u on Z d , its symbol is given by
2Z d
For denote the dierence operator given by
and   :=  1
d for
2Z d
To prove Algorithm 2.1, we need the following result.
Theorem 2.4. Let a be a nitely supported mask on Z d and let b be the sequence
dened in (1.3). Let  be a symmetry group with respect to a dilation matrix M .
Suppose that b is invariant under . Then (T b;M
and
where T b;M is the transition operator dened in (1.4) and W k is the minimal T b;M -
invariant nite dimensional space which is generated by (  -),  2 N d
Proof. Since  is a symmetry group with respect to the dilation matrix M and b
is invariant under , for
2Z d
2Z d
2Z d
Therefore, (T b;M
Note that b j. By the Parseval
identity, we have
kr  S n
Z
r  S n
(2) d
Z
S n
b;M -() d
From the denition of the transition operator, it is easy to verify that
For a sequence u such that b u() > 0 for all  2 R d , we observe that
[11]). From the fact that \
S n
follows that
is the minimal T b;M -invariant subspace generated by
we have
lim
do
lim
do
which completes the proof.
Proof of Algorithm 2.1: Let K Kg. Then it is easy to
check that both '(K) and ('(K)) are invariant under T b;M (see [14, Lemma 2.3]).
Since a satises the sum rules of order k, then the sequence b, which is dened in
(1.3), satises the sum rules of order 2k and V 2k 1 is invariant under T b;M (see [20,
Theorem 5.2]), where
2Z d
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 11
1g. Let W k denote the linear space in
Theorem 2.4. Observe that W k  U 2k 1  V 2k 1 . By Theorem 2.4 and (1.7), we
have  k (a; M;
Since b satises the sum rules of order 2k and b is invariant under , we have
Therefore, we have spec(T b;M j
denotes the set of all the
eigenvalues of T counting multiplicity and the linear space ('(K))=U 2k 1 is a quotient
group under addition. Note that U
the quotient group ('(K))=U 2k 1 is isomorphic to U 1 =U 0
By [25, Theorem 3.2] or by the proof of Theorem 3.1 in Section 3, we know that for any
all the eigenvalues of T b;M
we used the assumption that M is isotropic. Since U j 1 =U j is a subgroup of
we deduce that all the eigenvalues of T b;M
fact, by duality, we can prove that for any
without assuming that M is isotropic, where [ (q)](x) := q(M 1 x); q 2  2k 1 .) By
duality,
Note that f(- is a basis of ('(K)) and the matrix T is the representation
matrix of the linear operator T b;M acting on ('(K)) under the basis
g. This completes the proof.
From the above proof, without the assumption that M is isotropic, we observe
that  k (a; M; 2) is the largest number in the set (T )nfjj
where (T ) is dened in Algorithm 2.1 and [ (q)](x) := q(M 1
Since  is a symmetry group with respect to the dilation matrix M , it is easy to see
that
g. In passing, we mention that the calculation of the Sobolev smoothness for
a bivariate mask which is invariant under  A
2 with the dilation matrix 2I 2 was also
discussed by Zhang in [36]. When a mask has a nonnegative symbol, then we can
also compute  k (a; M;1) in a similar way (see [14, Theorem 4.1]). For complete-
ness, we present the following algorithm whose proof is almost identical to that of
Algorithm 2.1.
Algorithm 2.5. Let M be a d  d isotropic dilation matrix and let  be a
symmetry group with respect to the dilation matrix M . Let a be a mask on Z d such
that
1. Suppose that a is invariant under the symmetry group , the
symbol of a is nonnegative (i.e., ba() > 0 for all  2 R d ), and a satises the sum
rules of order k but not k + 1. The quantity 1 (a; M), or equivalently,  k (a; M;1),
is obtained via the following procedure:
(a) Find a nite subset K of Z d
such that
ag \ Z d
and
12 Bin Han
(b) Obtain a (#K )  (#K ) matrix T as follows:
(c) Let (T ) consist of the absolute values of all the eigenvalues of the square matrix
counting multiplicity of its eigenvalues. Then 1 (a; M) is the smallest
number in the following set
with positive multiplicity
Moreover, without the assumption that the symbol of the mask a is nonnegative,
(a; M) is equal to or less than the quantity obtained in (c).
Cohen and Daubechies in [4] discussed how to estimate the smoothness exponent
of a renable function using the Fredholm determinant theory. Matlab routines
for computing smoothness exponents using the method in [25] were developed and
described in [28]. When a mask has a nonnegative symbol, matlab routines for estimating
the Holder smoothness exponent was developed and described in [1] where
symmetry is not taken into account and eigenvectors have to be explicitly computed
and to be checked whether they belong to the subspace V k 1 or not.
3. Relations among  k (a; M; p); k 2 N 0 . In this section, we shall study the
relations among  k (a; M; p); k 2 N 0 . Using such relations we shall be able to overcome
the di-culty in D3 in Section 1 in order to check the stability condition for certain
renable functions.
The main results in this section are as follows.
Theorem 3.1. Let M be a dilation matrix. Let a be a nitely supported mask
on Z d such that
a satises the sum rules of order k with respect
to the lattice MZ d . Let min := min 16j6d
are all the eigenvalues of M . Then
min
and
for all j 2 N 0 and 1 6 p 6 q 6 1. Consequently,
We say that a mask a is an interpolatory mask with respect to the lattice MZ d
nf0g. Let a and b be two nitely supported masks on Z d .
Dene a sequence c by If c is an interpolatory mask with
respect to the lattice MZ d , then b is called a dual mask of a with respect to the lattice
MZ d and vice versa.
Let  be a continuous function on R d . We say that  is an interpolating function
nf0g. For discussion on interpolating renable
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 13
functions and interpolatory masks, the reader is referred to [7, 8, 9, 15, 16, 30, 31]
and references therein. For a compactly supported function  on R d , we say that
the shifts of  are linearly independent if for every  2 C d , b
Clearly, if the shifts of  are linearly independent, then the shifts of  are
stable. When  is a compactly supported interpolating function, then the shifts of
are linearly independent since
2Z d
be the renable function
with a nitely supported mask and the dilation matrix 2I d . A method was proposed
in Hogan and Jia [19] to check whether the shifts of  are linearly independent or
not. However, there are similar di-culties as mentioned in D1 and D2 in Section 1
when applying such a method in [19]. In fact, the procedure in [19] is not numerically
stable and exact arithmetic is needed. Also see [29] on stability.
An iteration scheme can be employed to solve the renement equation (1.1). Start
with some initial function  0 2 L p (R d ) such that b
nf0g. We employ the iteration scheme Q n
is the
linear operator on L p (R d by
2Z d
(R d
This iteration scheme is called a subdivision scheme or a cascade algorithm ([2, 18]).
When the sequence Q n
converges in the space L p (R d ), then the limit function
must be  M
a and we say that the subdivision scheme associated with mask a and
dilation matrix M converges in the L p norm. It was proved in [14] that the subdivision
scheme associated with the mask a and dilation matrix M converges in the L p norm if
and only if  1 (a; M; p) < j det M j 1=p (By Theorem 3.1, we see that this is equivalent to
references therein on convergence of subdivision
schemes.
Let  be a renable function with a nitely supported mask a and a dilation
matrix M . It is known that  is an interpolating renable function if and only
if the mask a is an interpolatory mask with respect to the lattice MZ d and the
subdivision scheme associated with mask a and dilation M converges in the L1 norm
(equivalently,  1 (a; M;1) < 1, see [14]). However, in general, it is di-cult to directly
check the condition  1 (a; M;1) < 1. On the other hand, in order to check that
is an interpolating renable function with a nitely supported interpolatory mask
a and a d  d dilation matrix M , it was known in the literature (for example, see
[1, 29, 31, 34]) that one needs to check the following two alternative conditions: 1)
is a continuous function (Often, one computes the Sobolev smoothness exponent
of  to establish that  2 () > d=2 and consequently  is a continuous function).
- is the unique eigenvector of the transition operator T a;M j
'(
corresponding
to a simple eigenvalue 1. In the following, we show that if a is an interpolatory
mask and  2 (a; M) > d=2, then 2) is automatically satised. In other words, for
an interpolatory mask a with respect to the lattice MZ d , we show that  2 (a; M) >
d=2 implies 1 (a; M) > 0. Consequently,  1 (a; M;1) < 1 and the corresponding
subdivision scheme converges in the L1 norm and its associated renable function is
indeed an interpolating renable function.
Corollary 3.2. Let a be a nitely supported mask on Z d and M be a dilation
matrix. Suppose that b is a dual mask of a with respect to the lattice MZ d and
14 Bin Han
Then the shifts of  M
a are linearly independent and consequently stable. If M is
isotropic and (3.2) holds, then  p (a; M) > 0 implies that  M
a 2 L p (R d ) and
a
In particular, if  2 (a; M) > d=2 (or more generally  p (a; M) > d=p for
and a is an interpolatory mask with respect to the lattice MZ d ,
then the subdivision scheme associated with mask a and dilation M converges in the
L1 norm and consequently  M
a is a continuous interpolating renable function.
Proof. Let j. Dene a sequence c by
is an interpolatory mask with respect to the lattice MZ d . By [12, Theorem 5.2] and
using Young's inequality, when 1=p
Note that
and
for some proper integers j and k. Therefore,  j+k (c; M;1) 6  p (a;M) q (b;M)
It follows from Theorem 3.1 that  1 (c; M;1) < 1 and therefore, the subdivision
scheme associated with mask c and dilation M converges in the L1 norm. Conse-
quently,  M
c is an interpolating renable function and so its shifts are linearly in-
dependent. Note that b
a
(). Therefore, the shifts of  M
a must be
linearly independent and consequently stable.
Note that - is a dual mask of an interpolatory mask and for any 1 6 q 6 1,
since . The second part of Corollary 3.2 follows directly from the
rst part. The second part can also be proved directly. Since  p (a; M) > d=p, by
Theorem 3.1, we have
for some proper integer k. By Theorem 3.1, we have  1 (a; M;1) < 1. So the
subdivision scheme associated with the mask a and the dilation matrix M converges
in the L1 norm and therefore, we conclude that  M
a is a continuous interpolating
renable function.
Let k be a nonnegative integer. We mention that if  j (a; M; p) <
for some positive integer j, then one can prove that the mask a must satisfy the sum
rules of order at least k respect to the lattice MZ d .
In order to prove Theorem 3.1, we need to introduce the concept of ' p -norm joint
spectral radius. Let A be a nite collection of linear operators on a nite-dimensional
normed vector space V . We denote kAk the operator norm of A which is dened to
be g. For a positive integer n, A n denotes the
Cartesian power of A:
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 15
and for 1 6 p 6 1, we dene
1=p
For any 1 6 p 6 1, the ' p -norm joint spectral radius (see [6, 15, 24] and references
therein on ' p -norm joint spectral radius) of A is dened to be
Let E be a complete set of representatives of the distinct cosets of the quotient group
Z d =MZ d . To relate the quantities  k (a; M; p) to the ' p -norm joint spectral radius, we
introduce the linear operator E) on ' 0 (Z d ) as follows:
2Z d
For
Proof of Theorem 3.1: Let m := j det M j. Let K
and
2Z d
Since a satises the sum rules of order k, by [20, Theorem 5.2],
By [14, Theorem 2.5], we have
Note that
g.
For any ;  2 N d
0 such that jj 6 jj < k, we have
2Z d
(M)
2Z d
2Z d
(M)
Note that
(M)
Since a satises the sum rules of order k, we have
2Z d
(M)
2Z d
2Z d
a(M)
(M)
Han
Thus, for ;  2 N d
0 such that jj 6 jj < k, we have
2Z d
a(M)
(M)
2Z d
[r  -]()
It is evident that
2Z d
[r  -]()
r  -;
Therefore,
2Z d
On the other hand, for any jj 6 jj,
2Z d
(M)
2Z d
2Z d
[r  -]()
is dened in (2.10). Therefore, we have
0 g is a basis for W j , we have
Note that the spectral radius of S(M
min for all j 2 N. Therefore, we
deduce that
holds.
By the denition of the ' p -norm joint spectral radius, using the Holder inequality,
we have
(see [14]) for all 1 6 p 6 q 6 1. This completes the proof.
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 17
4. Some examples of symmetric renable functions. In this section, we
shall give several examples to demonstrate the advantages of the algorithms and
results in Sections 2 and 3 on computing smoothness exponents of symmetric renable
functions.
Example 4.1. Let . The interpolatory mask a for the butter
y scheme
in [9] is supported on [ 3; 3] 2 and is given
Then a satises the sum rules of order 4 and a is invariant under the hexagonal
symmetry group  H . By Proposition 2.2, we have #K  and by computing
the eigenvalues of the 11  11 matrix T in Algorithm 2.1, we have
log
Let  be the renable function with mask a and the dilation matrix 2I 2 . So by Algorithm
2.1,  2 (a; 2I 2 )  2:44077 > 1. Therefore, by Corollary 3.2,  is an interpolating
renable function and  2 2:44077. Note that the matrix size using
the method in [25]
which is much larger than the matrix size
used in Algorithm 2.1.
Example 4.2. Let family of bivariate interpolatory masks RS r (r 2
N) was given in Riemenschneider and Shen [31] (also see Jia [22]) such that RS r is
supported on [1 the sum rules of order 2r with respect to
the lattice 2Z 2 and RS r is invariant under the hexagonal symmetry group  H . Using
the fact that the symbol of RS r has the factor [(1
by taking out some of such factors, Jia and Zhang [25, Theorem 4.1] was able to
compute the Sobolev smoothness exponents of  r for
the renable function with the mask RS r and the dilation matrix 2I 2 . Note that
the mask RS 16 is supported on [ In fact, in order to compute  2 ( 16 ), the
method in [25, Theorem 4.1] has to compute the eigenvalues of two matrices of size
(without factorization, the matrix size used in [25] is 11719). Without using any
factorization, for any mask a which is supported on [ 31; 31] 2 and is invariant under
H , by Algorithm 2.1, we have #K  992. So, to compute  2 ( 16 ), we only need
to compute the eigenvalues of a matrix of size 992.
Han
Example 4.3. Let
be the quincunx dilation matrix. The interpolatory
mask a is supported on [ 3; 3] 2 and is given
Note that a satises the sum rules of order 4 with respect to the quincunx lattice
MZ 2 and a is invariant under the full axes symmetry group  A
2 with respect to the
dilation matrix M . This example was discussed in [25] and belongs to a family of
quincunx interpolatory masks in [16]. Let  be the renable function with the mask
a and dilation matrix M . By Algorithm 2.1, we have #K  A 2
2:44792 > 1. Therefore,  2 2:44792. Note that the matrix to
compute  2 () using method in [25] has size 481 (see [25]) which is much larger than
the size 46 when using Algorithm 2.1. Note that the symbol of a is nonnegative. By
Algorithm 2.5, we have #K  A 2
Therefore, by
Corollary 3.2, 1 using method in [25], the
matrix size is 129 (see [25]) which is much larger than the size 13 in Algorithm 2.5.
Example 4.4. Let
. A family of quincunx interpolatory masks
r (r 2 N) was proposed in [16] such that g r is supported on [ the
sum rules of order 2r with respect to MZ 2 , is an interpolatory mask with respect to
MZ 2 and is invariant under the full axes symmetry group  A
. Note that the mask
in Example 4.3 corresponds to the mask g 2 in this family. Since the symbols of g r
are nonnegative, the L1 smoothness exponents 1 ( r ) were computed in [16] for
r is the renable function with mask g r and the dilation matrix
M . Using Algorithm 2.5, we are able to compute 1 in Table 3.

Table
The L1 (Holder) smoothness exponent of the interpolating renable function r whose mask
is gr .
5.71514 6.21534 6.70431 7.18321
7.65242 8.11171 8.56039 8.99752
A coset by coset (CBC) algorithm was proposed in [12, 16] to construct quincunx
biorthogonal wavelets. Some examples of dual masks of g r , denoted by (g r ) s
k , were
constructed in [16, Theorem 5.2] and some of their Sobolev smoothness exponents were
given in Table 4 of [16]. Note that the dual mask (g r ) s
k is supported on [ k
satises the sum rules of order 2k, has nonnegative symbol and is invariant under the
full axes symmetry group  A 2 . However, in the paper [16] we are unable to complete
the computation in Table 4 in [16] due to the di-culty mentioned in D2 in Section 1.
In fact, to compute  2 (a; M) for a mask supported on [ k; k] 2 , the
set
b;M dened
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 19
in (1.5) is given by
For example, in order to compute  2 ((g 4
set
b;M consists of 16321 points
which is beyond our ability to compute the eigenvalues of a 16321  16321 matrix.
We now can complete the computation using Algorithm 2.1 in Section 2. Note that
the quincunx dilation M here is denoted by Q in Table 4 of [16]. By computation,
and the rest of the computation is given in Table 4.

Table
Computing
by Algorithm 2.1. The result here completes Table 4 of [16].
3.01166 2.92850 2.90251 2.91546
In passing, we mention that if a nitely supported mask a on Z 2 is invariant under
the full axes symmetry group  A
proved in Han [13] that all the renable
functions with the mask a and any of the quincunx dilation matrices
are the same function which is also invariant under the full axes symmetry group  A
.
Also see [3, 4] on quincunx wavelets. For any primal (matrix) mask and any dilation
matrix, the CBC algorithm proposed in [12] can be used to construct dual (matrix)
masks with any preassigned order of sum rules.
Example 4.5. Let
be the dilation matrix in a
3-subdivision
scheme ([28]). The interpolatory mask a is supported on [ 4; 4] 2 and is given
Note that a satises the sum rules of order 6 with respect to the lattice MZ 2 and
a is invariant under the hexagonal symmetry group  H with respect to the dilation
matrix M . By Algorithm 2.1, we have #K
Han
be the renable function with the mask a and the dilation matrix M . Therefore,
by Corollary 3.2,  is a C 2 interpolating renable function and  2
3:28036. By estimate, the matrix
b;M using the method in [25] is greater
than 361 which is much larger than the size 38 when using Algorithm 2.1. Note
that the symbol of a is nonnegative. By Algorithm 2.5, we have #K
Therefore, by Corollary 3.2, 1
Using method in [25], the matrix
a;M is greater than 85 which is much larger
than the size 11 in Algorithm 2.5. Since  2 C 2 , this example gives us a C 2
pinterpolatory subdivision scheme.
In the rest of this section, let us present some examples in dimension three. By
generalizing the proof of [15, Theorem 4.3], we have the following result.
Theorem 4.6. Let d be the dilation matrix. For each positive integer r,
there exists a unique dyadic interpolatory mask g d
r in R d with the following properties:
(a) g d
r is supported on the set f2
(b) g d
r is symmetric about all the coordinate axes;
(c) g d
r satises the sum rules of order 2r with respect to the lattice 2Z d .
By the uniqueness, we see that each g d
r in Theorem 4.6 is invariant under the full
axes symmetry group  A
d . By the uniqueness of g d
r in Theorem 4.6 again, we see that
were the masks given in [8] and g 2
were the masks proposed in [15].
Moreover, the masks g d
r can be obtained via a recursive formula without solving any
equations.
In the following, let us give some examples of the above interpolatory masks in
dimension three. Let
A 3
Clearly, if a is a mask invariant under the group  A
3 , then it is totally determined by
all the coe-cients a();  2 Z 3
A 3
Example 4.7. The coe-cients of the interpolatory mask g 3
2 on the set Z 3
A 3
are
given by
other  2 Z 3
A 3
Then
2 satises the sum rules of order 4 and there are only 81 nonzero coe-cients
in the mask g 3
. Let  be the renable function with the mask g 3
2 and the dilation
matrix 2I 3 . By Algorithm 2.1, we have #K  A 3
Therefore, by Corollary 3.2,  is an interpolating renable function and  2 ()
2:44077. Note
Algorithm 2.1 can
greatly reduce the size of the matrix to compute  2 (g 3
Example 4.8. The coe-cients of the interpolatory mask g 3
3 on the set Z 3
A 3
are
Computing the Smoothness Exponent of a Symmetric Multivariate Renable Function 21
given by
A 3
Then
3 satises the sum rules of order 6 and it has 171 nonzero coe-cients. Let  be
the renable function with the mask g 3
3 and the dilation matrix 2I 3 . By Algorithm 2.1,
we have #K  A 3
1:5. Therefore, by Corollary 3.2,
is an interpolating renable function and  2 ()  3:17513. Note
and #K  A 3
101. Hence, Algorithm 2.1 can greatly reduce the size of the matrix to
compute  2 (g 3
Let  r be the renable function with the mask g 3
r (r 2 N) and the dilation matrix
2I 3 . The Sobolev smoothness exponents of  r are presented in Table 5.
By [15, Theorem 3.3] and [12, Theorem 5.1], we see that g 3
the optimal Sobolev smoothness and optimal order of sum rules with respect to the
support of their masks. In general, the Algorithms 2.1 and 2.5 roughly reduce the
size of the matrix to be 1=(#) of the number of points
in
b;M in (1.5). Note that
# A
Algorithms 2.1 and 2.5 are very useful in computing
the smoothness exponents of symmetric multivariate renable functions.

Table
The Sobolev smoothness exponent of the renable function r whose mask is
2:44077 3:17513 3:79313 4:34408 4:86202
5:36283 5:85293 6:33522 6:81143 7:28260

Acknowledgments

. The author is indebted to Rong-Qing Jia for discussion on
computing smoothness of multivariate renable functions. The author thanks IMA
at University of Minnesota for their hospitality during his visit at IMA in 2001. The
author also thanks the referees for their helpful comments to improve the presentation
of this paper and for suggesting the references [1, 4, 7, 18].



--R

The IGPM Villemoes Machine

Nonseparable bidimensional wavelet bases
A new technique to estimate the regularity of re



Symmetric iterative interpolation processes
A butter y subdivision scheme for surface interpolation with tension control
Sobolev characterization of solutions of dilation equations
Spectral radius formulas for subdivision operators
Analysis and construction of optimal multivariate biorthogonal wavelets with compact support
Symmetry property and construction of wavelets with a general dilation matrix
Multivariate re
Optimal interpolatory subdivision schemes in multidimensional spaces
Quincunx fundamental re
Multivariate re

Dependence relations among the shifts of a multivariate re
Approximation properties of multivariate wavelets
Characterization of smoothness of multivariate re
Interpolatory subdivision schemes induced by box splines
Spectral analysis of the transition operators and its applications to smoothness analysis of wavelets
Smoothness of multiple re
Spectral properties of the transition operator associated to a multivariate re
On the regularity of matrix re
Multivariate matrix re
On the analysis of p 3-subdivision schemes
Stability and orthonormality of multivariate re

Multidimensional interpolatory subdivision schemes
Simple regularity criteria for subdivision schemes
The Sobolev regularity of re
Computing the Sobolev regularity of re
Wavelet analysis of re
Properties of re
--TR

--CTR
Peter Oswald, Designing composite triangular subdivision schemes, Computer Aided Geometric Design, v.22 n.7, p.659-679, October 2005
Avi Zulti , Adi Levin , David Levin , Mina Teicher, C2 subdivision over triangulations with one extraordinary point, Computer Aided Geometric Design, v.23 n.2, p.157-178, February 2006
Bin Han, Compactly supported tight wavelet frames and orthonormal wavelets of exponential decay with a general dilation matrix, Journal of Computational and Applied Mathematics, v.155 n.1, p.43-67, 01 June
Bin Dong , Zuowei Shen, Construction of biorthogonal wavelets from pseudo-splines, Journal of Approximation Theory, v.138 n.2, p.211-231, February 2006
Bin Han, Vector cascade algorithms and refinable function vectors in Sobolev spaces, Journal of Approximation Theory, v.124 n.1, p.44-88, September
multivariate refinable functions;interpolating functions;eigenvalues of matrices;quincunx dilation matrix;smoothness exponent;regularity;symmetry