# Discrete Linear Canonical Transform on Graphs

Yu Zhanga,b Bing-Zhao Lia,b<EMAIL_ADDRESS>aSchool of Mathematics and
Statistics, Beijing Institute of Technology, Beijing 100081, China  bBeijing
Key Laboratory on MCAACI, Beijing Institute of Technology, Beijing 100081,
China

###### Abstract

With the wide application of spectral and algebraic theory in discrete signal
processing techniques in the field of graph signal processing, an increasing
number of signal processing methods have been proposed, such as the graph
Fourier transform, graph wavelet transform and windowed graph Fourier
transform. In this paper, we propose and design the definition of the discrete
linear canonical transform on graphs (GLCT), which is an extension of the
discrete linear canonical transform (DLCT), just as the graph Fourier
transform (GFT) is an extension of the discrete Fourier transform (DFT).
First, based on the centrality and scalability of the DLCT eigendecomposition
approach, the definition of GLCT is proposed by combining graph chirp-Fourier
transform, graph scale transform and graph fractional Fourier transform.
Second, we derive and discuss the properties and special cases of GLCT.
Finally, some GLCT examples of the graph signals are given to illustrate the
improvement of the transformation.

###### keywords:

Graph signal processing , Linear canonical transform , Eigenvalue
decomposition , Graph fractional Fourier transform.

##  1 Introduction

In conventional signal processing, the signal domain is determined by a set of
spatial measurement points at equal time intervals or on a uniform grid.
However, with the advancement of information and communication, actual signals
may not be related to the temporal or spatial dimension, and they exhibit
various forms of irregularities, including social irregularities, economical
irregularities, irregularities in transportation, irregularities in energy,
irregularities in sensors, and irregularities in biological networks. These
high-dimensional and massive signals require new processing techniques, which
eventually developed the field of graph signal processing [1], [2]. Signal
processing on graphs extends traditional discrete signal processing (DSP) to
signals with underlying complex and irregular structures and achieves the
transition from classical discrete signal processing to graph signal
processing by graphically modeling and vertex indexing the underlying
structure of the signals. Related works include graph-based transformation [3,
4, 5, 6, 7], filtering [3], [8, 9], sampling and interpolation [10, 11, 12],
reconstruction and restoration [13, 14, 15], denoising [12], [16], uncertainty
principle on graphs [17], etc.

There are two basic signal processing frameworks on the graph based on
spectral and algebraic methods. The first method is derived from spectrogram
theory [1]. The graph signal is expanded into the eigenfunction of the
Laplacian operator to define the graph Fourier transform, and the
corresponding spectrum is represented by the eigenvalues. Since standard graph
Laplacian matrices must be symmetric and positive semidefinite, this method is
limited to undirected graphs. The second is based on discrete signal
processing on graphs (DSPG) [2, 3], which is derived from algebraic signal
processing (ASP). The graph Fourier transform expands the signal into the
eigenvectors of the adjacency matrix and defines the spectrum by the
corresponding eigenvalues. Since the adjacency matrix can be asymmetric, the
second method can be applied to arbitrary graphs. However, this transformation
requires the information of the entire graph signal, and the conversion
process from the vertex domain to the graph frequency domain cannot be
obtained. To solve problems such as nonstationary graph signals, the windowed
graph Fourier transform [6], the fractional Fourier transform on the graph
[18] and the windowed fractional Fourier transform on the graph [19] have been
proposed, which further expands the methods and application prospects of
graphs. However, the above approaches still have the problems of insufficient
degrees of freedom, inadequate flexibility, and underutilized parameters.
Therefore, finding new graph signal processing methods is currently a popular
topic.

To address the above problems, we apply the linear canonical transform (LCT)
to graph signal processing. The LCT was proposed in the 1970s [20] and later
introduced into the field of signal processing in 2001 [21]. The linear
canonical transforms (LCTs) generalize Fourier transforms, fractional Fourier
transforms, Fresnel transforms, and scaling operations and have three free
parameters. Before the implementation of the DLCT into the field of graph
signals, the central discrete dilated Hermite function (CDDHF) [22, 23] was
used as the basis for the eigenfunctions of the fractional Fourier transform
(FrFT) and scaling operations to implement the DLCT. The introduction of LCT
into the field of graph signal processing can effectively solve the lack of
the degrees of freedom and flexibility, expand the method of graph signal
processing, and unify the graph Fourier transform, graph fractional Fourier
transform, and graph scale transform. In this paper, a definition of the
discrete linear canonical transform on graphs (GLCT) is proposed and
consolidated by the following steps.

Summary of the paper: In Section II, the theories of graph signal and discrete
linear canonical transformation on which this study is based are briefly
reviewed. In Section III, the definition of GLCT and several properties are
presented. In Section IV, examples of the graph signals under the GLCT
framework are given to illustrate the improvements of the transform. Finally,
in Section V, the paper is concluded.

##  2 Preliminaries

###  2.1 Graph Fourier transform

The graph Fourier transform is defined using algebraic methods, and some of
the most basic concepts and definitions are reviewed below. A detailed
introduction to the theory can be found in [2, 3].

We consider a dataset with $N$ elements, where the associated information of
some of the data elements is known through dependency. This relationship is
represented by the graph $\mathcal{G}=(\mathcal{V},\mathbf{A})$, where
$\mathcal{V}={v_{0},\ldots,v_{N-1}}$ is the set of vertices, and $\mathbf{A}$
is the weighted adjacency matrix of the graph. Each data element is indexed by
a node $v_{n}$, and each weighted edge $\mathbf{A}_{n,m}\in\mathbb{C}$ from
$v_{m}$ to $v_{n}$ represents the relation of the $m$th data element to the
$n$th data element. For undirected graphs, there is
$\mathbf{A}_{n,m}=\mathbf{A}_{m,n}$, that is, $\mathbf{A}$ is symmetric. The
dataset is called the graph signal, defined as the following:

