title: Adaptive directional Haar tight framelets on bounded domains for digraph signal representations
authors: Yuchen Xiao Xiaosheng Zhuang
text: 
  
  
  
  
  Adaptive directional Haar tight framelets for digraph signal representations        
  
  
  
  
  
  Y. Xiao and X. Zhuang (Corresponding Author) Department of Mathematics, City University of Hong Kong, Tat Chee Avenue, Kowloon Tong, Hong Kong.
                yuchexiao2@cityu.edu.hk; xzhuang7@cityu.edu.hk           
                
  
  
  
  
  
  Adaptive directional Haar tight framelets on bounded domains for digraph signal representations 
  
  
  
      Yuchen Xiao         Xiaosheng Zhuang
           
  
      Received: date / Accepted: date
  ===================================================================================================
  
  
  
  
  Based on  hierarchical partitions,  we provide the  construction of Haar-type tight framelets on any  compact set K⊆^d. In particular, on the unit block [0,1]^d,  such tight framelets can be built to be with adaptivity and directionality.  We show that the adaptive directional Haar tight framelet systems can be used for  digraph signal representations. Some examples are provided to illustrate results in this paper.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § INTRODUCTION AND MOTIVATION
  
  
  
  
  
  
  
  
  
  
  
  Harmonic analysis including Fourier analysis, frame theory, wavelet/framelet analysis, etc., has been one of the most active research areas in mathematics over the past two centuries <cit.>. Typical harmonic analysis is on theory and applications related to functions defined on regular Euclidean domains <cit.>. In recent years, driven by the rapid progress of deep learning and their successful applications in solving AI (artificial intelligence) related tasks, such as natural language processing, autonomous systems, robotics,  medical diagnostics, and so on, there has been a great interest in developing harmonic analysis  for data defined on non-Euclidean domains such as manifold data or graph data, e.g., see <cit.> and many references therein. For example,  data in machine/statistical learning, are typically from social networks, biology, physics, finance, etc., and can be naturally obtained or organized as graphs or graph data. Such data can be regarded as samples from an underlying manifold, where its graph Laplacian is connected to the manifold Laplacian encoding the essential information of the data to be exploited by various machine/deep learning approaches <cit.>. One also refers this area as the graph signal processing (GSP) in contrast to signal/image/video processing <cit.>.
  
  
  
  
  For graph signal analysis, the underlying graphs are typically directed graphs (or digraphs). For example, the citation networks modelling  relations among papers (as nodes) are digraphs where a paper can either be cited or cite other papers, which indicates a directed edge between two nodes; the information networks <cit.> with nodes consisting of URLs of web pages are digraphs, where an edge means that there is an URL in one web page linking to another web page; the traffic networks <cit.> in modern cities with nodes representing intersections and edges representing traffic flows from one node to another are digraphs; the human body networks,  the nervous systems, and biological networks, etc., are all digraphs. The interested reader can refer to  <cit.> and many references therein. Similar to the wavelets and framelets for signal/image processing, multiscale representation systems based on various approaches such as spectral theory <cit.>, diffusion wavelets<cit.>, non-spectral construction <cit.>, etc., have also been developed for graph signal representation and processing.
  
  
  In this paper, motivated by the recent development of directional Haar framelet systems on ^d <cit.> as well as wavelet-like systems for graph signal processing <cit.>, we focus on the development of directional multiscale representation systems for signals defined on digraphs. We are going to investigate the following two main problems:
  
  
    1) How to construct directional Haar tight framelets on bounded domains with adaptivity?
  
    2) How to efficiently represent digraph signals?
  
  In what follows, we lay out the main idea of this paper for the above two problems.  The details are given in the later sections.
  
  
  
  For the first problem, we start with Haar wavelets.  Recall that for a separable Hilbert space ℋ, a collection X={h_j}_j∈⊆ℋ is said to be a frame if there exist two positive constants 0<C_1≤ C_2<∞ such that
  
      C_1f^2≤∑_j∈| f, h_j|^2≤ C_2f^2  ∀ f∈ℋ,
  
  where ·,· and  · are the inner product and norm in ℋ, respectively. If C_1=C_2, then such an X is said to be tight. If C_1=C_2=1 and h_j=1 for all j, then such an X is an orthonormal basis for ℋ.
  
  Haar wavelet system <cit.> is the first ever constructed orthonormal wavelet system on the interval [0,1]. It is a very simple yet elegant system that even  nowadays there are many literatures on Haar-type systems, e.g.,  see <cit.>. Starting from a scaling (refinable) function ϕ:=χ_[0,1], which is a characteristic function defined on the unit interval I:=[0,1], and the mother wavelet function ψ:=χ_[0,1/2)-χ_[1/2,1], one can show that the system
  
      X(;ϕ,ψ):={ϕ(·-k) k∈}∪{ψ_j,k:=2^j/2ψ(2^j·-k) k∈}_j∈_0
  
  obtained from dilations and translations of ϕ and ψ, is an orthonormal wavelet basis for L_2() of square-integrable functions on  <cit.>. Here _0:=∪{0}. Thanks to their compact support property, the restriction of such an orthonormal wavelet basis on the unit interval I directly gives an orthonormal basis on the bounded domain for L_2([0,1]) of square-integrable functions on I:
  
      X(I;ϕ,ψ):={ϕ}∪{ψ_j,k 0≤ k < 2^j}_j∈_0.
  
  This is indeed the system constructed by Haar in <cit.>.
  
  
  
  
  
  
  In higher dimensions, the tensor product approach is usually employed to obtain orthonormal wavelets,  e.g., see Fig. <ref> for the 4 generators ϕ⊗ϕ, ϕ⊗ψ, ψ⊗ϕ, and ψ⊗ψ of the 2D orthonormal Haar wavelets. However, it is well-known that the tensor product orthonormal real-valued wavelets lack directionality <cit.>, which hinders the sparsity representation of such systems for high-dimensional data analysis and their applications in image/video processing.
  Various approaches including curvelets <cit.>, shearlets <cit.>, dual-tree complex wavelets <cit.>, TP-TFs <cit.>, etc., on increasing directionality of  multiscale representation systems have been proposed over the past two decades, which we will not get into much of such developments but draw our attentions only to the main focus of this paper: Haar-type multiscale representation systems with directionality on  bounded domains. Note that in order to increase directionality, one necessarily needs to consider  wavelet frames or framelet systems, which are more redundant representation systems than the orthonormal systems.
  
  
  
  
  
  
  
  In <cit.>, the authors proposed a new and simple  Haar-type directional system, the directional Haar tight framelets (DHF) for L_2(^2),  whose generators have 4 directions (0^∘, 90^∘, and  ± 45^∘). The system is generated from the scaling function φ = χ_I⊗χ_I and 6 generators in  Ψ:={ψ^(1,1),…, ψ^(3,4)} defined by
  
      ψ^(1,2)   = χ_B_1-χ_B_2,   ψ^(1,3)   = χ_B_1-χ_B_3,   ψ^(1,4)   = χ_B_1-χ_B_4,
      ψ^(2,3)   = χ_B_2-χ_B_3,   ψ^(2,4)   = χ_B_2-χ_B_4,   ψ^(3,4)   = χ_B_3-χ_B_4,
  
  where B_1:=[0,1/2)× [0,1/2), B_2:=[1/2,1]×[0,1/2), B_3:=[0,1/2)× [1/2,1], and B_4:=[1/2,1]× [1/2,1] are the 4 sub-blocks obtained from  refining  the unit square I^2 = [0,1]× [0,1]=∪_ℓ=1^4 B_ℓ,  see Fig. <ref>. Clearly, compared to the 2D tensor product Haar wavelets (see Fig. <ref>), the DHF system has more directionality: the generators ψ^(1,2) and ψ^(3,4) can be used for vertical edge information extraction, the generators ψ^(1,3) and ψ^(2,4) can be used for horizontal edge information extraction, and the generators ψ^(1,4) and ψ^(2,3) can be used for ±45^∘ edge information extraction.  Note that the labelling  (ℓ_1,ℓ_2), 1≤ℓ_1<ℓ_2≤ 4, is with respect to the number of choices of choosing two sub-blocks from the four sub-blocks in [0,1]^2  (4  2=6 , see Theorem <ref> for more general results). The system defined by
  
      X(^2;φ,Ψ):=
      {φ(·-k) k∈^2}∪{ψ_j,k: k∈^2, ψ∈Ψ}_j∈_0,
  
  where ψ_j,k:=2^j/2ψ(2^j·-k),
  is a tight frame  for L_2(^2).  Its restriction to the unit square I^2=[0,1]^2 can be shown as
  
      X(I^2;φ, Ψ):=
      {φ}∪{ψ_j,k: k=(k_1,k_2), 0≤ k_1,k_2<2^j; ψ∈Ψ}_j∈_0.
  
  This system X(I^2; φ,Ψ)
  is indeed also  a tight frame for L_2([0,1]^2) (see Theorem <ref>). Such a tightness property on [0,1]^2 is not explicitly shown in <cit.> nor in <cit.>. In <cit.>, the authors  further generalized such directional Haar tight framelets to arbitrary dimension ^d.
  
  By inspecting the structure of the system, we can  regroup X(I^2;φ,Ψ) as
  
      X(I^2;φ,Ψ)={φ}∪⋃_j=0^∞⋃_k_1,k_2=0^2^j-1Ψ_j,(k_1,k_2),
  
  where each
  
      Ψ_j,k:={2^j/2ψ^(ℓ_1,ℓ_2)(2^j·-k) 1≤ℓ_1<ℓ_2≤4}
  
  has 6 framelet functions supported on a sub-block
  
      B_j,(k_1,k_2)=[2^-jk_1,2^-j(k_1+1)]×[2^-jk_2,2^-j(k_2+1)]⊆ I^2
  
  at level j. Each B_j,(k_1,k_2)  is further refined to 4 sub-blocks  B_j+1,(2k_1,2k_2), B_j+1,(2k_1+1,2k_2), B_j+1,(2k_1,2k_2+1), and B_j+1,(2k_1+1,2k_2+1) at level j+1, see Fig. <ref> for the illustration. In other words, the system in (<ref>) is based on a hierarchical partition of the unit square I^2.  This  point of view together with how to sparsely represent digraph signals motivates us the main result in Theorem <ref>, where the question boils down to the construction of directional Haar tight framelet systems with adaptivity.  Here, by “adaptivity” we mean that the blocks are not necessary square sub-blocks. We  affirmatively  show that  a system X({_j}_j∈_0),  associated with a sequence _j with each _j being a collection of subsets of a compact set K⊆^d from a refining process, could be built to be a tight frame for L_2(K). When K=I^2=[0,1]^2, such a system is our adaptive directional Haar tight framelets and it plays a key role in our second problem of efficient representations of digraph signals.
  
  
  
  
  
  Now, continue to the second problem of efficient representations of signals on digraphs (directed graphs). We begin with undirected graphs. Recall that a graph is an ordered pair =(V,W) with a nonempty set V={v_1,…,v_n} of vertices and  an (weighted) adjacency matrix W: V× V→ [0,∞) of size n× n indicating edges  between vertices (W(v_i,v_j)≠ 0 if  there is an edge from the vertex v_i to  v_j; otherwise 0). If the edges are unordered, that is, the edge from v_i to v_j is considered to be the same as the edge from v_j to v_i, in which case, the matrix W is symmetric,  then  is said to be undirected; otherwise, it is called a directed graph or digraph,  see Fig. <ref> for an example of undirected graph and digraph. A signal defined on a graph  (or graph signal) is a function f: V→.
  
  
  
  For a signal f on an undirected graph =(V,W), one could identify it with a function on I=[0,1] by  associating each vertex v∈ V a suitable subinterval I_v⊆ I. In <cit.>, the paper uses the concept of a filtration, which a weight tree, for identifying vertices as subintervals in I as well as building an (Haar-type) orthonormal basis on the filtration to represent signals on the underlying graph . In this paper, we use the concept of the  coarse-grained chains (<cit.>). Roughly speaking, a coarse-grained chain _J→0:=(_J,_J-1,…,_0) of ≡_J is a sequence of graphs such that _j-1 is from the clustering result of  _j. When _0 has only one node, the coarse-grained chain is actually equivalent to a filtration in <cit.>.  See Fig. <ref> for an example of a coarse-grained chain _3→0:=(_3,…,_0) of . Each vertex in _j-1 is a cluster of vertices in _j. Based on such a coarse-grained chain, one can give a hierarchical representation {_j}_j=0^3 of the interval I, where each _j={I_j,k} is the collection of subintervals I_j,k of I such that ∪_k I_j,k = I, see Fig. <ref>.
  
  Based on such a hierarchical sequence, one could build a Haar-type orthonormal basis <cit.> for the function space {χ_I_3,k k = 1,…,6}, which is the space for the signal defined on the graph. See Section <ref> for more details.
  
  
  
  
  Returning to digraph signal representations, can one use similar approaches for undirected graph to represent digraph signals? The answer is yes and no. For “no” it is because most of the clustering algorithms are developed based on the symmetry property of the adjacency matrix W or the well-defined and well-understood operator on the undirected graph: the graph Laplacian <cit.>. It is not trivial to directly use them for digraph cases. For “yes” it is because there are undirect ways to circumvent such difficulties. In fact, one typical approach is to define a counterpart graph Laplacian on digraph, such as the Hodge Laplacian in <cit.>, the weighted adjacency matrix in <cit.>, the so-called dilaplacian in <cit.>, and so on. In this paper, we use the idea developed in <cit.>: to lift the dimension from one to two by using a pair of undirected graphs to represent a given digraph. In a nutshell, a digraph signal is identified as a signal defined on I^2=[0,1]× [0,1] through the following steps.
  
  
  
    1) In view of the singular value decomposition,  the adjacency matrix W in a digrah  =(V,W) is uniquely determined by WW^⊤ and W^⊤ W from which one could construct a pair of undirected graphs ^x = (V, WW^⊤) and ^y=(V,W^⊤ W).
  
    2)  Applying well-known techniques, e.g., <cit.>, for undirected graphs, one can represent vertices in each graph of ^x and ^y as subintervals in I=[0,1].
  
    3) Suppose a vertex v is identified as a subinterval I_v^x=[a,b) on ^x and I_v^y=[c,d) on ^y, then v in the original digraph  is identified as a block [a,b)× [c,d)⊆ I^2. Consequently, the vertices in the digraph are sub-blocks in the unit square.
  
    4) Then, signals on  can be viewed as functions defined on the unit square [0,1]^2.
  
  
  In <cit.>, once orthonormal bases are built for ^x and ^y, then the tensor product approach is  used to construct orthonormal bases for . As we pointed out, the tensor product approach lacks directionality. Since directional systems provide better sparse representations than those by the tensor product ones, in this paper, we  use our  adaptive directional Haar tight framelets in 2D for the digraph signal representations based on the above digraph representations ↔(^x,^y).
  
  The contribution of the paper is threefold. First, based on a hierarchical partition,  we provide a simply yet flexible construction of Haar-type tight framelets on any compact set K⊆^d. Second, such framelet systems include directional Haar systems in <cit.> as special cases and lead to the adaptive directional Haar tight framelet systems for non-dyadic partitions of the unit block [0,1]^d. Last but not least,  we demonstrate that digraph signals can be identified as signals defined on the unit square [0,1]^2 and hence could be efficiently represented by the adaptive directional Haar tight framelet systems where the directionality is a really desired property.
  
  The structure of the paper is as follows. In Section <ref>, we present our main results on the construction of tight frames for L_2(K) for some compact set K⊆^d. Then, adaptive directional Haar tight framelets on bounded domains are deduced. In Section <ref>, we show how to represent digraph signals using the developed adaptive directional Haar tight framelets. In Section <ref>, we provide some examples to illustrate our main results. Conclusion and further remarks are given in Section <ref>. Some proofs are postponed to the last section.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § ADAPTIVE DIRECTIONAL HAAR TIGHT FRAMELETS ON BOUNDED DOMAINS
  
  
  Let K⊆^d be a compact set  and consider the Hilbert space L_2(K):={ff_2:=(∫_K |f(x)|^2dx)^1/2<∞} of square-integrable functions f on K. The  inner product on L_2(K) is defined by f,g:=∫_K f(x)g(x)dx for f,g∈ L_2(K).  In this section, based on a hierarchical partition of K,
   we construct a system X={φ}∪{Ψ_j}_j∈_0of elements in L_2(K) and show that it is a tight frame for L_2(K). Such a system X leads to our adaptive directional Haar tight framelets (AdaDHF) on K.
  
  Before we present and prove our main result in Theorem <ref>, let us introduce some necessary notation, definitions, and auxiliary results first.  For a Hilbert space , the collection X={h_j}_j∈⊆  is a tight frame for  if
  
      f^2 = ∑_j∈| f, h_j|^2   ∀ f∈.
  
  Using the polarization identity, one can show that it is equivalent to
  
      f = ∑_j∈ f, h_j h_j  ∀ f∈.
  
  
  We denote _m  the identity matrix of size m× m. The matrix A in the following  lemma is used  to connect functions on two scales supported on a same block B⊆ K. Its proof is  postponed to Section <ref>.
  
  
  Let m∈ and  b_1, …, b_m be m positive constants such that ∑_ℓ=1^m b_ℓ =1.  Let n=m 2 and
  A=(a_i,ℓ)_0≤ i≤ n; 1≤ℓ≤ m be a matrix of size (n+1) × m of the form:
  
      A =
      [
      √(b_1)   √(b_2)   √(b_3)   ⋯   √(b_m-1)   √(b_m)
      √(b_2)    -√(b_1)    0    ⋯    0     0
      √(b_3)    0     -√(b_1)   ⋯    0     0
      ⋮   ⋮   ⋮   ⋱   ⋮   ⋮
      
      0     0     0    ⋯   √(b_m)    -√(b_m-1)
      ].
  
  That is, the first row of A (with respect to i=0) is
  
      (a_0,ℓ)_ℓ=1^m = (√(b_ℓ))_ℓ=1^m,
  
  and the  row (a_i,ℓ)_ℓ=1^m for i≠ 0 is given by
  
      a_i,ℓ = a_(i_1,i_2),ℓ=
      √(b_i_2)   ℓ = i_1,
      
      -√(b_i_1)   ℓ = i_2,
      
      0
  
  where for each i≠ 0, the index i is uniquely determined by a pair (i_1,i_2) satisfying 1≤ i_1< i_2≤ m through (i_1,i_2)↦ i=(2m-i_1)(i_1-1)/2+i_2-i_1.
  Then, A satisfies A^⊤ A=_m.
  
  
  
  
  For  a measurable set B⊆^d, we denote  |B| as its  Lebesgue measure and  χ_B as the characteristic function on B. The following lemma shows that we can construct a set of functions supported on B so that it is tight.
  
  
  
  Let B⊆ K⊆^d be a measurable subset in the compact set K satisfying |B|>0 and   B_ℓ, ℓ=1,…, m with m≥2 be measurable sub-blocks of B such that
  B =∪_ℓ=1^mB_ℓ,  |B_ℓ|>0 for all ℓ=1,…, m, and  |B_ℓ_1∩ B_ℓ_2|=0 for ℓ_1≠ℓ_2.      Define the set Ψ_B:={ψ^(ℓ_1,ℓ_2) 1≤ℓ_1<ℓ_2≤ m} of functions  by
   
      ψ^(ℓ_1,ℓ_2):=√(b_ℓ_2)γ_ℓ_1-
            √(b_ℓ_1)γ_ℓ_2,    1≤ℓ_1<ℓ_2 ≤ m,
  
   where γ_ℓ:=χ_B_ℓ/√(|B_ℓ|)  and b_ℓ:=|B_ℓ|/|B|. Then Ψ_B is a tight frame for
   
      _B:={ψ^(ℓ_1,ℓ_2) 1≤ℓ_1<ℓ_2≤ m }.
   That is,
   
      f = ∑_1≤ℓ_1<ℓ_2≤ m f, ψ^(ℓ_1,ℓ_2)ψ^(ℓ_1,ℓ_2)  ∀ f∈_B.
  
  
  
  
  
  The proof of Lemma <ref> uses results in Lemma <ref> and it is one of the key steps in our proof of the main theorem. We postpone it to Section <ref>.
  
  Note that ψ^(ℓ_1,ℓ_2) in Lemma <ref> are constructed from χ_B_ℓ, ℓ=1,…,m. The following lemma demonstrates that those χ_B_ℓ's can be constructed  from ψ^(ℓ_1,ℓ_2)'s  together with χ_B as well.
  
  
  
  
  Let B, B_ℓ, γ_ℓ, ℓ=1,…, m, and Ψ_B:={ψ^(ℓ_1,ℓ_2), 1≤ℓ_1<ℓ_2≤ m} be defined as  in Lemma <ref>. Define vectors Γ_B, Φ_B of functions by
  
      Γ_B:=(γ_ℓ)_ℓ=1^mΦ_B:=(γ_B,Ψ_B)=(γ_B,ψ_1,…,ψ_n),
  
  where γ_B:=χ_B/√(|B|) and ψ_1,…, ψ_n are from enumerating the elements in Ψ_B   through (ℓ_1,ℓ_2)↦(2m-ℓ_1)(ℓ_1-1)/2+(ℓ_2-ℓ_1) with n = m  2=m× (m-1)/2. Then
  
      Γ_B = A^⊤Φ_B.
  
  Consequently, the space _1:={γ_ℓℓ=1,…,m}=_B⊕_B where _B:={χ_B} and _B:={ψψ∈Ψ_B}.
  
  
  Note that Γ_B is a vector of size m while Φ_B is a vector of size n=m 2+1. From the definition of ψ^(ℓ_1,ℓ_2) in (<ref>) and B=∪_ℓB_ℓ, it is easy to verify that
  
      Φ_B = AΓ_B,
  
  where A=(a_i,ℓ)_0≤ i≤ n; 1≤ℓ≤ m is a matrix of size (n+1) × m  defined as in Lemma <ref>.
  
  By Lemma <ref>, we have A^⊤ A=_m, which implies that Γ_B = A^⊤Φ_B. Hence, _1⊆_B+_B.  Now the fact that _1=_B⊕_B follows directly from _B⊆_1, _B⊆_1 and _B⊥_B. This completes the proof.  ▪
  
  
  
  
  By splitting the compact set K, one can obtain subsets B_ℓ of K. For each subset B_ℓ, one can further refine it to have smaller subsets. Such a process could continue and one could obtain a hierarchical partition of K.  We say that the sequence {_j}_j∈_0 is a hierarchical partition of K if it satisfies the following conditions:
  
    
    a) Root property: each _j is a collection of finite number of measurable subsets of K with _0={K}, ∪_B∈_j B = K,  |B|>0 for all B∈_j, and |B_1∩ B_2|=0 for any B_1≠ B_2  in _j.
  
    
    b) Nested property: {_j}_j∈_0 is nested in the  sense that for each B∈_j-1,  B = ∪_ℓ=1^c_B B_ℓ with B_ℓ∈_j. That is B_ℓ's are children of B in _j and the positive integer c_B≥1 denotes the number of children of B in _j. In other words,   the sets in _j are obtained from the splitting of sets in _j-1.
  
    
    c) Density  property: lim_j→∞(_j)=0 where  (_j):=max{(B) B∈_j} and (B):=sup{|x-y| x,y∈ B} is the diameter of the set B.
  
  
  We are now ready to introduce and prove our main result.
  
  Let K⊆^d be a compact set in ^d with |K|>0 and {_j}_j∈_0 be a hierarchical partition of K.
  Define the set
  
      X({_j}_j∈_0):={φ_0}∪{Ψ_j,B B∈_j}_j∈_0
  
  of functions by φ_0 := χ_K/√(|K|)
  and  Ψ_j,B:={ψ_j,B^(ℓ_1,ℓ_2):  1≤ℓ_1<ℓ_2≤ c_B}_j=0^∞ with
        
      ψ_j,B^(ℓ_1,ℓ_2):=√(b_ℓ_2)γ_ℓ_1-
            √(b_ℓ_1)γ_ℓ_2,    1≤ℓ_1<ℓ_2 ≤ c_B,
  
   where  B_ℓ∈_j+1, ℓ=1,…, c_B are the children sub-blocks of B,
   γ_ℓ:=χ_B_ℓ/√(|B_ℓ|),  and b_ℓ:=|B_ℓ|/|B|.
  Then, X({_j}_j∈_0) is a tight frame for L_2(K).
  
  
  
  By (<ref>), we need to prove that
  
      f_2^2    
      =
      | f, φ_0|^2+∑_j=0^∞∑_B∈_j∑_1≤ℓ_1<ℓ_2≤ c_B | f, ψ^(ℓ_1,ℓ_2)_j,B|^2  ∀ f∈ L_2(K).
  
  We proceed  through the following steps.
  
  
  
    1) First, let _0:={χ_K}={φ_0} and
  
      _j:={χ_B B∈_j}
  
  for j∈_0. Then by the nested property of {_j}_j∈_0, we have
  
      _0⊆_1⊆⋯⊆_j⊆_j+1⊆⋯.
  
  By the density property of  {_j}_j∈_0, we see that ∪_j∈_0_j is dense in L_2(K).
  
  
    2) Let
  
      _j:={ψ: ψ∈Ψ_j,B, B∈_j}
  
  and
  
      _j,B:={ψψ∈Ψ_j,B},    j∈_0.
  
  Thanks to the nested property of {_j}_j∈_0 and our construction of ψ_j,B^(ℓ_1,ℓ_2), we have that for any B∈_j
  
      χ_B, ψ^(ℓ_1,ℓ_2)_j,B = 0,    1≤ℓ_1<ℓ_2≤ c_B.
  
  Hence, we see that _j⊥_j and _j⊥_j' for all j,j'∈_0 and j≠ j'. Moreover, we claim that
  
      _j+1 = _j ⊕_j  ∀ j∈_0.
  
  Obviously,  _j⊆_j+1 and _j⊆_j+1. Hence, we only need to show that _j+1⊆ (_j +_j), which by the nested property and noticing _j=⊕_B∈_j_j,B for all j∈_0, it suffices to show that for each B∈_j, functions in
  
      {χ_B_ℓ B_ℓ∈_j+1 B  }⊆_j+1
  
  are the linear combinations of functions in
  
      {χ_B}∪{ψ_j,B^(ℓ_1,ℓ_2) 1≤ℓ_1<ℓ_2≤ c_B}⊆ (_j+_j),
  
  which follows from Lemma <ref>.
  Therefore _j+1 = _j⊕_j for all j∈_0.
  
  
    3) Consequently, _0⊕⊕_j∈_0,B∈_j_j,B is dense in L_2(K). Hence,  for each f∈ L_2(K), there exists a sequence  {c_φ_0}∪{c_j,B^(ℓ_1,ℓ_2) B∈_j, 1≤ℓ_1,ℓ_2≤ c_B }_j∈_0 of constants such that
  
      f=c_φ_0φ_0 +∑_j=0^∞∑_B∈_j∑_1≤ℓ_1<ℓ_2≤ c_Bc_j,B^(ℓ_1,ℓ_2)ψ^(ℓ_1,ℓ_2)_j,B,
  
  where the equality holds in the L_2-sense. Define
  
      f_j,B:= ∑_1≤ℓ_1<ℓ_2≤ c_Bc_j,B^(ℓ_1,ℓ_2)ψ^(ℓ_1,ℓ_2)_j,B∈_j,B.
  
  Then f=c_φ_0φ_0+∑_j=0^∞∑_B∈^j f_j,B and we have
  
      f_2^2    =  f,f =
      |c_φ_0|^2 +∑_j=0^∞∑_B∈_jf_j,B_2^2,
  
  where the series converges absolutely. On the other hand, we have
  
      ∑_h∈ X({_j}_j∈_0 | f, h|^2
         =| f,φ_0|^2+∑_j=0^∞∑_B∈_j∑_1≤ℓ_1<ℓ_2≤ c_B| f, ψ^(ℓ_1,ℓ_2)_j,B|^2
         =| f,φ_0|^2+∑_j=0^∞∑_B∈_j∑_1≤ℓ_1<ℓ_2≤ c_B| f_j,B, ψ^(ℓ_1,ℓ_2)_j,B|^2.
  
  Hence, to prove that f_2^2 = ∑_h∈ X({_j}_j∈_0)| f, h|^2, it suffices to show that for each j∈_0 and B∈_j, we have
  
      f_j,B_2^2=∑_1≤ℓ_1<ℓ_2≤ c_B| f_j,B, ψ^(ℓ_1,ℓ_2)_j,B|^2.
  
  This is equivalent to showing that Ψ_j,B={ψ_j,B^(ℓ_1,ℓ_2) 1≤ℓ_1,ℓ_2≤ c_B} is a tight frame for _j,B, which  follows from Lemma <ref>.
  
  
  Consequently, we prove that X({_j}_j∈_0) is a tight frame for L_2(K).  ▪
  
  
  
  
  The system X({_j}_j∈_0) in Theorem <ref>, which depends only on the hierarchical partition of K,  is very flexible. Next, we discuss some of its special cases.
  
  In practice, signals usually lie in finite-dimensional spaces. Hence, it is useful to study  the cut-off system X({_j}_j=0^J) up to some scale J∈_0.
  
  
   Retaining all assumptions and notation in Theorem <ref>. Given J∈_0, define the cut-off system X({_j}_j=0^J) by
  
      X({_j}_j=0^J):={φ_0}∪{Ψ_j,B B∈_j}_j=0^J-1.
  
  Then, X({_j}_j=0^J) is a tight frame for _J defined as in (<ref>).
  
  
  
  Note that
  _J=_0⊕⊕_j=0^ J-1_j. The conclusion follows similarly to the proof of Theorem <ref> by showing that f_2^2=∑_h∈ X({_j}_j=0^J)| f, h|^2 for all f∈_J.
  
  
  We immediately have the following corollary if each splitting of a block B has at most two children (sub-blocks).
  
  
   Retaining all assumptions in Theorem <ref>. In addition, if c_B≤ 2 for each B∈_j and j∈_0, that is, the number of  children of each block B is at most 2, then X({_j}_j∈_0) is an orthonormal basis for L_2(K).
  
  
  
  Note that L_2(K) =_0⊕_j∈_0, B∈_j_j,B from the proof of Theorem <ref>.
  If c_B≤2, then there is at most one element ψ_j,B=√(b_2)γ_1-√(b_1)γ_2 in Ψ_j,B and ψ_j,B_2=1 for all j,B. Note that φ_0_2=1 also. Consequently, each _j,B is at most one-dimensional. Hence, X({_j}_j∈_0) is orthonormal. ▪
  
  
  The Haar orthonormal wavelets on I=[0,1] is a special case of the consequence of Corollary <ref>. It is with respect to the hierarchical partition {_j}_j∈_0 of the unit interval I with  _j:={I_j,k := [2^-jk,2^-j(k+1)] k = 0,…, 2^j-1}.  Note that each  I_j,k has exactly two children subintervals I_j+1,2k and  I_j+1,2k+1 with the same size. Such a type of partition is called dyadic.  More generally,  in  dimension d,  we have the following result, which  includes directional Haar tight framelets in <cit.> as special cases.
  
  
  For j∈_0, let
  _j:={I_j,k := [2^-jk,2^-j(k+1)] k = 0,…, 2^j-1}
  and define
  
      _j:=⊗_d _j:={I_j,k_1× I_j,k_2×⋯× I_j,k_d 0≤ k_1,…, k_d<2^j}.
  
  Then, the system X({_j}_j∈_0)  defined  as in Theorem <ref> is a tight frame for L_2([0,1]^d). In particular, when d=1, it is the Haar orthonormal wavelets X(I;ϕ,ψ)  defined  as in (<ref>) and when d=2, it is the directional Haar tight framelets X(I^2;φ,ψ) defined as in (<ref>).
  
  
  
  It is easy to show that {_j}_j∈_0 is a hierarchical partition of the unit block I^d :=[0,1]^d in d-dimension. Each B∈_j has exactly 2^d children sub-blocks in _j+1. The conclusions  follow directly from Theorem <ref> and Corollary <ref>.  ▪
  
  
  
  The blocks in _j  defined as in (<ref>) are dyadic. In practice, as demonstrated in Fig. <ref>, intervals used to identify nodes on a graph are not necessarily dyadic. Hence, we introduce the adaptive directional Haar tight framelets (AdaDHF) based on the following hierarchical partition of the unit square I^d=[0,1]^d, whose sub-blocks are not necessarily dyadic.
  
  
  For each  s=1,…,d, let {_j^s}_j∈_0 be a hierarchical partition of the unit interval I=[0,1], where
  _j^s:={I_j,k^s k = 1,…, n_j,s}.
  Define
  
      _j:=⊗_d _j^s = {I_j,k_1×⋯× I_j,k_d k_s=1,…, n_j,s, s = 1,…, d}.
  
  Then, {_j}_j∈_0 is a hierarchical partition of the unit block I^d=[0,1]^d and  the system X({_j}_j∈_0)  defined  as in Theorem <ref> is a tight frame for L_2([0,1]^d). In particular, for any J∈_0, the cut-off system X({_j}_j=0^J) as defined in (<ref>) is a tight frame for _J.
  
  
  Since {_j^s}_j∈_0 is a hierarchical partition of I, by the definition of _j, {_j}_j∈_0 is a hierarchical partition of the unit square I^d. The conclusions follow directly from Theorem <ref> and Corollary <ref>.  ▪
  
  
  
  
  
  
  
  
  
  
  
  
  
  § DIGRAPH SIGNAL REPRESENTATIONS
  
  
  In this section, we use the AdaDHF systems  developed in Corollary <ref> of Section <ref> to investigate digraph signal representations. We study representations of signals on undirected graphs first and then turn to digraph signal representations.
  
  
  
   §.§ The coarse-grained chain of an undirected graph
  
  
  We start with undirected graphs and the coarse-grained chain of an undirected graph.  For an undirected graph =(V,W) with vertex (or node) set V={v_1,…,v_n} and adjacency matrix  W: V× V→ [0,∞). We use |V| (abuse of notation) to denote the number of vertices of . The degree of a vertex v_i is denoted by (v_i):=∑_j=1^n W(v_i,v_j). If W(v_i,v_j)>0, then it corresponds to an edge (v_i,v_j) (unordered pair). Two vertices v_i, v_j are said to be connected if there exists a path between  them, that is, [W^m](v_i,v_j)≠0 for some positive integer m. The graph  is said to be connected if there exists a path between any two vertices. Throughout the paper, we only consider connected graphs.
  
  Let =(V,W) and ^cg=(V^cg,W^cg) be two undirected graphs. We say that ^cg is a coarse-grained graph of  if V^cg is a partition of V; i.e., there exists subsets U_1,…,U_m of V for some m∈ such that
  
      V^cg ={U_1,…,U_m},  
      U_1∪⋯∪ U_m = V,   
      U_i∩ U_j = ∅,   1≤ i< j≤ m.
  
  In such a case, each node U_i of ^cg is called a cluster  from . The edges of ^cg are edges between clusters. Clusters  U_1,…, U_m define an equivalence relation on : two vertices u,v∈ are equivalent, denoted by u∼ v, if u and v belong to the same cluster. An equivalent class (cluster) in , which is a node in ^cg, associated with a vertex v∈ V, then can be denoted as [v]_^cg:={u∈ u∼ v}, and we have V^cg=V/∼ ={[v]_^cg v ∈ V}. If no confusion arises, we will drop the subscript ^cg and simply use [v] to denote a cluster from . Note that a vertex v in  can be viewed as [v]_={v}, which is a singleton.
  
  Given an undirected graph =(V,W), there are many clustering algorithms can be used to obtain clusters from , see  e.g., <cit.>. Once we obtain the set {U_1,…,U_m}=:V^cg of clusters from , we can define the weighted adjacency matrix W^cg on V^cg× V^cg by
  
  
      W^cg([u],[v]):=∑_u∈[u]∑_v∈[v]W(u,v),    [u],[v]∈ V^cg.
  
  
  Then, the new graph ^cg:=(V^cg,W^cg)  is  a coarse-grained graph of . Given the new graph ^cg, we can further apply clustering process on it and obtain a coarse-grained graph of ^cg. Recursively doing such clustering processes, we would obtain a chain of graphs from the original graph . More precisely, let J≥ 0 be an integer. We say that the sequence _J→ 0:=(_J, _J-1,…,_0) with _J≡ is a coarse-grained chain of   if _j=(V_j, W_j) is a coarse-grained graph of  for all 0≤ j≤ J and [v]__j⊆ [v]__j-1 for each j=1,…, J and for all v∈ V. Note that, we treat each vertex v of the finest level graph _J≡ as a cluster of singleton. See Fig. <ref> and Fig. <ref> for  illustrations of coarse-grained chains.
  
  
  Once we have a coarse-grained chain _J→ 0 of , we next discuss how to associate it with a hierarchical partition of I=[0,1].  Without loss of generality, we could assume that _0=(V_0,W_0) has only one node, which is a cluster consisting of all vertices of . If not, we simply add such a graph to the chain.   Now we  define _j recursively as follows (c.f. Fig. <ref> and  Fig. <ref>).
  
  
    1) _0={I=[0,1]} is the root node.
  
  
    2) Suppose _j-1={I_j-1,k=[a_k,b_k] k=1,…,|V_j-1|} has been defined and associated with the graph _j-1=(V_j-1,W_j-1). Then, I_j-1,k is associated with a node u_k∈ V_j-1.
  
  
    3) For each u_k∈ V_j-1, denote (and order) the children of u_k in _j=(V_j,W_j) as u_k,1,…, u_k,m∈ V_j and define subintervals I_j,k,1,…, I_j,k,m by
  
      I_j,k,s = [a_k+w_s-1,a_k+w_s],   s=1,…, m,
  
  where w_s:=(b_k-a_k)×∑_i=1^s (u_k,i)/∑_i=1^m (u_k,i). Note that [a_k,b_k]=∪_s I_j,k,s. Collect all  such subintervals I_j,k,s as the collection   _j:={I_j,k' k'=1,…, |V_j|}. Then _j is associated with the graph _j.
  
  
  Given a hierarchical partition {_j}_j=0^J that is associated with a coarse-grained chain of the graph =(V,W), then the vertex v∈ V is  associated with a subinterval I_v∈_J.  A  signal f:V→ on the graph can  be identified  as a function
  
      f = ∑_v∈ V f(v) χ_I_v
  
  defined on I=[0,1].  We can thus define the space
  
      L_2():=L_2(|_J→0):={χ_I_v v∈ V}⊆ L_2([0,1])
  
   with the usual norm ·_2 and inner product ·,· for  L_2([0,1]). We immediately have the following result from Corollary <ref>.
  
  
  The system X({_j}_j=0^J)={φ_0}∪{Ψ_j,I I∈_j}_j=0^J-1  defined as in (<ref>) is a tight frame for L_2().
  
  
  We remark that, from Corollary <ref>,  when each I_j,k has at most two children,   such a system X({_j}_j=0^J) is an orthonormal basis for L_2() (c.f. <cit.>).
  
  
  
  
  
   §.§ Digraph signal representations
  
  
  
  Now continue to the digraph case.
  For a digraph (V, W), the underlying undirected graph is given by (V, W_0), where W_0=(W+W^⊤)/2.  A digraph  is weakly connected if the underlying undirected graph is connected.  For simplicity, we restrict ourselves  in this paper to weakly connected digraph while results in the paper can be easily extended to general digraphs. To represent signals on the digraph , we use the following steps to produce a pair (^x,^y) of two undirected graphs:
  
  
    1) Extension: we define the extended graph _e=(V, W_e) by  W_e= I+W, which is the same graph as =(V,W) except for a new (or enhanced) self-loop inserted at each vertex. This increases the connectivity of the undirected graphs obtained in the next step.
  
  
    2) Symmetrization: define the pre-symmetrized graph  _1=(V,W_1) and the post-symmetrized graph (<cit.>)  _2=(V, W_2) for the digraph _e=(V,W_e)  by W_1:=W_eW^⊤_e and  W_2:=W^⊤_eW_e.
  
  
    3) Post-processing: remove the self–loops of _1  and _2 by W^x:=W_1-(W_1) and W^y:=W_2-(W_2).  Define ^x = (V,W^x) and ^y=(V,W^y).
  
  It is not difficult to show that if  is weakly connected, then ^x and ^y are connected (undirected) graphs.
  
  We next use the pair (^x,^y)  to study signals defined on .  As discussed in previous subsections, using various clustering algorithms, we can obtain coarse-grained chains _J_x→0^x and ^y_J_y→ 0 of ^x and ^y, respectively for some J_x, J_y∈_0. Without loss of generality, we can assume J_x=J_y=:J. In fact, if J_x≠ J_y, say J_x<J_y, then we  simply extend the chain ^x_J_x→0 as ^x_J_y→ 0 by appending ^x:
  
      ^x_J_y→0:=(^x_J_y,…,^x_J_x+1, ^x_J_x,…,^x_0),
  
  where ^x_j≡^x for all j≥ J_x.
  
  
  For each of the coarse-grained chains  ^x_J→ 0 and ^y_J→ 0, it is associated with a hierarchical partition {_j^x}_j=0^J and {_j^y}_j=0^J, respectively.
  Define
  
      _j:=_j^x ⊗_j^y:={I^x × I^y   I^x∈_j^x, I^y∈_j^y },   j=0,…,J.
  
  Then, by Corollary <ref>, we immediately have the following result.
  
    Let _j, j=0,…,J be defined as in (<ref>) from  _j^x and _j^y associating with the coarse-grained chains ^x_J→ 0 and ^y_J→0 for graphs ^x, ^y, respectively.  Then, the system
   X({_j}_j=0^J)  defined as in (<ref>) is a tight frame for
   L_2(^x,^y):=L_2(^x|^x_J→0,^y|^y_J→0):=_J={χ_B B∈_J}.
  
  
  
  
  For signals f:V→ defined on the digraph , we can define the digraph signal space L_2() as follows. For v∈ V, there are I_v^x ∈_J^x and I_v^y∈_J^y. B_v:=I_v^x× I_v^y is then a block in _J. Thus, f can be identified as a function defined on [0,1]^2:
  
      f = ∑_v∈ V f(v) χ_B_v,   B_v = I_v^x× I^y_v,   v∈ V.
  
  Hence, we can define L_2() as
  
      L_2():=L_2(|(^x_J→0,^y_J→0)):={χ_B_v v∈ V}.
  
  with the usual norm ·_2 and inner product ·,· for  L_2([0,1]^2).
  
  Since f∈ L_2() is supported on ∪_v∈ V B_v,  we can conclude this section by the following result.
  
  Let X({_j}_j=0^J) be defined as in Theorem <ref> and B_v, v∈ V be blocks defined as in (<ref>) associated with the digraph . Define
  
      X({_j}_j=0^J|_)   :={φ_0}∪
         {ψ |ψ∩ B_v|>0  v∈ V, ψ∈Ψ_j,B, B∈_j}_j=0^J-1.
  
  Then X({_j}_j=0^J|_) is a tight frame for L_2().
  
  
  Note that
  
      L_2()⊆ L_2(^x,^y)⊆ L_2([0,1]^2).
  
  Hence, by Theorem <ref>, any f∈ L_2() can be represented by the tight frame system X({_j}_j=0^N) as
  
      f =  f, φ_0φ_0+∑_j=0^J-1∑_B∈_j∑_1≤ℓ_1<ℓ_2≤ c_B f, ψ_j,B^(ℓ_1,ℓ_2)ψ_j,B^(ℓ_1,ℓ_2).
  
  Since f is supported on ∪_v∈ VB_v, we can discard those of ψ^(ℓ_1,ℓ_2)_j,B whose essential support  is not intersecting with any  B_v, v∈ V. Then,
  
      f =  f, φ_0φ_0+∑_j=0^J-1∑_B∈_j∑_1≤ℓ_1<ℓ_2≤ c_B,|ψ∩ B_v|≠ 0 f, ψ_j,B^(ℓ_1,ℓ_2)ψ_j,B^(ℓ_1,ℓ_2).
  
  That is, the restriction  X({_j}_j=0^J|_) of X({_j}_j=0^J) on  is a tight frame for L_2().
  This completes the proof. ▪
  
  
  
  
  
  
  
  
  
  
  
  
  
  § ILLUSTRATION EXAMPLES
  
  
  In this section, we provide some examples to illustrate results in previous sections.
  
  
  
   §.§ Example 1: a tight frame on an  undirected graph
  
  Let =(V,W)=_3 be the graph in Fig. <ref> (see also ^x in Fig. <ref>). That is,
  
      W =
      [
      
      0     1    1     0    0     0   
      
      1     0    0     0    0     0   
      
      1     0    0     1    1     1   
      
      0     0    1     0    1     0   
      
      0     0    1     1    0     0   
      
      0     0    1     0    0     0   
      ],
  
  where the rows and columns are ordered from 1 to 6 with respect to the vertices a,b,c,d,e,f in V.
  
  Applying clustering algorithms, e.g., the NHC algorithm in <cit.>, to the graph ,  we can obtain a coarse-grained chain _3→0:=(_3,…,_0) of  as in Fig. <ref>. Each vertex in _j-1 is a cluster of vertices in _j. Based on such a coarse-grained chain, we can give a hierarchical sequence {_j}_j=0^3 and  build our tight frame system X({_j}_j=0^3)={φ_0}∪{Ψ_j}_j=0^2 as follows (see Fig. <ref>).
  
  
    1) The root node (j=0):  _0⟷_0:={I_0,1=I=[0,1]}. This is associated with φ_0 = χ_[0,1].
  
  
    2) At level j=1:  _1⟷_1:={I_1,1, I_1,2}. The graph _1 has two nodes [a]__1={a,b} (degree 3) and [c]__1={c,d,e,f} (degree 9). According to their degrees and (<ref>), we  identify the nodes [a]__1 and [c]__1 with the intervals
  
      I_1,1([a])=[0,3/12)=[0,1/4) I_1,2([c])=[3/12,3+9/12]=[1/4,1],
  
  respectively. The two subintervals I_1,1 and I_1,2 are the two children of I_0,1. Hence, by (<ref>), Ψ_0={ψ_0} with
  
      ψ_0:=3χ_I_1,1-χ_I_1,2/√(3).
  
  Note that ψ_0_2 = 1 and ψ_0_1=0.
  
  
  
  
    3)At level j=2: _2⟷_2:={I_2,1,I_2,2,I_2,3}. The graph _2 has three nodes [a]__2={a,b} (degree 3), [c]__2={c,d,e} (degree 8), and [f]__2={f} (degree 1). Similarly, we  identify them  with the intervals
  
      I_2,1([a])=[0,1/4), I_2,2([c])=[1/4,11/12), I_2,3([f])=[11/12,1],
  
  respectively. Only I_2,2 and I_2,3 are split from I_1,2. Hence,  by (<ref>), Ψ_1={ψ_1} with
  
      ψ_1:=χ_I_2,2-8χ_I_2,3/√(6).
  
  Note that ψ_1_2 = 1 and ψ_1_1=0.
  
  
  
    4) At level j=3: _3⟷_3:={I_3,1,…, I_3,6}. The graph _3 is the underlying graph with 6 vertices. According to their degrees, we  identify the vertices a,b,c,d,e,f with the intervals
  
      I_3,1(a)   =[0,1/6),   
      I_3,2(b)   =[1/6,1/4),   
      I_3,3(c)   =[1/4,7/12),   
      
      I_3,4(d)   =[7/12,3/4),   
      I_3,5(e)   =[3/4,11/12),   
      I_3,6(f)    = [11/12,1],
  
  respectively. Note that I_2,1 is split to I_3,1 and I_3,2 while I_2,2 is split to I_3,3, I_3,4, I_3,5. Hence,  by (<ref>), Ψ_2={ψ_2,ψ_3,ψ_4,ψ_5} with
  
      ψ_2:=√(2)(χ_I_3,1-2χ_I_3,2),    ψ_3:=√(3)/2(χ_I_3,3-2χ_I_3,4),
         ψ_4:=√(3)/2(χ_I_3,3-2χ_I_3,5),    ψ_5:=√(3/2)(χ_I_3,4-χ_I_3,5).
  
  Note that ψ_i_1 = 0 for i=2,…, 5.
  
  
  
  
  
  
  By Theorem <ref>, X({_j}_j=0^3) = {φ_0,ψ_0,…,ψ_5} is a tight frame for  L_2()={χ_I_3,k k = 1,…,6}.
  
  
  
  
   §.§ Example 2: tight frames on a digraph
  
  
  Let the digraph =(V,W) be determined by
  
      W =
      [
      
      0     1     0     0     0     0
      
      0     0     0     0     0     0
      
      1     0     0     1     0     1
      
      0     0     0     0     1     0
      
      0     0     1     0     0     0
      
      0     0     0     0     0     0
      ],
  
  where the rows and columns are ordered from 1 to 6 with respect to the vertices a,b,c,d,e,f in V, see Fig. <ref>.  After applying the symmetrization processing as discussed in Section <ref>, we obtain two undirected graphs ^x = (V,W^x) and ^y=(V,W^y), where ^x is the same graph considered as in Example 1 (see its adjacency matrix in (<ref>)) and ^y is determined by W^y:
  
      W^y=
      [
      
      0     1     1     1     0     1
      
      1     0     0     0     0     0
      
      1     0     0     1     1     1
      
      1     0     1     0     1     1
      
      0     0     1     1     0     0
      
      1     0     1     1     0     0
      ].
  
  
  
  
  
  
  
  Applying clustering algorithms, e.g., the NHC algorithm in <cit.>, to the undirected graphs ^x, ^y, we can obtain  coarse-grained chains ^x_3→0:=(^x_3,…,^x_0) and ^y_3→0:=(^y_3,…,^y_0) of ^x and  ^y, respectively. The coarse-grained chain ^x and its associated interval collection {_j^x}_j=0^3 are already shown in Example 1 (or see Fig. <ref>).   Now we describe the coarse-grained chain ^y_3→0 and its associated interval collections {_j^y}_j=0^3 (see Fig. <ref>).
  Based on the hierarchical interval sequences {^x_j,_j^y}_j=0^3, we can build the hierarchical block sequence {_j=^x_j⊗^y_j}_j=0^3 defined as in (<ref>). See Fig. <ref> (top) for the illustration of blocks and the blocks in _j are labelled with a number from 0 to 49 in Fig. <ref> (bottom).
  
  
  
    1) The root node (j=0):  _0^y⟷_0^y:={I^y_0,1=I=[0,1]}. Together with _0^x={[0,1]}, we have _0={I^2=[0,1]^2} and φ_0 = χ_[0,1]^2.
  
    2) At level j=1:  _1^y⟷_1^y:={I^y_1,1, I^y_1,2}. The graph _1^y has two nodes [a]__1^y={a,b,d} (degree 9) and [c]__1^y={c,e,f} (degree 9). According to their degrees, we  identify the nodes [a]__1^y and [c]__1^y  with the intervals
  
      I^y_1,1([a])=[0,9/18)=[0,1/2)  I^y_1,2([c])=[9/18,9+9/18]=[1/2,1],
  
  respectively. From _1^x={I_1,1^x,I_1,2^x}, see (<ref>), _1=_1^x⊗_1^y has four sub-blocks B_1,…,B_4 in [0,1]^2. Hence,  by (<ref>), Ψ_1={ψ^(ℓ_1,ℓ_2)_0,[0,1]^2 1≤ℓ_1,ℓ_2≤ 4} has 6 functions.
  
  
    3)At level j=2: _2^y⟷^y_2:={I^y_2,1,I^y_2,2,I^y_2,3}. The graph ^y_2 has three nodes [a]__2^y={a,b,d} (degree 9), [c]_^y_2={c,e} (degree 6), and [f]_^y_2={f} (degree 3). Similarly, we  identify them  with the intervals
  
      I^y_2,1([a])=[0,1/2),  I^y_2,2([c])=[1/2,5/6),  I^y_2,3([f])=[5/6,1],
  
  respectively. From _2^x in (<ref>), _2=_2^x⊗_2^y={B_5,…,B_13} has nine sub-blocks split from B_1,…,B_4: B_1 has  c_B_1=1 sub-block B_5=B_1; B_2 has c_B_2=2 sub-blocks B_6 and  B_7;B_3  has c_B_3=2 sub-blocks B_8 and B_11;   B_4 has c_B_4=4 sub-blocks B_9, B_10, B_12, and  B_13.  Hence, by (<ref>), Ψ_1={ψ^(ℓ_1,ℓ_2)_1,B_k 1≤ℓ_1,ℓ_2≤ c_B_k,k=1,2,3,4} has in total 2 2+2 2+4 2=8 functions.
  
  
    4) At level j=3: _3^y⟷^y_3:={I^y_3,1,…, I^y_3,6}. The graph ^y_3 is the underlying graph ^y with 6 vertices. According to their degrees, we  identify the vertices a,b,d,c,e,f with the intervals
  
  
      I^y_3,1(a)   =[0,2/9),    
      I^y_3,2(b)   =[2/9,5/18),    
      I^y_3,3(d)   =[5/18,1/2),    
      
      I^y_3,4(c)   =[1/2,13/18),   
      I^y_3,5(e)   =[13/18,5/6),   
      I^y_3,6(f)    = [5/6,1],
  
  respectively. From _3^x in (<ref>), _3=_3^x⊗_3^y has in total 36 blocks B_14, …, B_49. Hence, by (<ref>), Ψ_2={ψ^(ℓ_1,ℓ_2)_2,B_k 1≤ℓ_1,ℓ_2≤ c_B_k,k=5,…,13} containing 6  2+9 2+3  2+4  2+6  2+2  2+2 2+3  2=15+36+3+6+15+1+1+3=80 functions.
  
  According to Theorem <ref>, the  system X({_j}_j=0^3)={φ_0}∪{Ψ_j}_j=0^2 is a tight frame for L_2(^x,^y).
  
  
  
  
  
  
  
  
  Next, we focus on the tight frame X({_j}_j=0^3|_) for L_2() as in Corollary <ref>. Note that the vertices a,b,c,d,e,f in the  digraph  are with respect to blocks
  
      B_a    = [0,1/6)×[0,2/9),   
      B_b    = [1/6,1/4)×[2/9,5/18),    
      B_c    = [1/4,7/12)×[1/2,13/18),   
      
      B_d    = [7/12, 3/4)×[5/18,1/2),   
      B_e    = [3/4,11/12)×[13/18,5/6),   
      B_f    = [11/12,1]×[5/6,1].
  
  The functions in  X({_j}_j=0^3|_) are as follows.
  
  
    a) Supported on _0: {φ_0}∪{ψ_0,[0,1]^2^(ℓ_1,ℓ_2) 1≤ℓ_1<ℓ_2≤ 4}. There are 7=1+6 functions with support intersecting B_v  in (<ref>).
  
  
    b) Supported on _1:  ψ^(ℓ_1,ℓ_2)_1,B_k for k=2,4 and 1≤ℓ_1<ℓ_2<c_B_k. There are 6=1+5 functions with support intersecting B_v  in (<ref>).
  
  
    c) Supported on _2: ψ^(ℓ_1,ℓ_2)_2,B_k for k=5,6,9 and 1≤ℓ_1<ℓ_2<c_B_k. There are 26=9+8+9 functions with support intersecting B_v in (<ref>).
  
  
  
  We see that the number of functions in X({_j}_j=0^3|_) (39) is significantly less than  those in X({_j}_j=0^3) (95). We remark that the 26 functions from _2 could be further reduced in view of the non-effective blocks in _3. For example, the block B_6 has 9 sub-blocks (#16, #17, #18, #22, #23, #24, #28, #29, #30). These produce 8 functions  ψ^(ℓ_1,ℓ_2)_2,B_6 in X({_j}_j=0^3|_). But since the block B_29 representing the vertex d is the only effective block,  one function, say ψ_2,B_6^(29,30), is indeed enough. The total number of functions in X({_j}_j=0^3|_) could be reduced to 20=7(_0)+6(_1)+7(_2).
  
  
  
  
  
  
  
  
  
  
  
  
  § FINAL REMARKS
  
  
  We conclude the paper by some remarks and potential future work.
  
  
    1) In <cit.>, the systems used to represent graph (digraph) signals are orthonormal. They are obtained through the tensor product approach of two 1D orthonormal systems coming from the Gram–Schmidt process. The tensor product orthonormal system is used for the digraph signal representation. In this paper, we do not use the Gram-Schmidt process but simply rely on the selection of  two sub-blocks. The resulted systems are tight frame systems and could have more directionality than the tensor product approach orthonormal systems. Note that when each block has at most two children sub-blocks, our resulted system is also orthonormal. However, such an orthonormal system is different to those in <cit.>.
  
  
  
    2) Our construction of the system X({_j}_j∈_0) is not necessarily restricted to compact subsets K⊆^d. It is possible to extend the construction of the system on any σ-finite  measurable subsets of ^d. More generally, our construction could be extended to abstract measurable spaces as well as compact Riemannian manifolds.
  
  
  
    3)Since it is Haar-type, the framelet ψ∈Ψ_j,B has only vanishing moment of order 1: ∫_Kψ(x) dx=0. To increase the sparse representation ability, one could consider the construction of similar tight framelet systems with higher vanishing moments.
  
  
  
    4) The number of elements in X({_j}_j=0^J|_) could be significantly reduced  by discarding non-effective framelet functions as pointed out in the end of Example 2.
  
  
    5) Since there is a natural nested structure of the block sequences, fast algorithms could be developed for  framelet transforms.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § PROOFS
  
  
  We provide proofs of Lemma <ref> and Lemma <ref> here.
  
  
  We prove that A^⊤ A=_m by showing that the columns of A are orthogonal.  Indeed,  the 2-norm of the ℓ-th column of A is
  
      ∑_i=0^n |a_i,ℓ|^2
         =|a_0,ℓ|^2+∑_1≤ i_1<i_2≤ m |a_(i_1,i_2),ℓ|^2
         =|a_0,ℓ|^2+∑_1≤ i_1<ℓ≤ m |a_(i_1,ℓ),ℓ|^2+∑_1≤ℓ<i_2≤ m |a_(ℓ,i_2),ℓ|^2
         =b_ℓ+∑_i_1< ℓb_i_1 + ∑_i_2> ℓb_i_2= 1,   1≤ℓ≤ m.
  
  Moreover,  the dot product of the ℓ_1-th column and the ℓ_2-th column of A with ℓ_1<ℓ_2 is
  
      ∑_i=0^n a_i,ℓ_1a_i,ℓ_2
      =a_0,ℓ_1a_0,ℓ_2+∑_1≤ i_1<i_2≤ m a_(i_1,i_2),ℓ_1a_(i_1,i_2),ℓ_2
         =√(b_ℓ_1b_ℓ_2)+∑_i_2>ℓ_1a_(ℓ_1,i_2),ℓ_1a_(ℓ_1,i_2),ℓ_2+
      ∑_i_1<ℓ_1a_(i_1,ℓ_1),ℓ_1a_(i_1,ℓ_1),ℓ_2
           +
      ∑_i_2>ℓ_2a_(ℓ_2,i_2),ℓ_1a_(ℓ_2,i_2),ℓ_2
      +
      ∑_i_1<ℓ_2, i_1≠ℓ_1a_(i_1,ℓ_2),ℓ_1a_(i_1,ℓ_2),ℓ_2
         =√(b_ℓ_1b_ℓ_2)+∑_i_2>ℓ_1a_(ℓ_1,i_2),ℓ_1a_(ℓ_1,i_2),ℓ_2=√(b_ℓ_1b_ℓ_2)+∑_i_2>ℓ_1√(b_i_2)(-√(b_ℓ_1)δ_i_2,ℓ_2)
      
         =√(b_ℓ_1b_ℓ_2)-√(b_ℓ_2)√(b_ℓ_1)=0.
  
  Similarly, ∑_i=0^n a_i,ℓ_1a_i,ℓ_2=0 for ℓ_1>ℓ_2. Hence, A^⊤ A = _m is an identity matrix. ▪
  
  
  
  
  
  To prove that Ψ_B is tight, by linearity,  it suffices to show that
  
      ψ^(ℓ_1,ℓ_2)=∑_1≤ℓ_1'<ℓ_2'≤ mψ^(ℓ_1,ℓ_2), ψ^(ℓ_1',ℓ_2')ψ^(ℓ_1',ℓ_2'),    1≤ℓ_1<ℓ_2≤ m.
  
  In fact, from (<ref>), we have
  ψ^(ℓ_1,ℓ_2) = √(b_ℓ_2)γ_ℓ_1-√(b_ℓ_1)γ_ℓ_2
  =∑_ℓ=1^ma_(ℓ_1,ℓ_2),ℓγ_ℓ,
  where (a_(ℓ_1,ℓ_2),ℓ)_ℓ=1^m is the row  of the matrix A in Lemma <ref>.  By A^⊤ A= I and the orthogonality of {γ_ℓ 1≤ℓ≤ m},  we have
  
      ∑_1≤ℓ_1'<ℓ_2'≤ mψ^(ℓ_1,ℓ_2),ψ^(ℓ_1',ℓ_2')ψ^(ℓ_1',ℓ_2')
      
      =   ∑_1≤ℓ_1'<ℓ_2'≤ m(∑_ℓa_(ℓ_1,ℓ_2),ℓa_(ℓ_1',ℓ_2'),ℓ∑_ℓ̃a_(ℓ_1',ℓ_2'),ℓ̃γ_ℓ̃)
      
      =   ∑_ℓa_(ℓ_1,ℓ_2),ℓ∑_ℓ̃∑_1≤ℓ_1'<ℓ_2'≤ ma_(ℓ_1',ℓ_2'),ℓa_(ℓ_1',ℓ_2'),ℓ̃γ_ℓ̃
      
      =   ∑_ℓa_(ℓ_1,ℓ_2),ℓ∑_ℓ̃(δ_ℓ,ℓ̃-√(b_ℓ b_ℓ̃))γ_ℓ̃
      = ∑_ℓa_(ℓ_1,ℓ_2),ℓ(γ_ℓ-∑_ℓ̃√(b_ℓ b_ℓ̃)γ_ℓ̃)
      
      
      =    (√(b_ℓ_2)γ_ℓ_1-∑_ℓ̃√(b_ℓ_1b_ℓ_2 b_ℓ̃)γ_ℓ̃)-(√(b_ℓ_1)γ_ℓ_2-∑_ℓ̃√(b_ℓ_2b_ℓ_1 b_ℓ̃)γ_ℓ̃)
      
      =   √(b_ℓ_2)γ_ℓ_1-√(b_ℓ_1)γ_ℓ_2=ψ^(ℓ_1,ℓ_2),
  
  where the 3^ rd equation follows from that
  √(b_ℓ b_ℓ̃)+∑_1≤ℓ_1'<ℓ_2'≤ ma_(ℓ_1',ℓ_2'),ℓa_(ℓ_1',ℓ_2'),ℓ̃
  is the dot product of the ℓ-th column and ℓ̃-th column of A, which equals to δ_ℓ,ℓ̃. Therefore, Ψ_B is a tight frame for _B. ▪
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  spmpsci      
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Bronstein_etal2017
  M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst, Geometric deep learning: Going beyond euclidean data, IEEE Signal Processing Magazine, 34 (4),
    18–42,  2017.
  
  CandesDonoho
  E. J. Candès and D. L.  Donoho, New tight frames of curvelets and optimal representations of objects with piecewise C^2 singularities,
   Communications on Pure and Applied Mathematics, 57 (2), 219–266, 2004.
  
  AST2
  Z. Che and X. Zhuang,  Digital affine shear filter banks with 2-Layer structure and their applications in image processing, IEEE Transactions on Image Processing,  27 (8): 3931–3941, 2018.
  
  qiyu2
  C. Cheng, N. Emirov, and Q. Sun, Preconditioned gradient descent algorithm for inverse filtering on spatially distributed Networks, arXiv:2007.11491, 2020.
  
  Book:Chui
  C. K. Chui.
  An Introduction to Wavelets, volume 1 of Wavelet
    Analysis and its Applications,  Academic Press, Inc., Boston, MA, 1992.
  
  achaspissue
  C. K. Chui and D. L. Donoho, Special issue: Diffusion maps and wavelets,  Applied and Computational Harmonic Analysis, 21 (1), 2006.
  
  
  treepap
  C. K. Chui, F. Filbir, and H. N. Mhaskar,  Representation of functions on big data: graphs and trees.
   Applied and Computational Harmonic Analysis, 38(3), 489–509,  2015.
  
  CMZ:ACHA:18
  C. K. Chui, H. N. Mhaskar, and X. Zhuang,  Representation of functions on big data associated with directed graphs, Applied and Computational Harmonic Analysis, 44 (1), 165–188, 2018.
  
  
  chung1997spectral
  F. R. K. Chung,  Spectral Graph Theory, volume 92,  American Mathematical Soc., 1997.
  
  chung_directed_laplacian
  F. Chung,  Laplacians and the cheeger inequality for directed graphs,
   Annals of Combinatorics, 9 (1),1–19, 2005.
  
  CDV
  A. Cohen, I. Daubechies, and P. Vial, Wavelets on the interval and fast wavelet transforms,
  Applied and Computational Harmonic Analysis, 1 (1),  54–81, 1993.
  
  
  
  
  Book:Daubechies1992
  I. Daubechies, Ten Lectures on Wavelets, volume 61 of CBMS-NSF Regional
    Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia,  PA, 1992.
  
  Dong2017
  B. Dong, Sparse representation on graphs by tight wavelet frames and applications,  Applied and Computational Harmonic Analysis, 42 (3), 452–479, 2017.
  
  shearlab
  D. L. Donoho, G. Kutyniok,  M. Shahram, and X. Zhuang,  A rational design of a digital shearlet transform,  The 9th International Conference on Sampling Theory and Applications (SampTA'11), Singapore, 2011.
  
  
  
  
  qiyu3
  N. Emirov, C. Cheng, J.  Jiang, and Q. Sun, Polynomial graph filter of multiple shifts and distributed implementation of inverse filtering,  arXiv:2003.11152, 2020.
  
  arjuna2013
  C. Garcia-Cardona, E. Merkurjev, A. L. Bertozzi, A. Flenner, and A. G. Percus,  Fast multiclass segmentation using diffuse interface methods on  graphs,
  Technical report, DTIC Document, 2013.
  
  gavish2010multiscale
  M. Gavish, B. Nadler, and R. R. Coifman,  Multiscale wavelets on trees, graphs and high dimensional data:  Theory and applications to semi supervised learning, Proceedings of the 27th International Conference on Machine Learning (ICML-10), 367–374, 2010.
  
  
  
  
  
  Haar1910
  A. Haar, Zur theorie der orthogonalen funktionensysteme, Mathematische Annalen, 69 (3), 331–371,  1910.
  
  
  
  
  hammond
  D. K. Hammond, P. Vandergheynst, and R. Gribonval,  Wavelets on graphs via spectral graph theory,
   Applied and Computational Harmonic Analysis, 30(2),129–150,  2011.
  
  Book:Han
  B. Han, Framelets and Wavelets: Algorithms, Analysis, and  Applications, Birkhäuser, 2017.
  
  han2012extended
  X. Han, Y. Chen, J. Shi, and Z. He,  An extended cell transmission model based on digraph for urban
    traffic road network,  15th   International IEEE Conference on Intelligent Transportation Systems (ITSC), 2012,  558–563,  2012.
  
  
  HLZ:AML
  B. Han, T. Li,  and X. Zhuang, Directional compactly supported box spline tight framelets with simple geometric structure,  Applied Mathematics Letters,  91, 213–219, 2019.
  
  HM:AA
  B. Han and M. Michelle, Construction of wavelets and framelets on a bounded interval, Analysis and Applications, 16 (06), 807–849, 2018
  
  
  TPCTF2
  B. Han, Q.  Mo, Z. Zhao, and X. Zhuang, Directional compactly supported tensor product complex tight framelets with applications to image denoising and inpainting, SIAM Journal on Imaging Sciences, 12 (4), 1739–1771, 2019.
  
  
  
  
  TPCTF1
  B. Han, Z. Zhao, and X. Zhuang, Directional tensor product complex tight framelets with low redundancy, Applied and Computational Harmonic Analysis,  41 (2),  603–637, 2016.
  
  
  
  HanZhuang:alg.num
  B. Han and X. Zhuang,  Algorithms for matrix extension and orthogonal wavelet filter banks over algebraic number fields,  Mathematics of Computation, 82 (281), 459–490, 2013.
  
  
  AST0
  B. Han and X. Zhuang, Smooth affine shear tight frames with MRA structures, Applied and Computational Harmonic Analysis,  39 (2), 300–338, 2015.
  
  
  Qiyu
  J. Jiang, D. B. Tay, Q. Sun and S. Ouyang, Design of nonsubsampled graph filter banks via lifting schemes, IEEE Signal Processing Letters,  27, 441–445, 2020.
  
  
  
  Book:Shearlets
  G. Kutyniok and D. Labate., Shearlets: Multiscale Analysis for Multivariate Data, Applied and Numerical Harmonic Analysis, Springer Science & Business Media, 2012.
  
  
  
  
  
  
  
  lafonncut
  S. Lafon and A. B. Lee,  Diffusion maps and coarse-graining: A unified framework for
    dimensionality reduction, graph partitioning, and data set parameterization,  IEEE Transactions
    on Pattern Analysis and Machine Intelligence, 28 (9),1393–1403, 2006.
  
  
  
  Wa:NN
  M. Li, Z. Ma, Y. G. Wang,  and X. Zhuang, Fast Haar transform for graph neural networks, Neural Networks, 128, 188–198, 2020.
  
  
  Li:DHF
  Y.-R. Li, R. H. Chan, L.  Shen, Y.-C. Hsu, and W.-Y. I. Tseng,  An adaptive directional Haar framelet-based reconstruction algorithm for parallel magnetic resonance imaging, SIAM Journal on Imaging Sciences,  9 (2), 794–821, 2016.
  
  li2012digraph
  Y. Li and Z.-L. Zhang, Digraph laplacian and the degree of asymmetry.  Internet Mathematics, 8 (4), 381–401, 2012.
  
  
  Li:spie
  Y.-R. Li and X. Zhuang,  Parallel magnetic resonance imaging reconstruction algorithm by 3-dimension directional Haar tight framelet regularization,  Wavelets and Sparsity XVIII, SPIE Proc. 11138-47, 2019.
  
  hodge_laplacian_lim2015
  L.-H. Lim, Hodge laplacians on graphs, arXiv:1507.05379, 2015.
  
  
  Book:Mallat
  S. Mallat, A Wavelet Tour of Signal Processing. The Sparse Way, With
    Contributions from Gabriel Peyré,  Elsevier/Academic Press,  Amsterdam, Third edition, 2009.
  
  malliaros2013clustering
  F. D. Malliaros and M. Vazirgiannis,  Clustering and community detection in directed networks: A survey,  Physics Reports, 533 (4), 95–142, 2013.
  
  
  newman2003structure
  M. E. Newman,  The structure and function of complex networks,  SIAM review, 45(2), 167–256, 2003.
  
  
  
  
  
  Pesenson
  I. Pesenson, Sampling in Paley-Wiener spaces on combinatorial graphs,  Transactions of the American Mathematical Society, 360 (10),  5603–5627, 2008.
  
  Pesenson2
  I. Pesenson, Q. T. Le Gia, A. Mayeli, H. Mhaskar, D. X. Zhou,
  Recent Applications of Harmonic Analysis to Function Spaces, Differential Equations, and Data Science: Novel Methods in Harmonic Analysis, Volume 2, Applied and Numerical Harmonic Analysis, Birkhäuser, 2017
  
  
  przulj2011introduction
  N. Przulj, Introduction to the special issue on biological networks, Internet Mathematics, 7 (4), 207–208, 2011.
  
  diagraphcluster_ohiostate_2011
  V. Satuluri and S. Parthasarathy,  Symmetrizations for clustering directed graphs,  ACM Proceedings of the 14th International Conference on Extending   Database Technology,  343–354, 2011.
  
  
  
  DWT
  I. W. Selesnick, R. G. Baraniuk and N. C. Kingsbury, The dual-tree complex wavelet transform, IEEE Signal Processing Magazine,  22 (6),  123–151, 2005.
  
  
  singer
  A. Singer,  From graph to manifold Laplacian: The convergence rate, Applied and Computational Harmonic Analysis, 21 (1), 128–134,  2006.
  
  smith2013role
  L. M. Smith, L. Zhu, K. Lerman, and Z. Kozareva, The role of social media in the discussion of controversial topics,   2013 IEEE International Conference
    on Social Computing (SocialCom),  236–243,  2013.
  
  Book:Stein1993
  E. M. Stein, Harmonic Analysis: Real-Variable Methods, Orthogonality, and
    Oscillatory Integrals, Princeton University Press, 1993.
  
  
  
  
  
  
  van2001graph
  S. M. Van Dongen,  Graph Clustering by Flow Simulation,  PhD thesis, University of Utrecht, 2001.
  
  
  WaZh:spie
  Y. G. Wang and X.  Zhuang,   Tight framelets on graphs for multiscale data analysis, Wavelets and Sparsity XVIII, SPIE Proc. 11138-11, 2019.
  
  WaZh2018
  Y. G. Wang and X. Zhuang, Tight framelets and fast framelet filter bank transforms on
    manifolds,  Applied and Computational Harmonic Analysis, 48 (1), 64–95, 2020.
  
  Wa:ICML
  Y. G. Wang, M. Li, Z. Ma, G. Montufar, X. Zhuang, and Y. Fan,  Haar graph pooling,  Proceedings of ICML 2020 (ICML 2020),  3807–3817, 2020.
  
  
  
  AST1
  X. Zhuang,   Digital affine shear transforms: fast realization and applications in image/video processing, SIAM Journal on Imaging Sciences,  9 (3), 1437–1466, 2016.
  
  TPCTF3
  X. Zhuang and B. Han, Compactly supported tensor product complex tight framelets with directionality, 2019 International Conference on Sampling Theory and Applications (SampTA), Bordeaux, France. 1–5, 2019.
  
  
  
  
  
  