# A Brief Survey of the Graph Wavelet Frame

Authors: Jie Zhou; Zeze Zhang
Journal: Complexity
 (2022)

---

## Abstract

In recent years, the research of wavelet frames on the graph has become a hot topic in harmonic analysis. In this paper, we mainly introduce the relevant knowledge of the wavelet frames on the graph, including relevant concepts, construction methods, and related theory. Meanwhile, because the construction of graph tight framelets is closely related to the classical wavelet framelets onℝ, we give a new construction of tight frames on ℝ. Based on the pseudosplines of type II, we derive an MRA tight wavelet frame with three generators ψ1,ψ2, and ψ3 using the oblique extension principle (OEP), which generate a tight wavelet frame in L2ℝ. We analyze that three wavelet functions have the highest possible order of vanishing moments, which matches the order of the approximation order of the framelet system provided by the refinable function. Moreover, we introduce the construction of the Haar basis for a chain and analyze the global orthogonal bases on a graph G. Based on the sequence of framelet generators in L2ℝ and the Haar basis for a coarse-grained chain, the decimated tight framelets on graphs can be constructed. Finally, we analyze the detailed construction process of the wavelet frame on a graph.


---

## Body

## 1. Introduction

In the past two centuries, harmonic analysis, including Fourier analysis and wavelet analysis, has been intensively researched and widely applied in areas, such as signal processing, representation theory, and number theory. Since Daubechies constructed the compactly supported orthonormal wavelet bases in 1988 [1], wavelet analysis has been extensively studied and successfully applied to more fields. For an orthonormal wavelet basis, the corresponding refinable function ϕ and its mask a must satisfy the following conditions:(1)ϕ⋅−k,ϕ=∫ℝϕx−kϕx¯dx=δk,k∈ℤ,(2)a^ξ2+a^ξ+π2=1,∀ξ∈ℝ.These two conditions enforce very restrictive constraints for the refinable function, and many refinable functions do not satisfy the conditions. By introducing redundancy into a wavelet system, a tight wavelet frame is considered as a generalization of an orthonormal wavelet basis [2–4]. It is much easier and more flexible to construct tight wavelet frames than orthonormal wavelet bases. This theory of the construction of tight wavelet frames on regular Euclidean domains is relatively mature [5–11]. In recent years, driven by the rapid progress of deep learning and their successful applications in an interdisciplinary area, data in deep learning are typically from social networks, biology, physics, finance, etc., and can be naturally organized as graphs [12–22]. There has been a great interest in developing harmonic analysis for data defined on non-Euclidean domains such as manifold data or graph data [23–26]. Such data are usually regarded as random samples from a smooth manifold. The matrix is used to organize it as an undirected graph, where the graph Laplacian approximates the manifold Laplacian. The underlying manifold encodes the geometric information of the data, which has been widely used in various machine learning and statistical models [27–32].Different from that on Euclidean domains, the construction systems and the corresponding fast algorithm for tight framelets on graphs are less studied. The main reason is that we do not know how to define the operators of translation and dilation on the manifolds or graphs similar to the classical wavelet framelet systems. In order to further study the construction of tight framelets on non-Euclidean domains, some alternative approaches are proposed. By introducing diffusion operators, Coifman and Maggioni in [33] constructed orthogonal diffusion wavelets on a smooth manifold. Maggioni and Mhaskar in [34] further extended the construction from diffusion wavelets to diffusion polynomial frames on manifolds. In recent years, with the development of computer science and mathematics, the classical spectral theory has been introduced into the construction of wavelet framework on the graph. The eigenvalues and eigenvectors of the graph Laplacian matrix can be effectively used to define translation and dilation transformation of graph functions, and the construction of tight framelets on graphs can be obtained [23, 24, 35–37]. Based on spectral theory and graph Laplacian [38], some work about the construction of tight framelets on graphs has been derived [23–25, 35–37, 39–44]. In this paper, we focus on the review of a number of representative construction methods of tight framelets on graphs and provide a specific introduction for wavelet frame on graphs.We organize the rest of the paper as follows: in Section2, we introduce some basic theoretical knowledge, including the classical wavelet frame theory, graph, chain, and tight framelets on the graph, and review some construction methods of tight framelets on graphs; in Section 3, we construct three wavelet functions ψ1,ψ2, and ψ3, which generate a tight wavelet frame in L2ℝ, and give a specific example of the construction process of wavelet frame on the graph; and in Section 4, we conclude this paper and discuss future challenges of the graph wavelet frame.


## 2. Wavelet Frame on the Graph

The construction method of wavelet frames on the graph is to design the wavelet function on the graph and its corresponding translation and dilation transformation of graph functions. With the spectral graph theory, by considering the spectral decomposition of the graph Laplacian, Hammond in [35] defined translation and dilation transformation on a graph and constructed the spectral graph wavelets and spectral graph scaling functions based on an indicator function. However, the spectral scaling functions in this way did not generate the graph wavelets, which is analogous to the construction of traditional wavelets through the two-scale relation. Hence, the associated construction of wavelet frames on the graph did not have the filter bank. Dong in [36] defined the quasi-affine systems on a given manifold by considering generalized translation and dilation transformation of wavelet functions in L2ℝ, and constructed wavelet frames on both compact manifold and discrete graphs. These wavelet functions are defined from the scaling functions, which implies that the associated construction of wavelet frames on the graph has the filter bank.However, the graph wavelet frames constructed by the above two methods are the undecimated wavelet frames. When the level number of framelet transforms is big, the undecimated wavelet frames may result in a high redundancy rate. In contrast, using clustering techniques, the decimated framelet system can be constructed by embedding edge relation and clustering feature in a chain-based orthonormal system and would achieve a low redundancy rate. Chui [23] first defined an orthogonal system based on a local filtration and constructed the different orthogonal system at the vertices at each level. Later, Chui [24] further extended the work to directed graphs and established an orthogonal system with localization properties on the tree. Based on graph clustering algorithms [45–50], a suitable orthonormal eigenpair can be constructed for a coarse-grained chain on the graph, and decimated tight framelets can be constructed based on the orthonormal eigenpair in [37]. By introducing a Haar basis for a coarse-grained chain on a graph, the graph neural networks and graph pooling under the Haar basis can be defined in [25, 39], and achieved low computational cost when the graph size is large.The construction of decimated tight framelets on the graph first utilizes graph clustering to obtain the coarse-grained chain. Once a chain of nested graphs is obtained, we can build the multiscale structure on a graph by framelet filter banks, which bridges with the classical wavelet framelets systems onℝ. In this paper, we focus on the construction of decimated tight framelets on the graph. In the following, we will review relevant knowledge for the construction methods of decimated tight framelets on the graph.


### 2.1. Tight Wavelet Frames onℝ

