Kumari Neeraj Singh*
| Sanjeev Kumar
© 2024 The authors. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).
OPEN ACCESS
In this paper, we introduce a fractional-order variant of the Stockwell transform, specifically designed for analyzing signals that can be represented in terms of a graph data structure and integrates the ideas of fractional Stockwell transform and spectral graph theory. The proposed transform is named the ‘Spectral Graph Fractional Stockwell Transform’ or ‘SGFrST’ for short. Fundamentally, SGFrST makes use of the graph spectral domain to extract the underlying connection patterns and network structure of complex systems. SGFrST essentially fills the gap between signal processing methods and spectral graph theory by providing a flexible instrument that allows for hitherto unheard-of levels of precision and efficiency when comprehending and interpreting signals on graph-based domains. To begin, we introduce the spectral graph Stockwell transform by modulating the graph wavelet transform. Subsequently, we extend this concept by incorporating the spectral graph wavelet operator alongside the fractional order, resulting in the SGFrST. We derive various mathematical properties associated with the SGFrST, including an inversion mechanism and an inner product theorem. The proposed transform demonstrates effective applicability across a spectrum of graph signal processing scenarios. Basically, this makes it possible to extract useful features from signals that are present on graph structures, which helps with a variety of tasks in domains such as the social sciences, neuroscience, image processing and telecommunications. These tasks include image restoration, anomaly detection, pattern identification, and classification.
graph wavelet transform, graph fractional Fourier transform, graph fractional wavelet transform, graph Stockwell transform, Laplacian matrix, graph signal processing, time-frequency analysis, Stockwell transform
In signal processing, the wavelet transforms and Stockwell transform are two commonly used transforms for time-frequency analysis of stationary and varying signals. Their fractional variants also play a promising tool in analyzing time-varying signals and images. Existing literature [1-4] depict the importance of the fractional order transforms in the signal and image processing.
To analyze the signals those can be represented as graphs, a new domain is emerged called signal processing on graphs [5-7]. It can be seen as an extension of classical signal processing while analyzing signals using results from spectral graph theory. Spectral graph consists of the eigenfunctions and eigenvalues of its graph Laplacian matrix. The basic approaches of the graph signal analysis is rooted in spectral graph theory [8] and algebraic signal processing theory [9]. The graph theory is a mathematical approach for understanding the geometrical structure and for finding a relationship between data points. Some of the applications of graph signal processing can be explored in work like sampling and graph-based Wiener filtering [10], graph representation of geometrical data [11], graph learning on biological data [12]. For more details about graph signal processing, one can refer to the study of Ortega [13].
In spectral graph analysis, the classical transforms were extended to their graph variants to deal with signal vertex-frequency distributions on weighted graphs. Subsequently, the graph Fourier transform (GFT) [14, 15] and graph wavelet transform (GWT) [16, 17] are, respectively, the graph variants of the Fourier transform and wavelet transform. In general, graph transforms may provide a highly adaptable model for approximating the data domains of a wide variety of problems. Examples include piecewise smooth image compression [18], traffic prediction in transportation systems [19], and vibration signal denoising outcomes [20]. The GFT is a mapping between the graph signal set and its representation as the direct sum of irreducible shift-invariant subspaces. In other terms, it is a matrix of eigenvectors of the constructed graph Laplacian matrix. Hence, the frequency ordering is predicated on the quadratic form. Small eigenvalues correspond to low frequencies and vice versa due to the natural ordering of frequencies. The studies [16, 21, 22] devised wavelet transforms on graphs. Spectral Graph Wavelet Transform (SGWT) refers to the transformation associated with the classical wavelet transform in the spectral graph domain.
The fractional form of graph transforms is also discovered as in the case of their integer counterparts. One such example is graph fractional Fourier transform (GFrFT) [23, 24]. Similarly, graph fractional wavelet transform (GFrWT) [25] is an extension of the SGWT to fractional domain. In traditional signal processing, the Stockwell transform was derived from the windowed Fourier transform to circumvent this transform's limitations. The Gaussian window of the S-transform, which is governed by frequency, produces superior results compared to other conventional transforms. Thus, the graph Stockwell transform [26] was developed for graph-based signals by adjusting the window size of the graph windowed Fourier transform [27] for various frequencies.
In this study, a generalization of the spectral graph Stockwell transform called ‘spectral graph fractional Stockwell transform’ (SGFrST) is proposed by incorporating the fractional order. Such a generalization provides a more flexible tool to analyze the signals/images those can be represented in terms of a graph signal. Hence, along with the definition, the study also focuses to derive some of the basic mathematical properties of the proposed SGFrST. Further, an application of the proposed transform is given for its feasibility in signal processing.
The remaining sections are organized as follows: In Section 2, we present preliminaries like fractional S-transform, spectral graph theory, and spectral graph S-transform. In Section 3, the proposed spectral graph fractional Stockwell transform is defined for the graph signals. We establish the inversion formula and the inner product theorem for the proposed transform in Section 4. In Section 5, an application is shown in image denoising. Finally, the concluding remarks is given in the Section 6.
2.1 Fractional Stockwell transform
The fractional Stockwell transform (FrST) of a signal $s(t) \in L^2(\mathbb{R})$ with respect to the window function g(t) is defined as [28]:
$\begin{aligned} \mathrm{S}_s^\theta(a, b)=\left[\mathrm{S}_\psi^\theta s(t)\right](a, b)=\frac{1}{\sqrt{2 \pi}} \int s(t) g_{\theta, a, b}^*(t) d t\end{aligned}$ (1)
where, gθ,a,b(t) is defined as:
$g_{\theta, a, b}(t)=a g(a(t-b)) e^{i a t \csc \theta-\frac{i}{2}\left(t^2-b^2\right) \cot \theta}$ (2)
and, θ stands for the rotation angle of FrST.
Based on the Parseval identity of FrFT, the Eq. (1) can be leads to another form of FrST [28]:
$\begin{aligned} & \mathbf{S}_s^\theta(a, b)=\frac{1}{\sqrt{2 \pi}} e^{-i a b \csc \theta} \int e^{-i t \csc \theta} \hat{s}_\theta(u) \hat{g}_\theta^*\left(\frac{u}{a} \csc \theta\right) K_\theta^*(b, u) d u\end{aligned}$ (3)
where, $\hat{s}_\theta$ is the $\operatorname{FrFT}$ of $s$ with $\theta$-order and $K_\theta^*(b, u)$ is the complex conjugate of kernel $K_\theta(b, u)$ [28].
2.2 Spectral graph theory
A weighted graph may be denoted by $\mathcal{G}=\{\mathcal{V}, \mathcal{E}, \omega\}$ consisting of a finite set of nodes or vertices $v_i \in \mathcal{V}$ with $|\mathcal{V}|=P<\infty$, a set of edges $\mathcal{E}$ such that the vertices linking edges $\left(v_i, v_j\right) \in \mathcal{E}$ and the weighted function $\omega: \mathcal{\varepsilon} \rightarrow \mathbb{R}^{+}$. The adjacency matrix $\mathcal{W}=\left\{w_{i, j}\right\}_{P \times P} \in \mathbb{R}^{P \times P}$ is used to describe the connectedness of vertices for the weighted graph $\mathcal{G}$, where $w_{i j}$ denotes the weight of the edge connecting vertices $v_i$ and $v_j$. If the vertices $v_i$ and $v_j$ are not connected then the weight $w_{i j}$ $=0$, otherwise the weight $w_{i j}$ is defined as follows:
$$
w_{i, j}=\left\{\begin{array}{l}
\omega\left(e_{i, j}\right), \text { if } e_{i, j} \text { connects the vertices } i \text { and } j \\
0 \quad \text { otherwise,}
\end{array}\right.
$$
where, $\quad w_{i, j}=\|f(i)-f(j)\|$ and $\|\cdot\|$ represents the Euclidean distance between two vertices. The function $f: \mathcal{V} \rightarrow$ $\mathbb{R}$ is a real valued function on the vertices of the weighted graph $\mathcal{G}$. The function $f$ can be viewed as a vector in $\mathbb{R}^P$ and the value of the function on vertex defines each coordinate.
For weighted graph $\mathcal{G}$, the diagonal matrix $\mathcal{D}$ is expressed as $\mathcal{D}=\operatorname{diag}\left(d\left(v_1\right), d\left(v_2\right), \ldots d\left(v_P\right)\right)$, where $d\left(v_i\right)$ represent the degree of vertex $v_i$ and can be obtained by $d\left(v_i\right)=\sum_j w_{i, j}$. This means, the diagonal matrix $\mathcal{D} \in \mathbb{R}^{P \times P}$ describing the degrees of each vertex. For spectral graph analysis, the graph Laplacian matrix $\mathcal{L}$ is essential and defined as $\mathcal{L}=\mathcal{D}-\mathcal{W}$. As the matrix $\mathcal{L}$ is real and symmetric positive definite, then it can be written as:
$\mathcal{L}=X \Lambda X^H$ (4)
where, the eigenvector matrix $X=\left\{x_0, x_1, x_2, \ldots, x_{P-1}\right\}$ is shorted according to the eigenvalues $0 \leq \lambda_0 \leq \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_{P-1}$ and diagonal eigenvalue matrix $\Lambda=\operatorname{diag}\left(\lambda_0, \lambda_1, \lambda_2, \ldots, \lambda_{P-1}\right)$ satisfying $\mathcal{L} x_i=\lambda_i x_i$.
2.3 Spectral graph Stockwell transform
The graph Stockwell transform of a graph signal $s \in \mathbb{R}^P$ is defined by the modulation $\left(\mathcal{M}_q s\right)(n)=\sqrt{P} s(n) x_q^*(n)$ in graph wavelet transform $[15,19,20,25]$ domain:
$\begin{gathered}\mathrm{W}_s(a, n)=\left(\mathcal{J}_k^a s\right)(n) \\ =\sum_{q=0}^{P-1} k\left(a \lambda_q\right) \hat{s}(q) x_q(n)=\left\langle\psi_{a, n}, s\right\rangle\end{gathered}$ (5)
where, $n=1,2, \ldots, P$ and $\psi_{\underline{\underline{a,n}}}$ is the coefficients of graph wavelet transform $W_s(a, n)$, and $\mathcal{J}_k^a=k(a \mathcal{L})$ is the spectral graph wavelet operator corresponding to the scale $a=\left(a_1, a_2, \ldots\right.$, $a_J$ ) and $J$ is the decomposition level. The wavelet kernel function $k: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$should behave as a band pass filter. The spectral graph wavelet at scale $a$ corresponding to the vertex $n$ is defined as:
$\psi_{a, n}(m)=\sum_{q=0}^{P-1} k\left(a \lambda_q\right) x_q^*(n) x_q(m) m=1,2, \ldots, P.$ (6)
and the graph Fourier transform is given as:
$\begin{gathered}\hat{s}(q)=\sum_{n=1}^P s(n) x_q^*(n)=\left\langle s, x_q\right\rangle, \\ q=0,1,2, \ldots, P-1 .\end{gathered}$ (7)
Hence, by the modulation of the Eq. (5), the graph Stockwell transform is defined as:
$\begin{gathered}\mathcal{S}_s(a, n)=\left(\mathbf{L}_k^a s\right)(n)=\sqrt{P} x_q^*(n) \sum_{q=0}^{P-1} k\left(a \lambda_q\right) \hat{s}(q) x_q(n)\end{gathered}$ (8)
where, $\mathbf{L}_k^a=\sqrt{P} x_q^* \mathcal{J}_k^a$. The window function $k$ in vertex domain is given as:
$k(n, q)=\frac{\left|\lambda_q\right|}{\sqrt{2 \pi}} e^{-\frac{n^2 \lambda_q^2}{2}}$ (9)
From the Eqs. (7) and (8), we have:
$\begin{array}{r}
\mathcal{S}_s(a, n)=\left(\mathbf{L}_k^a s\right)(n)=\sum_{m=1}^P s(m)\left(\sqrt{P} x_q^*(n) \sum_{q=0}^{P-1} k\left(a \lambda_q\right) x_q^*(m) x_q(n)\right) \\
=\sum_{m=1}^P s(m) S_{a, n}^*(m)=\left\langle s, S_{a, n}\right\rangle
\end{array}$ (10)
where,
$S_{a, n}(m)=\sqrt{P} x_q(n) \sum_{q=0}^{P-1} k\left(a \lambda_q\right) x_q^*(n) x_q(m)$ (11)
is the graph Stockwell coefficient.
To define SGFrST, first we define the fractional Laplacian matrix $\mathcal{L}_\theta$, where $0<\theta \leq 1$. Consider the fractional Laplacian matrix $\mathcal{L}_\theta$ is defined as:
$\mathcal{L}_\theta=y \mathcal{U} y^H$ (12)
where,
$y=\left[y_0, y_1, y_2, \ldots, y_{P-1}\right]=x^\theta$ (13)
and
$\mathcal{U}=\operatorname{diag}\left(\left[u_0, u_1, u_2, \ldots, u_{P-1}\right]\right)=\Lambda^\theta$ (14)
We claim that
$y_q=x_q^\theta$ and $u_q=\lambda_q^\theta, q=0,1,2, \ldots, P-1$ (15)
The GFrFT of a signal $S$ on vertices $\mathcal{V}$ of graph $\mathcal{G}$ is defined as [25]:
$\begin{gathered}\hat{s}_\theta(q)=\sum_{m=1}^P s(m) y_q^*(m)=\left\langle s, y_q\right\rangle, \\ q=0,1,2, \ldots, P-1\end{gathered}$ (16)
and the inverse GFrFT is defined by [25]:
$\begin{gathered}s(m)=\sum_{q=0}^{P-1} \hat{s}_\theta(q) y_q(m)=\left\langle\hat{s}_\theta, y_q^*\right\rangle \\ m=1,2, \ldots, P\end{gathered}$ (17)
The SGFrST on nodes $\mathcal{V}$ of graph $\mathcal{G}$ for a signal $s$ with operator $\mathbf{L}_{k_\theta}^a$ can be proposed as:
$\begin{gathered}\mathcal{S}_s(\theta, a, n)=\left(\mathbf{L}_{k_\theta}^a s\right)(n)=\sqrt{P} y_q^*(n) \sum_{q=0}^{P-1} k\left(a \lambda_q^\theta\right) \hat{s}_\theta(q) y_q(n)\end{gathered}$ (18)
where, $y_q^*$ is the complex conjugate of eigenvector, $k\left(a \lambda_q^\theta\right)$ is a window function and $\hat{s}_\theta$ is the graph fractional Fourier transform.
Substituting the value of Eq. (16) in Eq. (18), we have:
$\begin{gathered}\mathcal{S}_s(\theta, a, n)=\sqrt{P} y_q^*(n) \sum_{q=0}^{P-1} k\left(a \lambda_q^\theta\right) \sum_{m=1}^P s(m) y_q^*(m) y_q(n)\end{gathered}$ (19)
Rearranging the above equation, we obtain:
$\begin{gathered}\mathcal{S}_s(\theta, a, n)=\sum_{m=1}^P s(m) \sqrt{P} y_q^*(n) \sum_{q=0}^{P-1} k\left(a \lambda_q^\theta\right) y_q^*(m) y_q(n)\end{gathered}$ (20)
Write the equation in the form of inner product:
$\begin{gathered}\mathcal{S}_s(\theta, a, n)=\left(\mathbf{L}_{k_\theta}^a s\right)(n)=\sum_{m=1}^P s(m) S_{\theta, a, n}^*(m)=\left\langle s, S_{\theta, a, n}\right\rangle, n=1,2,3, \ldots, P\end{gathered}$ (21)
where,
$\mathbf{L}_{k_\theta}^a=\sqrt{P} y_q k\left(a \mathcal{L}_\theta\right)$ (22)
$\begin{gathered}S_{\theta, a, n}(m)=\sqrt{P} y_q(n) \sum_{q=0}^{P-1} k\left(a \lambda_q^\theta\right) y_q^*(n) y_q(m) \\ m=1,2,3, \ldots, P\end{gathered}$ (23)
Thus, the Eq. (21) gives the SGFrST of a graph signal s. The SGFrST's capability to analyze signals with time-varying spectral content within the graph domain makes it a versatile and valuable tool across domains. Its ability to capture both time and frequency information simultaneously facilitates a comprehensive understanding of graph signals in graph-based systems.
In the above definition of the GFrST, the graph fractional Laplacian operator $\mathcal{L}_\theta$ can be calculated mainly in the following two ways:
(A) Using the classical definition of FrST: According to the window function ψθ,a,b of FrST given in the Eq. (2), the GFrST of a graph signal s can be defined as:
$\begin{aligned} \mathcal{S}_s(\theta, a, n) & =\left(\mathbf{L}_{k_\theta}^a s\right)(n)=\sum_{m=1}^P s(m) S_{\theta, a, n}^*(m) \\ & =\left\langle s, S_{\theta, a, n}\right\rangle, n=1,2,3, \ldots, P\end{aligned}$
where,
$\begin{gathered}\mathbf{L}_{k_\theta}^a=\sqrt{P} e^{i a m \csc \theta-\frac{i}{2}\left(m^2-n^2\right) \cot \theta} x_q k(a \mathcal{L}) \\ S_{\theta, a, n}(m)=\sqrt{P} e^{i a m \csc \theta-\frac{i}{2}\left(m^2-n^2\right) \cot \theta} x_q(n) \sum_{q=0}^{P-1} k\left(a \lambda_q\right) x_q^*(n) x_q(m), m=1,2,3, \ldots, P\end{gathered}$
From the above equation we can see that the basis $S_{\theta, a, n}(m)$ still depend on the same eigenvectors $x_q(m)$ of the Laplacian matrix $\mathcal{L}$. However, in this case the basis $S_{\theta, a, n}(m)$ depends on new function $y_q(n)$.
(B) Using a different form of Laplacian operator $\mathcal{L}^\theta$ : The graph fractional Laplacian operator $\mathcal{L}^\theta$ can also be given as the following:
$\mathcal{L}^\theta=\left(X \Lambda X^H\right)^\theta=X \Lambda^\theta X^H$
Comparing the above equation with Eq. (4), we see that fractional Laplacian operator $\mathcal{L}^\theta$ use the same function $\mathcal{X}$ as the Laplacian $\mathcal{L}$. Hence, define the GFrST similar to Eq. (10), we have:
$\begin{aligned} \mathcal{S}_s(\theta, a, n)= & \left(\mathbf{L}_{k_\theta}^a s\right)(n)=\sum_{m=1}^P s(m) S_{\theta, a, n}^*(m)=\left\langle s, S_{\theta, a, n}\right\rangle, n=1,2,3, \ldots, P\end{aligned}$
where,
$\begin{gathered}\mathbf{L}_{k_\theta}^a=\sqrt{P} x_q k\left(a \mathcal{L}^\theta\right), \\ S_{\theta, a, n}(m)=\sqrt{P} x_q(n) \sum_{q=0}^{P-1} k\left(a \lambda_q^\theta\right) x_q^*(n) x_q(m), \\ m=1,2,3, \ldots, P\end{gathered}$
From the above equation we can see that the basis Sθ,a,n(m) still depend on the same eigenvectors xq(m) of the Laplacian matrix $\mathcal{L}$. However, in our case the basis Sθ,a,n(m) depend on new function yq(n).
In this section we discuss the inversion formula and inner product theorem of the proposed transform.
4.1 Inverse spectral graph fractional Stockwell transform
In many of the signal processing applications, a reconstruction of a signal is an essential step. The reconstruction of an original graph signal in spectral graph domain may be recovered corresponding to the given transform coefficients. Hence, we give the following result related to the inverse SGFrST which can be utilized for the signal reconstruction from its transform coefficients.
Lemma 1: Let the window kernel function k of the graph transforms satisfies the admissibility condition:
$P \int_0^{\infty} \frac{k^2(t)}{t} d t=C_{k_\theta}<\infty$ (24)
and $k(0)=0$. Let $s \in \mathbb{R}^P$ be a signal and $s^{\#}$ be the projection of $s$ onto the orthogonal complement of the span of $y_0$, i.e. $\mathrm{s}^{\#}(m)=s(m)-\langle s(m), \quad y(m)\rangle \mathrm{y}_0(m)$. Then the continuous reconstruction formula can be given as:
$\frac{1}{c_{k_\theta}} \sum_{n=1}^P \int_0^{\infty} S_s(\theta, a, n) S_{\theta, a, n}(m) \frac{d a}{a}=s^{\#}(m)$ (25)
In particular, the complete reconstruction formula is given by s(m)=s#(m)+⟨s(m), y(m)⟩y0(m).
Proof: To prove the reconstruction formula for the SGFrST, we start with the definition of the transform and its coefficient. So, using the Eq. (18) and Eq. (23) in the Eq. (25), we have:
$\frac{1}{C_{k_\theta}} \sum_{n=1}^P \int_0^{\infty} \mathcal{S}_s(\theta, a, n) S_{\theta, a, n}(m) \frac{d a}{a}=\frac{1}{C_{k_\theta}} \sum_{n=1}^P \int_0^{\infty} \sqrt{P} y_q^*(n) \sum_{q=0}^{P-1} k\left(a \lambda_q^\theta\right) \hat{s}_\theta(q) y_q(n) \sqrt{P} y_{q^{\prime}}(n) \sum_{q^{\prime}=0}^{P-1} k\left(a \lambda_{q^{\prime}}^\theta\right) y_{q^{\prime}}^*(n) y_{q^{\prime}}(m) \frac{d a}{a}$
Rearranging the above equation in a simplified form, we have:
$\frac{1}{C_{k_\theta}} \sum_{n=1}^P \int_0^{\infty} \mathcal{S}_s(\theta, a, n) S_{\theta, a, n}(m) \frac{d a}{a}=\frac{P}{C_{k_\theta}} \int_0^{\infty} \sum_{q, q^{\prime}=0}^{P-1} k\left(a \lambda_q^\theta\right) k\left(a \lambda_{q^{\prime}}^\theta\right) \hat{s}_\theta(q) y_{q^{\prime}}(m) \sum_{n=1}^P y_q^*(n) y_q(n) y_{q^{\prime}}(n) y_{q^{\prime}}^*(n) \frac{d a}{a}$
Since, the eigenvectors $y_q$ are orthonormal so $\sum_n y_q^*(n) y_{q^{\prime}}(n)=\delta_{q, q^{\prime}}$. Inserting this in above equation and summing over $q^{\prime}$, we have:
$\begin{gathered}\frac{1}{c_{k_\theta}} \sum_{n=1}^P \int_0^{\infty} \mathcal{S}_s(\theta, a, n) S_{\theta, a, n}(m) \frac{d a}{a}= \frac{P}{c_{k_\theta}} \sum_{q=0}^{P-1}\left(\int_0^{\infty} k^2\left(a \lambda_q^\theta\right) \frac{d a}{a}\right) \hat{s}_\theta(q) y_q(m)\end{gathered}$.
Consider $a \lambda_q^\theta=t$ except $\lambda_q^\theta=0$ when $q=0$. Thus, we have $\int_0^{\infty} k^2\left(a \lambda_q^\theta\right) \frac{d a}{a}=\int_0^{\infty} k^2(t) \frac{d t}{t}=\frac{c_{k_\theta}}{P}$ which is independent of q. Hence:
$\begin{gathered}\frac{1}{c_{k_\theta}} \sum_{n=1}^P \int_0^{\infty} \mathcal{S}_s(\theta, a, n) S_{\theta, a, n}(m) \frac{d a}{a}=\sum_{q=0}^{P-1} \hat{s}_\theta(q) y_q(m)- \hat{s}_\theta(0) y_0(m)\end{gathered}$
It's look like the definition of inverse GFrFT. Thus, using the definition of the inverse GFrFT (17) and $\hat{s}_\theta(q)$ for $q=0$, we obtain:
$\begin{aligned} \frac{1}{C_{k_\theta}} \sum_{n=1}^P \int_0^{\infty} & \mathcal{S}_s(\theta, a, n) S_{\theta, a, n}(m) \frac{d a}{a}=s(m)- \langle s(m), y(m)\rangle y_0(m)\end{aligned}$
Hence, we can obtain the complete reconstruction of the graph signal by $s=s^{\#}+\hat{s}_\theta(0) y_0$, which proves the result. This lemma also shows that the graph signal $s$ can not be reconstructed for zero mean of the fractional graph Stockwell.
4.2 Inner product result for spectral graph fractional Stockwell transform
The inner product theorem for a graph signal $s$ in spectral graph domain with window function $k(n, q)=\frac{\left|\lambda_q\right|}{\sqrt{2 \pi}} e^{-\frac{n^2 \lambda_q^2}{2}}$ in vertex domain is given as:
$\begin{gathered}\sum_n\left|S_s(\theta, a, n)\right|^2= \\ P\left(\sum_q \frac{a^2 \lambda_q^2}{2 \pi} e^{-n^2 a^2\left(\lambda_q^\theta\right)^2}\right)\left\langle\hat{s}_\theta(q), \hat{s}_\theta^*(q)\right\rangle\end{gathered}$ (26)
where, $\mathcal{S}_S(\theta, a, n), \hat{S}_\theta$ are the SGFrST and graph fractional Fourier transform of graph signal $s$ respectively.
Proof: Let $s$ is a graph signal on graph $\mathcal{G}$ then the SGFrST is given by (18):
$\mathcal{S}_s(\theta, a, n)=\sqrt{P} y_q^*(n) \sum_{q=0}^{P-1} k\left(a \lambda_q^\theta\right) \hat{s}_\theta(q) y_q(n)$ (27)
Taking the complex conjugate of (27), we get:
$\mathcal{S}_s^*(\theta, a, n)=\sqrt{P} y_q(n) \sum_{q=0}^{P-1} k^*\left(a \lambda_q^\theta\right) \hat{s}_\theta^*(q) y_q^*(n)$ (28)
Thus, the LHS of Eq. (26) can be written as:
$\begin{aligned} \sum_n \mathcal{S}_s(\theta, a, n) \mathcal{S}_s^*(\theta, a, n)=P \sum_n\left(y_q^*(n) \sum_{q=0}^{P-1} k\left(a \lambda_q^\theta\right) \hat{s}_\theta(q) y_q(n)\right) \\ \left(y_{q^{\prime}}(n) \sum_{q^{\prime}=0}^{P-1} k^*\left(a \lambda_{q^{\prime}}^\theta\right) \hat{s}_\theta^*\left(q^{\prime}\right) y_{q^{\prime}}^*(n)\right)\end{aligned}$ (29)
Rearranging the terms of the Eq. (29), we have:
$\sum_n \mathcal{S}_s(\theta, a, n) \mathcal{S}_s^*(\theta, a, n)=\mathrm{P} \sum_{q, q^{\prime}}\left(\left(k\left(a \lambda_q^\theta\right) k^*\left(a \lambda_{q^{\prime}}^\theta\right) \hat{s}_\theta(q) \hat{s}_\theta^*\left(q^{\prime}\right)\right) \sum_n y_q^*(n) y_{q^{\prime}}(n) y_q(n) y_{q^{\prime}}^*(n)\right)$ (30)
Taking the summation over $q^{\prime}, n$ and using the orthogonality property of eigenvectors, i.e., $\sum_n y_q^*(n) y_{q^{\prime}}(n)=\delta_{q, q^{\prime}}$, we get:
$\sum_n\left|\mathcal{S}_s(\theta, a, n)\right|^2=P \sum_q\left|k\left(a \lambda_q^\theta\right)\right|^2\left|\hat{s}_\theta(q)\right|^2$ (31)
Substituting the value of window function $k$ in the above equation, we get:
$\sum_n\left|\mathcal{S}_s(\theta, a, n)\right|^2=P \sum_q \frac{a^2 \lambda_q^2}{2 \pi} e^{-n^2 a^2\left(\lambda_q^\theta\right)^2}\left|\hat{s}_\theta(q)\right|^2$ (32)
Rewrite the Eq. (32) in the following form:
$\begin{gathered}\left\langle\mathcal{S}_S(\theta, a, n), \mathcal{S}_s^*(\theta, a, n)\right\rangle=P\left(\sum_q \frac{a^2 \lambda_q^2}{2 \pi} e^{-n^2 a^2\left(\lambda_q^\theta\right)^2}\right)\left\langle\hat{s}_\theta(q), \hat{s}_\theta^*(q)\right\rangle\end{gathered}$ (33)
Thus, we get the desired result.
The theorem allows us to analyze a particular graph signal by examining its spectral representation. It provides insights into the frequency components, correlations, and interactions of the signal in the graph domain, enabling further analysis, manipulation, or reconstruction of the graph signal based on its spectral properties.
Figure 1. First row: Denoising of a noisy image corrupted with Gaussian noise of zero mean and variance 0.08 in the transformed domain (with soft thresholding with fixed fractional order). Second row: The corresponding spectral graph representations
Figure 2. First row: Denoising of a noisy image corrupted with Gaussian noise of zero mean and variance 0.25 in the transformed domain (with soft thresholding with fixed fractional order). Second row: The corresponding spectral graph representations
Figure 3. First row: Denoising of a noisy image corrupted with Gaussian noise of zero mean and variance 0.08 in the transformed domain (with soft thresholding with fixed fractional order). Second row: The corresponding spectral graph representations
Figure 4. First row: Denoising of a noisy image corrupted with Gaussian noise of zero mean and variance 0.25 in the transformed domain (with soft thresholding with fixed fractional order). Second row: The corresponding spectral graph representations
To demonstrate the practicality of the transformation, we have applied it to denoise medical images. In this application, we employed soft threshold in the transformed domain using the spectra of two distinct images. These images were corrupted with Gaussian noise of mean zero and variances of 0.08 and 0.25. The qualitative outcomes are depicted in Figures 1-4. The perceptual quality of the reconstructed images confirms the efficacy of the transformation in restoring images degraded by noise. An image can be envisioned as a graph signal, where individual pixels serve as vertices and the interconnectedness of regions is akin to edge connections. We also provided the corresponding graph representations [29] for each of the results. The graph representations reveal that the restored image closely resembles the original, barring intensity variations. These variations can be addressed through post-processing steps, such as histogram specification.
Furthermore, the proposed transformation holds potential for image segmentation (as indicated by the graph representations). Beyond image processing, the same transformation can be harnessed to analyze other graph signals across diverse domains like social networks, sensor networks, data analysis on graph structures, and other fields where time-frequency analysis plays a pivotal role.
We first introduced a new variant of the S-transform say SGST in spectral graph domain. Then the approximation of graph Stockwell coefficients has been examined. The main contribution of this paper is summarized as:
(1) A new transform namely SGFrST is defined for analysing Graph signals.
(2) For the proposed transform the inversion formula is established which is based on the admissibility condition of window kernel function.
(3) The inner product theorem for the proposed transform is derived with the help of a fixed window function.
The proposed transform is having applications for analysing signals those can be representing in terms of graph-based data structures. The proposed transform is highly dependent on the underlying graph structure of the signals. Moreover, the value of fractional order will depend on the signal underlying to have a best transform domain representation. Hence, choice of the appropriate fractional order for such a transform is challenging. In future, we will try to extend this work for having a signal-driven choice of the fractional order and other parameters. Further, we will explore the applications of the proposed transform in the domains like social network analysis and recommendation systems.
One of the authors, Km. Neeraj Singh, is grateful to the Ministry of Education, Government of India and the Indian Institute of Technology, Roorkee for the financial support during her PhD.
[1] Bultheel, A., Martínez-Sulbaran, H. (2007). Recent developments in the theory of the fractional Fourier and linear canonical transforms. Bulletin of the Belgian Mathematical Society-Simon Stevin, 13(5): 971-1005. https://doi.org/10.36045/bbms/1170347822
[2] Yetik, İ.Ş., Kutay, M.A., Ozaktas, H.M. (2001). Image representation and compression with the fractional Fourier transform. Optics Communications, 197(4-6): 275-278. https://doi.org/10.1016/S0030-4018(01)01462-6
[3] Liu, J., Chen, S., Tan, X. (2008). Fractional order singular value decomposition representation for face recognition. Pattern Recognition, 41(1): 378-395. https://doi.org/10.1016/j.patcog.2007.03.027
[4] Liu, L., Wu, J., Li, D., Senhadji, L., Shu, H. (2018). Fractional wavelet scattering network and applications. IEEE Transactions on Biomedical Engineering, 66(2): 553-563. https://doi.org/10.1109/TBME.2018.2850356
[5] Shuman, D.I., Narang, S.K., Frossard, P., Ortega, A., Vandergheynst, P. (2013). The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3): 83-98. https://doi.org/10.1109/MSP.2012.2235192
[6] Chen, S., Varma, R., Sandryhaila, A., Kovačević, J. (2015). Discrete signal processing on graphs: Sampling theory. IEEE Transactions on Signal Processing, 63(24): 6510-6523. https://doi.org/10.1109/TSP.2015.2469645
[7] Marques, A.G., Segarra, S., Leus, G., Ribeiro, A. (2015). Sampling of graph signals with successive local aggregations. IEEE Transactions on Signal Processing, 64(7): 1832-1843. https://doi.org/10.1109/TSP.2015.2507546
[8] Spielman, D. (2012). Spectral graph theory. Combinatorial Scientific Computing, 18: 18.
[9] Püschel, M., Moura, J.M. (2008). Algebraic signal processing theory: 1-D space. IEEE Transactions on Signal Processing, 56(8): 3586-3599. https://doi.org/10.1109/TSP.2008.925259
[10] Ortega, A., Frossard, P., Kovačević, J., Moura, J.M., Vandergheynst, P. (2018). Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5): 808-828. https://doi.org/10.1109/JPROC.2018.2820126
[11] Hu, W., Pang, J., Liu, X., Tian, D., Lin, C.W., Vetro, A. (2021). Graph signal processing for geometric data and beyond: Theory and applications. IEEE Transactions on Multimedia, 24: 3961-3977. https://doi.org/10.1109/TMM.2021.3111440
[12] Li, R., Yuan, X., Radfar, M., Marendy, P., Ni, W., O’Brien, T.J., Casillas-Espinosa, P.M. (2021). Graph signal processing, graph neural network and graph learning on biological data: A systematic review. IEEE Reviews in Biomedical Engineering, 16: 109-135. https://doi.org/10.1109/RBME.2021.3122522
[13] Ortega, A. (2022). Introduction to Graph Signal Processing. Cambridge University Press.
[14] Sandryhaila, A., Moura, J.M. (2013). Discrete signal processing on graphs: Graph fourier transform. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, Vancouver, BC, Canada, pp. 6167-6170. https://doi.org/10.1109/ICASSP.2013.6638850
[15] Dong, X., Li, G., Jia, Y., Xu, K. (2021). Multiscale feature extraction from the perspective of graph for hob fault diagnosis using spectral graph wavelet transform combined with improved random forest. Measurement, 176: 109178. https://doi.org/10.1016/j.measurement.2021.109178
[16] Hammond, D.K., Vandergheynst, P., Gribonval, R. (2011). Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2): 129-150. https://doi.org/10.1016/j.acha.2010.04.005
[17] Hammond, D.K., Vandergheynst, P., Gribonval, R. (2018). The spectral graph wavelet transform: Fundamental theory and fast computation. In Vertex-Frequency Analysis of Graph Signals, pp. 141-175. https://doi.org/10.1007/978-3-030-03574-7_3
[18] Hu, W., Cheung, G., Ortega, A., Au, O.C. (2014). Multiresolution graph fourier transform for compression of piecewise smooth images. IEEE Transactions on Image Processing, 24(1): 419-433. https://doi.org/10.1109/TIP.2014.2378055
[19] Cui, Z., Ke, R., Pu, Z., Ma, X., Wang, Y. (2020). Learning traffic as a graph: A gated graph wavelet recurrent neural network for network-scale traffic prediction. Transportation Research Part C: Emerging Technologies, 115: 102620. https://doi.org/10.1016/j.trc.2020.102620
[20] Dong, X., Li, G., Jia, Y., Li, B., He, K. (2021). Non-iterative denoising algorithm for mechanical vibration signal using spectral graph wavelet transform and detrended fluctuation analysis. Mechanical Systems and Signal Processing, 149: 107202. https://doi.org/10.1016/j.ymssp.2020.107202
[21] Coifman, R.R., Lafon, S. (2006). Diffusion maps. Applied and Computational Harmonic Analysis, 21(1): 5-30.
[22] Gavish, M., Nadler, B., Coifman, R.R. (2010). Multiscale wavelets on trees, graphs and high dimensional data: theory and applications to semi supervised learning. In ICML, pp. 367-74.
[23] Wang, Y.Q., Li, B.Z., Cheng, Q.Y. (2017). The fractional Fourier transform on graphs. In 2017 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), Kuala Lumpur, Malaysia, pp. 105-110. https://doi.org/10.1109/APSIPA.2017.8282010
[24] Wang, Y., Li, B. (2018). The fractional Fourier transform on graphs: Sampling and recovery. In 2018 14th IEEE International Conference on Signal Processing (ICSP), Beijing, China, pp. 1103-1108. https://doi.org/10.1109/ICSP.2018.8652296
[25] Wu, J., Wu, F., Yang, Q., Zhang, Y., Liu, X., Kong, Y., Senhadji, L., Shu, H. (2020). Fractional spectral graph wavelets and their applications. Mathematical Problems in Engineering, 2020: 2568179. https://doi.org/10.1155/2020/2568179
[26] Jestrović, I., Coyle, J.L., Sejdić, E. (2017). A fast algorithm for vertex-frequency representations of signals on graphs. Signal Processing, 131: 483-491. https://doi.org/10.1016/j.sigpro.2016.09.008
[27] Shuman, D.I., Ricaud, B., Vandergheynst, P. (2016). Vertex-frequency analysis on graphs. Applied and Computational Harmonic Analysis, 40(2): 260-291. https://doi.org/10.1016/j.acha.2015.02.005
[28] Wei, D., Zhang, Y. (2021). Fractional Stockwell transform: Theory and applications. Digital Signal Processing, 115: 103090. https://doi.org/10.1016/j.dsp.2021.103090
[29] Perraudin, N., Paratte, J., Shuman, D., Martin, L., Kalofolias, V., Vandergheynst, P., Hammond, D.K. (2014). GSPBOX: A toolbox for signal processing on graphs. arXiv preprint arXiv:1408.5781. https://doi.org/10.48550/arXiv.1408.5781