$\displaystyle\mathbf{s}:\mathcal{V}$ $\displaystyle\rightarrow\mathbb{C},$
(1) $\displaystyle v_{n}$ $\displaystyle\mapsto s_{n},$

where $\mathbb{C}$ is the set of complex numbers. It can be written as graph
signals as vectors

$\mathbf{s}=\begin{bmatrix}s_{0}&s_{1}&\ldots&s_{N-1}\end{bmatrix}^{T}\in\mathbb{C}^{N}.$

For simplicity of the discussion, it is assumed that $\mathbf{A}$ is
diagonalizable and its eigendecomposition is

$\mathbf{A}=\mathbf{V\Lambda V^{-1}},$ (2)

where the columns $v_{n}$ of the matrix
$\mathbf{V}=\begin{bmatrix}v_{0}&v_{1}&\ldots&v_{N-1}\end{bmatrix}\in\mathbb{C}^{N\times
N}$ are the eigenvectors of $\mathbf{A}$, and
$\mathbf{\Lambda}\in\mathbb{C}^{N\times N}$ is the diagonal matrix of the
distinct eigenvalues $\lambda_{0},~{}\lambda_{1},\dots,\lambda_{N-1}$ of
$\mathbf{A}$ .The eigenvalues are the graph frequencies that form the spectrum
of the graph. If $\mathbf{A}$ is not diagonalizable, Jordan decomposition[2,
3] into generalized eigenvectors is uesd.

######  Definition 1.

The graph Fourier transform of a graph signal can be defined as

$\hat{\mathbf{s}}=\mathbf{Fs}:=\mathbf{V^{-1}s},$ (3)

where $\mathbf{F}=\mathbf{V}^{-1}$ is the graph Fourier transform matrix,
$\hat{\mathbf{s}}=\begin{bmatrix}\hat{s}_{0}&\hat{s}_{1}&\ldots&\hat{s}_{N-1}\end{bmatrix}^{T}$.

The inverse graph Fourier transform is defined as

$\mathbf{s}=\mathbf{F^{-1}\hat{s}}:=\mathbf{V\hat{s}}.$ (4)

###  2.2  Graph Fractional Fourier transform

To further study graph signals and the fractional Fourier transform, the
discrete fractional Fourier transform (DFrFT) is extended to the graph
fractional Fourier transform (GFrFT) [18], [24], similar to the extension of
DFT to GFT.

######  Definition 2.

The $a$th fractional graph Fourier transform of the graph signal
$s\in\mathbb{C}^{N\times N}$ is defined as

$\mathbf{\hat{s}}=\mathcal{F}^{a}\mathbf{s}:=\mathbf{F}^{a}s.$ (5)

The signal $\mathbf{s}$ on the graph $\mathcal{G}$ has a diagonalizable
adjacency matrix $\mathbf{A=V\Lambda_{(A)}V}^{-1}$. If the GFT matrix
$\mathbf{F}$ is ortho-diagonalized, then

$\mathbf{F}=\mathbf{V}^{-1}=\mathbf{Q\Lambda Q}^{-1},$ (6)

where the matrices $\mathbf{Q}$ and $\mathbf{\Lambda}$ are given by the
spectral decomposition of the GFT matrix. Similar to the definition of the
$a$th DFrFT matrix, the GFrFT matrix can be given by:

$\mathbf{\hat{s}}=\mathbf{F}^{a}=\mathbf{Q}\mathbf{\Lambda}^{a}\mathbf{Q}^{-1}\mathbf{s},\
\ a\in\left[0,1\right],$ (7)

and its inverse transform (IGFRFT) is

$\mathbf{s}=\mathbf{F}^{-a}=\mathbf{Q}\mathbf{\Lambda}^{-a}\mathbf{Q}^{-1}\mathbf{\hat{s}}.$
(8)

###  2.3 Linear Canonical Transforms

####  2.3.1 Definition

The linear canonical transform of the signal $x(t)$ with the
parameters$(a,b,c,d)$ is defined as

$\displaystyle L^{\left(a,b,c,d\right)}\left(x\left(t\right)\right)=$
$\displaystyle\sqrt{\frac{1}{ib}}\cdot\int^{\infty}_{-\infty}\exp\left[i\pi\left(\frac{d}{b}u^{2}-\frac{2}{b}ut+\frac{a}{b}t^{2}\right)\right]$
(9) $\displaystyle\times x\left(t\right)\mathrm{d}t\ \ \ \ \ \text{when}\
b\neq 0,$ $\displaystyle
L^{\left(a,0,c,d\right)}\left(x\left(t\right)\right)=$
$\displaystyle\sqrt{d}\cdot\exp\left(i\pi dct^{2}\right)x\left(d\cdot
t\right)$ $\displaystyle\times\text{when}\ b=0,$

where $L^{\left(a,b,c,d\right)}$ denotes the LCT operator. The matrix
$\mathbf{M}$ entries are $(a,b,c,d)$, which is called an LCT parameter matrix,
and $ad-bc=1,\ a,b,c,d\in\mathbb{R}$.

The DLCT can also be decomposed into chirp multiplication(CM), scaling and
FrFT:

$\left[\begin{matrix}a&b\\\ c&d\end{matrix}\right]=\left[\begin{matrix}1&0\\\
\xi&1\end{matrix}\right]\left[\begin{matrix}\sigma&0\\\
0&\sigma^{-1}\end{matrix}\right]\left[\begin{matrix}\cos\alpha&\sin\alpha\\\
-\sin\alpha&\cos\alpha\end{matrix}\right],$ (10)

