LITMIR.BIZ

Figure 5.B.1 A directed graph and the corresponding matrices.

      Graph Fourier transform based on directed Laplacian: Using Jordan decomposition, the graph Laplacian is decomposed as

(5.B.2)

      where J, known as the Jordan matrix, is a block diagonal matrix similar to L, and the Jordan eigenvectors of L constitute the columns of V. We define the graph Fourier transform (GFT) of a graph signal f as

      (5.B.3)

      Here, V is treated as the graph Fourier matrix whose columns constitute the graph Fourier basis. The inverse graph Fourier transform can be calculated as

      (5.B.4)

      In this definition of GFT, the eigenvalues of the graph Laplacian act as the graph frequencies, and the corresponding Jordan eigenvectors act as the graph harmonics. The eigenvalues with a small absolute value correspond to low frequencies and vice versa. Before discussing the ordering of frequencies, we consider a special case when the Laplacian matrix is diagonalizable.

Diagonalizable Laplacian matrix: When the graph Laplacian is diagonalizable, Eq. (5.B.2) is reduced to

      (5.B.5)

      Here, Λ ∈ ℂ^{N × N} is a diagonal matrix containing the eigenvalues λ₀, λ₁ , …, λ_{N − 1} of L, and V = [v₀, v₁, …, v_{N − 1}] ∈ ℂ^{N × N} is the matrix with columns as the corresponding eigenvectors of L. Note that for a graph with real non‐negative edge weights, the graph spectrum will lie in the right half of the complex frequency plane (including the imaginary axis).

      Undirected graphs: For an undirected graph with real weights, the graph Laplacian matrix L is real and symmetric. As a result, the eigenvalues of L turn out to be real, and L constitutes orthonormal set of eigenvectors. Hence, the Jordan form of the Laplacian matrix for undirected graphs can be written as

      (5.B.6)

where V^T = V⁻¹, because the eigenvectors of L are orthogonal in th undirected case. Consequently, the GFT of a signal f can be given as , and the inverse can be calculated as f=V. One can show that for the example from Figure 5.B.1 for the signal f = [0.12 0.38 0.81 0.24 0.88] we have the GFT as