In this subsection, we first recall some basic theories of the tight wavelet frame on theL2ℝ, which are the basis for the construction of decimated tight framelets [5, 8, 9]. A function ϕ is a refinable function if it satisfies the following refinement equation:(3)ϕ=2∑k∈ℤakϕ2⋅−k,where ak is called the mask for the refinable function ϕ, which is a finitely supported sequence on ℤ. The Fourier series of a sequence ak is defined to be(4)a^ξ=∑k∈ℤake−iξk,ξ∈ℝ.The Fourier transform of a functionf∈L1ℝ is defined by(5)f^ξ=∫ℝfxe−ixξdx,ξ∈ℝ,and can be naturally extended to L2ℝ functions. In terms of the Fourier transform, the refinement equation in (3) can be rewritten as follows:(6)ϕ^ξ=a^ξ2ϕ^ξ2,ξ∈ℝ.Throughout this paper, we assumea^0=ϕ^0=1. According to (6), we have ϕ^ξ=∏j=1∞a^2−jξ.We say that a setψ1,…,ψr of functions in L2ℝ generates a tight wavelet frame in L2ℝ if(7)f2=∑l=1r∑j∈ℤ∑k∈ℤf,ψj,kl2,∀f∈L2ℝ,where ψj,kl=2j/2ψl2j⋅−k,f,g=∫ℝfxgx¯dx and f2=f,f. The set ψ1,…,ψr is called a set of generators for the corresponding tight wavelet frame. For any function f∈L2ℝ, we have the wavelet expansion(8)f=∑l=1r∑j∈ℤ∑k∈ℤf,ψj,klψj,kl.By introducing redundancy into a wavelet system, it has a lot of freedom in the construction of tight wavelet frames derived from refinable function. Petukhov [7] showed that if the mask a satisfies a^ξ2+a^ξ+π2≤1 for all ξ∈ℝ, then a symmetric tight wavelet frame with three generators can be obtained. Jiang [8] systematically analyzed the construction of hexagonal tight wavelet frame filter banks with three high-pass filters. For the construction of the wavelet frame, the oblique extension principle is considered as a popular approach, which was first proposed in the literature [5], and the specific contents are as follows.Theorem 1.
Letϕbe a compactly supported refinable function inL2ℝwith a finitely supported maskaonℤsuch thatϕ^0=a^0=1anda^π=0. Suppose that there exist finitely supported sequencesb1,…,brand a2π-periodic trigonometric polynomialΘsuch thatΘ0=1and(9)b^1ξ⋯b^rξb^1ξ+π⋯b^rξ+πb^1ξ¯b^1ξ+π¯⋮⋮b^rξ¯b^rξ+π¯=MΘξ,where(10)MΘξ=Θξ−Θ2ξa^ξ2−Θ2ξa^ξa^ξ+π¯−Θ2ξa^ξ+πa^ξ¯Θξ+π−Θ2ξa^ξ+π2.Thewavelet functionsψ1,…,ψr is defined as follows:(11)ψl^ξ=b^lξ2ϕ^ξ2,l=1,…,r.Then,ψ1,…,ψr generates a tight wavelet frame in L2ℝ. Moreover, ψ1,…,ψr has m vanishing moments if and only if(12)Θξ−Θ2ξ|a^ξ|2=O|ξ|2m,ξ⟶0.The construction in Theorem1 is called the oblique extension principle. Daubechies et al. in [5] discussed the importance of the nonconstant Θ in this principle, which provides a tight wavelet frame with good vanishing moments. The order of vanishing moments is an important property of a tight wavelet frame. For a set ψ1,…,ψr of compactly supported functions in L2ℝ, it has vanishing moments of order m if(13)∫ℝtjψltdt=0∀l=1,…r;j=0,…,m−1.The related theory of compactly supported functions with good vanishing moments can be found in references [9, 51]. Moreover, some scholars have also studied the construction of multiwavelet and multiwavelet frames [52–56]. Based on two-direction refinable functions, Li and Yang [52] studied the construction of dual multiwavelet frames with symmetry and discussed the vanishing moment of the constructed multiwavelet frames. Atreas et al. [53] discussed homogeneous dual multiwavelet frames from a pair of refinable function vectors and derived that the mixed oblique extension principle can be described by dual multiwavelet frames. For OEP-based tight framelets, Han [54] also extended to high dimensional case and constructed compactly supported tight M-wavelet frames from compactly supported M-refinable functions for any d×d dilation matrix M. Based on the approach of polyphase matrix extension of multiscaling vectors, Cen et al. [55] presented a novel approach for the construction of symmetric compactly supported bi-orthogonal multiwavelets with multiplicity of 2. Li and Peng [56] analyzed the sampling property of bi-orthogonal multiwavelets and discussed the application of bi-orthogonal multiwavelets in image compression filter bank. In addition, some researchers investigated the construction and application of multivariate wavelet frames. The interested readers are referred to the literature [57–65].


### 2.2. Graph and Chain

In this subsection, we introduce some basic conceptions about a graph and chain [6, 37].A graphG=V,E,ω is made up of a set of vertices V=υ1,…,υn and a set of edges E⊆V×V between vertices. The non-negative function ω:E⟶ℝ indicates weight of edges between vertices. ωυi,υj≠0 if there is an edge from the vertex υi to vertex υj; otherwise, 0. If we ignore the directionality of the edges, the graph is called an undirected graph. In this case, weight ω is symmetric, that is, ωυi,υj=ωυj,υi for all υi,υj∈V. Otherwise, the graph G is said to be a directed graph. The degree of a vertex υ∈V is denoted as dυ=∑p∈V=ωυ,p. The sum of degrees of all vertices of G is denoted as vol G≔ vol V=∑υ∈Vdυ, which is the volume of the graph [6, 37]. For a subset V0 of V, the volume V0 is the sum of degrees of all nodes in V0.Lete1,e2,…,en be a sequence of edges in G. If there exist distinct vertices v0,…vn in V such that any pair of consecutive nodes is connected by the edges of G, that is, ei=vi−1,vi for i=1,2,…,n, then the sequence e1,e2,…,en is called a path of the graph G between v0 and vn. The length of the path is defined to be ∑i=1nωvi−1,vi. If there exists a path between the vertex υi and vertex υj, the length of the shortest possible path is defined as the distance between them, denoted as ρvi,vj. If there is no path between vertices vi and vj, we define the distance ρvi,vj=∞. A graph is said to be connected if any two distinct vertices of G are connected [6, 37].LetG=V,E,ω and Gc=Vc,Ec,ωc be two graphs; we say that Gc is the coarse-grained graph of G if Vc is a partition of V. In this case, there exists subsets V1,…,Vk of V for some k∈ℕ such that(14)Vc=V1,…,Vk,V1∪⋯∪Vk=V,Vi∩Vj=∅,1≤i<j≤k.That is, each vertexVj of Gc is called a cluster for G. The edges of Gc are the links between clusters of G. We define that two vertices vi and vj are equivalent, if vi and vj are in the same cluster, denoted by vi∼vj [6]. Generally, we use v to denote a cluster in G with respect to a vertex in the coarse-grained graph Gc.LetJ,J0,J≥J0 be two integers; a coarse-grained chain GJ⟶J0≔GJ,GJ−1,…,GJ0 of G is a sequence of graphs with GJ≡G. Each Gj=Vj,Ej,ωj is a coarse-grained graph of G for all J0⩽j⩽J, and vGj⊆vGj−1 for all j=J0+1,…,J and all v∈G. The graph Gj is the level j graph of the chain GJ⟶J0, and the Gj−1 can be viewed as a coarse-grained graph of Gj for j=J0+1,…,J. If Gj≡G for all j=J0+1,…,J, the chain GJ⟶J0 is called as an undecimated chain of G. Otherwise, GJ⟶J0 is called an decimated chain of G. For convenience of discussion, it is usually assumed each vertex v of the finest level graph GJ≡G as a cluster of singleton. When there is only one vertex in the coarsest graph GJ0, we call GJ⟶J0 a tree [6].


### 2.3. Orthonormal Bases on Graphs

In this subsection, we introduce the orthonormal bases for the coarse-grained chain on a graph [6, 35–37].LetL2G≔L2G,⋅,⋅G be the Hilbert space of vectors f:V⟶ℂ on the graph G with the inner product ⋅,⋅G, which is defined as follows:(15)f,gG≔∑v∈Vfvgv¯,f,g∈L2G,where g¯ is the complex conjugate to g. The norm ⋅G is given by fG≔f,fG for f∈L2G. Let δl,l′ be the Kronecker delta satisfying δl,l′=1 if l=l′ and 0 otherwise, and N≔V is the number of vertices. A set μll=1N of vectors in f∈L2G is an orthonormal basis for f∈L2G if(16)μl,μl′=δl,l′,1≤l,l′≤N.The generalized Fourier coefficient of degreel for f∈L2G with respect to μl is defined to be fl^≔f,μl. Then, for all f∈L2G, we have f=∑l=1Nfl^μl. Let λll=1N⊆ℝ be a nondecreasing sequence of non-negative numbers satisfying 0=λ1≤⋯≤λN, if μll=1N is an orthonormal basis for f∈L2G with μ1≡1/N; we say μl,λll=1N is an orthonormal eigenpair for f∈L2G [35]. Meanwhile, Hammond [35] also gives the definition of the graph Laplacian ℒ:L2G⟶L2G(17)ℒfp≔dpfp−∑v∈Vωp,vfv,p∈V,f∈L2G.Iff,ℒf≥0, the equation ℒμl=λlμl corresponding to the eigenvalues λl,l=1,…,N and eigenvectors μl is non-negative, and satisfies 0=λ1≤⋯≤λN with μ1≡1/N [37].Based on the properties of the eigenvalues and eigenvectors, Wang and Zhuang in [37] gave an orthonormal basis for the chain. Let GJ⟶J0≔GJ,GJ−1,…,GJ0 be a chain on the graph G with N vertices; L2GJ⟶J0 be the set of all vectors f defined on the union of vertices on all levels VJ∪⋯∪VJ0. If the restriction μl,λll=1N on the j th-level graphs Gj is an orthonormal basis for L2Gj at each level j=J0,…,J, a set pairs of vectors and complex numbers μl,λll=1N in L2GJ⟶J0 are called an orthonormal basis for the chain GJ⟶J0.


### 2.4. Decimated Tight Framelets on Graphs