where $\xi$ denotes the CM parameter, $\sigma$ denotes the scaling parameter,
and $\alpha$ denotes the FrFT parameter and satisfies the determinant
constraint $ad-bc=1$. The parameter relations between $(a,b,c,d)$ and
$(\xi,\sigma,\alpha)$ are

$\begin{gathered}\xi=\frac{ac+bd}{a^{2}+b^{2}},\ \ \ \ \
\sigma=\sqrt{a^{2}+b^{2}},\\\
\alpha=\cos^{-1}\left(\frac{a}{\sigma}\right)=\sin^{-1}\left(\frac{b}{\sigma}\right).\end{gathered}$
(11)

####  2.3.2 Discretization Process

There are three main ways to define and calculate the DLCT: the direct
discretization method [25] based on classical discrete-time Fourier transform
ideas and methods, the linear canonical transform decomposition method based
on the principle of the FFT algorithm [26, 27, 28], and the parameter matrix
decomposition method [29]. Because a discrete Hermite function with
centralization and expandability is required when implementing the DLCT, the
approach of eigendecomposition of the CDDHFs is adopted in this paper to
achieve the DLCT. Since the LCT matrix is not commutative, it is implemented
in the order of DFrFT, scaling transform, and CM [24], [30]. For a discrete
signal $x[n]$, we have

$L^{\left(\cos\alpha,\sin\alpha,-\sin\alpha,\cos\alpha\right)}\left(x\left[n\right]\right)=ED_{\alpha}E^{T}x\left[n\right],$
(12)

where the parameters
$(a,b,c,d)=(\cos\alpha,\sin\alpha,-\sin\alpha,\cos\alpha)$ , $E$ is a square
matrix of $N\times N$, and $D_{\alpha}$ is a diagonal matrix. Then, the
discrete scale transform can be expressed as

$L^{\left(\sigma,0,0,\sigma^{-1}\right)}\left(x\left[n\right]\right)=E_{\sigma}E^{T}x\left[n\right],$
(13)

where the parameters $(a,b,c,d)=(\sigma,0,0,\sigma^{-1})$, $E_{\sigma}$ is an
$N\times N$ square matrix, and $\sigma$ is a constant, when $\sigma>1$, the
transformed signal is a dilated signal. Finally, the CM is defined as

$L^{\left(1,0,\xi,1\right)}\left(x\left[n\right]\right)=D_{\xi}x\left[n\right],$
(14)

where, the parameters $(a,b,c,d)=(1,0,\xi,1)$, and $D_{\xi}$ is the diagonal
chirp matrix.

In summary, combining the discrete FrFT, scaling and CM in Eqs(12)–(14), DLCT
based on Eq(10) is proposed. Therefore, the cascaded combination of the three
operations is:

$\displaystyle L^{\left(a,b,c,d\right)}\left(x\left[n\right]\right)$
$\displaystyle=\left\\{\left(D_{\xi}\right)\left(E_{\sigma}E^{T}\right)\left(ED_{\alpha}E^{T}\right)\right\\}x\left[n\right]$
(15)
$\displaystyle=\left\\{D_{\xi}E_{\sigma}D_{\alpha}E^{T}\right\\}x\left[n\right].$

The DLCT Eq(15) is a unitary transformation because the DLCT matrix
$D_{\xi}E_{\sigma}D_{\alpha}E^{T}$ is unitary, and the matrix $E^{T}E$ is the
identity matrix, since $E$ forms an orthogonal Hermite basis set. Figure 1 is
a schematic diagram of the eigendecomposition of the DLCT, where
$\hat{x}\left[n\right]$ is the frequency in the linear canonical domain.

Figure 1: Eigendecomposition of the DLCT.

##  3  Discrete Linear Canonical Transform on Graphs

In the field of graph signals, there is little theoretical literature defining
chirped signals on graphs, therefore, we propose a definition of the chrip-
Fourier transform on graphs [30]. Using the previously proposed definitions of
graph scale transforms [31, 32] and the fractional Fourier transform on graphs
[18], we finally define a linear canonical transform on graphs.

###  3.1 Definition

This definition generalizes the DLCT in the same way that the GFT generalizes
the DFT. Similar to defining the GFrFT, we first assume that the GLCT can be
represented in matrix form as

$\mathbf{\hat{s}}=\mathcal{L}^{(a,b,c,d)}\mathbf{s}:=\mathbf{L}^{(a,b,c,d)}\mathbf{s}.$
(16)

Then, we consider the signal $\mathbf{s}$ on the graph $\mathcal{G}$, which
has a diagonalizable adjacency matrix $\mathbf{A=V\Lambda V}^{-1}$. It is
assumed that the GFT matrix $\mathbf{L}$ can be orthogonally diagonalized.

$\mathbf{L}=\mathbf{V}^{-1}=\mathbf{Q\Lambda Q^{T}}.$ (17)

The GLCT can also be decomposed into three stages of CM, scaling, and FrFT.
This method uses the Hermite function (HF) or Hermite-Gaussian function to
define the eigenfunctions and eigenvalues. However, the eigenfunctions of the
GFrFT and scaling transform derived using discrete HF are not dilated.
Therefore, the GLCT is implemented using the CDDHFs as the basis for the
eigenfunctions of the FrFT and scaling operations. According to the
eigendecomposition of the DLCT in Figure 1, we can deduce the
eigendecomposition of the GLCT into the form of Figure 2 by analogy.

Figure 2: Eigendecomposition of the GLCT.

To obtain the eigendecomposition matrix shown in Figure 2, we achieve it
through the following three steps.

  1. 1.

GFrFT Stage
Since arbitrary LCT matrices are not commutative, the same order as defined
for the DFrFT matrices should be implemented first.

$\mathbf{L^{\alpha}}=\mathbf{V}^{-1}=\mathbf{Q\Lambda^{\alpha}Q^{T}},$ (18)

