# Dual Wavelet Frame Transforms on Manifolds and Graphs

Authors: Lihong Cui; Qiaoyun Wu; Jiale Liu; Jianjun Sun
Journal: Journal of Mathematics
 (2019)

---

## Abstract

In this paper, we consider the dual wavelet frames in both continuum setting, i.e., on manifolds, and discrete setting, i.e., on graphs. Firstly, we give sufficient conditions for the existence of dual wavelet frames on manifolds by their corresponding masks. Then, we present the formula of the decomposition and reconstruction for the dual wavelet frame transforms on graphs. Finally, we give a numerical example to illustrate the validity of the dual wavelet frame transformation applied to the graph data.


---

## Body

## 1. Introduction

Interest in signal processing algorithms in various applications has increased in recent years. Examples of these signal processing algorithms include sensor networks, transportation networks, the Internet, and social networks. In these applications, data are defined on topologically complicated domains, such as high-dimensional structures, irregularly sampled spaces, and manifolds. Such datasets are commonly referred to as big data. Several attempts have been made to extend conventional signal processing techniques to big data. As described in [1], the success of wavelet frames for data defined on flat domains has encouraged research on the generalization of wavelets and wavelet frames on topologically complicated domains. For example, Coifman and Maggioni constructed diffusion wavelets and diffusion polynomial frames on manifolds in [2, 3]. Geller and Mayeli studied the construction of wavelets on compact differentiable manifolds in [4]. Hou et al. constructed the well-known Mexican hat wavelet on a manifold geometry in [5]. Graphs are effective ways to represent the geometric structures of data on complicated domains. Hammond et al. first used spectral graph theory to characterize spectral graph wavelets on graphs in [6]. Leonardi and Van De Ville introduced Meyer-like wavelets and scaling kernels that result in tight spectral graph wavelet frames in [7, 8]. Shuman et al. first characterized a family of systems of uniformly translated kernels in the graph spectral domain that gave rise to tight frames of atoms generated via generalized translation on a graph in [9]. In addition, wavelet frames can be applied to sparse representation of piecewise smooth functions. Dong developed a system frame for sparse representation on graphs using tight wavelet frames and applications in [1]. Wang and Zhuang provided a complete characterization for the tightness of framelet systems in both continuous and discrete framelets on a manifold in [10]. Analogous to the standard Cohen-Daubechies-Feauveau (CDF) construction of factorizing a maximally flat Daubechies half-band filter, Narang and Ortega proposed the design of graph-QMF for arbitrary undirected weighted graphs in [11]. Tanaka and Sakiyama studied M-channel oversampled filter banks satisfying the perfect reconstruction condition for graph signals and showed oversampled graph filter banks for applications to graph signal denoising in [12].As a generalization of tight wavelet frames, pairs of dual wavelet frames have proved particularly useful in signal denoising and many other applications where translation invariance or redundancy is important. Han first characterized homogeneous dual wavelet frames for any general dilation matrix in the spaceFL2(S) in [13]. In this case, FL2(S)≔{f∈L2(Rn);suppf^⊂S}, where S denotes a measurable subset of Rn. Chui et al. were the first to completely characterize tight dual frames with maximum vanishing moments generated using two generators derived from the same refinable function in [14]. Daubechies and Han constructed pairs of dual wavelet frames from two refinable functions in [15]. Ehler constructed compactly supported multivariate pairs of dual wavelet frames called biframes, based on the mixed oblique extension principle in [16]. Han and Shen generalized the mixed extension principle in L2(Rn) to obtain and characterize dual Riesz bases in Sobolev spaces in [17]. Jiang and Pounds studied sixfold symmetric biframes with four framelets (frame generators) for triangular-mesh-based surface multiresolution processing in [18]. Readers can refer to [19–22] for more construction methods and properties regarding dual wavelet frameworks in L2(Rn).Motivated by these and other applications, in this paper, we introduce and study dual wavelet frames on manifolds. We consider the characteristics for the existence of dual wavelet frames in both continuous and discrete settings. In particular, discrete dual wavelet frame transforms and numerical examples on graphs are provided. The results may serve as an analysis tool for the processing of graph data. The paper is organized as follows. In Section2, we briefly review some basic notations and concepts related to our present work. In Section 3, the conditions for the existence of dual wavelet frames on manifolds are proved. In Section 4, we discuss discrete dual wavelet frame transforms on graphs (DWFTG) and provide a multiresolution analysis (MRA) on a graph. For computation and applications in practice, in Section 5, we show that discrete dual wavelet frame transforms on graphs can be achieved by using low-degree Chebyshev polynomials. In addition, we give numerical simulations of fast dual wavelet frame transforms on graphs to demonstrate the efficient implementation of the framelet transforms.The following is the list of notations used in this paper. LetR, N, and Z denote the set of real numbers and the set of natural number and integers, respectively. Let z∗ denote the conjugate of complex number z. Let l2(Z) be the set of 2 convergent sequences on Z. Let M be a manifold. For a given compact, connected, and smooth Riemannian manifold (M,μ), let L2(M) be a space of complex-valued square integrable functions on M. Let Δ be the Laplace-Beltrami operator on M with respect to the metric μ. δl,l′ is the Kronecker delta function with δl,l′=1 if l=l′ and 0 otherwise. Moreover, let G≔{V,E,w} denote a undirected, connected, weighted graphs, where V≔{vn∈M:n=1,⋯,K} is a discretization of a given manifold M, E⊂V×V is an edge set, and w:E↦R+ denotes a weight function. We consider here only finite graphs with V=K<∞.


## 2. Definitions and Concepts on Manifolds

