Semi-regular Dubuc-Deslauriers wavelet tight frames
Alberto Viscardi




alberto.viscardi@unimib.it
Dipartimento di Matematica e Applicazioni, Università degli Studi di Milano-Bicocca, via Roberto Cozzi 55, 20126 Milano, Italy



In this paper, we construct wavelet tight frames with n vanishing moments for Dubuc-Deslauriers 2n-point
semi-regular interpolatory subdivision schemes. Our motivation for this construction is its practical use
for further regularity analysis of wide classes of semi-regular subdivision. Our constructive tools are
local eigenvalue convergence analysis for semi-regular Dubuc-Deslauriers subdivision,
the Unitary Extension Principle and the generalization of the Oblique Extension Principle to the
irregular setting by Chui, He and Stöckler.  This group of authors derives suitable approximation of the inverse 
Gramian for irregular B-spline 
subdivision. Our main contribution is the derivation of the appropriate 
approximation of the inverse Gramian for the semi-regular Dubuc-Deslauriers scaling functions 
ensuring n vanishing moments of the corresponding framelets. 



wavelet tight frame semi-regular subdivision Dubuc-Deslauriers UEP


Semi-regular Dubuc-Deslauriers wavelet tight frames
    Alberto Viscardi
    
===================================================






§ INTRODUCTION



Wavelets, from the seminal works of Meyer <cit.> and Daubechies <cit.>, and wavelet tight frames, from the works of Ron and Shen <cit.> and further contributions in <cit.>, have been a productive research area in the last thirty years, both in theory and applications (see e.g. <cit.>).
One of the standard starting points in the construction of such function systems are refineable functions arising from subdivision schemes, iterative methods for generating curves and surfaces (see e.g. <cit.>). In the stationary uniform setting, i.e. when the subdivision rules are shift-invariant and do not change between the iterations, the so called Unitary Extension Principle (UEP) <cit.> and Oblique Extension Principle (OEP) from <cit.> are used for constructions of wavelet tight frames with one or more vanishing moments. UEP and OEP are based on Fourier techniques and on factorizations of trigonometric polynomials. A generalization of the UEP procedure for nonstationary uniform schemes, when the subdivision rules can change from one iteration to the other, was presented in <cit.>. 
A general setting that also covers the semi-regular case is the one proposed in <cit.> where a matrix formulation of the UEP and OEP is given and examples with nonuniform B-spline schemes are shown.