where $\alpha=\frac{\pi}{2}a$ , $a$ is the order of the previous GFrFT in
(2.2).

  2. 2.

Graph Scaling Stage
In classical DSP, using the graph representation of finite, periodic time
series in Fig.3 [33], for which the scaled adjacency matrix is the $N\times N$
circulant matrix $\mathbf{A}=\mathbf{C}$, and weights are

$\mathbf{A}_{n,m}=\begin{cases}1,&\text{if}\ n-m=1\
\mathrm{m}\mathrm{o}\mathrm{d}\ N\\\ 0,&\text{otherwise}\end{cases},$ (19)

we can write the scaled adjacency matrix as $\mathbf{A}=\mathbf{C}$, and the
shift operation is

$\tilde{\mathbf{s}}=\mathbf{C}\mathbf{s}=\mathbf{As}.$ (20)

Figure 3: Time-series with the length of N represented by a cycle graph.

The process implemented by the linear operator can be expressed as

$\left[x\right]_{n,t}=p\left[x\right]_{n,t-1}+\sum_{m\in
E_{n}}q_{n,m}\left[x\right]_{m,t-1},$ (21)

where $q$ is the edge weights of $n$ and $m$, $p$ is an arbitrary weight at
$t-1$, and $E_{n}$ is the sum of $\mathcal{G}$ edges. In the case of the
scaled adjacency matrix, what each node performs [32] on the signal is

$\left[x\right]_{n,t}=\frac{1}{\sigma}\sum_{m\in
E_{n}}\left[x\right]_{m,t-1}.$ (22)

In this way, the scaled adjacency matrix is
$\mathbf{A^{\prime}}=\frac{1}{\sigma}\mathbf{A}$ as the graph shift operator.
When in an arbitrary graph $\mathcal{G}=(\mathcal{V},\mathbf{A})$, the graph
shift operation is:

$\tilde{\mathbf{s}}_{n}=\sum^{N-1}_{m=0}\mathbf{A}_{n,m}\mathbf{s}_{m}=\sum_{m\in
E_{n}}\mathbf{A}_{n,m}\mathbf{s}_{m}.$ (23)

This matrix $\mathbf{A}_{n,m}$ is the scaled adjacency matrix, and
$\mathbf{A}_{n,m}=\mathbf{A^{\prime}}$.

We consider that the adjacency matrix $\mathbf{A}$ is first scaled to obtain
$\mathbf{A^{\prime}}$, and then the eigenvalues and eigenvectors of
$\mathbf{A^{\prime}}$ are obtained. Similar to GFT, the graph spectrum
decomposition is

$\mathbf{A^{\prime}}=\mathbf{Q_{\sigma}\Lambda^{\prime}Q^{T}_{\sigma}},$ (24)

where $\mathbf{Q}_{\sigma}$ and $\mathbf{\Lambda}^{\prime}$ denote the
eigenvectors of the matrix $\mathbf{A}^{\prime}$ and its corresponding
eigenvalues, espectively. $\sigma$ is the scaling parameter.

  3. 3.

Graph CM Stage
Because of its noncommutativity, the CM is performed on the adjacency matrix
$\mathbf{A}$ , as

$\displaystyle\mathbf{L_{\xi}}=$
$\displaystyle\mathbf{V}^{-1}=\mathbf{Q\Lambda_{\xi}Q^{T}}$ (25)
$\displaystyle=$
$\displaystyle\mathbf{Q}\begin{bmatrix}\mathrm{\lambda}_{0}&&\\\ &\ddots&\\\
&&\lambda_{N-1}\end{bmatrix}_{\xi}\mathbf{Q^{T}}=\mathbf{Q}\begin{bmatrix}\mathrm{\lambda}_{\xi_{0}}&&\\\
&\ddots&\\\ &&\lambda_{\xi_{N-1}}\end{bmatrix}\mathbf{Q^{T}},$

where $\xi$ is the CM parameter, and $\mathbf{\Lambda}_{\xi}$ is the
eigenvalues of the matrix $\mathbf{A}$ after scaling and CM.

The discrete chirp matrix is defined in terms of the discrete chirp-Fourier
transform [30]. The chirp-Fourier transform is closely related to the
fractional Fourier transform, where the angle is related to the variable $l$,
hence, we define the chirp transform on the graph as:

$F\left[m,n\right]=\sum^{N-1}_{k=0}u_{k}\left[m\right]\exp\left(j\frac{\pi}{2}k\left(\xi\right)\right)u_{k}\left[n\right],$
(26)

where $\xi=lk+f,$ $\xi$ is a linear function of $k,$ $l$ and $f$ are
constants, and the graph eigenvalues are $\lambda^{\xi}_{k}$.

Based on the above information, we formally provide the definition of the GLCT
as follows:

######  Definition 3.

We have described and shown the graph FrFT, scaling and CM phases in
Eqs(18)-(25). The DLCT is the proposed equation-based GLCT. Therefore, it can
be expressed as a cascading combination of these three operations:

$\mathbf{L}^{\left(a,b,c,d\right)}=\mathbf{V}^{-1}=\mathbf{\Lambda}_{\xi}\mathbf{Q}_{\sigma}\mathbf{\Lambda}^{\alpha}\mathbf{Q^{T}},$
(27)

and the definition of the GLCT of the signal $\mathbf{s}$ is

$\mathbf{\hat{s}}=\mathcal{L}^{\left(a,b,c,d\right)}\mathbf{s}:=\mathbf{L}^{\left(a,b,c,d\right)}\mathbf{s}=\left\\{\mathbf{\Lambda}_{\xi}\mathbf{Q}_{\sigma}\mathbf{\Lambda}^{\alpha}\mathbf{Q^{T}}\right\\}\cdot\mathbf{s},$
(28)