In this subsection, we introduce the construction methods of a decimated tight framelet on a graph. The conclusion of this part mainly comes from reference [6]. Let G=V,E,ω be a graph and GJ⟶J0≔GJ,GJ−1,…,GJ0 be a chain on the graph G. For each vertex p in Gj=Vj,Ej,ωj, a weight ωj,p∈ℝ is defined. For the bottom level with j=J, let ωJ,pGJ≡1. Let Qj≔ωj,p:p∈Vj be the set of weights on Gj, and QJ⟶J0≔QJ,…,QJ0 be the sequence of weights for the coarse-grained chain GJ⟶J0. Zheng et al. in [6] gave the construction method of the decimated framelets on the graph, and the details are as follows.Definition 1.
LetΨj=ϕj;ψj1,…,ψjr be a tight frame in L2ℝ at scale j for j=J0,…,J. The decimated framelets ϕj,pv and ψj,pnv,p,v∈V, at scale j=J0,…,J for the chain GJ⟶J0 on the graph Gj are defined by(18)ϕj,pv=ωj,p∑l=1Nϕj^λlΛjμlp¯μlv,p∈Vj,ψj,pnv=ωj+1,p∑l=1Nψjn^λlΛjμlp¯μlv,p∈Vj+1,n=1,…,r,where for j=J, we let VJ+1=VJ and ωJ+1,p=ωJ,p. We call ϕj,p and ψj,pn low-pass and high-pass framelets at scale j.
The decimated tight framelets in Definition1 are constructed based on framelet generators in L2ℝ and the orthonormal basis associated with the chain GJ⟶J0. The function μlp can be defined by μlp=minv∈pμlv. In order to obtain the decimated tight framelets on the graph G, first, we study the construction methods of tight frames on ℝ. Then, in next section, we focus on the specific construction process of the graph wavelet frame.


## 2.1. Tight Wavelet Frames onℝ

In this subsection, we first recall some basic theories of the tight wavelet frame on theL2ℝ, which are the basis for the construction of decimated tight framelets [5, 8, 9]. A function ϕ is a refinable function if it satisfies the following refinement equation:(3)ϕ=2∑k∈ℤakϕ2⋅−k,where ak is called the mask for the refinable function ϕ, which is a finitely supported sequence on ℤ. The Fourier series of a sequence ak is defined to be(4)a^ξ=∑k∈ℤake−iξk,ξ∈ℝ.The Fourier transform of a functionf∈L1ℝ is defined by(5)f^ξ=∫ℝfxe−ixξdx,ξ∈ℝ,and can be naturally extended to L2ℝ functions. In terms of the Fourier transform, the refinement equation in (3) can be rewritten as follows:(6)ϕ^ξ=a^ξ2ϕ^ξ2,ξ∈ℝ.Throughout this paper, we assumea^0=ϕ^0=1. According to (6), we have ϕ^ξ=∏j=1∞a^2−jξ.We say that a setψ1,…,ψr of functions in L2ℝ generates a tight wavelet frame in L2ℝ if(7)f2=∑l=1r∑j∈ℤ∑k∈ℤf,ψj,kl2,∀f∈L2ℝ,where ψj,kl=2j/2ψl2j⋅−k,f,g=∫ℝfxgx¯dx and f2=f,f. The set ψ1,…,ψr is called a set of generators for the corresponding tight wavelet frame. For any function f∈L2ℝ, we have the wavelet expansion(8)f=∑l=1r∑j∈ℤ∑k∈ℤf,ψj,klψj,kl.By introducing redundancy into a wavelet system, it has a lot of freedom in the construction of tight wavelet frames derived from refinable function. Petukhov [7] showed that if the mask a satisfies a^ξ2+a^ξ+π2≤1 for all ξ∈ℝ, then a symmetric tight wavelet frame with three generators can be obtained. Jiang [8] systematically analyzed the construction of hexagonal tight wavelet frame filter banks with three high-pass filters. For the construction of the wavelet frame, the oblique extension principle is considered as a popular approach, which was first proposed in the literature [5], and the specific contents are as follows.Theorem 1.
Letϕbe a compactly supported refinable function inL2ℝwith a finitely supported maskaonℤsuch thatϕ^0=a^0=1anda^π=0. Suppose that there exist finitely supported sequencesb1,…,brand a2π-periodic trigonometric polynomialΘsuch thatΘ0=1and(9)b^1ξ⋯b^rξb^1ξ+π⋯b^rξ+πb^1ξ¯b^1ξ+π¯⋮⋮b^rξ¯b^rξ+π¯=MΘξ,where(10)MΘξ=Θξ−Θ2ξa^ξ2−Θ2ξa^ξa^ξ+π¯−Θ2ξa^ξ+πa^ξ¯Θξ+π−Θ2ξa^ξ+π2.Thewavelet functionsψ1,…,ψr is defined as follows:(11)ψl^ξ=b^lξ2ϕ^ξ2,l=1,…,r.Then,ψ1,…,ψr generates a tight wavelet frame in L2ℝ. Moreover, ψ1,…,ψr has m vanishing moments if and only if(12)Θξ−Θ2ξ|a^ξ|2=O|ξ|2m,ξ⟶0.The construction in Theorem1 is called the oblique extension principle. Daubechies et al. in [5] discussed the importance of the nonconstant Θ in this principle, which provides a tight wavelet frame with good vanishing moments. The order of vanishing moments is an important property of a tight wavelet frame. For a set ψ1,…,ψr of compactly supported functions in L2ℝ, it has vanishing moments of order m if(13)∫ℝtjψltdt=0∀l=1,…r;j=0,…,m−1.The related theory of compactly supported functions with good vanishing moments can be found in references [9, 51]. Moreover, some scholars have also studied the construction of multiwavelet and multiwavelet frames [52–56]. Based on two-direction refinable functions, Li and Yang [52] studied the construction of dual multiwavelet frames with symmetry and discussed the vanishing moment of the constructed multiwavelet frames. Atreas et al. [53] discussed homogeneous dual multiwavelet frames from a pair of refinable function vectors and derived that the mixed oblique extension principle can be described by dual multiwavelet frames. For OEP-based tight framelets, Han [54] also extended to high dimensional case and constructed compactly supported tight M-wavelet frames from compactly supported M-refinable functions for any d×d dilation matrix M. Based on the approach of polyphase matrix extension of multiscaling vectors, Cen et al. [55] presented a novel approach for the construction of symmetric compactly supported bi-orthogonal multiwavelets with multiplicity of 2. Li and Peng [56] analyzed the sampling property of bi-orthogonal multiwavelets and discussed the application of bi-orthogonal multiwavelets in image compression filter bank. In addition, some researchers investigated the construction and application of multivariate wavelet frames. The interested readers are referred to the literature [57–65].


## 2.2. Graph and Chain

In this subsection, we introduce some basic conceptions about a graph and chain [6, 37].A graphG=V,E,ω is made up of a set of vertices V=υ1,…,υn and a set of edges E⊆V×V between vertices. The non-negative function ω:E⟶ℝ indicates weight of edges between vertices. ωυi,υj≠0 if there is an edge from the vertex υi to vertex υj; otherwise, 0. If we ignore the directionality of the edges, the graph is called an undirected graph. In this case, weight ω is symmetric, that is, ωυi,υj=ωυj,υi for all υi,υj∈V. Otherwise, the graph G is said to be a directed graph. The degree of a vertex υ∈V is denoted as dυ=∑p∈V=ωυ,p. The sum of degrees of all vertices of G is denoted as vol G≔ vol V=∑υ∈Vdυ, which is the volume of the graph [6, 37]. For a subset V0 of V, the volume V0 is the sum of degrees of all nodes in V0.Lete1,e2,…,en be a sequence of edges in G. If there exist distinct vertices v0,…vn in V such that any pair of consecutive nodes is connected by the edges of G, that is, ei=vi−1,vi for i=1,2,…,n, then the sequence e1,e2,…,en is called a path of the graph G between v0 and vn. The length of the path is defined to be ∑i=1nωvi−1,vi. If there exists a path between the vertex υi and vertex υj, the length of the shortest possible path is defined as the distance between them, denoted as ρvi,vj. If there is no path between vertices vi and vj, we define the distance ρvi,vj=∞. A graph is said to be connected if any two distinct vertices of G are connected [6, 37].LetG=V,E,ω and Gc=Vc,Ec,ωc be two graphs; we say that Gc is the coarse-grained graph of G if Vc is a partition of V. In this case, there exists subsets V1,…,Vk of V for some k∈ℕ such that(14)Vc=V1,…,Vk,V1∪⋯∪Vk=V,Vi∩Vj=∅,1≤i<j≤k.That is, each vertexVj of Gc is called a cluster for G. The edges of Gc are the links between clusters of G. We define that two vertices vi and vj are equivalent, if vi and vj are in the same cluster, denoted by vi∼vj [6]. Generally, we use v to denote a cluster in G with respect to a vertex in the coarse-grained graph Gc.LetJ,J0,J≥J0 be two integers; a coarse-grained chain GJ⟶J0≔GJ,GJ−1,…,GJ0 of G is a sequence of graphs with GJ≡G. Each Gj=Vj,Ej,ωj is a coarse-grained graph of G for all J0⩽j⩽J, and vGj⊆vGj−1 for all j=J0+1,…,J and all v∈G. The graph Gj is the level j graph of the chain GJ⟶J0, and the Gj−1 can be viewed as a coarse-grained graph of Gj for j=J0+1,…,J. If Gj≡G for all j=J0+1,…,J, the chain GJ⟶J0 is called as an undecimated chain of G. Otherwise, GJ⟶J0 is called an decimated chain of G. For convenience of discussion, it is usually assumed each vertex v of the finest level graph GJ≡G as a cluster of singleton. When there is only one vertex in the coarsest graph GJ0, we call GJ⟶J0 a tree [6].