Throughout this paper, we will use the following notations for the inner product and norm for the space ofL2(M).(1)f,g≔∫Mfxg∗xdμx,fL2M≔∫Mfx2dμx1/2,where f,g∈L2(M), dμ(x) (or simply dx) denotes the measure from the area element of a Riemannian metric μ on M, a probability measure μ satisfies μ(M)=1, and endowed with the L2 norm.Definition 1.
LetΔ be the Laplace-Beltrami operator on M, {ul}l=0∞⊂L2(M) and {λl}l=0∞⊂R; if the eigenvalue problem (2)Δul+λl2ul=0holds, then the sequence {(ul,λl)}l=0∞ of pairs is called a well-defined eigensystem for L2(M).Definition 2.
The two sequences pairs{(ul,λl)} and {(u~l,λ~l)} are said to be a biorthonormal eigenpair for L2(M), if they satisfy the following properties:
(1) A pair of sequencesul,u~l⊂L2(M) form an biorthonormal basis of L2(M); i.e., ul,u~l′=δl,l′.
(2) Each of the two sequences{λl}l=0∞,{λ~l}l=0∞⊂R is a nondecreasing sequence of nonnegative numbers and satisfies liml→∞λl=∞ and liml→∞λ~l=∞, respectively.Since{(ul,λl)} and {(u~l,λ~l)} are an biorthonormal eigenpair for L2(M), the following can be given.Definition 3.
The generalized Fourier transform of a functionf∈L2(M) is defined by (3)f^l=f,ulL2M.with f^l∈l2(Z+), Z+={0,1,2,⋯}.So, we can get the following result [6].Theorem 4.
Anyf∈L2(M) has the Fourier expansion f=∑l=0∞‍f^lul in L2(M) and the Parseval relation (4)f,g=∑l=0∞f^lg^l∗.holds. In particular, when f=g, Parseval’s identity (5)fL2M2=∑l=0∞f^l2.holds.Let refinable functionφ=ψ0∈L2(R) and its dual function φ~=ψ~0∈L2(R) which satisfy the following scaling equation: (6)ψ^02ξ=a^0ξψ^0ξψ~^02ξ=a~^0ξψ~^0ξξ∈Rwhere a^0(ξ)=∑k∈Z‍a0,ke-ikξ, a~^0(ξ)=∑k∈Z‍a~0,ke-ikξ are all finitely supported and called a refinement mask or the low filter, respectively.Given such a pair refinable functionφ=ψ0 and ψ~0 with mask a^0 and a~^0, we define a pair functions set Ψ≔{ψ1,⋯,ψr}⊂L2(R) and Ψ~≔{ψ~1,⋯,ψ~r}⊂L2(R) as follows: (7)ψ^j2ξ=a^jξψ^0ξ,ψ~^j2ξ=a~^jξψ~^0ξξ∈Rwhere a^j(ξ)=∑k∈Z‍aj,ke-ikξ and a~^j(ξ)=∑k∈Z‍a~j,ke-ikξ,j=1,2,⋯,r are called wavelet frame masks or the high pass filters of the system, respectively.Forψj and ψ~j defined by (7), denote Ψ≔{ψ1,⋯,ψr}⊂L2(R) and Ψ~={ψ~1,⋯,ψ~r}⊂L2(R). So, there is the following definition of a quasi-affine system on manifold M [1].Definition 5.
LetΨ≔{ψ1,⋯,ψr}⊂L2(R) be a set of functions. A quasi-affine system X(Ψ)⊂L2(M) is defined as (8)XΨ≔ψj,n,yM∈L2M:1≤j≤r,n∈Z,y∈M,where (9)ψj,n,yMx=∑l=0∞ψ^j2-nλlul∗yulx,n∈Z,x∈M,y∈M.In fact,ψj,n,yM(x) can be explained as the dilation and translation of ψj at scale n and a point y∈M. And again, a similar definition for X(ψ~)⊂L2(M) can be given as follows: (10)XΨ~≔ψ~j,n,yM∈L2M:1≤j≤r,n∈Z,y∈M,where (11)ψ~j,n,yMx=∑l=0∞ψ~^j2-nλ~lu~l∗yu~lx,n∈Z,x∈M,y∈M.Definition 6.
Given a Hilbert spaceH and a set of vectors Γk∈H, if there exist two positive constants A and B such that the inequality (12)Af2≤∑kf,Γk2≤Bf2holds for all f∈H, then a set of vectors Γk∈H is called a frame in H.Now, we begin to give the definition of a pair of dual wavelet frame on manifolds.Definition 7.
For givenΨ≔{ψ1,⋯,ψr}⊂L2(R) and Ψ~={ψ~1,⋯,ψ~r}⊂L2(R), if
( 1 )   X ( Ψ ) and X(Ψ~) defined by (8) and (10) are in L2(M)
( 2 ) each of X(Ψ) and X(Ψ~) is a wavelet frame in L2(M)
( 3 ) in L2-sense, the following perfect reconstruction formula holds for any f,g∈L2(M)(13)f=∑j=1r∑n∈Z∫Mf,ψj,n,yMψ~j,n,yMdyor, equivalently, (14)f,gL2M=∑j=1r∑n∈Z∫Mf,ψj,n,yMψ~j,n,yM,gdy.Then the pair of systems (X(Ψ),X(Ψ~)) is called a dual wavelet frame for L2(M). In particular, when Ψ=Ψ~, the frame is said to be a tight frame for L2(M).


## 3. Existences of Dual Wavelet Frames on Manifolds