where the parameter relations between $(a,b,c,d)$ and $(\xi,\sigma,\alpha)$
are

$\begin{gathered}\xi=\frac{ac+bd}{a^{2}+b^{2}},\ \ \ \ \
\sigma=\sqrt{a^{2}+b^{2}},\\\
\alpha=\cos^{-1}\left(\frac{a}{\sigma}\right)=\sin^{-1}\left(\frac{b}{\sigma}\right).\end{gathered}$
(29)

######  Definition 4.

In our GLCT approach, the invertibility can be obtained by additivity as
follows Its inverse transform is

$\displaystyle\mathbf{L}^{\left(d,-b,-c,a\right)}\left\\{\mathbf{L}^{\left(a,b,c,d\right)}\mathbf{s}\right\\}$
$\displaystyle=\mathbf{s}$ (30) $\displaystyle\ \text{i.e.},\
\left[\begin{matrix}a&b\\\
c&d\end{matrix}\right]^{-1}\left[\begin{matrix}a&b\\\ c&d\end{matrix}\right]$
$\displaystyle=\left[\begin{matrix}1&0\\\ 0&1\end{matrix}\right],$

where $\mathbf{L}^{\left(d,-b,-c,a\right)}$ denotes the inverse GLCT (IGLCT)
operator of $\mathbf{L}^{\left(a,b,c,d\right)}$. Thus, its inverse transform
is

$\mathbf{s}=\left(\mathcal{L}^{\left(a,b,c,d\right)}\right)^{-1}\mathbf{\hat{s}}:=\mathbf{L}^{\left(d,-b,-c,a\right)}\mathbf{\hat{s}}=\left\\{\mathbf{Q}\mathbf{\Lambda}_{-\alpha}\mathbf{Q^{T}}_{\sigma}\mathbf{\Lambda}_{-\xi}\right\\}\cdot\mathbf{\hat{s}}.$
(31)

######  Remark 1.

In particular, when $a=\cos\alpha,b=\sin\alpha,c=-\sin\alpha,$ and
$d=\cos\alpha$, the GLCT operator will be the GFRFT operator,

$\mathbf{L}^{\left(\cos\alpha,\sin\alpha,-\sin\alpha,\cos\alpha\right)}=\mathbf{\Lambda}_{0}\mathbf{Q}_{1}\mathbf{\Lambda}_{\alpha}\mathbf{Q^{T}}=\mathbf{IQ}_{1}\mathbf{\Lambda}_{\alpha}\mathbf{Q^{T}}=\mathbf{Q\Lambda}_{\alpha}\mathbf{Q^{T}},$
(32)

where
$\xi=\frac{-\sin\alpha\cos\alpha+\sin\alpha\cos\alpha}{\cos^{2}\alpha+\sin^{2}\alpha}=0,\sigma=\sqrt{\cos^{2}\alpha+\sin^{2}\alpha}=1.$

######  Remark 2.

When $a=0,b=1,c=-1,$ and $d=0$, the GLCT operator will be the GFT operator,

$\mathbf{L}^{\left(0,1,-1,0\right)}=\mathbf{\Lambda}_{0}\mathbf{Q}_{1}\mathbf{\Lambda}_{\frac{\pi}{2}}\mathbf{Q^{T}}=\mathbf{IQ}\mathbf{\Lambda}_{\frac{\pi}{2}}\mathbf{Q^{T}}=\mathbf{Q\Lambda}_{\frac{\pi}{2}}\mathbf{Q^{T}}=\mathbf{F},$
(33)

where
$\xi=\frac{-1+1}{1}=0,\sigma=\sqrt{0+1}=1,\alpha=\cos^{-1}\left(0\right)=\sin^{-1}\left(1\right)=\frac{\pi}{2}$,
and $\mathbf{F}$ is the GFT operator.

###  3.2 Properties

Similar to the GFrFT, we introduce the zero rotation, additivity, and
invertibility properties of GLCT, define the convolution operator of GLCT, and
derive its translation property.

  1. 1.

Zero rotation

$\mathbf{L}^{\left(1,0,0,1\right)}=\mathbf{\Lambda}_{0}\mathbf{Q}_{1}\mathbf{\Lambda}_{0}\mathbf{Q^{T}}=\mathbf{IQIQ^{T}}=\mathbf{QQ^{T}}=\mathbf{I},$
(34)

where $a=1,b=0,c=0,d=1,$ and calculated $\xi=0,\sigma=1,\alpha=0$.

  2. 2.

Additivity
The additivity of the LCT is expressed as matrix multiplication, and the
additivity of the GLCT can be obtained by replacing the matrix as

$\mathbf{\Lambda}_{\xi_{3}}\mathbf{Q}_{\sigma_{3}}\mathbf{\Lambda}_{\alpha_{3}}\mathbf{Q^{T}}\left(s\left[n\right]\right)=\mathbf{\Lambda}_{\xi_{2}}\mathbf{Q}_{\sigma_{2}}\mathbf{\Lambda}_{\alpha_{2}}\mathbf{Q^{T}}\left\\{\mathbf{\Lambda}_{\xi_{1}}\mathbf{Q}_{\sigma_{1}}\mathbf{\Lambda}_{\alpha_{1}}\mathbf{Q^{T}}\left(s\left[n\right]\right)\right\\},$
(35)

where

$\left[\begin{matrix}a_{3}&b_{3}\\\
c_{3}&d_{3}\end{matrix}\right]=\left[\begin{matrix}a_{2}&b_{2}\\\
c_{2}&d_{2}\end{matrix}\right]\left[\begin{matrix}a_{1}&b_{1}\\\
c_{1}&d_{1}\end{matrix}\right].$ (36)

  3. 3.