## 2.3. Orthonormal Bases on Graphs

In this subsection, we introduce the orthonormal bases for the coarse-grained chain on a graph [6, 35–37].LetL2G≔L2G,⋅,⋅G be the Hilbert space of vectors f:V⟶ℂ on the graph G with the inner product ⋅,⋅G, which is defined as follows:(15)f,gG≔∑v∈Vfvgv¯,f,g∈L2G,where g¯ is the complex conjugate to g. The norm ⋅G is given by fG≔f,fG for f∈L2G. Let δl,l′ be the Kronecker delta satisfying δl,l′=1 if l=l′ and 0 otherwise, and N≔V is the number of vertices. A set μll=1N of vectors in f∈L2G is an orthonormal basis for f∈L2G if(16)μl,μl′=δl,l′,1≤l,l′≤N.The generalized Fourier coefficient of degreel for f∈L2G with respect to μl is defined to be fl^≔f,μl. Then, for all f∈L2G, we have f=∑l=1Nfl^μl. Let λll=1N⊆ℝ be a nondecreasing sequence of non-negative numbers satisfying 0=λ1≤⋯≤λN, if μll=1N is an orthonormal basis for f∈L2G with μ1≡1/N; we say μl,λll=1N is an orthonormal eigenpair for f∈L2G [35]. Meanwhile, Hammond [35] also gives the definition of the graph Laplacian ℒ:L2G⟶L2G(17)ℒfp≔dpfp−∑v∈Vωp,vfv,p∈V,f∈L2G.Iff,ℒf≥0, the equation ℒμl=λlμl corresponding to the eigenvalues λl,l=1,…,N and eigenvectors μl is non-negative, and satisfies 0=λ1≤⋯≤λN with μ1≡1/N [37].Based on the properties of the eigenvalues and eigenvectors, Wang and Zhuang in [37] gave an orthonormal basis for the chain. Let GJ⟶J0≔GJ,GJ−1,…,GJ0 be a chain on the graph G with N vertices; L2GJ⟶J0 be the set of all vectors f defined on the union of vertices on all levels VJ∪⋯∪VJ0. If the restriction μl,λll=1N on the j th-level graphs Gj is an orthonormal basis for L2Gj at each level j=J0,…,J, a set pairs of vectors and complex numbers μl,λll=1N in L2GJ⟶J0 are called an orthonormal basis for the chain GJ⟶J0.


## 2.4. Decimated Tight Framelets on Graphs

In this subsection, we introduce the construction methods of a decimated tight framelet on a graph. The conclusion of this part mainly comes from reference [6]. Let G=V,E,ω be a graph and GJ⟶J0≔GJ,GJ−1,…,GJ0 be a chain on the graph G. For each vertex p in Gj=Vj,Ej,ωj, a weight ωj,p∈ℝ is defined. For the bottom level with j=J, let ωJ,pGJ≡1. Let Qj≔ωj,p:p∈Vj be the set of weights on Gj, and QJ⟶J0≔QJ,…,QJ0 be the sequence of weights for the coarse-grained chain GJ⟶J0. Zheng et al. in [6] gave the construction method of the decimated framelets on the graph, and the details are as follows.Definition 1.
LetΨj=ϕj;ψj1,…,ψjr be a tight frame in L2ℝ at scale j for j=J0,…,J. The decimated framelets ϕj,pv and ψj,pnv,p,v∈V, at scale j=J0,…,J for the chain GJ⟶J0 on the graph Gj are defined by(18)ϕj,pv=ωj,p∑l=1Nϕj^λlΛjμlp¯μlv,p∈Vj,ψj,pnv=ωj+1,p∑l=1Nψjn^λlΛjμlp¯μlv,p∈Vj+1,n=1,…,r,where for j=J, we let VJ+1=VJ and ωJ+1,p=ωJ,p. We call ϕj,p and ψj,pn low-pass and high-pass framelets at scale j.
The decimated tight framelets in Definition1 are constructed based on framelet generators in L2ℝ and the orthonormal basis associated with the chain GJ⟶J0. The function μlp can be defined by μlp=minv∈pμlv. In order to obtain the decimated tight framelets on the graph G, first, we study the construction methods of tight frames on ℝ. Then, in next section, we focus on the specific construction process of the graph wavelet frame.


## 3. Construction of Tight Wavelet Frames on the Graph

In this section, we introduce the construction process of decimated tight framelets on the graphG in detail. First, we start from the construction of the tight wavelet frames on ℝ by a given scaling function.


### 3.1. Construction of Tight Wavelet Frames onℝ

