In mathematics, the graph Fourier transform is a mathematical transform which eigendecomposes the Laplacian matrix of a graph into eigenvalues and eigenvectors. Analogously to the classical Fourier transform, the eigenvalues represent frequencies and eigenvectors form what is known as a graph Fourier basis. The Graph Fourier transform is important in spectral graph theory. It is widely applied in the recent study of graph structured learning algorithms, such as the widely employed convolutional networks.
Definition Given an undirected weighted graph G = ( V , E ) {\displaystyle G=(V,E)} , where V {\displaystyle V} is the set of nodes with | V | = N {\displaystyle |V|=N} ( N {\displaystyle N} being the number of nodes) and E {\displaystyle E} is the set of edges, a graph signal f : V → R {\displaystyle f:V\rightarrow \mathbb {R} } is a function defined on the vertices of the graph G {\displaystyle G} . The signal f {\displaystyle f} maps every vertex { v i } i = 1 , … , N {\displaystyle \{v_{i}\}_{i=1,\ldots ,N}} to a real number f ( i ) {\displaystyle f(i)} . Any graph signal can be projected on the eigenvectors of the Laplacian matrix L {\displaystyle L} . Let λ l {\displaystyle \lambda _{l}} and μ l {\displaystyle \mu _{l}} be the l th {\displaystyle l_{\text{th}}} eigenvalue and eigenvector of the Laplacian matrix L {\displaystyle L} (the eigenvalues are sorted in an increasing order, i.e., 0 = λ 0 ≤ λ 1 ≤ ⋯ ≤ λ N − 1 {\displaystyle 0=\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{N-1}} ), the graph Fourier transform (GFT) f ^ {\displaystyle {\hat {f}}} of a graph signal f {\displaystyle f} on the vertices of G {\displaystyle G} is the expansion of f {\displaystyle f} in terms of the eigenfunctions of L {\displaystyle L} . It is defined as:
G F [ f ] ( λ l ) = f ^ ( λ l ) = ⟨ f , μ l ⟩ = ∑ i = 1 N f ( i ) μ l ∗ ( i ) , {\displaystyle {\mathcal {GF}}[f](\lambda _{l})={\hat {f}}\left(\lambda _{l}\right)=\langle f,\mu _{l}\rangle =\sum _{i=1}^{N}f(i)\mu _{l}^{*}(i),}
where μ l ∗ = μ l T {\displaystyle \mu _{l}^{*}=\mu _{l}^{\text{T}}} . Since L {\displaystyle L} is a real symmetric matrix, its eigenvectors { μ l } l = 0 , ⋯ , N − 1 {\displaystyle \{\mu _{l}\}_{l=0,\cdots ,N-1}} form an orthogonal basis. Hence an inverse graph Fourier transform (IGFT) exists, and it is written as:
I G F [ f ^ ] ( i ) = f ( i ) = ∑ l = 0 N − 1 f ^ ( λ l ) μ l ( i ) {\displaystyle {\mathcal {I}}{\mathcal {G}}{\mathcal {F}}[{\hat {f}}](i)=f(i)=\sum _{l=0}^{N-1}{\hat {f}}(\lambda _{l})\mu _{l}(i)}
… excerpt ends here. Continue reading the full article.