Invertibility
The invertibility of the GLCT means that the IGLCT can be implemented by
another GLCT whose parameter matrix equals to the inverse of the forward
transform matrix, and the invertibility can be obtained by the above
additivity:

$\mathrm{i}\mathrm{n}\mathrm{v}\left(\mathbf{L}^{\left(a,b,c,d\right)}\right)=\left(\mathbf{L}^{\left(a,b,c,d\right)}\right)^{\mathbf{H}}=\mathbf{Q\Lambda}_{-\alpha}\mathbf{Q^{T}}_{\sigma}\mathbf{\Lambda}_{-\xi},$
(37)

where $\mathrm{i}\mathrm{n}\mathrm{v}\left(\cdot\right)$ represents the
inverse matrix, and $\left(\cdot\right)^{\mathbf{H}}$represents the
conjugation transpose. An alternative to the IGLCT is to recalculate the
parameters of another GLCT whose matrix is the inverse of the previous GLCT
matrix:

$\mathrm{i}\mathrm{n}\mathrm{v}\left(\mathbf{L}^{\left(a,b,c,d\right)}\right)=\mathbf{L}^{\left(d,-b,-c,a\right)}=\mathbf{\Lambda}_{\hat{\xi}}\mathbf{Q}_{\hat{\sigma}}\mathbf{\Lambda}_{\hat{\alpha}}\mathbf{Q^{T}}.$
(38)

  4. 4.

Reduction of the DLCT on the cycle graphs
It has been discussed before that when $\mathbf{A}=\mathbf{C}$, the GFT matrix
and the DFT matrix are identical, so that the GLCT matrix is the same as the
DLCT matrix in the cyclic graph, where the scaling parameter $\sigma=1$.

  5. 5.

Convolution theorem
The convolution in the domain of the linear canonical transform on a graph can
be given by

$\displaystyle\left(f\ast g\right)\left[n\right]$
$\displaystyle:=\sum^{N-1}_{m=0}\hat{f}\left[m\right]\hat{g}\left[m\right]L^{\left(d,-b,-c,a\right)}\left[n,m\right]$
(39) $\displaystyle\text{or}\ \ \mathbf{f}\ast\mathbf{g}$
$\displaystyle:=\mathbf{L}^{\left(d,-b,-c,a\right)}\left(\hat{\mathbf{f}}\odot\hat{\mathbf{g}}\right),$

where, the $\odot$ denotes the Hadamard product of the matrices. The
convolution in the vertex domain is a Hadamard product in the domain of the
graph linear canonical transform.

$\displaystyle\widehat{\mathbf{f}\ast\mathbf{g}}$
$\displaystyle=\widehat{\mathbf{L}^{\left(d,-b,-c,a\right)}\left(\hat{\mathbf{f}}\odot\hat{\mathbf{g}}\right)}$
(40)
$\displaystyle=\mathbf{L}^{\left(a,b,c,d\right)}\cdot\mathbf{L}^{\left(d,-b,-c,a\right)}\left(\hat{\mathbf{f}}\odot\hat{\mathbf{g}}\right)$
$\displaystyle=\hat{\mathbf{f}}\odot\hat{\mathbf{g}}.$

  6. 6.

Translation property
First, we define a $\delta$ function:

$\delta_{i}\left[n\right]=\begin{cases}1,&n=i\\\
0,&\text{otherwise}\end{cases}.$ (41)

The translation operator $\mathcal{T}_{i}$ can be obtained by convolution with
the $\delta_{i}$ function:

$\displaystyle\mathcal{T}_{i}\mathbf{f}:=\sqrt{N}\mathbf{f}\ast\delta_{i}$
$\displaystyle=\sqrt{N}\mathbf{L}^{\left(d,-b,-c,a\right)}\left(\hat{\mathbf{f}}\odot\hat{\delta}_{i}\right)$
(42)
$\displaystyle=\sqrt{N}\mathbf{L}^{\left(d,-b,-c,a\right)}\left(\hat{\mathbf{f}}\odot\mathbf{L}^{\left(a,b,c,d\right)}_{i}\right),$

where $\mathbf{L}^{\left(a,b,c,d\right)}_{i}$ denotes the $i$th column of the
matrix $\mathbf{L}^{\left(a,b,c,d\right)}$ . Then its GLCT is calculated to be

$\displaystyle\mathcal{L}^{\left(a,b,c,d\right)}\left(\mathcal{T}_{i}\mathbf{f}\right)$
$\displaystyle=\sqrt{N}\mathcal{L}^{\left(a,b,c,d\right)}\mathbf{L}^{\left(d,-b,-c,a\right)}\left(\hat{\mathbf{f}}\odot\mathbf{L}^{\left(a,b,c,d\right)}_{i}\right)$
(43)
$\displaystyle=\sqrt{N}\hat{\mathbf{f}}\odot\mathbf{L}^{\left(a,b,c,d\right)}_{i}.$

  7. 7.

Unitary
The adjacency matrix $\mathbf{A}$ of the real edge-weighted undirected graph
is a real symmetric matrix, so $\mathbf{A}$ can be orthogonally diagonalized:

$\mathbf{A}=\mathbf{V\Lambda_{(A)}V}^{-1}=\mathbf{V\Lambda_{(A)}V^{T}},$ (44)

where $\mathbf{L}=\mathbf{V^{T}}$ is an orthogonal matrix, so it can be
decomposed unitarily as:

$\mathbf{L}=\mathbf{V^{T}}=\mathbf{\Lambda_{0}Q_{1}\Lambda}\mathbf{Q}^{-1}=\mathbf{\Lambda_{0}Q_{1}\Lambda}\mathbf{Q^{H}}.$
(45)

Since the modulus of the eigenvalues of the orthogonal matrix is 1, the
diagonal elements of the diagonal matrix $\mathbf{\Lambda}$ can be written in
the form of $\exp\left(j\theta\right)$. Thus, by the definition of