For the construction of classical tight wavelet frames onℝ, there have been many creative results. These works are generally based on the multiresolution analysis viewpoint. Chui and He in [11] demonstrated that a tight wavelet frame with 3 symmetric generators can be derived from the B-spline functions Bmm∈ℕ. However, this construction only has single-order vanishing moments. It is desirable to construct symmetric tight wavelet frames with high vanishing moments in applications. In order to achieve high order of vanishing moments, Daubechies et al. [5] considered a tight wavelet frame with 2 compactly supported generators from the B-spline functions Bmm∈ℕ, which have m order vanishing moments. Unfortunately, this tight wavelet frames are not symmetry. For studying symmetric tight wavelet frames, based on symmetric compactly supported refinable functions, Petukhov [66] discussed the symmetry of tight wavelet frames using the unitary extension principle and obtained the existence criterion of the symmetric or antisymmetric compactly supported framelets. For any compactly supported symmetric real-valued refinable function, Bin and Mo [67] showed that symmetric tight wavelet frames with 3 generators and high vanishing moments can be derived.The tight wavelet frames with desired approximation orders are very critical in practical applications. Dong and Shen in [68] proved that the tight frame system derived from a pseudospline normally have better approximation order than that derived from B-splines. Later, Dong showed that the shifts of an arbitrarily given pseudosplines are linearly independent [69]. The pseudosplines are considered an important family of refinable functions and provide a wide variety of choices of refinable functions. By selecting different parameters, pseudosplines with various orders fill in the gaps between the B-splines and orthogonal refinable functions for the first type and between B-splines and interpolatory refinable functions for the second type [69]. Hence, pseudosplines have large flexibilities in wavelet and framelet construction. In this subsection, we focus on the construction of tight wavelet frames on ℝ based on the pseudosplines.In many applications, such as computational cost and storage concern [70–75], we hope a symmetric tight wavelet frame with as small as possible number of generators; that is, the symmetric tight wavelet frame is generated by a single wavelet function. Yet, except the tight frames generated by the discontinuous Haar wavelet function or its dilated version, it is impossible to exist an MRA compactly supported real-valued symmetric tight wavelet frame with one continuous generator [25]. Therefore, one is interested in considering a symmetric tight wavelet frame with two generators. They have been extensively studied in [13, 68, 76–80]. As shown in [68], a necessary and sufficient condition has been derived for the existence of a symmetric tight wavelet frame with two generators, and details are as follows: 2π, Θ(1)
There exists a2π-periodic trigonometric polynomial Θ with real coefficients such that Θ0=1 and Θξ≥0 for all ξ∈ℝ;(2)
There exists a real-valued sequenceb on ℤ with symmetry such that detMΘξ=b^2ξ2, where the matrix MΘ is defined in (10);(3)
The greatest common factor of all the entries of the matrixMΘ satisfies a technical “gcd” condition. The technical “gcd” condition is shown in [68].However, it is difficult to obtain a2π-periodic trigonometric polynomial Θ satisfying all above the conditions, since there exist nonlinear equations in these conditions. Therefore, the symmetric tight wavelet frame with three generators is usually considered. Here, we will derive a new construction method of a symmetric tight wavelet frame with three generators based on pseudosplines.Pseudosplines are defined in terms of their refinement masks [5, 68]. The refinement mask of the first type of pseudosplines with order m,l is given by(19)1a^ξ2=1a^m,lξ2=cos2mξ2∑j=0lm+ljsin2jξ2cos2l−jξ2,and the refinement mask of the second type of pseudosplines with order m,l is given by(20)2a^ξ=2a^m,lξ=cos2mξ2∑j=0lm+ljsin2jξ2cos2l−jξ2,where 0≤l≤m−1.In this subsection, we only consider the construction of tight wavelet frame from the second type of pseudosplines using the oblique extension principle. In order to state the main results, we review the following results in [67].Theorem 2 (see [67]).
Letabe a finitely supported real-valued mask onℤsuch thata^2π/3>1anda^2π/3∉2j:j∈ℕ. Then, there does not exist a2π-periodic trigonometric rational polynomialΘwith real coefficient such that(i)
Θ0=1andΘξ≥0, a.e.ξ∈ℝ;(ii)
Θξ−Θ2ξa^ξ2can be regarded as a2π-periodic trigonometric polynomial andΘξ−Θ2ξa^ξ2≥0for allξ∈ℝ.Consequently, for any positive integerr, there do not exist finitely supported real-valued sequences ψ1,…,ψr and a 2π-periodic trigonometric rational polynomial Θ with real coefficient such that all the conditions in Theorem 2 are satisfied.Theorem 3 (see [67]).
Letabe a finitely supported real-valued mask onℤsuch thata^ξ=1+e−iξmb^ξfor some positive integermand some finitely supported sequencebonℤ. Letϕbe the compactly supported real-valued refinable function associated with maska. Suppose thatϕ∈L2ℝand the shifts ofϕare stable. Then, there exists a2π-periodic trigonometric polynomialθsuch that(21)θ0=1,θξ>0,ξ∈ℝ.Theorem 4 (see [67]).
Letabe a finitely supported mask inℤsuch thata^ξ2+a^ξ+π2≥1for allξ∈ℝanda^ξ02+a^ξ0+π2>1for someξ0∈ℝ. Then, there does not exist a2π-periodic trigonometric polynomialθ0such thatθ00=1and(22)θ0ξ−θ02ξa^ξ2+a^ξ+π2≥0∀ξ∈−π,π.Symmetry is an important property in various purposes. For a Laurent polynomialpz with real coefficients, we say that pz is symmetric (or antisymmetric) about k/2 for some k∈ℤ if pz=zkp1/z (or pz=−zkp1/z). For a nonzero Laurent polynomial p, we introduce an operator S to be(23)Spz=pzp1/z,z∈ℤ∖0.The following result can be given, as shown in [76].Theorem 5 (see [76]).
Letpandqbe two Laurent polynomials with real coefficients. Then,(1)
pis (anti)symmetric aboutk/2for somek∈ℤif and only ifSpz=±zk.(2)
Sp1/⋅z=Sp1/z=1/Spz.(3)
Spqz=SpzSqzandS⋅kz=z2kfork∈ℤ.(4)
Ifpandqare (anti)symmetric such thatSq=Sp, thenp±qis (anti)symmetric andSp±q=Sp=Sq.Next, we give the construction of symmetric tight wavelet frame. For a given refinable function with maska, the key is to find a 2π-periodic Θ, such that OEP condition is satisfied. We have the following the main result.Theorem 6.
Let2ϕdenote the second type of pseudosplines of orderm,lwith a finitely supported maska, which is defined in (20). Suppose that there is a2π-periodic trigonometric polynomialθwith real coefficients such thatθ0=1, θis symmetric, andθξ>0for allξ∈ℝ. In addition, assume the following:(24)θ0ξ=Θξ−Θ2ξa^ξ2+a^ξ+π2≥0,∀ξ∈ℝ,whereΘξ=θξ2. By the Fejér–Riesze´lemma, there exists a2π-periodic trigonometric polynomialθ1with real coefficients such thatθ1ξ2=θ0ξ, defined by(25)b^1ξ=e−iξa^ξ+π¯θ2ξ,(26)b^2ξ=12θ1ξ+e−iξθ1ξ¯,(27)b^3ξ=12−θ1ξ+e−iξθ1ξ¯.The wavelet functionsψ1,ψ2, and ψ3 are defined by(28)ψ^1ξ=b^1ξ22ϕ^ξ2,ψ^2ξ=b^2ξ22ϕ^ξ2,ψ^3ξ=b^3ξ22ϕ^ξ2.Then,ψ1,ψ2,ψ3 generates a tight wavelet frame in L2ℝ and each of the wavelet functions ψ1,ψ2, and ψ3 is either symmetric or antisymmetric.Proof 1.
By the oblique extension principle, in order to proveψ1,ψ2,ψ3 generates a tight wavelet frame, we need to check the condition (9). From (26) and (27), we deduce the following:(29)b^2ξ2=b^2ξb^2ξ¯=14θ1ξ+e−iξθ1ξ¯θ1ξ¯+eiξθ1ξ=14θ1ξ2+eiξθ1ξ2+e−iξθ1ξ¯2+θ1ξ2,and(30)b^3ξ2=b^3ξb^3ξ¯=14−θ1ξ+e−iξθ1ξ¯−θ1ξ¯+eiξθ1ξ=14θ1ξ2−eiξθ1ξ2−e−iξθ1ξ¯2+θ1ξ2.
Then,(31)b^2ξ2+b^3ξ2=θ1ξ2=θ0ξ.
Hence,(32)a^ξ2Θ2ξ+b^1ξ2+b^2ξ2+b^3ξ2=a^ξ2Θ2ξ+Θ2ξa^ξ+π2+Θξ−Θ2ξaξ2+aξ+π2=Θξ.
Sinceθ1 is a 2π-periodic trigonometric polynomial with real coefficients, we have the following:(33)b2^ξb2^ξ+π¯+b3^ξb3^ξ+π¯=0,which implies the following:(34)b1^ξb1^ξ+π¯+b2^ξb2^ξ+π¯+b3^ξb3^ξ+π¯=−a^ξa^ξ+π¯Θ2ξ.
Therefore, all the conditions in (9) are satisfied. By Theorem 1, ψ1,ψ2,ψ3 generates a tight wavelet frame in L2ℝ.
Now, we show the symmetry of the wavelet functionsψ1,ψ2, and ψ3. 2ϕ is the second type of pseudospline of order m,l, which is symmetric. Then, according to the definition of symmetry and Theorem 5, we can obtain the wavelet functions ψ1,ψ2, and ψ3 that are symmetric (or antisymmetric).Remark 1.
It is easy to see that2π-periodic trigonometric polynomial θ is existent. 2ϕ is the second type of pseudospline of order m,l with a finitely supported mask a, which is defined in (20), and the shifts of 2ϕ are stable. So, the conditions of Theorem 3 are satisfied. That is, there exists a 2π-periodic trigonometric polynomial θ such that θ0=1,θξ>0 for all ξ∈ℝ.Remark 2.
Pseudospline’s definition starts with the simple identity1=cos2ξ/2+sin2ξ/2m+l for given non-negative integers l and m with l≤m−1. By the summation of the first l+1 terms of the binomial expansion of this identity, we can define the refinement mask of pseudosplines in (20). So, we have a^ξ2+a^ξ+π2≤1. That is, θ0 of Theorem 6 can be found.
According to the above results, we give the following theorem.Theorem 7.
Let2ϕdenote the second type of pseudospline of orderm,lwith a finitely supported maska. Suppose that there are the wavelet functionsψ1,ψ2,ψ3being defined in (28). Then,(1)
ψ1,ψ2,ψ3haslvanishing moments.(2)
The approximation order of the framelet system, which be obtained byψ1,ψ2,ψ3, isminm,2l+2.Proof 2.
Since2ϕ is the second type of pseudosplines of order m,l and Θ is a 2π-periodic trigonometric polynomial, we have the following:(35)θ0ξ=Oξ2lasξ⟶0,where θ0 is defined in (24). It is straightforward to see that b^lξ=Oξl as ξ⟶0 for all l=1,2,3, where b^1,b^2,b^3 are defined in 3.5−3.7. Therefore, ψ1,ψ2,ψ3 has l vanishing moments.Next, we give an example to illustrate our constructed tight wavelet frame by Theorem6.Example: Let2ϕ denote the second type of pseudosplines of order 3,1 with a finitely supported mask,(36)a^ξ=cos6ξ21+3sin2ξ2,in which there exists a 2π-periodic trigonometric polynomial θξ, which is expressed as follows:(37)θξ=437320−97240cos2ξ+37960cos4ξ,and satisfies(38)θ0=1,θξ>0,∀ξ∈ℝ.According to Theorem6, we have the following:(39)θ0ξ=Θξ−Θ2ξaξ2+aξ+π2≥0,θ1ξ2=θ0ξ,∀ξ∈ℝ.The wavelet filtersb1,b2,b3 are defined as follows:(40)b^1ξ=e−iξa^ξ+π¯θ2ξ,b^2ξ=12θ1ξ+e−iξθ1ξ¯,b^3ξ=12−θ1ξ+e−iξθ1ξ¯.Then, the wavelet functionsψ1,ψ2, and ψ3 are defined as follows:(41)ψ^1ξ=b^1ξ22ϕ^ξ2,ψ^2ξ=b^2ξ22ϕ^ξ2,ψ^3ξ=b^3ξ22ϕ^ξ2.According to Theorem6, ψ1,ψ2,ψ3 generates a tight wavelet frame in L2ℝ. Moreover, all the wavelet functions ψ1,ψ2,ψ3 are symmetric or antisymmetric. Figure 1 shows the tight filter bank a;b1,b2,b3 with symmetric functions constructed by Theorem 6. a is the graph of the second type of pseudosplines of order 3,1. b−d are the graphs of the framelet functions ψ1,ψ2,ψ3, respectively. The set ψ1,ψ2,ψ3 generates a symmetric tight wavelet frame in L2ℝ.Figure 1
Graphs of the scaling function and the corresponding wavelets.
(a)(b)(c)(d)