In this section, we give sufficient conditions for the existence of dual wavelet frames forL2(M) by their corresponding masks. First, we give Weyl’s asymptotic formula [23, 24] and Griesers uniform bound of the eigenfunctions [25] as below similar to the way of literature [1, 10].Lemma 8.
Let{(ul,λl)}l=0∞ and {(u~l,λ~l)}l=0∞ be well-defined eigensystem of the Laplace-Beltrami operator Δ on M; then (15)λl≍l1/d,λ~l≍l1/d;and (16)ulL∞M≤cλld-1/2,u~lL∞M≤cλ~ld-1/2.where the constant c depends only on the dimension d≥2 of the manifold. Here, the symbol an≍bn means that there exist positive constants c, c′ independent of n such that 0<c=liminfn|an/bn|≤limsupn|an/bn|=c′<∞.Lemma 9.
Suppose a pair of functions{ψj:0≤j≤r},{ψ~j,0≤j≤r} in L2(R) and the corresponding pair of masks {a^j:0≤j≤r},{a~^j,0≤j≤r} satisfying equations (6) and (7). Let ψj,n,yM and ψ~j,n,yM, j=0,1,⋯,r be defined as in (9) and (11), respectively. If (17)ψ^0≤C01+ξ-sandψ~^0≤C01+ξ-s∀ξ∈Rwiths>d-12,then, for any n∈Z, (18)supy∈Mψj,n,yML2M<∞andsupy∈Mψ~j,n,yML2M<∞.Similar to the literature [1], we can obtain the following results.Theorem 10.
Let{ψj:0≤j≤r},{ψ~j:0≤j≤r} in L2(R) be a pair functions with masks pair {a^j:0≤j≤r},{a~^j:0≤j≤r} satisfying (6) and (7). Assume that the refinable function pair ψ0,ψ~0 satisfy conditions (17) and corresponding masks satisfy (19)a^0ξ-1≤Cξanda~^0ξ-1≤Cξfor ξ near the origin. Then, the pair of systems X(Ψ),X(Ψ~) given by (8) and (10) forms a dual wavelet frame in L2(M) provided the equality (20)∑j=0ra^j∗ξa~^jξ=1holds for ξ∈[-π,π].Proof.
For simplicity’s sake, we define the operationPn,j in L2(M) as (21)Pn,jf≔∫Mf,ψj,n,yMψ~j,n,yMdy,where0≤j≤r.In particular, (22)Pnf≔Pn,0f≔∫Mf,φn,yMφ~n,yMdy.By formulas (9) and (11), we obtain (23)ψj,n,yM^l=ψ^j2-nλlul∗y,andψ~j,n,·M*^l=ψ~^j∗2-nλ~lu~l∗x,By Parseval’s relation, we have (24)f,ψj,n,yM=f^,ψj,n,yM^=∑l=0∞f^lψ^j∗2-nλluly.Further, (25)f,ψj,n,·M^l=f^lψ^j∗2-nλl.Therefore, we have (26)Pn,jfx=f,ψj,n,·M,ψ~j,n,·M*=f,ψj,n,·M^,ψ~j,n,·M*^=∑l=0∞f^lψ^j∗2-nλlψ~^j2-nλ~lu~lx.Thus, (27)Pn,jf^l=f^lψ^j∗2-nλlψ~^j2-nλ~lfor0≤j≤r.
By∑j=0r‍a^j∗(ξ)a~^j(ξ)=1, we get (28)Pn,0f^l=f^lψ^0∗2-nλlψ~^02-nλ~l=f^lψ^0∗2-nλlψ~^02-nλl∑j=0ra^j∗2-nλla~^j2-nλ~l=∑j=0rf^la^j∗2-nλlψ^0∗2-nλla~^j2-nλ~lψ~^02-nλ~l=∑j=0rf^lψ^j∗2-n+1λlψ~^j2-n+1λ~l=∑j=0rPn-1,jf^l.Therefore, (29)Pnf=∑j=0rPn-1,jf=Pn-1f+∑j=1rPn-1,jf,and hence (30)Pn1f=Pn2f+∑j=1r∑n=n2n1Pn,jfTo obtain (13), we first need to prove that (31)limn1→+∞Pn1f=f,f∈L2M.
Due to(32)Pn1f-fL2M2=∑l=0∞f^lφ^∗2-n1λlφ~^2-n1λ~l-f^l2=∑l=0∞f^l2φ^∗2-n1λlφ~^2-n1λ~l-12.By assumption (19), we have limξ→0φ^(ξ)=1, limξ→0φ~^(ξ)=1; thus, for each l≥0, (33)limn1→+∞φ^∗2-n1λl=1andlimn1→+∞φ~^2-n1λ~l=1,and hence φ^ and φ~^ are bounded. Therefore, limn1→+∞Pn1Pn1f-fL2(M)2=0, and then (34)limn1→+∞Pn1f=f.
Second, we show that(35)limn2→-∞Pn2f=0.Since limξ→∞φ^(ξ)=0 and limξ→∞φ~^(ξ)=0, for l≥0, we have (36)limn2→-∞Pn2f^l=limn2→-∞f^lφ^∗2-n2λlφ~^2-n2λ~l=0.Therefore, by the boundedness of φ^ and φ~^, we have limn2→-∞Pn2f=0.
This completes the proof of the theorem.


## 4. Discrete Dual Wavelet Frame Transforms on Graphs

