Graph Fourier Transform

In mathematics, graph Fourier transform is a mathematical transform which eigendecomposes the Laplacian matrix of a graph into eigenvalues and eigenvectors. Analogously to classical Fourier Transform, the eigenvalues represent frequencies and eigenvectors form what is known as a graph Fourier basis.

Graph Fourier Transform (GFT) is defined as:
$\mathcal{GF}[f](\lambda_l) = \hat{f} (\lambda_l) = <\pmb{f}, \pmb{u}_l> = \sum_{i = 1}^{N} f(i) u_l^T(i).$
where

$G = (V, E)$ : undirected weighted graph
$V$ : the set of nodes with $|V| = N$
$E$ : the set of edges
$f: V \rightarrow \mathbb{R}$ : a graph signal that is a function defined on the vertices of the graph $G$ , which maps every vertex $\{v_i\}_{i = 1, \cdots, N}$ to a real number $f(i)$ . Any graph signal can be projected on the eigenvectors $(0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_{N})$ of the Laplacian matrix ${\bf L}$
$\lambda_l$ : the $l$ th eigenvalue of the Laplacian matrix ${\bf L}$
$\pmb{u}_l$ : the $l$ th eigenvector of the Laplacian matrix ${\bf L}$

It can also be represented as
$\begin{aligned}\begin{bmatrix}\hat{f}(\lambda_1)\\\hat{f}((\lambda_2)\\\vdots\\\hat{f}((\lambda_N)\end{bmatrix}=\begin{bmatrix}u_1(1) & u_2(1) & \cdots & u_{N}(1)\\u_1(2) & u_2(2) & \cdots & u_{N}(2)\\\vdots & \vdots & \ddots & \vdots\\u_1(N) & u_2(N) & \cdots & u_{N}(N)\\\end{bmatrix}^T\begin{bmatrix}f(1)\\f(2)\\\vdots\\f(N)\end{bmatrix}\end{aligned},$
which is equal to
$\pmb{\hat{f}} = {\bf U}^T \pmb{f} .$
Since Laplacian matrix ${\bf L}$ is a real symmetric matrix, its eigenvectors $\pmb{u}_1, \pmb{u}_2, \cdots, \pmb{u}_{N}$ form an orthogonal basis. Hence an inverse graph Fourier transform (IGFT) exists, and it is written as

$\mathcal{IGF}[\hat{f}](i)= f (i) = <\pmb{\hat{f}}, \pmb{u}_l> =\sum_{i = 1}^{n} \hat{f}(\lambda_l) u_l(i).$

It can be also represented as

$\begin{aligned}\begin{bmatrix}f(1)\\f(2)\\ \vdots\\ f(N) \end{bmatrix}= \begin{bmatrix} u_1(1) & u_2(1) & \cdots & u_{N}(1)\\ u_1(2) & u_2(2) & \cdots & u_{N}(2)\\ \vdots & \vdots & \ddots & \vdots\\ u_1(N) & u_2(N) & \cdots & u_{N}(N)\\ \end{bmatrix} \begin{bmatrix} \hat{f}(\lambda_1)\\ \hat{f}((\lambda_2)\\ \vdots\\ \hat{f}((\lambda_N) \end{bmatrix} \end{aligned},$

which is equal to
$\pmb{f} = {\bf U} \pmb{\hat{f}}.$

Orthogonal basis for the Fourier transform

The eigenvectors of Laplacian matrix are a set of linearly independent orthogonal bases, thus any graph signal can be expressed as a linear combination of the eigenvectors of Laplacian matrix
$\pmb{f} = \pmb{\hat{f}}_1 \pmb{u}_1+\pmb{\hat{f}}_2) \pmb{u}_2+\cdots+\pmb{\hat{f}}_N \pmb{u}_N.$

Convolution Operation on Graph

Generalized convolution in the vertex domain is multiplication in the graph spectral domain:
$\pmb{f} * \pmb{h} = \text{IGFT} (\pmb{\hat{f}} \pmb{\hat{h}})$
which can be also expressed as
$\pmb{f} * \pmb{h}(i) = \sum_{l = 1}^{N} \hat{f}(\lambda_l)\hat{h}(\lambda_l) u_l(i).$

$\pmb{h}$ : convolution kernel

Steps of Convolution Operation on Graph:

$\pmb{\hat{f}} = {\bf U}^T \pmb{f}$
$\pmb{\hat{h}} = {\bf U}^T \pmb{h}$
$\pmb{\hat{h}} \pmb{\hat{f}} = {\bf U}^T \pmb{h} \odot {\bf U}^T \pmb{f} = \pmb{\hat{f}} \pmb{\hat{h}}$ , i,e,

$\begin{aligned}\pmb{f} * \pmb{h} &= {\bf U} \pmb{\hat{f}} \pmb{\hat{h}}\\&={\bf U}\begin{bmatrix}\hat{h}(\lambda_1) & & \\ & \ddots & \\ & & \hat{h}(\lambda_N)\end{bmatrix}{\bf U}^T\pmb{f}\end{aligned}$

【图论】Graph Fourier Transform

Graph Fourier Transform

Orthogonal basis for the Fourier transform

Convolution Operation on Graph

相关推荐