### 3.2. Construction of Orthogonal Bases onG

In above subsection, we constructed the tight wavelet framelets onℝ. In order to achieve the construction of decimated tight framelets on G, according to Definition 1, we need to give the orthonormal basis associated with the chain GJ⟶J0. We only consider the Haar wavelet basis for the chain GJ⟶J0 in the paper, which is a particular case of Daubechies wavelets, and is developed onto a graph by Chui, Filbir, and Mhaskar in [23]. The Haar basis μljl=1Nj,j=J0,…,J is a sequence of collections of vectors. Each Haar basis is associated with a single layer of the chain GJ⟶J0 on a graph G. The detail discussed about the Haar basis is based on the coarse-grained chain on a graph in [6, 25, 37, 81].We first give the construction of the Haar basis for a chain with two levels. For the construction of the Haar basis for a chain with more levels, one can use this method recursively. LetGc=Vc,Ec,ωc be a coarse-grained graph of G=V,E,ω with Nc=|Vc|. We sequence the vertices of Gc by their degrees as(42)Vc=pjGc:j=1,…,Nc,dpjGc≥dpj+1Gc.Nc vectors μlc on Gc are defined by(43)μ1cvc=1Nc1,vc∈Vc;μlc=Nc−l+1Nc−l+2χl−1c−∑j=1NcχjcNc−l+1,l=2,…,Nc,where χjc is the indicator function for the j th vertex pjGc on Gc, which is given by(44)χjcv=1,v=pjGc,0,otherwise.Then, the set of functionμlcl=1Nc forms an orthonormal basis for L2Gc [6, 37].Now, we extend the orthonormal basisμlcl=1Nc for Gc on the G. For each element of μlc:l=1,…,Nc with the vertex plGc on Gc, we define(45)μl,1v=μlcvNc,v∈V,l=1,…,Nc.Letkl=plGc; we order the cluster plGc according to their degrees,(46)plGc=vl,1,…,vl,kl⊆V,dvl,j≥dvl,j+1.Fork=2,…,kl, we define(47)μl,k=kl−k+1kl−k+2χl,k−1−∑j=kklχl,jkl−k+1,j=1,…,kl,where χl,j is given by(48)χl,jv=1,v=vl,j,0,otherwise.Then, the resultingμl,k:l=1,…,Nc,k=1,…,kl is an orthonormal basis for L2G [6].Next, we can give the Haar basis for the coarse-grained chain on a graph by repeating the above process. Starting fromGJ0, an orthonormal basis μlJ0:l=1,…,NJ0 for L2GJ0 is generated as the above definition. By the chain relation of GJ0 and GJ1, we can obtain an orthonormal basis μlJ1:l=1,…,NJ1 for L2GJ1. Continuing carrying out this process on each Gj,j=1,…,J, for L2Gj, we can obtain orthonormal basis μljl=1Nj,j=1,…,J. Then, the resulting orthonormal basis μll=1N forms a Haar global orthonormal basis for a coarse-grained chain GJ⟶J0 on the graph G [6].In the following, we give a new orthogonal basis on the graphG.Theorem 8.
LetG′=V′,E′,ω′be a coarse-grained graph ofG=V,E,ωwithN′=V′. We sequence the vertices ofG′by their degrees as(49)V′=pjG′:j=1,…,N′,dpjG′≥dpj+1G′.N′vectorsμl′onG′ are defined by(50)μ1′v′=1N′1,υ′∈V′;μl′=χl−1′−∑j=1N′χjcN′−l+1,l=2,…,N′,where χj′ is the indicator function for the j th vertex pjG′ on G′, which is given by(51)χj′v=1,v=pjG′,0,otherwise.Then, the set of functionμl′l=1N′ forms an orthogonal basis for L2G′.Proof 3.
Forl=2,…,N′,(52)μ1′,μl′=1N′1,χl−1′−∑j=lN′χj′N′−l+1.
And for2≤k≤l≤N′,(53)μl′,μk′=χl−1′−∑j=lN′χj′N′−l+1,χk−1′−∑j=kN′χj′N′−k+1=−∑j=kN′χl−1′,χj′N′−k+1+∑j=lN′χj′,∑j=kN′χj′N′−k+1N′−l+1=−1N′−k+1+N′−l+1N′−k+1N′−l+1=0.
Thus, the set of functionμl′l=1N′ is an orthogonal basis for L2G′.Analogous to the above construction of the Haar basis for a chain, we can obtain the resulting orthonormal basisμl′l=1N that forms a global orthogonal basis for a coarse-grained chain GJ⟶J0 on the graph G. Once we obtain the set of function that forms an orthonormal basis for L2GJ⟶J0, the decimated tight framelet on chain GJ⟶J0 can be constructed by Definition 1. In general, the weight function ωc on Vc×Vc is defined as follows:(54)ωcp,v=∑p∈p∑v∈vωp,vvolG,p,v∈Vc.


## 3.1. Construction of Tight Wavelet Frames onℝ