$\mathbf{L}^{\left(a,b,c,d\right)}=\mathbf{\Lambda}_{\xi}\mathbf{Q}_{\sigma}\mathbf{\Lambda}^{\alpha}\mathbf{Q^{H}}.$
(46)

We consider multiplying $\mathbf{L}^{\left(a,b,c,d\right)}$ with its conjugate
transpose,

$\displaystyle\mathbf{L}^{\left(a,b,c,d\right)}\left(\mathbf{L}^{\left(a,b,c,d\right)}\right)^{\mathbf{H}}$
$\displaystyle=\left(\mathbf{\Lambda}_{\xi}\mathbf{Q}_{\sigma}\mathbf{\Lambda}^{\alpha}\mathbf{Q^{H}}\right)\left(\mathbf{\Lambda}_{\xi}\mathbf{Q}_{\sigma}\mathbf{\Lambda}^{\alpha}\mathbf{Q^{H}}\right)^{\mathbf{H}}$
(47)
$\displaystyle=\mathbf{\Lambda}_{\xi}\mathbf{Q}_{\sigma}\mathbf{\Lambda}^{\alpha}\mathbf{Q^{H}}\mathbf{Q\Lambda}^{-\alpha}\mathbf{Q^{T}}_{\sigma}\mathbf{\Lambda}_{-\xi}$
$\displaystyle=\mathbf{I}\ ,$

therefore, $\mathbf{L}^{\left(a,b,c,d\right)}$ is also a unitary matrix.

##  4 Simulation

To verify the validity, rationality and characteristics of the GLCT, we
provide two examples to illustrate the GLCT. The calculations are based on the
Graph Signal Processing toolbox (GSPBox) [34] in MATLAB.

###  4.1 The Cycle Diagram

Figure 4 shows examples of bipolar rectangular signals on the cycle diagram
[33] to illustrate the GLCT. Figure 5 shows a comparison of the imaginary and
real graphs for the cycle diagram under different $\xi$. We can understand the
transformation process from vertex domain to the frequency domain by observing
the GLCT of different $\xi,\sigma,\alpha$.

Specifically, the first example shows a GLCT degraded to a traditional DLCT on
a cycle diagram, where $\sigma\equiv 1$. When $\xi$ is a constant, with the
increase in $\alpha$, the eigenvalue (frequency) of the signal increases. When
$\alpha$ is constant, the real part of the signal becomes slower as $\xi$
increases, while the imaginary part becomes steeper as $\xi$ increases.

Figure 4: The GLCT of the bipolar rectangular signal on the cycle graph with
different $\alpha$. Figure 5: Comparison of the GLCT real and imaginary values
of the bipolar rectangular signals on cycle graphs with different $\xi$.

###  4.2 The Minnesota Road Diagram

Figure 6 depicts examples of bipolar rectangular signals on the Minnesota road
diagram [35] to illustrate GLCT. Figure 7 shows a comparison of the imaginary
and real graphs for the Minnesota road diagram under different $\xi$. We can
understand the transformation process from the vertex domain to the frequency
domain by observing the GLCT of different $\xi,\sigma,$and $\alpha$.

These properties can also be seen from the second example, and when $\xi,$ and
$\alpha$ are constant, as $\sigma$ increases, the eigenvalues of the graph
signal stabilize.

Figure 6: The GLCT of the bipolar rectangular signal on the Minnesota road
graph with different $\sigma,\alpha$. Figure 7: Comparison of the GLCT real
and imaginary values of the bipolar rectangular signals on the Minnesota road
graph with different $\xi$

##  5  Conclusions