Discrete dual wavelet frames onM are more desirable in practice. Graphs are usually understood as a certain discretization or a random sample from some smooth Riemannian manifold. In this section, we discuss discrete dual wavelet frame transforms on graphs.For a given undirected, connected, weighted graphsG≔{V,E,w}; let A be a K×K adjacency matrix for a weighted graph G with entries (am,n), where (37)am,n=wvm,vn,ifvmandvnareconnectedbyanedgeinE,0,otherwise.LetD represent the degree matrix defined as follows: (38)D=diagd1,d2,⋯,dK,where d(m)=∑n‍am,n is called the degree d(m) of a vertex vm.The graph Laplacian plays an important role in the analysis and processing of graph data. The consistency of the graph Laplacian to the Laplace-Beltrami operator was studied in [26–28].Definition 11.
A nonnormalized graph Laplacian is defined as follows:(39)L=D-A.Let{(uk,λk)}k=0K be the set of pairs of eigenvalues and eigenfunctions of L; then,( 1 ) without losing generality, we have 0=λ0≤λ1≤λ2≤⋯λK-1≔λmax;( 2 ) the eigenfunctions form an orthonormal basis for all functions on the graph; that is, uk,uk′=δk,k′.Definition 12.
LetfG:V↦R be a function on the graph G. Then its Fourier transform is defined by (40)fG^k≔fG,uk≔∑n=1KfGnukn.SupposefG is sampled from the underlying function f:M↦R by fG(vk)≔f,φN,vk,vk∈V, where the dilation scale N is the smallest integer such that λmax≔λK-1≤2Nπ. Therefore, its Fourier transform is given by (41)fG^k=f^kφ^∗2-Nλk.Note that the scale N is selected such that 2-Nλk∈[0,π] for 0≤k≤K-1.Given a graph functionfG, we define the discrete L-level dual wavelet frame decomposition operator as (42)WfG≔Wj,lfG;j,l∈B,B≔1,1,2,1,⋯,r,1,1,2,⋯,r,L∪0,L,where Wj,lfG is its dual wavelet frame coefficient. Let (43)α=WfG=αj,l:j,l∈B,withαj,l=Wj,lfGand (44)WTα=α0,0,Wj,lTα=α0,l-1,where WT is the reconstruction operator.Now, we can define the discreteL-level dual wavelet frame decomposition and reconstruction algorithm for graph data as shown below.Algorithm 13.
Given a signalfG:V↦R, fG(vk)≔f,φN,vk, vk∈V and the associated trigonometric polynomials {a^j(ξ):0≤j≤r} and {a~^j(ξ):0≤j≤r}, we assign α^0,0[k]=fG^[k]. Then, the discrete L-level fast dual wavelet frame decomposition and reconstruction for L2(M) is given as follows (in the Fourier domain). (1)
Decomposition: for each l=1,2,⋯,L.
(a)
Obtain the low-frequency approximation ofα^0,0[k] at level l: (45)α^0,lk=a^0∗2-N+l-1λkα^0,l-1k;(b)
Obtain the dual framelet coefficients ofα^0,0[k] at level l: (46)α^j,lk=a^j∗2-N+l-1λkα^0,l-1k,j=1,2,⋯,r.(2)
Reconstruction: for each j=L,L-1,⋯,1, (47)α^0,l-1k=∑j=0ra~^j2-N+l-1λkα^j,lk.Then we have the following perfect reconstruction formula fromα to fG through WT.Theorem 14.
If a given set of masks{aj:0≤j≤r} and {a~j:0≤j≤r} in l1(Z) satisfy (20), then, the discrete dual wavelet frame transforms W and WT defined on G={V,E,w} satisfy (48)WTWfG=fGforallfG:V↦G.Proof.
For simplicity, we only give proof in the case of L=2L=2. For a general L, it can be obtained in a similar way. For L=2, we have α≔{αj,l:(j,l)∈B} with αj,l≔Wj,lfG and B={(j,l):1≤j≤r,l=1,2}∪{(0,2)}. In accordance with (45) and (46), we have (49)α^j,2k=a^j∗2-N+1λka^0∗2-NλkfG^k.Therefore, by assuming l=2 in (47), we obtain (50)α^0,2-1k=α^0,1k=∑j=0ra~^j2-N+1λkα^j,2k=∑j=0ra~^j2-N+1λka^j∗2-N+1λka^0∗2-NλkfG^k=∑j=0ra~^j2-N+1λka^j∗2-N+1λka^0∗2-NλkfG^k=a^0∗2-NλkfG^k.By assuming l=1 in (47), we obtain (51)α^0,0k=∑j=0ra~^j2-Nλkα^j,1k=∑j=0ra~^j2-Nλka^j∗2-NλkfG^k=∑j=0ra~^j2-Nλka^j∗2-NλkfG^k=fG^k.This shows that WTWfG=fG.


## 5. Polynomial Approximation and Numerical Simulations

### 5.1. Polynomial Approximation and Fast DWFTG