For the construction of classical tight wavelet frames onℝ, there have been many creative results. These works are generally based on the multiresolution analysis viewpoint. Chui and He in [11] demonstrated that a tight wavelet frame with 3 symmetric generators can be derived from the B-spline functions Bmm∈ℕ. However, this construction only has single-order vanishing moments. It is desirable to construct symmetric tight wavelet frames with high vanishing moments in applications. In order to achieve high order of vanishing moments, Daubechies et al. [5] considered a tight wavelet frame with 2 compactly supported generators from the B-spline functions Bmm∈ℕ, which have m order vanishing moments. Unfortunately, this tight wavelet frames are not symmetry. For studying symmetric tight wavelet frames, based on symmetric compactly supported refinable functions, Petukhov [66] discussed the symmetry of tight wavelet frames using the unitary extension principle and obtained the existence criterion of the symmetric or antisymmetric compactly supported framelets. For any compactly supported symmetric real-valued refinable function, Bin and Mo [67] showed that symmetric tight wavelet frames with 3 generators and high vanishing moments can be derived.The tight wavelet frames with desired approximation orders are very critical in practical applications. Dong and Shen in [68] proved that the tight frame system derived from a pseudospline normally have better approximation order than that derived from B-splines. Later, Dong showed that the shifts of an arbitrarily given pseudosplines are linearly independent [69]. The pseudosplines are considered an important family of refinable functions and provide a wide variety of choices of refinable functions. By selecting different parameters, pseudosplines with various orders fill in the gaps between the B-splines and orthogonal refinable functions for the first type and between B-splines and interpolatory refinable functions for the second type [69]. Hence, pseudosplines have large flexibilities in wavelet and framelet construction. In this subsection, we focus on the construction of tight wavelet frames on ℝ based on the pseudosplines.In many applications, such as computational cost and storage concern [70–75], we hope a symmetric tight wavelet frame with as small as possible number of generators; that is, the symmetric tight wavelet frame is generated by a single wavelet function. Yet, except the tight frames generated by the discontinuous Haar wavelet function or its dilated version, it is impossible to exist an MRA compactly supported real-valued symmetric tight wavelet frame with one continuous generator [25]. Therefore, one is interested in considering a symmetric tight wavelet frame with two generators. They have been extensively studied in [13, 68, 76–80]. As shown in [68], a necessary and sufficient condition has been derived for the existence of a symmetric tight wavelet frame with two generators, and details are as follows: 2π, Θ(1)
There exists a2π-periodic trigonometric polynomial Θ with real coefficients such that Θ0=1 and Θξ≥0 for all ξ∈ℝ;(2)
There exists a real-valued sequenceb on ℤ with symmetry such that detMΘξ=b^2ξ2, where the matrix MΘ is defined in (10);(3)
The greatest common factor of all the entries of the matrixMΘ satisfies a technical “gcd” condition. The technical “gcd” condition is shown in [68].However, it is difficult to obtain a2π-periodic trigonometric polynomial Θ satisfying all above the conditions, since there exist nonlinear equations in these conditions. Therefore, the symmetric tight wavelet frame with three generators is usually considered. Here, we will derive a new construction method of a symmetric tight wavelet frame with three generators based on pseudosplines.Pseudosplines are defined in terms of their refinement masks [5, 68]. The refinement mask of the first type of pseudosplines with order m,l is given by(19)1a^ξ2=1a^m,lξ2=cos2mξ2∑j=0lm+ljsin2jξ2cos2l−jξ2,and the refinement mask of the second type of pseudosplines with order m,l is given by(20)2a^ξ=2a^m,lξ=cos2mξ2∑j=0lm+ljsin2jξ2cos2l−jξ2,where 0≤l≤m−1.In this subsection, we only consider the construction of tight wavelet frame from the second type of pseudosplines using the oblique extension principle. In order to state the main results, we review the following results in [67].Theorem 2 (see [67]).
Letabe a finitely supported real-valued mask onℤsuch thata^2π/3>1anda^2π/3∉2j:j∈ℕ. Then, there does not exist a2π-periodic trigonometric rational polynomialΘwith real coefficient such that(i)
Θ0=1andΘξ≥0, a.e.ξ∈ℝ;(ii)
Θξ−Θ2ξa^ξ2can be regarded as a2π-periodic trigonometric polynomial andΘξ−Θ2ξa^ξ2≥0for allξ∈ℝ.Consequently, for any positive integerr, there do not exist finitely supported real-valued sequences ψ1,…,ψr and a 2π-periodic trigonometric rational polynomial Θ with real coefficient such that all the conditions in Theorem 2 are satisfied.Theorem 3 (see [67]).
Letabe a finitely supported real-valued mask onℤsuch thata^ξ=1+e−iξmb^ξfor some positive integermand some finitely supported sequencebonℤ. Letϕbe the compactly supported real-valued refinable function associated with maska. Suppose thatϕ∈L2ℝand the shifts ofϕare stable. Then, there exists a2π-periodic trigonometric polynomialθsuch that(21)θ0=1,θξ>0,ξ∈ℝ.Theorem 4 (see [67]).
Letabe a finitely supported mask inℤsuch thata^ξ2+a^ξ+π2≥1for allξ∈ℝanda^ξ02+a^ξ0+π2>1for someξ0∈ℝ. Then, there does not exist a2π-periodic trigonometric polynomialθ0such thatθ00=1and(22)θ0ξ−θ02ξa^ξ2+a^ξ+π2≥0∀ξ∈−π,π.Symmetry is an important property in various purposes. For a Laurent polynomialpz with real coefficients, we say that pz is symmetric (or antisymmetric) about k/2 for some k∈ℤ if pz=zkp1/z (or pz=−zkp1/z). For a nonzero Laurent polynomial p, we introduce an operator S to be(23)Spz=pzp1/z,z∈ℤ∖0.The following result can be given, as shown in [76].Theorem 5 (see [76]).
Letpandqbe two Laurent polynomials with real coefficients. Then,(1)
pis (anti)symmetric aboutk/2for somek∈ℤif and only ifSpz=±zk.(2)
Sp1/⋅z=Sp1/z=1/Spz.(3)
Spqz=SpzSqzandS⋅kz=z2kfork∈ℤ.(4)
Ifpandqare (anti)symmetric such thatSq=Sp, thenp±qis (anti)symmetric andSp±q=Sp=Sq.Next, we give the construction of symmetric tight wavelet frame. For a given refinable function with maska, the key is to find a 2π-periodic Θ, such that OEP condition is satisfied. We have the following the main result.Theorem 6.
Let2ϕdenote the second type of pseudosplines of orderm,lwith a finitely supported maska, which is defined in (20). Suppose that there is a2π-periodic trigonometric polynomialθwith real coefficients such thatθ0=1, θis symmetric, andθξ>0for allξ∈ℝ. In addition, assume the following:(24)θ0ξ=Θξ−Θ2ξa^ξ2+a^ξ+π2≥0,∀ξ∈ℝ,whereΘξ=θξ2. By the Fejér–Riesze´lemma, there exists a2π-periodic trigonometric polynomialθ1with real coefficients such thatθ1ξ2=θ0ξ, defined by(25)b^1ξ=e−iξa^ξ+π¯θ2ξ,(26)b^2ξ=12θ1ξ+e−iξθ1ξ¯,(27)b^3ξ=12−θ1ξ+e−iξθ1ξ¯.The wavelet functionsψ1,ψ2, and ψ3 are defined by(28)ψ^1ξ=b^1ξ22ϕ^ξ2,ψ^2ξ=b^2ξ22ϕ^ξ2,ψ^3ξ=b^3ξ22ϕ^ξ2.Then,ψ1,ψ2,ψ3 generates a tight wavelet frame in L2ℝ and each of the wavelet functions ψ1,ψ2, and ψ3 is either symmetric or antisymmetric.Proof 1.
By the oblique extension principle, in order to proveψ1,ψ2,ψ3 generates a tight wavelet frame, we need to check the condition (9). From (26) and (27), we deduce the following:(29)b^2ξ2=b^2ξb^2ξ¯=14θ1ξ+e−iξθ1ξ¯θ1ξ¯+eiξθ1ξ=14θ1ξ2+eiξθ1ξ2+e−iξθ1ξ¯2+θ1ξ2,and(30)b^3ξ2=b^3ξb^3ξ¯=14−θ1ξ+e−iξθ1ξ¯−θ1ξ¯+eiξθ1ξ=14θ1ξ2−eiξθ1ξ2−e−iξθ1ξ¯2+θ1ξ2.
Then,(31)b^2ξ2+b^3ξ2=θ1ξ2=θ0ξ.
Hence,(32)a^ξ2Θ2ξ+b^1ξ2+b^2ξ2+b^3ξ2=a^ξ2Θ2ξ+Θ2ξa^ξ+π2+Θξ−Θ2ξaξ2+aξ+π2=Θξ.
Sinceθ1 is a 2π-periodic trigonometric polynomial with real coefficients, we have the following:(33)b2^ξb2^ξ+π¯+b3^ξb3^ξ+π¯=0,which implies the following:(34)b1^ξb1^ξ+π¯+b2^ξb2^ξ+π¯+b3^ξb3^ξ+π¯=−a^ξa^ξ+π¯Θ2ξ.
Therefore, all the conditions in (9) are satisfied. By Theorem 1, ψ1,ψ2,ψ3 generates a tight wavelet frame in L2ℝ.
Now, we show the symmetry of the wavelet functionsψ1,ψ2, and ψ3. 2ϕ is the second type of pseudospline of order m,l, which is symmetric. Then, according to the definition of symmetry and Theorem 5, we can obtain the wavelet functions ψ1,ψ2, and ψ3 that are symmetric (or antisymmetric).Remark 1.
It is easy to see that2π-periodic trigonometric polynomial θ is existent. 2ϕ is the second type of pseudospline of order m,l with a finitely supported mask a, which is defined in (20), and the shifts of 2ϕ are stable. So, the conditions of Theorem 3 are satisfied. That is, there exists a 2π-periodic trigonometric polynomial θ such that θ0=1,θξ>0 for all ξ∈ℝ.Remark 2.
Pseudospline’s definition starts with the simple identity1=cos2ξ/2+sin2ξ/2m+l for given non-negative integers l and m with l≤m−1. By the summation of the first l+1 terms of the binomial expansion of this identity, we can define the refinement mask of pseudosplines in (20). So, we have a^ξ2+a^ξ+π2≤1. That is, θ0 of Theorem 6 can be found.
According to the above results, we give the following theorem.Theorem 7.
Let2ϕdenote the second type of pseudospline of orderm,lwith a finitely supported maska. Suppose that there are the wavelet functionsψ1,ψ2,ψ3being defined in (28). Then,(1)
ψ1,ψ2,ψ3haslvanishing moments.(2)
The approximation order of the framelet system, which be obtained byψ1,ψ2,ψ3, isminm,2l+2.Proof 2.
Since2ϕ is the second type of pseudosplines of order m,l and Θ is a 2π-periodic trigonometric polynomial, we have the following:(35)θ0ξ=Oξ2lasξ⟶0,where θ0 is defined in (24). It is straightforward to see that b^lξ=Oξl as ξ⟶0 for all l=1,2,3, where b^1,b^2,b^3 are defined in 3.5−3.7. Therefore, ψ1,ψ2,ψ3 has l vanishing moments.Next, we give an example to illustrate our constructed tight wavelet frame by Theorem6.Example: Let2ϕ denote the second type of pseudosplines of order 3,1 with a finitely supported mask,(36)a^ξ=cos6ξ21+3sin2ξ2,in which there exists a 2π-periodic trigonometric polynomial θξ, which is expressed as follows:(37)θξ=437320−97240cos2ξ+37960cos4ξ,and satisfies(38)θ0=1,θξ>0,∀ξ∈ℝ.According to Theorem6, we have the following:(39)θ0ξ=Θξ−Θ2ξaξ2+aξ+π2≥0,θ1ξ2=θ0ξ,∀ξ∈ℝ.The wavelet filtersb1,b2,b3 are defined as follows:(40)b^1ξ=e−iξa^ξ+π¯θ2ξ,b^2ξ=12θ1ξ+e−iξθ1ξ¯,b^3ξ=12−θ1ξ+e−iξθ1ξ¯.Then, the wavelet functionsψ1,ψ2, and ψ3 are defined as follows:(41)ψ^1ξ=b^1ξ22ϕ^ξ2,ψ^2ξ=b^2ξ22ϕ^ξ2,ψ^3ξ=b^3ξ22ϕ^ξ2.According to Theorem6, ψ1,ψ2,ψ3 generates a tight wavelet frame in L2ℝ. Moreover, all the wavelet functions ψ1,ψ2,ψ3 are symmetric or antisymmetric. Figure 1 shows the tight filter bank a;b1,b2,b3 with symmetric functions constructed by Theorem 6. a is the graph of the second type of pseudosplines of order 3,1. b−d are the graphs of the framelet functions ψ1,ψ2,ψ3, respectively. The set ψ1,ψ2,ψ3 generates a symmetric tight wavelet frame in L2ℝ.Figure 1
Graphs of the scaling function and the corresponding wavelets.
(a)(b)(c)(d)