To solve the problems of insufficient degrees of freedom, inadequate
flexibility, and underutilized parameters that cannot be solved by the GFrFT,
a generalization of the DLCT, which is called linear canonical transform on
graphs, abbreviated as GLCT, is proposed in this paper. The transform depends
on the parameters $\xi,\sigma$ and $\alpha$, which can solve the above
problems very well. Specifically, GLCT can be reduced to GTrFT, GFT and the
identity operator, and when the adjacency matrix $\mathbf{A=C}$, GLCT is
reduced to the traditional DLCT. Two successive GLCTs are equivalent to
another GLCT. The innovations of this paper are as follows. We provide the
definition of a chirp signal on the graph, use the new eigendecomposition
method (CDDHFs) to define the linear canonical transform on the graph, and
carry out emulation experiments. Finally, the eigendecomposition method of the
graph signal adjacency matrix used in this paper is not unique, nor is the
matrix used in the chirp multiplication and scaling stages, and the current
research may open up new areas in the field of graph signal processing and
lead to further research. It is hoped that there will be more transformation
methods and matrix forms in future research and that useful processing
techniques and specific applications can be developed in the field of linear
canonical transforms on graphs.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * [1] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, P. Vandergheynst, The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag. 30 (3) (2013) 83-98.
  * [2] A. Sandryhaila, J. M. F. Moura, Big data processing with signal processing on graphs: representation and processing of massive data sets with irregular structure, IEEE Signal Process. Mag. 31 (5) (2014) 80-90.
  * [3] A. Sandryhaila, J. M. F. Moura, Discrete signal processing on graphs, IEEE Trans. Signal Process. 61 (7) (2013) 1644-1656.
  * [4] D. K. Hammond, P. Vandergheynst, and R. Gribonval, Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal. 30 (2) (2011) 129-150.
  * [5] A. Sandryhaila and J. M. F. Moura, Discrete signal processing on graphs: Frequency analysis, IEEE Trans. Signal Process. 62 (12) (2014) 3042-3054.
  * [6] S. Chen, R. Varma, A. Sandryhaila, J. Kovačević, Vertex-frequency analysis on graphs, Appl. Comput. Harmon. Anal. 40 (2) (2016) 260-291.
  * [7] L. Stanković, D. Mandic, M. Daković, B. Scalzo, M. Brajović, E. Sejdić, A. G. Constantinides, Vertex-frequency graph signal processing: a comprehensive review, Digit. Signal Process. 107 (2020) 102802.
  * [8] S. K. Narang and A. Ortega, Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs, IEEE Trans. Signal Process. 61 (19) (2015) 4671-4685.
  * [9] L. Li, Y. F. Pu, Z. Y. Luo, Distributed functional link adaptive filtering for nonlinear graph signal processing, Digit. Signal Process. 128 (2022) 103558.
  * [10] S. Chen, R. Varma, A. Sandryhaila, J. Kovačević, Discrete signal processing on graphs: sampling theory, IEEE Trans. Signal Process. 63 (24) (2015) 6510-6523.
  * [11] Y. Wang, B. Z. Li, The fractional Fourier transform on graphs: sampling and recovery, in: 2018 14th IEEE International Conference on Signal Processing (ICSP), IEEE, 2018, pp. 1103-1108.
  * [12] N. H. Nguyen, K. Doğançay, W. Wang, Adaptive estimation and sparse sampling for graph signals in alpha-stable noise, Digit. Signal Process. 105 (2020) 102782.
  * [13] S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovačević, Signal recovery on graphs: variation minimization, IEEE Trans. Signal Process. 63 (17) (2015) 4609-4624.
  * [14] S. K. Narang and A. Ortega, Signal recovery on graphs: fundamental limits of sampling strategies, IEEE Trans. Signal and Inf. Proc. over Networks, 2 (4) (2016) 539-554.
  * [15] Z. Yang, G. Yang, L. Yang, Q. Zhang, A reconstruction method for graph signals based on the power spectral density estimation, Digit. Signal Process. 122 (2022) 103347.
  * [16] S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovačević, Signal denoising on graphs via graph filtering, in: 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), IEEE, 2014, pp. 872-876.
  * [17] A. Agaskar and Y. M. Lu, A spectral graph uncertainty principle, IEEE Trans. Inf. Theory, 59 (7) (2013) 4338–4356.
  * [18] Y. Wang, B. Li, Q. Cheng, The fractional Fourier transform on graphs, in: 2017 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), IEEE, 2017, pp. 105–110.
  * [19] F. J. Yan, B. Z. Li, Windowed fractional Fourier transform on graphs: Properties and fast algorithm, Digit. Signal Process. 118 (2021) 103210.
  * [20] M. Marcos, Q. Christiane, Linear canonical transformations and their unitary representations, J. Math. Phys. 12 (8) (1971) 1772-1783.
  * [21] H. M. Ozaktas, Z. Zalevsky, M. A. Kutay, The fractional Fourier transform with applications in optics and signal processing, Chichester ; New York : Wiley Sons. (2001).
  * [22] R. Simon, N. Mukunda, Iwasawa decomposition in first-order optics: universal treatment of shape-invariant propagation for coherent and partially coherent beams, J. Opt. Soc. Am. A, 15 (8) (1998) 2146–2155.
  * [23] S. C. Pei, Y. C. Lai, Discrete linear canonical transforms based on dilated Hermite functions, J. Opt. Soc. Am. A, 28 (8) (2011) 1695-1708.
  * [24] C. Candan, M. A. Kutay, H. M. Ozaktas, The discrete fractional Fourier transform, IEEE Trans. Signal Process. 48 (5) (2000) 1329-1337.
  * [25] J. Zhao, R. Tao, Y. Wang, Sampling rate conversion for linear canonical transform, Signal Process. 88 (11) (2008) 2825-2832.
  * [26] A. Koç, B. Bartan, H. M. Ozaktas, Discrete linear canonical transform based on hyperdifferential operators, IEEE Trans. Signal Process. 67 (9) (2019) 2237-2248.
  * [27] A. Koç, H. M. Ozaktas, L. Hesselink, Fast and accurate computation of two-dimensional non-separable quadratic-phase integrals, J. Opt. Soc. Am. A, 27 (6) (2010) 1288–1302.
  * [28] A. Koç, H. M. Ozaktas, L. Hesselink, Fast and accurate algorithm for the computation of complex linear canonical transforms, J. Opt. Soc. Am. A, 27 (9) (2010) 1896–1908.
  * [29] A. Koc, H. M. Ozaktas, C. Candan and M. A. Kutay, Digital computation of linear canonical transforms, IEEE Trans. Signal Process. 56 (6) (2008) 2383-2394.
  * [30] X. Guo, H. B. Sun, S. L. Wang, and G. S. Liu, Comments on discrete chirp-Fourier transform and its application to chirp rate estimation, IEEE Trans. Signal Process. 50 (12) (2002) 3115-3116.
  * [31] L. Ruiz, L. F. O. Chamon, A. Ribeiro, The graphon fourier transform, in: 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2020, pp. 5660-5664.
  * [32] M. W. Morency and G. Leus, Graphon filters: Graph signal processing in the limit, IEEE Trans. Signal Process. 69 (2021) 1740-1754.
  * [33] M. Puschel, J. M. F. Moura, Algebraic signal processing theory: Foundation and 1-D time, IEEE Trans. Signal Processing. 56 (8) (2008) 3572-3585.
  * [34] N. Perraudin, J. Paratte, D. Shuman, V. Kalofolias, P. Vandergheynst, D. K. Hammond, GSPBOX: A toolbox for signal processing on graphs. ArXiv e-prints, Aug. 2014. http://arxiv.org/abs/1408.5781.
  * [35] D. Gleich, “The MatlabBGL Matlab library,” http://www.cs.purdue.edu/homes/dgleich/packages/matlab_bgl/index.html.