Chebyshev polynomials have an important application in the approximation theory. In this section, we describe the details of the dual wavelet frame transform on graphs based on polynomial approximation by using the method proposed in literature [1, 6]. One of the advantages of using lower Chebyshev polynomials to approach trigonometric polynomials is the efficiency of computing if the Laplacian is sparse.We recall the relevant definitions and properties of the Chebyshev polynomials.Definition 15.
The Chebyshev polynomialTk(x) is defined as follows: Tk(x)=cos⁡(karccos(x)), x∈[-1,1].Proposition 16.
The Chebyshev polynomials have the following properties.
( 1 )   T k ( x ) and Tj(x) are orthogonal with respect to the weight function 1/1-x2 in the interval [-1,1]; that is, (52)Tk,Tj=∫-1111-x2TkxTjxdx=∫0πcos⁡kθcos⁡jθdθ=π2δk,j,k,j>0;π,k=j=0,where x=cos⁡θ.
( 2 )   T k ( x ) satisfies recursive relations (53)T0ξ=1,T1ξ=ξ-π/2π/2,Tkξ=4πξ-π2Tk-1ξ-Tk-2ξ.
( 3 ) For a given g(ξ) with ξ∈[0,π], it has a convergent Chebyshev series (54)g=12c0+∑k=1∞ckTk,where the Chebyshev coefficients is ck=2/π∫0π‍cos⁡kθg(π/2(cos⁡(θ)+1)dθ.Thus, a smooth functiong(ξ) has the following accurate approximate: (55)gξ≈Tnξ=12c0+∑k=1n-1ckTk.and we denote the Chebyshev polynomial approximation of a^j(ξ) and a~^j(ξ) as (56)a^jξ≈Tjnξ=12cj,0+∑k=1n-1cj,kTk,cj,k=2π∫0πcos⁡kθa^jπ2cos⁡θ+1dθ;(57)a~^jξ≈T~jnξ=12c~j,0+∑k=1n-1c~j,kTk,c~j,k=2π∫0πcos⁡kθa~^jπ2cos⁡θ+1dθ.The LaplacianL is a symmetric matrix so that the eigenvalue decomposition L=UΛU exists, where Λ=diag{λ0,λ1,⋯,λK-1} and columns of U are the eigenvectors. Now, we can use the above approximation to speed up the decomposition transform. First, we can rewrite the decomposition transform in the following matrix form: (58)Wj,lfG^=a^j∗2-NΛfG^,l=1,a^j∗2-N+l-1Λa^0∗2-N+l-2Λ⋯a^0∗2-NΛfG^,2≤l≤L.where a^j∗(γΛ)=diag{a^j∗(γλ0),a^j∗(γλ1),⋯,a^j∗(γλK-1)}.Due toUTU=I, we have (59)UWj,lfG^=Ua^j∗2-NΛUTUfG^,l=1,Ua^j∗2-N+l-1Λa^0∗2-N+l-2Λ⋯a^0∗2-NΛUTUfG^,2≤l≤L.However, (60)u00u10⋯uK-10u01u11⋯uK-11⋮⋮⋱⋮u0K-1u1K-1⋯uK-1K-1Wj,lfG^0Wj,lfG^1⋮Wj,lfG^K-1=Wj,lfG0Wj,lfG1⋮Wj,lfGK-1where Wj,lfG[p]=∑k=0K-1‍Wj,lfG^[k]uk[p]; i.e., UWj,lfG^=Wj,lfG, and (61)u00u10⋯uK-10u01u11⋯uK-11⋮⋮⋱⋮u0K-1u1K-1⋯uK-1K-1fG^0fG^1⋮fG^K-1=fG0fG1⋮fGK-1where Wj,lfG[p]=∑k=0K-1‍fG^[k]uk[p]; i.e., UfG^=fG.Therefore, (58) can be equivalently written in physical domain: (62)Wj,lfG=Ua^j∗2-NΛUTfG,l=1,Ua^j∗2-N+l-1Λa^0∗2-N+l-2Λ⋯a^0∗2-NΛUTfG,2≤l≤L.Substitute (56) into (62) and notice that Tjn are polynomials; we obtain the fast DWFTG as follows: (63)Wj,lfG=Tjn∗2-NLfG,l=1,Tjn∗2-N+l-1LT0n∗2-N+l-2L⋯T0n∗2-NLfG,2≤l≤L.Next, reconstruction transformWT can be obtained similarly; i.e., (47) can be rewritten as the following matrix form: (64)W0,l-1fG^0W0,l-1fG^1⋮W0,l-1fG^K-1=∑j=0ra~^j2-N+l-1λ00⋯00∑j=0ra~^j2-N+l-1λ1⋯0⋮⋮⋱⋮00⋯∑j=0ra~^j2-N+l-1λK-1Wj,lfG^0Wj,lfG^1⋮W0,lfG^K-1Therefore, the above formula can be equivalently written in physical domain: (65)W0,l-1fG=∑j=0rUa~^j2-N+l-1ΛUTWj,lfG.We can obtain the fast dual wavelet frame reconstruction transform on graphs as follows: (66)W0,l-1Tα=∑j=0rT~jn2-N+l-1LWj,lfG.And we have WTW≈I.


### 5.2. Numerical Simulations of DWFTG

In this section, we give a numerical example to illustrate the validity of the dual wavelet frame transformation applied to the graph data.Example 17 (linear).
Leta^0(ξ)=a~^(ξ)=1/4eiξ(1+e-iξ)2 be the refinement masks of the continuous linear B-splines φ and φ~ supported on [-1,1]. Define (67)a^1ξ=-12eiξ1-e-iξ2,a~^1ξ=18eiξ1+e-iξ2,a^2ξ=-121-e-iξ2,a~^2ξ=12e-iξ.Then, this group of masks satisfy (20). Hence, the system pair (X(Ψ),X(Ψ~)) defined in (8) and (10) associated with the mask {a^0,a^1,a^2}, {a~^0,a~^1,a~^2} is a dual wavelet frame for L2(M).Example 18 (cubic).
Leta^0(ξ)=1/4eiξ(1+e-iξ)2 be the refinement masks of the continuous linear B-splines φ supported on [-1,1] and a~^0(ξ)=1/16ei2ξ(1+e-iξ)4 be the refinement masks of the C2 cubic B-splines φ~ supported on [-2,2]. Define (68)a^1ξ=-12eiξ1-e-iξ2,a~^1ξ=38,a^2ξ=-184+eiξ+e-iξ1-e-iξ2,a~^2ξ=181+4e-iξ+e-i2ξ.Then, this group of masks satisfy (20). Hence, the system pair (X(Ψ),X(Ψ~)) defined in (8) and (10) associated with the masks {a^0,a^1,a^2}, {a~^0,a~^1,a~^2} is a dual wavelet frame for L2(M).Example 19 (pseudo).
Leta^0(ξ)=cos4(ξ/2) and a~^0(ξ)=cos4(ξ/2)(1+4sin2(ξ/2) be the mask of the m order pseudo-spline. Define (69)a^1ξ=e-iξsin4ξ21+4sin2ξ2,a~^1ξ=eiξsin4ξ2,a^2ξ=54sin2ξ,a~^2ξ=54sin2ξ,a^3ξ=e-iξ54sin2ξ,a~^3ξ=eiξ54sin2ξ.Then, this group of masks satisfy (20). Hence, the system pair (X(Ψ),X(Ψ~)) defined in (8) and (10) associated with the masks {a^0,a^1,a^2,a^3}, {a~^0,a~^1,a~^2,a~^3} is a dual wavelet frame for L2(M).In our simulations, we choose the dual wavelet frame system given in Example17. We accurately approximate the trigonometric polynomial masks a^j∗ and a~^j in Example 17 by low-degree Chebyshev polynomials; see Table 1.Table 1
Approximation errorsTjn∗-a^j∗∞ and T~jn-a~^j∞ with a^j and a~^j in Example 17.
Errors a ^ 0 ∗ a ^ 1 ∗ a ^ 2 ∗ a ~ ^ 0 a ~ ^ 1 a ~ ^ 2 Average error n=7 3.40E-05 6.78E-05 3.471E-03 3.40E-05 1.53E-05 3.40E-05 6.09E-04 n=8 3.73E-07 7.27E-07 7.12E-04 3.73E-07 3.13E-06 3.40E-06 1.20E-04 n=9 3.51E-06 5.44E-07 1.27E-04 3.51E-06 4.13E-06 3.07E-07 2.31E-05 n=10 3.75E-06 3.91E-07 2.03E-05 3.75E-06 4.06E-06 6.08E-08 5.38E-06 n=11 3.89E-06 3.44E-07 2.98E-06 3.89E-06 4.12E-06 4.41E-08 2.54E-06In numerical experiment, we take16728 points sampled on the manifold and we build a weighted graph by setting edge weights w(vm,vn)=e-vm-vn22/σ for vm,vn∈V. For larger datasets, this graph could be sparsified by thresholding the edge weights. We use σ=10 and threshold the adjacency matrix A to limit the number of nearest neighbors of each vertex to 10 for computing the underlying weighted graph. The functions fG:V→R are generated by mapping two images, Slope and Eric, onto the graph G; see Figure 2 of the literature [1]. We perform 4 levels of DWFTG and use n=11 for the Chebyshev polynomial approximation of the masks.As described in Algorithm13, we can decompose graph data on Slope and Eric to obtain the dual wavelet frame coefficients Wj,lfG for 0≤j≤2 and 1≤l≤4 by the decomposition of (63) (see Figures 1 and 2) and reconstruct graph data on Slope and Eric from these framelet coefficient sequences by the reconstruction of (66); see Figure 3.Figure 1
The figure shows that the graph data on Slope is decomposed to the dual wavelet frame coefficientsWj,lfG for 0≤j≤2 (row 1-3) and 1≤l≤4 (column 1-4).Figure 2
The figure shows that graph data on Eric is decomposed to the dual wavelet frame coefficientsWj,lfG for 0≤j≤2 (row 1-3) and 1≤l≤4 (column 1-4).Figure 3
The graph data on Slope and Eric, respectively, reconstructed from corresponding framelet coefficient sequences are shown on the right of each image.The graphs in Figures1 and 2 show that the dual wavelet frame systems provide both good data approximation and detail separation based on multiresolution analysis; thus we demonstrate the ability of the fast dual wavelet frame transform for graph data analysis.The computation time and reconstruction errors of a4-level decomposition and reconstruction of the DWFTG are summarized in Table 2. For a similar computation time, the reconstruction error of DWFTG using linear masks is smaller than DWFTG using cubic masks and DWFTG using pseudo masks. However, the DWFTG using linear masks is a more redundant transformation than the DWFTG using cubic masks and DWFTG using pseudo masks.Table 2
The reconstruction time is in seconds and errors are measured by thel∞-norm.
Image name Linear Cubic Pseudo Errors Time(s) Errors Time(s) Errors Time(s) Slope 2.570E-05 5.960 9.526E-05 5.912 6.686E-04 5.788  Eric 2.971E-05 6.039 1.034E-04 5.536 4.700E-04 5.768Remark 20.
Note that, the sparsity of the high frequency coefficientsWj,lfG is related to the support set of the scale function and the symmetry of the filter in image processing. When the support set of the scale function is smaller and the filter banks pair generating the dual wavelet frame system are symmetrical, the high frequency coefficients Wj,lfG are good sparse. On the contrary, the sparsity of the image is not guaranteed. At the same time, the reconstruction error will be slightly larger with the number of filters increasing. But the result is also ideal.


## 5.1. Polynomial Approximation and Fast DWFTG

Chebyshev polynomials have an important application in the approximation theory. In this section, we describe the details of the dual wavelet frame transform on graphs based on polynomial approximation by using the method proposed in literature [1, 6]. One of the advantages of using lower Chebyshev polynomials to approach trigonometric polynomials is the efficiency of computing if the Laplacian is sparse.We recall the relevant definitions and properties of the Chebyshev polynomials.Definition 15.
The Chebyshev polynomialTk(x) is defined as follows: Tk(x)=cos⁡(karccos(x)), x∈[-1,1].Proposition 16.
The Chebyshev polynomials have the following properties.
( 1 )   T k ( x ) and Tj(x) are orthogonal with respect to the weight function 1/1-x2 in the interval [-1,1]; that is, (52)Tk,Tj=∫-1111-x2TkxTjxdx=∫0πcos⁡kθcos⁡jθdθ=π2δk,j,k,j>0;π,k=j=0,where x=cos⁡θ.
( 2 )   T k ( x ) satisfies recursive relations (53)T0ξ=1,T1ξ=ξ-π/2π/2,Tkξ=4πξ-π2Tk-1ξ-Tk-2ξ.
( 3 ) For a given g(ξ) with ξ∈[0,π], it has a convergent Chebyshev series (54)g=12c0+∑k=1∞ckTk,where the Chebyshev coefficients is ck=2/π∫0π‍cos⁡kθg(π/2(cos⁡(θ)+1)dθ.Thus, a smooth functiong(ξ) has the following accurate approximate: (55)gξ≈Tnξ=12c0+∑k=1n-1ckTk.and we denote the Chebyshev polynomial approximation of a^j(ξ) and a~^j(ξ) as (56)a^jξ≈Tjnξ=12cj,0+∑k=1n-1cj,kTk,cj,k=2π∫0πcos⁡kθa^jπ2cos⁡θ+1dθ;(57)a~^jξ≈T~jnξ=12c~j,0+∑k=1n-1c~j,kTk,c~j,k=2π∫0πcos⁡kθa~^jπ2cos⁡θ+1dθ.The LaplacianL is a symmetric matrix so that the eigenvalue decomposition L=UΛU exists, where Λ=diag{λ0,λ1,⋯,λK-1} and columns of U are the eigenvectors. Now, we can use the above approximation to speed up the decomposition transform. First, we can rewrite the decomposition transform in the following matrix form: (58)Wj,lfG^=a^j∗2-NΛfG^,l=1,a^j∗2-N+l-1Λa^0∗2-N+l-2Λ⋯a^0∗2-NΛfG^,2≤l≤L.where a^j∗(γΛ)=diag{a^j∗(γλ0),a^j∗(γλ1),⋯,a^j∗(γλK-1)}.Due toUTU=I, we have (59)UWj,lfG^=Ua^j∗2-NΛUTUfG^,l=1,Ua^j∗2-N+l-1Λa^0∗2-N+l-2Λ⋯a^0∗2-NΛUTUfG^,2≤l≤L.However, (60)u00u10⋯uK-10u01u11⋯uK-11⋮⋮⋱⋮u0K-1u1K-1⋯uK-1K-1Wj,lfG^0Wj,lfG^1⋮Wj,lfG^K-1=Wj,lfG0Wj,lfG1⋮Wj,lfGK-1where Wj,lfG[p]=∑k=0K-1‍Wj,lfG^[k]uk[p]; i.e., UWj,lfG^=Wj,lfG, and (61)u00u10⋯uK-10u01u11⋯uK-11⋮⋮⋱⋮u0K-1u1K-1⋯uK-1K-1fG^0fG^1⋮fG^K-1=fG0fG1⋮fGK-1where Wj,lfG[p]=∑k=0K-1‍fG^[k]uk[p]; i.e., UfG^=fG.Therefore, (58) can be equivalently written in physical domain: (62)Wj,lfG=Ua^j∗2-NΛUTfG,l=1,Ua^j∗2-N+l-1Λa^0∗2-N+l-2Λ⋯a^0∗2-NΛUTfG,2≤l≤L.Substitute (56) into (62) and notice that Tjn are polynomials; we obtain the fast DWFTG as follows: (63)Wj,lfG=Tjn∗2-NLfG,l=1,Tjn∗2-N+l-1LT0n∗2-N+l-2L⋯T0n∗2-NLfG,2≤l≤L.Next, reconstruction transformWT can be obtained similarly; i.e., (47) can be rewritten as the following matrix form: (64)W0,l-1fG^0W0,l-1fG^1⋮W0,l-1fG^K-1=∑j=0ra~^j2-N+l-1λ00⋯00∑j=0ra~^j2-N+l-1λ1⋯0⋮⋮⋱⋮00⋯∑j=0ra~^j2-N+l-1λK-1Wj,lfG^0Wj,lfG^1⋮W0,lfG^K-1Therefore, the above formula can be equivalently written in physical domain: (65)W0,l-1fG=∑j=0rUa~^j2-N+l-1ΛUTWj,lfG.We can obtain the fast dual wavelet frame reconstruction transform on graphs as follows: (66)W0,l-1Tα=∑j=0rT~jn2-N+l-1LWj,lfG.And we have WTW≈I.


## 5.2. Numerical Simulations of DWFTG

In this section, we give a numerical example to illustrate the validity of the dual wavelet frame transformation applied to the graph data.Example 17 (linear).
Leta^0(ξ)=a~^(ξ)=1/4eiξ(1+e-iξ)2 be the refinement masks of the continuous linear B-splines φ and φ~ supported on [-1,1]. Define (67)a^1ξ=-12eiξ1-e-iξ2,a~^1ξ=18eiξ1+e-iξ2,a^2ξ=-121-e-iξ2,a~^2ξ=12e-iξ.Then, this group of masks satisfy (20). Hence, the system pair (X(Ψ),X(Ψ~)) defined in (8) and (10) associated with the mask {a^0,a^1,a^2}, {a~^0,a~^1,a~^2} is a dual wavelet frame for L2(M).Example 18 (cubic).
Leta^0(ξ)=1/4eiξ(1+e-iξ)2 be the refinement masks of the continuous linear B-splines φ supported on [-1,1] and a~^0(ξ)=1/16ei2ξ(1+e-iξ)4 be the refinement masks of the C2 cubic B-splines φ~ supported on [-2,2]. Define (68)a^1ξ=-12eiξ1-e-iξ2,a~^1ξ=38,a^2ξ=-184+eiξ+e-iξ1-e-iξ2,a~^2ξ=181+4e-iξ+e-i2ξ.Then, this group of masks satisfy (20). Hence, the system pair (X(Ψ),X(Ψ~)) defined in (8) and (10) associated with the masks {a^0,a^1,a^2}, {a~^0,a~^1,a~^2} is a dual wavelet frame for L2(M).Example 19 (pseudo).
Leta^0(ξ)=cos4(ξ/2) and a~^0(ξ)=cos4(ξ/2)(1+4sin2(ξ/2) be the mask of the m order pseudo-spline. Define (69)a^1ξ=e-iξsin4ξ21+4sin2ξ2,a~^1ξ=eiξsin4ξ2,a^2ξ=54sin2ξ,a~^2ξ=54sin2ξ,a^3ξ=e-iξ54sin2ξ,a~^3ξ=eiξ54sin2ξ.Then, this group of masks satisfy (20). Hence, the system pair (X(Ψ),X(Ψ~)) defined in (8) and (10) associated with the masks {a^0,a^1,a^2,a^3}, {a~^0,a~^1,a~^2,a~^3} is a dual wavelet frame for L2(M).In our simulations, we choose the dual wavelet frame system given in Example17. We accurately approximate the trigonometric polynomial masks a^j∗ and a~^j in Example 17 by low-degree Chebyshev polynomials; see Table 1.Table 1
Approximation errorsTjn∗-a^j∗∞ and T~jn-a~^j∞ with a^j and a~^j in Example 17.
Errors a ^ 0 ∗ a ^ 1 ∗ a ^ 2 ∗ a ~ ^ 0 a ~ ^ 1 a ~ ^ 2 Average error n=7 3.40E-05 6.78E-05 3.471E-03 3.40E-05 1.53E-05 3.40E-05 6.09E-04 n=8 3.73E-07 7.27E-07 7.12E-04 3.73E-07 3.13E-06 3.40E-06 1.20E-04 n=9 3.51E-06 5.44E-07 1.27E-04 3.51E-06 4.13E-06 3.07E-07 2.31E-05 n=10 3.75E-06 3.91E-07 2.03E-05 3.75E-06 4.06E-06 6.08E-08 5.38E-06 n=11 3.89E-06 3.44E-07 2.98E-06 3.89E-06 4.12E-06 4.41E-08 2.54E-06In numerical experiment, we take16728 points sampled on the manifold and we build a weighted graph by setting edge weights w(vm,vn)=e-vm-vn22/σ for vm,vn∈V. For larger datasets, this graph could be sparsified by thresholding the edge weights. We use σ=10 and threshold the adjacency matrix A to limit the number of nearest neighbors of each vertex to 10 for computing the underlying weighted graph. The functions fG:V→R are generated by mapping two images, Slope and Eric, onto the graph G; see Figure 2 of the literature [1]. We perform 4 levels of DWFTG and use n=11 for the Chebyshev polynomial approximation of the masks.As described in Algorithm13, we can decompose graph data on Slope and Eric to obtain the dual wavelet frame coefficients Wj,lfG for 0≤j≤2 and 1≤l≤4 by the decomposition of (63) (see Figures 1 and 2) and reconstruct graph data on Slope and Eric from these framelet coefficient sequences by the reconstruction of (66); see Figure 3.Figure 1
The figure shows that the graph data on Slope is decomposed to the dual wavelet frame coefficientsWj,lfG for 0≤j≤2 (row 1-3) and 1≤l≤4 (column 1-4).Figure 2
The figure shows that graph data on Eric is decomposed to the dual wavelet frame coefficientsWj,lfG for 0≤j≤2 (row 1-3) and 1≤l≤4 (column 1-4).Figure 3
The graph data on Slope and Eric, respectively, reconstructed from corresponding framelet coefficient sequences are shown on the right of each image.The graphs in Figures1 and 2 show that the dual wavelet frame systems provide both good data approximation and detail separation based on multiresolution analysis; thus we demonstrate the ability of the fast dual wavelet frame transform for graph data analysis.The computation time and reconstruction errors of a4-level decomposition and reconstruction of the DWFTG are summarized in Table 2. For a similar computation time, the reconstruction error of DWFTG using linear masks is smaller than DWFTG using cubic masks and DWFTG using pseudo masks. However, the DWFTG using linear masks is a more redundant transformation than the DWFTG using cubic masks and DWFTG using pseudo masks.Table 2
The reconstruction time is in seconds and errors are measured by thel∞-norm.
Image name Linear Cubic Pseudo Errors Time(s) Errors Time(s) Errors Time(s) Slope 2.570E-05 5.960 9.526E-05 5.912 6.686E-04 5.788  Eric 2.971E-05 6.039 1.034E-04 5.536 4.700E-04 5.768Remark 20.
Note that, the sparsity of the high frequency coefficientsWj,lfG is related to the support set of the scale function and the symmetry of the filter in image processing. When the support set of the scale function is smaller and the filter banks pair generating the dual wavelet frame system are symmetrical, the high frequency coefficients Wj,lfG are good sparse. On the contrary, the sparsity of the image is not guaranteed. At the same time, the reconstruction error will be slightly larger with the number of filters increasing. But the result is also ideal.


## 6. Conclusion

Wavelet frames on manifolds are a new research topic in the area of wavelet analysis. This paper is primarily concerned with the construction of the dual wavelet frames on manifolds and graphs using the machinery of extension principles. We have obtained the characterizations for the existence of dual wavelet frames in both the continuous and the discrete setting. In addition, we have also obtained the decomposition and reconstruction for the dual wavelet frame transforms on graphs. A complete section has been devoted to studying discrete dual wavelet frames on graphs using low-degree Chebyshev polynomials. Finally, some numerical simulations of fast dual wavelet frame transform on graphs have also been carried out to demonstrate the efficiency and accuracy of the framelet transforms.



---

*Source: 1637623-2019-05-28.xml*