## 3.2. Construction of Orthogonal Bases onG

In above subsection, we constructed the tight wavelet framelets onℝ. In order to achieve the construction of decimated tight framelets on G, according to Definition 1, we need to give the orthonormal basis associated with the chain GJ⟶J0. We only consider the Haar wavelet basis for the chain GJ⟶J0 in the paper, which is a particular case of Daubechies wavelets, and is developed onto a graph by Chui, Filbir, and Mhaskar in [23]. The Haar basis μljl=1Nj,j=J0,…,J is a sequence of collections of vectors. Each Haar basis is associated with a single layer of the chain GJ⟶J0 on a graph G. The detail discussed about the Haar basis is based on the coarse-grained chain on a graph in [6, 25, 37, 81].We first give the construction of the Haar basis for a chain with two levels. For the construction of the Haar basis for a chain with more levels, one can use this method recursively. LetGc=Vc,Ec,ωc be a coarse-grained graph of G=V,E,ω with Nc=|Vc|. We sequence the vertices of Gc by their degrees as(42)Vc=pjGc:j=1,…,Nc,dpjGc≥dpj+1Gc.Nc vectors μlc on Gc are defined by(43)μ1cvc=1Nc1,vc∈Vc;μlc=Nc−l+1Nc−l+2χl−1c−∑j=1NcχjcNc−l+1,l=2,…,Nc,where χjc is the indicator function for the j th vertex pjGc on Gc, which is given by(44)χjcv=1,v=pjGc,0,otherwise.Then, the set of functionμlcl=1Nc forms an orthonormal basis for L2Gc [6, 37].Now, we extend the orthonormal basisμlcl=1Nc for Gc on the G. For each element of μlc:l=1,…,Nc with the vertex plGc on Gc, we define(45)μl,1v=μlcvNc,v∈V,l=1,…,Nc.Letkl=plGc; we order the cluster plGc according to their degrees,(46)plGc=vl,1,…,vl,kl⊆V,dvl,j≥dvl,j+1.Fork=2,…,kl, we define(47)μl,k=kl−k+1kl−k+2χl,k−1−∑j=kklχl,jkl−k+1,j=1,…,kl,where χl,j is given by(48)χl,jv=1,v=vl,j,0,otherwise.Then, the resultingμl,k:l=1,…,Nc,k=1,…,kl is an orthonormal basis for L2G [6].Next, we can give the Haar basis for the coarse-grained chain on a graph by repeating the above process. Starting fromGJ0, an orthonormal basis μlJ0:l=1,…,NJ0 for L2GJ0 is generated as the above definition. By the chain relation of GJ0 and GJ1, we can obtain an orthonormal basis μlJ1:l=1,…,NJ1 for L2GJ1. Continuing carrying out this process on each Gj,j=1,…,J, for L2Gj, we can obtain orthonormal basis μljl=1Nj,j=1,…,J. Then, the resulting orthonormal basis μll=1N forms a Haar global orthonormal basis for a coarse-grained chain GJ⟶J0 on the graph G [6].In the following, we give a new orthogonal basis on the graphG.Theorem 8.
LetG′=V′,E′,ω′be a coarse-grained graph ofG=V,E,ωwithN′=V′. We sequence the vertices ofG′by their degrees as(49)V′=pjG′:j=1,…,N′,dpjG′≥dpj+1G′.N′vectorsμl′onG′ are defined by(50)μ1′v′=1N′1,υ′∈V′;μl′=χl−1′−∑j=1N′χjcN′−l+1,l=2,…,N′,where χj′ is the indicator function for the j th vertex pjG′ on G′, which is given by(51)χj′v=1,v=pjG′,0,otherwise.Then, the set of functionμl′l=1N′ forms an orthogonal basis for L2G′.Proof 3.
Forl=2,…,N′,(52)μ1′,μl′=1N′1,χl−1′−∑j=lN′χj′N′−l+1.
And for2≤k≤l≤N′,(53)μl′,μk′=χl−1′−∑j=lN′χj′N′−l+1,χk−1′−∑j=kN′χj′N′−k+1=−∑j=kN′χl−1′,χj′N′−k+1+∑j=lN′χj′,∑j=kN′χj′N′−k+1N′−l+1=−1N′−k+1+N′−l+1N′−k+1N′−l+1=0.
Thus, the set of functionμl′l=1N′ is an orthogonal basis for L2G′.Analogous to the above construction of the Haar basis for a chain, we can obtain the resulting orthonormal basisμl′l=1N that forms a global orthogonal basis for a coarse-grained chain GJ⟶J0 on the graph G. Once we obtain the set of function that forms an orthonormal basis for L2GJ⟶J0, the decimated tight framelet on chain GJ⟶J0 can be constructed by Definition 1. In general, the weight function ωc on Vc×Vc is defined as follows:(54)ωcp,v=∑p∈p∑v∈vωp,vvolG,p,v∈Vc.


## 4. Conclusion

In this paper, we surveyed the construction methods of decimated tight framelets on the graphs. The related theory of the graph wavelet frame was analyzed, including wavelet frame onL2ℝ, graph, and chain, orthonormal bases on graphs, and the specific construction of decimated tight framelets. Because the wavelet frames on L2ℝ are the basis for the construction of the graph wavelet frame, and the filter bank of decimated tight framelets is closely related to the classical wavelet framelets, then based on the second type of pseudosplines, we presented a symmetric tight wavelet frame with 3 generators in L2ℝ using the oblique extension principle. By considering the general fundamental function Θ instead of the case Θ=1, we obtained a tight wavelet frame with good vanishing moments. Moreover, we analyzed the construction of the Haar basis for the coarse-grained chain on a graph G and obtained the new orthogonal basis on a graph G.The study of decimated tight framelets on a graph is only limited to the Haar basis. The specific construction method and practical application are only completed on the transformation of the graph Haar wavelet frame. In the future, we can consider more generalized graph wavelet frame research with a non-Haar basis. In this paper, we mainly introduced related theory of the graph wavelet frame and the detailed construction methods of the graph Haar frame, and provided theoretical basis for the later non-Haar wavelet frame construction on a graph.



---

*Source: 8153249-2022-10-03.xml*