The main contributions of this paper are twofold: we construct wavelet tight frames with n vanishing moments from semi-regular Dubuc-Deslauriers 2n-point subdivision schemes and, to meet this goal, we also present a detailed convergence analysis of such semi-regular schemes.
The family of semi-regular Dubuc-Deslauriers 2n-point schemes was defined in <cit.>, where, without loss of generality, the initial mesh is of the type 

    𝐭(k) = {[    kh_ℓ if  k<0;        ;    kh_r if  k≥0 ]. ,   h_ℓ, h_r > 0 .

Our convergence analysis of this family uses the local eigenvalue analysis <cit.>.
Our construction of the corresponding wavelet tight frames on the regular part of the mesh uses the UEP and is based on the well known <cit.> link between Dubuc-Deslauriers and Daubechies scaling functions <cit.>. The interpolation and polynomial generation (up to degree 2n-1) properties of the corresponding subdivision schemes ensure n vanishing moments for the framelets. 
On the irregular part of the mesh, in a neighborhood of 𝐭(0), we apply the matrix factorization technique from <cit.>, a generalization of the Oblique Extension Principle (OEP) <cit.> to the irregular setting. Similarly to <cit.>, instead of factorizing a certain global positive semi-definite matrix, we used the regular framelets to reduce the construction on the irregular part of the mesh to a factorization of a (12n-9)×(12n-9) matrix. The corresponding vanishing moment recovery matrix is a suitable approximation to the inverse Gramian.
This approximation to the inverse Gramian guarantees n vanishing moments of the irregular framelets. However, the existence of the underlying scaling functions is ensured only for certain values of h_ℓ/h_r.

The advantage of our construction is in its simplicity. Indeed, with our UEP based construction we obtain regular framelets with n vanishing moments without endeavouring into more tedious computations required by the OEP. Furthermore, compared to the B-spline based wavelet tight frames in <cit.> (the only other semi-regular wavelet tight frame in literature) whose filters have size (number of non-zero coefficients) 3n-1, the corresponding filters obtained from the Dubuc-Deslauriers 2n-point framelets are of size 2n+1. The disadvantage occurs on the irregular part of the mesh, where our filters have possibly larger supports.

The paper is organized as follows. Section <ref> presents notation and recalls some background facts about subdivision and wavelet tight frames. In Section <ref> we introduce the family of semi-regular Dubuc-Deslauriers 2n-point schemes, providing their convergence analysis, and define the corresponding scaling functions. The wavelet tight frame construction for the regular case is presented in Section <ref>. In Section <ref>, we compute the Gramian and present our semi-regular wavelet tight frame construction. To conclude, in Section <ref>, we illustrate our theoretical results by examples for n=1,2. 





§ NOTATION AND BACKGROUND
 


In this section, we recall some basic facts about subdivision and wavelet tight frames.

A stationary subdivision scheme with the bi-infinite subdivision matrix 𝐏: ℓ(ℤ) →ℓ(ℤ) 
maps recursively the initial data 𝐟_0=[𝐟_0(k) :  k ∈ℤ]∈ℓ(ℤ) parametrized by the starting mesh 𝐭 (see (<ref>)) to 
finer sequences 𝐟_j=[𝐟_j(k) :  k ∈ℤ] ∈ℓ(ℤ) parametrized by the meshes 2^-j𝐭, j ∈ℕ by

    𝐟_j = 𝐏^j𝐟_0,   j∈ℕ.


In the regular case, i.e. 𝐭=ℤ, the subdivision matrix 𝐏 is 2-slanted  with 

    𝐏(k,m) = 𝐩(k-2m),  𝐩∈ℓ_0(𝐙),    k,m∈ℤ.

We make use of the trigonometric polynomial (subdivision symbol)

    p(ω) = 1/2∑_k∈ℤ 𝐩(k) e^i2kπω,   ω∈ [0,1),

associated to the mask 𝐩∈ℓ_0(𝐙). The support of the mask 𝐩 is the set of indeces

    (𝐩) = { min{k∈ℤ : 𝐩(k)≠0}, …, max{k∈ℤ : 𝐩(k)≠0} }.


The subdivision scheme is said to be convergent if, for every k∈ℤ, there exists φ_k∈ C^0(ℝ) called basic limit function such that 

    lim_j→∞sup_m ∈ℤ | φ_k(2^-j m)- 𝐟_j(m)|= 0   for  𝐟_0(m)=δ_k(m)= {[         1,       m=k,;         0, otherwise. ].

Equivalently, φ_k must be the uniform limit of the piecewise linear functions that interpolate the data 𝐟_j on the mesh 2^-j𝐭.
A well known necessary condition <cit.> for convergence of subdivision states that 1 is the right eigenvalue of 
𝐏 with algebraic multiplicity one and all other eigenvalues of 𝐏 are in the absolute value
less than 1. In terms of the subdivision symbol, this condition reads as p(0)=1.
The associated eigenvector is 1=[1 :  k∈ℤ]. This implies the partition of unity property

    [ φ_k ]_k∈ℤ^T 1 ≡ 1 .

The basic limit functions satisfy the  refinement equation

    [φ_k(x) : k∈ℤ] = 𝐏^T  [ φ_k(2x) :  k∈ℤ],    x ∈ℝ.

In the regular case, due to (<ref>) and (<ref>), we have φ_k = φ_0(·-k), k∈ℤ
and the refinement equation becomes

    φ_0(ω) = p(ω/2) φ_0(ω/2),   ω∈ [0,1),

with the Fourier transform φ_0 of φ_0 defined by

    φ_0(ω) = ∫_ℝ e^-i2πω x φ_0(x) dx .

As for the semi-regular case, the subdivision matrix 𝐏 can differ from the regular one at the columns whose indeces belong to the set

    ℐ_irr = { k∈ℤ : -max((𝐩))<k<-min((𝐩)) }.

This implies the loss of shift-invariace, i.e. the basic limit functions
{φ_k}_k∈ℐ_irr, which are the ones with 0 in the interior of their support, are no longer
the shifts of any other basic limit function. Nevertheless, each of the functions φ_k, k<min(ℐ_irr), and 
φ_k, k>max(ℐ_irr), are basic limit functions of the corresponding regular subdivision schemes.

If the matrix 

    𝐃 = ( ∫_ℝ  [φ_k(x) :  k∈ℤ] dx )

is positive definite we can define the corresponding scaling functions 

    Φ=[ϕ_k :  k∈ℤ]=𝐃^-1/2  [φ_k :  k∈ℤ]

for which, by (<ref>),

    Φ(x)^T ∫_ℝ Φ(y) dy ≡ 1 ,


The refinement equation (<ref>) holds also for Φ with a renormalized subdivision matrix 

    Φ = 𝐃^-1/2 𝐏^T 𝐃^1/2 Φ(2 ·) .


 A semi-regular wavelet tight frame of L^2(ℝ) is a family Φ∪{Ψ_j :  j∈ℕ} of 
L^2(ℝ) functions  such that


  * Φ generates a Multi Resolution Analysis (MRA), i.e,

    [ {ϕ_k(2^j·)}_k∈ℤ^L^2 ⊂ {ϕ_k(2^j+1·)}_k∈ℤ^L^2,  ∀ j∈ℤ,;                                                     ;                     {0} = ⋂_j∈ℤ {ϕ_k(2^j·)}_k∈ℤ^L^2,;                                                     ;              L^2(ℝ) = ⋃_j∈ℤ {ϕ_k(2^j·)}_k∈ℤ^L^2^L^2, ]


  * there exists a bi-infinite matrix 𝐐 such that


    Ψ_j = 2^j/2 𝐐^T Φ(2^j·),   j∈ℕ,


  * the tight frame property (decomposition) holds, i.e.

    f = ∑_k∈ℤ ⟨ f,ϕ_k⟩ϕ_k + ∑_j∈ℕ ∑_k∈ℤ ⟨ f,ψ_j,k⟩ ψ_j,k ,    f∈ L^2(ℝ).


The functions ϕ_k, k∈ℤ, are called scaling functions and ψ_j,k, j∈ℕ,k∈ℤ are framelets.


 
We say that a wavelet tight frame Φ∪{Ψ_j :  j∈ℕ} has v∈ℕ vanishing moments if

    ∫_ℝ x^α Ψ_j(x) dx = 0,  α∈{0,…,v-1},     j∈ℕ.







§ DUBUC-DESLAURIERS 2N-POINT SUBDIVISION SCHEMES AND THEIR SCALING FUNCTIONS
 


The elements of the family of Dubuc-Deslauriers schemes, introduced in <cit.> in the regular case, are defined
in the semi-regular setting in <cit.> as solutions of the following interpolation problems. Let n∈ℕ and define the mesh 𝐭 as in (<ref>). We require that the subdivision matrix
𝐏 is interpolatory and maps any data π(𝐭), π∈Π_2n-1, into
π(𝐭/2)=𝐏π(𝐭) by using linear combinations of the 2n neighbouring points, i.e.


  * 𝐏(2k,k)=1, k∈ℤ,

  * the entries 𝐏_k=[𝐏(2k+1,j)  :  j=k-n+1, …, k+n], k ∈ℤ,
 satisfy

    𝐏_k  [             1      𝐭(k-n+1)             ⋯ 𝐭(k-n+1)^2n-1;             1      𝐭(k-n+2)             ⋯ 𝐭(k-n+2)^2n-1;             ⋮             ⋮             ⋱             ⋮;             1        𝐭(k+n)             ⋯   𝐭(k+n)^2n-1 ]
    = [                1        𝐭(2k+1)/2                ⋯ (𝐭(2k+1)/2)^2n-1 ].


  * all other entries of 𝐏 are equal to zero.



Let n∈ℕ and 𝐏 be the subdivision matrix constructed in 1.-3. on the mesh 𝐭. Then


  (i) 1 is a simple eigenvalue of 𝐏 associated  to the right eigenvector 1 and all other
eigenvalues of 𝐏 are less than 1 in the absolute value;

  (ii) the subdivision scheme with subdivision matrix 𝐏 converges.




Part (i): Let n ∈ℕ and ℐ={1-2n,…,2n-1}. By <cit.>, all non-zero eigenvalues of 𝐏 are uniquely determined by the eigenvalues
of its finite section, the square matrix 𝐏=(𝐏(m,k))_m,k ∈ℐ.  By
construction, due to the interpolation property, 𝐏1=1. We show next, that λ∈ℂ∖{0,1} with 𝐏𝐯=λ𝐯, 𝐯∈ℂ^4n-3∖{0}, must satisfy |λ|<1.
The proof is by contradiction, we assume that |λ| ≥ 1. Note first that 𝐏(0,0)=1 and by step 3. of the construction above, we get 𝐯(0)=λ 𝐯(0), thus, 𝐯(0)=0. Step 1. of the construction
forces 𝐯(k)=λ 𝐯(2k) for k,2k ∈ℐ. To determine the odd entries of 𝐯, let m ∈ℐ be odd and consider the polynomial interpolation problem with the pairwise distinct knots
𝐭(j) and values 𝐯(j) for j ∈{m+1/2-n, …, n+m+1/2}.
This interpolation problem possesses a unique solution, possibly complex-valued, interpolation polynomial π∈Π_2n-1. Therefore, by the interpolation property of 𝐏, we have

    λ π(𝐭(m) )  = λ 𝐯(m) = (𝐏 𝐯)(m)  = π(𝐭(m)/2).
 
Iterating we obtain

    lim_r →∞ |λ|^r  |π( 𝐭(m))| = lim_r →∞| π(𝐭(m)/2^r) | = |π(0)| = |𝐯(0)| = 0,

which leads to a contradiction: for |λ|=1, we have 𝐯(m)=π(𝐭(m))=0 or, for |λ|>1,  the identity (<ref>) is violated. It is left to show that λ=1 is simple. The proof is by contradiction. W.l.o.g. we assume that 1 has an algebraic multiplicity 2. Note that δ^T 𝐏=
δ^T, where δ(0)=1 and its other entries are equal to zero and define  
𝐁=𝐏-1δ^T. Then 𝐁 has a simple eigenvalue 1 with 𝐁 𝐯=𝐯, 𝐯≠0. By construction 𝐯(0)=0, thus 𝐁𝐯=𝐏𝐯. Following
a similar argument as above we arrive at the contradiction 𝐯=0.

Part (ii): To prove the convergence of the scheme, due to <cit.>, it suffices to prove the continuity of the basic limit functions in 0, i.e. 

    |𝐟_j,k(0)-𝐟_j,k(1)|  j→∞⟶ 0,   and   |𝐟_j,k(0)-𝐟_j,k(-1)| j→∞⟶ 0

for 𝐟_j,k = 𝐏^j δ_k, k∈ℤ. Or, equivalently, we show that

    |𝐟_j,k(0) - 𝐟_j,k(1)| = |[ 0,…,0,1_0-th,-1,0,…,0 ] 𝐏^j δ_k| → 0

and, similarly, for the other difference in (<ref>). The claim follows then by part (i), together with steps 1. and 3. of the construction, which imply that 𝐏^j δ_k→δ_k(0) 1.


The structure of 𝐏 implies that ([𝐏(m,k) : m∈ℤ])={2k-2n+1,…,2k+2n-1}
and, thus, by <cit.>, the corresponding basic limit functions satisfy

    (φ_k)=[𝐭(k+1-2n),𝐭(k+2n-1)],    k ∈ℤ.

The construction of 𝐏 in 1.-3. does not only unify regular and the semi-regular cases, but also ensures that
the corresponding subdivision schemes are interpolatory and reproduce polynomials up to degree 2n-1. In particular,
the convergence and the interpolation property imply that the functions {φ_k  :   k ∈ℤ} are linearly independent 
and, thus, the representation

    x^α = ∑_k∈ℤ 𝐭^α(k) φ_k(x) ,    x∈ℝ,
    	  α∈{0,…,2n-1},

is unique. The existence of the corresponding scaling functions ϕ_k in (<ref>)  depends on the choice of h_ℓ and h_r in (<ref>),
which ensures that the integrals of the basic limit functions appearing in (<ref>) are positive,
see Section <ref>. Under this assumption, the corresponding scaling functions ϕ_k in the column vector Φ=[ϕ_k :  k∈ℤ] in (<ref>) inherit the polynomial reproduction property in (<ref>) and we have

    x^α = Φ^T(x)  𝐜_α,  𝐜_α=𝐃^1/2 𝐭^α,
       α∈{0,…,2n-1} .

Furthermore, note that, in the semi-regular case,
(<ref>) becomes

    ℐ_irr = {2-2n,…,2n-2}  with  |ℐ_irr| = 4n-3,

and, denoted with Φ_ℓ and Φ_r the vectors of scaling functions on the regular meshes 𝐭_ℓ=h_ℓℤ and 𝐭_r=h_rℤ respectively, we have

    𝐈_ℓ Φ = 𝐈_ℓ Φ_ℓ   and   𝐈_r Φ = 𝐈_r Φ_r,

where

    𝐈_ℓ(j,k) = {[            1, if  j=k<2-2n,;              ;            0,    otherwise, ]. 
       and   𝐈_r(j,k) = {[          1, if j=k>2n-2;            ;          0,  otherwise. ].





§ REGULAR CASE : UNITARY EXTENSION PRINCIPLE
 


In the regular case, our wavelet tight frame construction, see Proposition <ref>, relies on the well known Unitary Extension Principle <cit.>. Note that the interpolation property of Dubuc-Deslauriers 2n-point schemes guarantees
n vanishing moments for the corresponding framelets, higher than it is usually expected for a general UEP based construction. 
Thus, in the regular setting, we avoid using the more general and demanding Oblique Extension Principle <cit.>.
However, in the next section, the Oblique Extension Principle appears, see Remark <ref>, as a special case of the 
irregular framework presented in <cit.>.

 
Let p(ω) be the symbol of a convergent subdivision scheme. If the trigonometric polynomials
q_j(ω)=1/2∑_k∈ℤ𝐪_j(k)  e^i2 k πω, j=1, …, J,
satisfy

    {[         p(ω)p(ω) + ∑_j=1^J q_j(ω)q_j(ω) = 1; p(ω)p(ω-1/2) + ∑_j=1^J q_j(ω)q_j(ω-1/2) = 0;                                             ].,  ω∈[0,1),

then the bi-infinite matrix 𝐐 with entries 𝐐(k,m+j-1)=2^-1/2𝐪_j(k-2m),
k,m∈ℤ, j=1, …, J,
defines a wavelet tight frame  in (<ref>).


 We call the trigonometric polynomials in Theorem <ref> framelet symbols.
The number v ∈ℕ of the vanishing moments of the corresponding wavelet tight frame is given by (see e.g. <cit.>)

    v=min_j∈ J{ μ_j ∈ℕ :   q^(k)_j(0)=0,  k=0,…, μ_j-1  and  q^(μ_j)_j(0)≠0   }.



Theorem <ref> holds, in particular, for orthonormal Daubechies wavelets. Indeed, the Daubechies 2n-tap scheme <cit.> has the scaling symbol d(ω) with coefficients 𝐝 supported on {1-2n,…,0} which satisfies (<ref>) with

    q_d(ω)=q_1(ω) = e^-i2π (2n-1) ω d(ω-1/2)  and   v=n,    n∈ℕ.

Daubechies wavelets are closely connected to the Dubuc-Deslauriers subdivision schemes, see <cit.>. Indeed, the
symbol d(ω) of the Daubechies 2n-tap scheme satisfies

    p(ω) = d(ω) d(ω),   ω∈ [0,1),

where p(ω) is the symbol of the Dubuc-Deslauriers 2n-point scheme.
The identity (<ref>), together with Theorem <ref>, lead to our UEP construction
of Dubuc-Deslauriers wavelet tight frame in Proposition <ref>.

 
Let n∈ℕ, d and p be the symbols of the Daubechies 2n-tap scheme and the Dubuc-Deslauriers 2n-point scheme, respectively. Then

    q_1(ω) = √(2) e^i2π(2n-1)ωd(ω) d(ω-1/2)   and   q_2(ω) = d(ω-1/2) d(ω-1/2),   ω∈ [0,1),

define a wavelet tight frame (with n vanishing moments) for p.



Note that the convergence of the subdivision associated to d(ω) implies the convergence of the subdivision
associated to d(ω). Moreover, by conjugating the second identity in (<ref>), we see that the UEP identities in (<ref>) are also satisfied by d(ω). Thus, applying Theorem <ref>
to d and d, multiplying the resulting identities and using (<ref>), we obtain a wavelet tight frame for p=dd with n vanishing moments and consisting of framelets

    d(ω) q_d(ω),   d(ω) q_d(ω),  and   q_d(ω) q_d(ω).

To reduce the number of frame generators we take a closer look to the structure of these framelets. Indeed, the UEP identities  (<ref>) and (<ref>) yield

    [                                                                                                1                                                                                                =                                      ( d(ω) d(ω) + q_d(ω) q_d(ω) ) ( d(ω) d(ω) + q_d(ω) q_d(ω) );                                                                                                 ;                                                                                                                                                                                                 = (d(ω) d(ω)) (d(ω) d(ω)) + √(2) d(ω) q_d(ω) (√(2) d(ω) q_d(ω)) + (q_d(ω) q_d(ω)) (q_d(ω) q_d(ω)),;                                                                                                 ;                                                                                                 ;                                                                                                0                                                                                                =                      ( d(ω) d(ω-1/2) + q_d(ω) q_d(ω-1/2) ) ( d(ω) d(ω-1/2) + q_d(ω) q_d(ω-1/2) );                                                                                                 ;                                                                                                                                                                                                 =                        (d(ω) d(ω)) (d(ω-1/2) d(ω-1/2)) + (q_d(ω) q_d(ω)) (q_d(ω-1/2) q_d(ω-1/2));                                                                                                 ;                                                                                                                                                                                                                 + d(ω) q_d(ω) (d(ω-1/2) q_d(ω-1/2)) + d(ω) q_d(ω) d(ω-1/2) q_d(ω-1/2),   ω∈ [0,1). ]

From (<ref>), we have

    q_d(ω) d(ω-1/2) = q_d(ω) d(ω-1/2),   ω∈ [0,1).

Moreover, the periodicity of the symbols implies

    d(ω) q_d(ω-1/2) = d(ω) q_d(ω-1/2),   ω∈ [0,1).

Next, we rewrite the last term of the second identity in (<ref>)

    d(ω) q_d(ω) d(ω-1/2) q_d(ω-1/2) = d(ω) q_d(ω) (d(ω-1/2) q_d(ω-1/2)),   ω∈ [0,1),

obtaining the framelets q_1(ω)=√(2)d(ω)q_d(ω) and
q_2(ω)=q_d(ω)q_d(ω). The claim follows by (<ref>).


This result is equivalent to the one in <cit.>. The proof presented here, however, 
can be easily adapted to get the following more general result.


Let a and p be trigonometric polynomials that satisfy (<ref>) with
b_j, j=1, …, J_a and q_j, j=1, …, J_p, respectively.
Then the product ap satisfies (<ref>) with

    { p  b_j:  j=1, …,J_a } ∪ { a  q_j  :  j=1, …, J_p} ∪ {q_j   b_k   : j=1,…,J_p,  k=1,…,J_a }.

Moreover, if the schemes associated to a, p and ap are convergent and the corresponding framelets b_j, j=1,…,J_a and q_j, j=1, …,J_p have v_a and v_p vanishing moments, respectively, then the wavelet tight frame for the
trigonometric polynomial a p
has v=min{v_a,v_p} vanishing moments.



Theorem <ref> can be used to obtain explicit algebraic expressions for framelets with 1 vanishing moment
for the family of B-spline schemes, since the B-spline symbols are products of Haar symbols. The same trick as in the proof
of Proposition <ref>, allows us to reduce the number of framelets to the order of the corresponding B-spline.
This is an alternative, more straightforward way for obtaining the framelets in <cit.> in the regular case.








§ SEMI-REGULAR CASE : MATRIX UNITARY EXTENSION PRINCIPLE
 


Let n∈ℕ and h_ℓ,h_r>0. In this section,  we construct a semi-regular wavelet tight frame from the column vector 
Φ=[ϕ_k : k∈ℤ]
of scaling functions ϕ_k generated by the semi-regular Dubuc-Deslauriers 2n-point scheme on the mesh 𝐭 in (<ref>). 
This semi-regular wavelet tight frame has n vanishing moments and its construction is based on the time domain characterization in
<cit.>. To be able to apply the result in <cit.>, we check  first certain properties of Φ, see subsection
<ref>. The actual construction of the corresponding wavelet tight frame and its properties are presented in 
subsection <ref>.





 §.§ Properties of Dubuc-Deslauriers scaling functions Φ
 





  (i) Φ is a Riesz basis for (Φ)^L^2, i.e. there exist 0<A≤ B< ∞ such that

    A 𝐟^2_ℓ^2 ≤ Φ^T𝐟 ^2_L^2 ≤ B 𝐟^2_ℓ^2,  𝐟∈ℓ^2(ℤ).


  (ii) Φ is uniformly bounded, i.e. sup_k∈ℤϕ_k_L^∞< ∞.

  (iii) Φ is strictly local, i.e. sup_k∈ℤ|(ϕ_k)|< ∞ and there exists s ∈ℕ
 such that, for every index set ℐ⊂ℤ with |ℐ|>s,

    ⋂_k∈ℐ (ϕ_k) = ∅.


  (iv) lim_j→∞sup_k∈ℤ|ϕ_k(2^j ·)|=0. 




(i): Let B_ℓ >0 and B_r >0 be the Riesz constants for the regular scaling functions Φ_ℓ and 
Φ_r (<ref>), respectively. Then, for every 𝐟∈ℓ_2(ℤ),

    Φ^T𝐟^2_L^2 =   (∑_k<min{ℐ_irr} + ∑_k∈ℐ_irr + ∑_k>max{ℐ_irr}) 𝐟(k)ϕ_k ^2_L^2≤(B_ℓ + max_k∈ℐ_irrϕ_k_L^2^2 + B_r) 𝐟^2_ℓ^2 .

The existence of A>0 follows from the linear independence of functions in Φ. 

Part (ii) follows directly, due to the continuity and compact support of the functions in Φ.

(iii): For every k∈ℤ, by (<ref>) and by the definition of 𝐭, we have

    sup_k∈ℤ|(ϕ_k)| = max{h_ℓ,h_r}(4n-2) < ∞.
 
Thus, choose s=4n-2. 
 
The claim (iv) follows directly from (iii).


Lemma <ref> shows an important property of the bi-infinite Gramian matrix (of Φ) 

    𝐆_Φ = ∫_ℝ Φ(x) Φ(x)^T dx .


 For 𝐜_α= 𝐃^1/2𝐭^α, α∈{0,…,2n-1},
we have

    𝐆_Φ^-1 𝐦_α = 𝐜_α,   α∈{0,…,2n-1},

where 𝐦_α are the moments of Φ, i.e.

    𝐦_α = ∫_ℝ x^α Φ(x) dx.



By <cit.>, part (i) of Lemma <ref> guarantees that 𝐆_Φ is a bounded 
invertible operator on ℓ^2(ℤ) with the bounded inverse.
By (<ref>), we get

    𝐆_Φ 𝐜_α = ∫_ℝ Φ(x) Φ(x)^T 𝐜_α dx = ∫_ℝ x^α Φ(x) dx = 𝐦_α,   α∈{0,…,2n-1}.



For computation of the moments in section <ref>, by <cit.>, we first determine 𝐆_Φ
by solving the system in (<ref>). 
Theorem <ref> gives a formal justification for the algorithm presented in <cit.> for B-splines. 

 
Let

    𝐆 = ∫_ℝ [φ_k(x) : k∈ℤ] [φ_k(x) : k∈ℤ]^T dx.

Assume that [𝐆(k,m)]_k,m∉ℐ_irr are given.
The rest of the elements of  𝐆 are uniquely determined from the linear system 
of equations given by

    𝐆 = 1/2 𝐏^T 𝐆 𝐏.

Moreover 

    𝐆_Φ = 𝐃^-1/2 𝐆 𝐃^-1/2,  where  𝐃 = (𝐆·1).




Observe first that 𝐆 satisfies (<ref>). Indeed, using the refinement equation (<ref>) and the substitution y=2x, we have

    [                                                             𝐆                                                             =                        ∫_ℝ [φ_k(x) : k∈ℤ] [φ_k(x) : k∈ℤ]^T dx;                                                              ;                                                                                                                           = 𝐏^T ∫_ℝ [φ_k(2x) : k∈ℤ] [φ_k(2x) : k∈ℤ]^T dx 𝐏 = 1/2 𝐏^T 𝐆 𝐏. ]

Suppose next that there exist another solution to (<ref>), i.e. another bi-infinite matrix  𝐆. 
Then 𝐇 = 𝐆- 𝐆 is non-zero and, by definition of I_irr, has all its non-zero entries in the block
(𝐇_i,j)_5-6n ≤ i,j ≤ 6n-5. By linearity, 𝐇 also satisfies (<ref>). Define
the index sets

    ℐ_𝐇={ k∈ℤ : ∃ m∈ℤ  with  𝐇(m,k)≠0   or  𝐇(k,m)≠0 },   ℐ_𝐏={ k∈ℤ : 𝐏(k,k)≠ 0 },

and the set ℐ as the intersection of ℤ with the convex hull of 
ℐ_𝐇∪ℐ_𝐏. Furthermore, define the square matrices
𝐇=[𝐇(i,j)]_i,j ∈ℐ  and  𝐏=[𝐏(i,j)]_i,j ∈ℐ.
We obtain an equivalent finite version of (<ref>)

    𝐇 = 1/2 𝐏^T 𝐇 𝐏.

Due to  𝐇≢0, there exist k,m ∈ℕ such that 𝐇(k,m) ≠ 0. Consider the canonical unit vectors 𝐞_k and 𝐞_m of ℝ^|ℐ|. Iterating (<ref>), we have 

    0 ≠ 𝐇(k,m)  = 𝐞_k^T 𝐇 𝐞_m = 1/2^j 𝐞_k^T (𝐏^T)^j 𝐇 (𝐏)^j 𝐞_m,    j ∈ℕ.

Since 𝐏 is constructed to contain all the corresponding non-zero elements in the rows of 𝐏, which is possible due to its 2-slanted nature, these two matrices have the same right eigenvalues. Since 𝐏 has largest eigenvalue 1 in absolute value with multiplicity one (see e.g. <cit.>), 𝐞_k^T (𝐏^T)^j_2  ≤ C < ∞ for all j∈ℕ and, therefore,

    0 < | 𝐞_k^T 𝐇 𝐞_m | ≤ | 1/2^j 𝐞_k^T (𝐏^T)^j 𝐇 (𝐏)^j 𝐞_m | ≤ 1/2^j C^2 𝐇_2  j → +∞⟶ 0,

which leads to a contradiction for the non-uniqueness of 𝐆. Identity (<ref>) follows directly from (<ref>) and (<ref>).



(i) The assumption about [𝐆(k,m)]_k,m∉ℐ_irr is not restrictive. For the computation of such scalar products one can use <cit.>, with the correct necessary renormalization on h_ℓℤ and h_rℤ. 

(ii) Thanks to Theorem <ref> and Lemma <ref> we are able to compute all the vectors 𝐜_α and 𝐦_α, for every α∈{0,…,2n-1}.

(iii) The result of Theorem <ref> can be generalized to the case of two different semi-regular subdivision with subdivision matrices 𝐀, 𝐁 and basic limit functions [α_k  : k∈ℤ], [β_k  : k∈ℤ] respectively, to compute ∫_ℝ[α_k(x)  : k∈ℤ] [β_k(x)  : k∈ℤ]^Tdx.
This is a crucial tool for applications. 






 §.§ Semi-regular Dubuc-Deslauriers wavelet tight frame
 


We start our construction of semi-regular Dubuc-Deslauriers (2n-point) wavelet tight frames by building a bi-infinite matrix 𝐒, see Algorithm 1. In Proposition <ref> and Conjecture <ref>,  we list and analyze the properties of 
𝐒 that, by <cit.>, guarantee the wavelet tight frame property of the families in (<ref>).
Proposition <ref> ensures that the wavelet tight frame in (<ref>) has n vanishing moments.


Algorithm 1:


  * Define the (4n-3)× n matrix 𝐂 = [   [𝐜_0(k)]_k∈{2-2n,…,2n-2}                          |                          …                          | [𝐜_n-1(k)]_k∈{2-2n,…,2n-2} ],
where the bi-infinite column vectors 𝐜_α, α=0, …, n-1, are defined in (<ref>);

  * Compute the QR factorization 𝐂=𝐎𝐔
with orthogonal 𝐎∈ℝ^(4n-3)× (4n-3) and upper triangular 𝐔∈ℝ^(4n-3)× n;

  * Define 𝐒=𝐈 and, if h_ℓ≠ h_r, modify

    𝐒_irr := [𝐒(k,m)]_k,m∈ℐ_irr =𝐎 𝐎^T,     𝐎=[ [𝐎(k,1)]_k∈ℐ_irr | … | [𝐎(k,n)]_k∈ℐ_irr ].



The matrix 𝐒 from Algorithm 1 defines a kernel Φ(x)^T𝐒Φ(y) with desired approximation properties.

   Let  𝐒 be defined by Algorithm 1. Then, for all f∈ L^2(ℝ),


  (i) ∃ C>0 : ∫_ℝ^2 f(x) Φ(x)^T 𝐒 Φ(y) f(y) dx dy ≤ C f^2_L^2,

  (ii) 2^j ∫_ℝ^2 f(x) Φ(2^jx)^T 𝐒 Φ(2^jy) f(y) dx dy ⟶ {[         0,  if  j→-∞,;   f^2_L^2, if   j→+∞. ].



 Part (i): Recall that the regular elements in Φ are the elements of Φ_ℓ and Φ_r in (<ref>). 
For such regular families 
of scaling functions the characterization in <cit.> with 𝐒=𝐈 implies the existence
of  C_ℓ>0 and C_r>0, respectively, such that, for all f∈ L^2(ℝ),

    max{ ∫_ℝ^2 f(x) Φ_ℓ(x)^T Φ_ℓ(y) f(y) dx dy, ∫_ℝ^2 f(x) Φ_r(x)^T Φ_r(y) f(y) dx dy } ≤ max{C_ℓ,C_r} f^2_L^2.

Decompose the bi-infinite identity 𝐈 = 𝐈_ℓ + 𝐈_irr +𝐈_r with 

    𝐈_ℓ(j,j)={[         1,    j<1-2n,;         0, otherwise, ].   and  𝐈_r(j,j)={[         1,    j>2n-1,;         0, otherwise. ].

Then, for all f ∈ L^2(ℝ), by (<ref>) and the Cauchy-Schwarz inequality, we have

    [    ∫_ℝ^2 f(x) Φ(x)^T 𝐒 Φ(y) f(y) dx dy  = ∫_ℝ^2 f(x) Φ(x)^T ( 𝐈_ℓ + 𝐈_irr 𝐒 𝐈_irr + 𝐈_r ) Φ(y) f(y) dx dy;                                                                                                          ; ≤ max{C_ℓ,C_r} f^2_L^2 + ∑_j=2-2n^2n-2 ∑_k=2-2n^2n-2 |𝐒(j,k)| |∫_ℝ f(x) ϕ_j(x) dx | |∫_ℝ ϕ_k(y) f(y) dy |;                                                                                                          ;                                         ≤ ( max{C_ℓ,C_r} + (4n-3) 𝐒_irr_∞ max_k∈ℐ_irrϕ_k^2_L^2 ) f^2_L^2. ]

Part (ii): Using again 𝐈 = 𝐈_ℓ + 𝐈_irr +𝐈_r and (<ref>), for every
f∈ L^2(ℝ), we get

    [          f - 2^j ∫_ℝ f(x) Φ(2^jx)^T 𝐒 Φ(2^j·) dx ^2_L^2 ≤  f χ_(-∞,0) - 2^j ∫_-∞^0 f(x) Φ_ℓ(2^jx)^T Φ_ℓ(2^j·) dx^2_L^2 +;                                                                                                                         ; +  2^j ∫_ℝ f(x) Φ(2^jx)^T 𝐈_irr 𝐒 𝐈_irr Φ(2^j·) dx ^2_L^2 +  f  χ_(0,∞) - 2^j ∫_0^∞ f(x) Φ_r(2^jx)^T Φ_r(2^j·) dx ^2_L^2;                                                                                                                         ;                                                                                                    =: γ_ℓ + γ_irr + γ_r. ]

The indices of the non-zero elements of 𝐈_irr 𝐒 𝐈_irr belong to the set 
ℐ_irr×ℐ_irr in  (<ref>), thus, 

    ⋃_k∈ℐ_irr (ϕ_k)=:[a,b],    -∞<a≤ b < ∞.

The continuity of Φ and the Cauchy-Schwarz inequality yield

    γ_irr = 2^2j∫_[a,b]/2^j | ∫_[a,b]/2^j f(x) Φ(2^jx)^T 𝐈_irr 𝐒 𝐈_irr Φ(2^jy) dx |^2 dy 
     ≤  C f^2_L^2([a,b]/2^j)

with the constant C=(b-a)^2 Φ^T 𝐈_irr 𝐒 𝐈_irr Φ^2_L^∞. Thus, γ_irr
goes to zero as j goes to ∞. Moreover, since fχ_(-∞,0) and fχ_(0,∞) belong to L^2(ℝ), by the argument 
from the regular case, both  γ_ℓ and γ_r go to zero as j goes to ∞. 

On the other hand, for the sequence 

    𝐟_j = 2^j/2∫_ℝ f(x) Φ(2^jx) dx,    f∈ L^2(ℝ),    j∈ℤ,

with [a_k,b_k]=supp(ϕ_k), k ∈ℤ, by Lemma <ref> part (iii), we have

    𝐟_j^2_ℓ^2 ≤ ∑_k∈ℤ ∫_[a_k,b_k]/2^j |f(x)|^2 dx ∫_ℝ |ϕ_k(2^j x)|^2 2^j dx 
     ≤   s f^2_L^2 max_k∈ℤϕ_k^2_L^2 < ∞.

Thus,  𝐟_j ∈ℓ^2(ℤ) and, consequently, 𝐒 𝐟_j ∈ℓ^2(ℤ). Hence, by Lemma <ref> part (i),
we have

    2^j ∫_ℝ f(x) Φ(2^jx)^T 𝐒 Φ(2^j·) dx = 2^j/2 𝐟_j^T 𝐒 Φ(2^j·) ∈ (Φ(2^j·))^L^2.
 
Due to the MRA structure (<ref>), we get lim_j→ -∞ 2^j/2 𝐟_j^T 𝐒 Φ(2^j·) =0.
Therefore, the claim follows due to the continuity of the inner product.


Examples in section <ref> and  numerical evidence 
for n=3,…,8 with different h_ℓ,h_r>0 (defining the mesh 𝐭) lead to the following conjecture.

  Let  𝐒 be defined by Algorithm 1, 𝐏 and 𝐃 as in
section <ref> and 𝐩, 𝐪_1 and 𝐪_2 as in Proposition <ref>.

 
  (i) For

    𝐑=𝐒 -1/2 𝐃^1/2 𝐏 𝐃^-1/2𝐒 𝐃^-1/2 𝐏^T 𝐃^1/2,

and  𝐑_k, k∉ℐ_irr with entries

    𝐑_k(u,v)=𝐩𝐩^T(u-2k,v-2k) +𝐪_1𝐪_1^T (u-2k,v-2k)+
    𝐪_2𝐪_2^T (u-2k,v-2k),    u,v∈ℤ,

the matrix

    𝐑_irr=𝐑 - 1/2∑_k∉ℐ_irr 𝐑_k

 is positive semi-definite.

  (ii) For all α∈{0,…,n-1}, the bi-infinite vectors 𝐜_α in (<ref>) and the
moments
𝐦_α in (<ref>) satisfy 

    𝐒 𝐦_α = 𝐜_α.




 Note that the requirement that 𝐑_irr is positive semi-definite is stronger than the positive semi-definedness
of 𝐑, which is one of the sufficient conditions in <cit.> that ensures the existence of the 
wavelet tight frame

    Ψ_j=2^j/2𝐐^T Φ(2^j·),   𝐑 = 𝐐 𝐐^T,   j∈ℕ

Here indeed we also get an explicit form 

    𝐐 = [[              … 𝐐_min(ℐ_irr)-1          𝐐_irr 𝐐_max(ℐ_irr)+1              … ]]

with 𝐑_irr=𝐐_irr𝐐_irr^T and 𝐑_k=𝐐_k𝐐_k^T for 
k ∉ℐ_irr.


Apart from Examples in section <ref> and  numerical evidence 
for n=3,…,8, there are other facts that support Conjecture <ref>.

  
(i) In the regular case Conjecture <ref> is well known. Indeeed, the characterization in 
<cit.> is also valid and the construction in Proposition <ref> is one particular factorization 
of 𝐑 in (<ref>)  with 𝐒=𝐈. 
Indeed, (<ref>) is equivalent to

    {[   [ e^i2kπω : k∈ℤ]^T ( 1/2𝐩𝐩^T + 1/2∑_j=1^J𝐪_j𝐪_j^T ) [ e^-i2kπω : k∈ℤ] =  2,; [ e^i2kπω : k∈ℤ]^T ( 1/2𝐩𝐩^T + 1/2∑_j=1^I𝐪_j𝐪_j^T ) [(-1)^k e^i2kπω : k∈ℤ]=0, ].   ω∈ [0,1).

The identity (<ref>), due to 𝐭=ℤ, becomes

    𝐑_irr=𝐑-1/2∑_k∈ℤ 𝐑_k=0.

Moreover, in the regular case, by <cit.> and Proposition <ref>, 
we have

    𝐦_α = 𝐜_α,  α∈{0,…,n-1}.


(ii) In the irregular case,  due to the special structure of 𝐒 and (<ref>) from the regular case, 
the identity (<ref>) reduces to an identity for certain finite matrices. For 𝐦_α in (<ref>) and 𝐜_α in (<ref>), α=0,…,n-1, define 

    𝐌=[[𝐦_0(k)]_k∈ℐ_irr|…|[𝐦_n-1(k)]_k∈ℐ_irr]  and  𝐂=[[𝐜_0(k)]_k∈ℐ_irr|…|[𝐜_n-1(k)]_k∈ℐ_irr].

Then the irregular part of (<ref>) becomes
𝐒_irr𝐌 =𝐂, which implies

    𝐌^T 𝐂 = 𝐌^T 𝐒_irr 𝐌.

Thus, for (<ref>) to hold the matrix 𝐌^T 𝐂 must be symmetric. 
Indeed, for every α,β∈{0,…,n-1}, by (<ref>), we get

    [ 0 = x^αΦ^T 𝐜_β-𝐜_α^T Φ x^β =  [x^αϕ_k(x)]^T_k∈ℐ_irr [𝐜_β(k)]_k∈ℐ_irr 
    - [𝐜_α(k)]_k∈ℐ_irr^T [x^βϕ_k(x)]_k∈ℐ_irr;                                                                                                               ;                                                     + ∑_k∉ℐ_irr(𝐜_β(k)   x^αϕ_k(x)-𝐜_α(k)x^βϕ_k(x) ),
       x ∈ℝ. ]

Integrating both sides of the above identity and using (<ref>) for the summation over k∉ℐ_irr, we obtain

    [                                                                           (𝐌^T𝐂)(α,β)-(𝐌^T 𝐂)(β,α)c =;                                                                                                      ; =  [𝐦_α(k)]_k∈ℐ_irr^T   [𝐜_β(k)]_k∈ℐ_irr - [𝐜_α(k)]_k∈ℐ_irr^T  [𝐦_β(k)]_k∈ℐ_irr=0,     α,β∈{0,…,n-1}. ]

We strongly believe  that part (ii) of Conjecture <ref> is due to some special, intriguing property of the Dubuc-Deslauriers schemes.


Furthermore, Lemma <ref> and Conjecture <ref> part (ii) are sufficient to ensure the higher number of vanishing moments
of framelets in (<ref>) without additional assumptions <cit.> on the existence of the anti-difference schemes. Proposition <ref> shows that part (i) of Conjecture <ref> is sufficient to guarantee n vanishing moments for Dubuc-Deslauriers framelets in (<ref>). 

 
Let 𝐏 be the subdivision matrix of a convergent Dubuc-Deslauriers 2n-point semi-regular scheme. If 𝐑_irr in
(<ref>) is positive semi-definite, then the framelets Ψ in (<ref>) satisfy

    ∫_ℝ Ψ_j(x)  x^α dx = 0,   α∈{0,…,n-1}, j∈ℕ.


 Let α∈{0,…,n-1}. We start by proving that the moments 𝐦_α in (<ref>) and 
𝐜_α in (<ref>) satisfy

    𝐦_α^T (𝐃/2)^1/2𝐏𝐃^-1/2 = 2^α+1/2𝐦_α^T    and    (𝐃/2)^1/2𝐏𝐃^-1/2𝐜_α = 2^-(α+1/2)𝐜_α

with 𝐃 in (<ref>).
From (<ref>), using the refinement equation (<ref>), we obtain

    2^α+1/2𝐦_α^T   =   2^α+1/2 ∫_ℝ x^α Φ^T(x) dx =
      2^α+1/2 ∫_ℝ x^α Φ^T(2x) dx 𝐃^1/2 𝐏 𝐃^-1/2
    
       =   1/√(2) ∫_ℝ y^α Φ^T(y) dy 𝐃^1/2 𝐏 𝐃^-1/2 = 𝐦_α^T (𝐃/2)^1/2𝐏𝐃^-1/2.

To show the second identity in (<ref>), first note that, by the construction of 𝐏 in Section <ref>, 
we have that 𝐏𝐭^α=2^-α𝐭^α for 𝐭 in (<ref>). Thus, 
due to (<ref>), we get
 
    2^-(α+1/2)𝐜_α=2^-(α+1/2) 𝐃^1/2 𝐭^α = 1/√(2) 𝐃^1/2 𝐏 𝐭^α
    =(𝐃/2)^1/2𝐏𝐃^-1/2 𝐃^1/2 𝐭^α = (𝐃/2)^1/2𝐏𝐃^-1/2 𝐜_α.

Next, by (<ref>) and the first identity in (<ref>), we get

    [ 𝐑 𝐦_α=𝐒 𝐦_α - 1/2 𝐃^1/2 𝐏 𝐃^-1/2𝐒 𝐃^-1/2 𝐏^T 𝐃^1/2𝐦_α
    = 𝐒 𝐦_α -2^α+1/2 (𝐃/2)^1/2 𝐏 𝐃^-1/2𝐒 𝐦_α. ]

Thus, by (<ref>) and the second identity in (<ref>), 𝐑𝐦_α=0.
Since, by Proposition <ref> and (<ref>), we have 𝐑_k𝐦_α=0, k∉ℐ_irr, due to (<ref>), we obtain 

    𝐑_irr 𝐦_α = 𝐑 𝐦_α -1/2 ∑_k∉ℐ_irr 𝐑_k 𝐦_α = 0.

Therefore, with 𝐐 in (<ref>), we have

    ∫_ℝ Ψ_j(x)  x^α dx = 2^j/2 𝐐^T ∫_ℝ Φ(2^jx)  x^α dx = 2^-j(α+1/2) 𝐐^T 𝐦_α = 0.



 Note that while the first identity in (<ref>) does not rely on any property of Dubuc-Deslauriers schemes, the second one is particular to subdivision that reproduces polynomial up to degree n-1. This justifies our choice of the Dubuc-Deslauriers schemes, 
which posses the best ratio between polynomial reproduction and the support length of their basic limit functions.



If one chooses n<n columns of 𝐎 in (<ref>), then the corresponding matrix 𝐒 would
generate a wavelet tight frame with n vanishing moments. Since it is not possible to get more than n vanishing moments
in the regular case, the choice n=n is optimal in the semi-regular case.






§ EXAMPLES
 


In subsections <ref> and <ref>, we present two simple examples illustrating the construction in section <ref> for n=1 and
n=2, respectively. The small bandwidth  of the corresponding subdivision matrices 𝐏 allows for exact computations in terms of
the mesh parameter. Without loss of generality, after a suitable renormalization, we consider the mesh 𝐭 with h_ℓ=1 and h_r=h, h>0. In the case n=1, the Dubuc-Deslauriers 2-point scheme corresponds to the linear B-spline scheme. The case n=2, is more interesting and involved due to the high complexity of the entries of the corresponding matrices. For these two examples we are able to prove both parts of 
Conjecture <ref>. 

For the interested reader, the irregular filters 𝐐_irr for n=2,3,4,5 and several values of h_r>0 are available in <cit.>.





 §.§ Case n=1: linear B-spline scheme
 


In the regular case, i.e. h_ℓ=h_r=1, the linear B-spline scheme is defined by the mask 
    [𝐩(k) :  k=-1,0,1]=
    [[ 1/2   1 1/2 ]].
 By 
Proposition <ref>, with [𝐝(k) : k=-1,0]=[[ 1 1 ]], we get the well-known

    [𝐪_1(k) :  k=-1,0,1]=1/√(2)[[  1  0 -1 ]]   and   
    	[𝐪_2(k) :  k=-1,0,1]=1/2[[ -1  2 -1 ]].

In the semi-regular case,  the subdivision matrix 𝐏 does not depend on h and is the 2-slanted matrix with columns
determined by 𝐩^T. The corresponding basic limit functions {φ_k : k∈ℤ} of the subdivision scheme, 
the so-called hat functions,

    φ_k(x)={[ x-𝐭(k-1)/𝐭(k)-𝐭(k-1),      x∈[𝐭(k-1),𝐭(k)],;                      ; 𝐭(k+1)-x/𝐭(k+1)-𝐭(k),      x∈[𝐭(k),𝐭(k+1)],;                      ;                    0,            otherwise, ].  satisfy  ∫_ℝ φ_k(x) dx = {[     1,  k <0,;       ; 1+h/2,   k=0,;       ;     h,   k>0. ].

Thus, the entries of 𝐃 in (<ref>) are well defined for every h>0 and, the first moments of the scaling functions, 
by (<ref>), 
satisfy  

    𝐦_0=𝐃^1/21=[ [        …        1        …        1 √(1+h/2)     √(h)        …     √(h)        … ]].

The Algorithm 1 computes 𝐒_irr=1, thus, by (<ref>), part (ii) of Conjecture <ref> is true. Moreover, by (<ref>), we get

    𝐑_irr = [    2h+1/4(h+1)  -√(2)/4√(h+1)   -√(h)/4(h+1);               ;  -√(2)/4√(h+1)            1/2 -√(2h)/4√(h+1);               ;   -√(h)/4(h+1) -√(2h)/4√(h+1)     h+2/4(h+1) ] = 𝐐_irr𝐐_irr^T  with  𝐐_irr = [[    -1/2 √(h+1) √(2h)/2 √(h+1);               ;         √(2)/2              0;               ; -√(h)/2 √(h+1) -√(2)/2 √(h+1) ]],
 
therefore, part (i) of Conjecture <ref> is also true. Proposition <ref> guarantees  that the irregular framelets in (<ref>) have one vanishing moment.





 §.§ Case n=2: Dubuc-Deslauriers 4-point scheme
 


For n=2, which is also a special case of the family of schemes constructed in <cit.>, we obtain, via the construction in section <ref>, the regular columns of 𝐏 as shifts of the regular mask 

    [𝐩(k) :  k=-3,…,3]=1/16[[ -1  0  9 16  9  0 -1 ]]
 
and the five irregular columns of 𝐏 are given by

    [𝐏(m,k)]_-7≤ m≤7 
    k∈ℐ_irr = [                  -1/16                                                                                            ;                      0                                                                                            ;                   9/16                  -1/16                                                                     ;                      1                      0                                                                     ;                   9/16                   9/16                  -1/16                                              ;                      0                      1                      0                                              ;      -2h + 1/16(h + 2)     3(2h + 1)/8(h + 1)          3(2h + 1)/16h        -3/8h(h+1)(h+2)                       ;                                             0                      1                      0                       ;                        -3h^3/8(2h + 1)(h + 1)              3(h+2)/16      3(h + 2)/8(h + 1)      -h + 2/16(2h + 1);                                                                    0                      1                      0;                                                                -1/16                   9/16                   9/16;                                                                                           0                      1;                                                                                       -1/16                   9/16;                                                                                                                  0;                                                                                                              -1/16 ].

Proposition <ref> with 
[𝐝(k) :  k=-3,…,0]=1/4[[ 1+√(3) 3+√(3) 3-√(3) 1-√(3) ]],  yields

    [𝐪_1(k) :  k=-3,…,3]  = √(2)/16 [  √(3)-2       0  6-√(3)       0 -6-√(3)       0  √(3)+2 ],


    [𝐪_2(k) :  k=-3,…,3]  = 1/16 [  1  0 -9 16 -9  0  1 ].

Applying <cit.> in the regular part of the mesh, we obtain 𝐦_0(k)=1, k<-2, and
𝐦_0(k)=√(h), k>2, and, by Lemma <ref> and Theorem <ref> 
applied to the corresponding basic limit functions, we get

    𝐦_0(-2)   =   √(1/120(h-3/2)^2+479/480),     𝐦_0(-1)= √((7-2h)(h+2)/15),   𝐦_0(0)= √((h + 1)^3/8h), 
    𝐦_0(1)   =   √((7h - 2)(2h + 1)/15h)  and  𝐦_0(2)=  √(122/120h(h-3/244)^2+479/58560h).

The expressions for 𝐦_0(-1) and 𝐦_0(1) imply that 𝐃  in (<ref>) is positive definite 
if and only if h∈(2/7,7/2). 
Thus, the frame construction in Section <ref> is not valid for other h. Moreover, for the second moment we have

    𝐦_1(k)=k,    k<-2,   and  𝐦_1(k)=k√(h),    k>2,

and in the irregular part

    [                                                                    [𝐦_1(k) :  k=-2,…,2] =;                                                                                          ; ([𝐦_0(k) :  k=-2,…,2])^-1 [ h^3-3h^2+7h-1205/600; 
                -(h+2)(4h^2-14h+35)/75; ….;                                                                                          ;   .… (h + 1)(h-1)(31h^2+40h+31)/600h; (2h + 1)(35h^2-14h+4)/75h; 1205h^3-7h^2+3h-1/600h]. ]

Next, we construct 𝐒_irr to check the validity of Conjecture <ref>. The entries of 𝐒_irr depend in
an intricate way on the parameter h, thus, we work with 𝐒_irr instead, where,  
for

    α = 5(h+1)/2,    β = 37(h^2-1)/12,    γ = 5(h+1)^3(431h^2+938h+431)/288,

we have

    𝐒_irr = 1/αγ([𝐦_0(k) :  k=-2,…,2]) 𝐒_irr ([𝐦_0(k) :  k=-2,…,2]).

with
 

𝐒_irr = ( α β^2 + γ ) [(11^T)(m,k)]_-2≤ m,k≤2 + α^3 [(𝐭𝐭^T)(m,k)]_-2≤ m,k≤2 - α^2β [(1𝐭^T+𝐭1^T)(m,k)]_-2≤ m,k≤2 
  

= 25(h + 1)^3/48
[[  60 h^2+88 h+32   60 h^2+51 h+9  60 h^2+14 h-14   23 h^2-9 h-14 -14 h^2-32 h-14;   60 h^2+51 h+9  60 h^2+14 h+16  60 h^2-23 h+23  23 h^2-16 h+23  -14 h^2-9 h+23;  60 h^2+14 h-14  60 h^2-23 h+23  60 h^2-60 h+60  23 h^2-23 h+60 -14 h^2+14 h+60;   23 h^2-9 h-14  23 h^2-16 h+23  23 h^2-23 h+60  16 h^2+14 h+60   9 h^2+51 h+60; -14 h^2-32 h-14  -14 h^2-9 h+23 -14 h^2+14 h+60   9 h^2+51 h+60  32 h^2+88 h+60 ]].
 

Note that part (ii)  of Conjecture <ref> is equivalent to the system 

    {[ 𝐒_irr ([𝐦_0(k) :  k=-2,…,2]) [𝐦_0(k) :  k=-2,…,2]                                                 =                            α γ [1(k) :  k=-2,…,2];                                                  ; 𝐒_irr ([𝐦_0(k) :  k=-2,…,2]) [𝐦_1(k) :  k=-2,…,2]                                                 =                            α γ [𝐭(k) :  k=-2,…,2] ].

of polynomial equations, whose validity we checked with the help of MATLAB symbolic tool. Due to α,γ>0 for h∈(2/7,7/2), part (i) of Conjecture <ref>
is equivalent to checking that

    𝐑_irr = α γ h (𝐦_0)^-1 𝐑_irr (𝐦_0)^-1

is positive semi-definite. The renormalization leads to 𝐑_irr with polynomial entries and allows for
symbolic manipulations. Indeed, this way, the generalized Sylvester criterion, confirms that 𝐑_irr is
positive semi-definite for h∈(2/7,7/2). In Figure <ref> one can see the framelets corrisponding to a possible factorization of 𝐑 with h=2.


The value 2/7 ≈ 0.2857 resembles the corresponding critical value in <cit.> computed for the irregular knot insertion for the 4-point scheme. Below this critical value the scheme loses regularity. This fact makes the restriction on the range of the stepsize h less surprising in this case. 





§ CONCLUSIONS



We presented a method for constructing wavelet tight frames associated with the Dubuc-Deslauriers family of semi-regular interpolatory subdivision schemes, from their convergence analysis, to the choice of a suitable approximation of the corresponding Gramian matrix. This is the first step towards developing a practical tool for regularity analysis of wide classes of semi-regular subdivision schemes. 
There are several prominent tools for regularity analysis in the regular setting, e.g. difference operator <cit.>, joint spectral radius <cit.> and wavelet techniques <cit.>. In the irregular setting, the available methods for regularity analysis of subdivision schemes are either based on difference operator techniques in the interpolatory case <cit.>, or, for semi-regular schemes, on local eigenvalue analysis technique from <cit.>. The next step in this direction will be to extend standard wavelet techniques to the wavelet tight frames constructed here for the analysis of wide classes of semi-regular subdivision schemes. The simplicity of our construction may also have a strength in other practical applications.






§ ACKNOWLEDGEMENTS



This research has been accomplished within RITA (Research ITalian network on Approximation). The author would also like to thank M. Charina, C. Conti, L. Romani and J. Stöckler for the fruitful discussions and suggestions and the anonymous reviewers for the comments which improved this work considerably.




§ REFERENCES



siam



