Artificial Intelligence and Quantum Computing for Advanced Wireless Networks. Savo G. Glisic

Скачать книгу

to a random walk. In the following, we summarize several properties of L_sym and L_rw.

      Proposition 5.2

      (Properties of L_sym and L_rw ) The normalized Laplacians satisfy the following properties:

      1 For every f ∈ ℝn we have

      2 λ is an eigenvalue of Lrw with eigenvector u if and only if λ is an eigenvalue of Lsym with eigenvector w = D1/2 u.

      3 λ is an eigenvalue of Lrw with eigenvector u if and only if λ and u solve the generalized eigen problem Lu = λDu.

      4 0 is an eigenvalue of Lrw with the constant one vector I as eigenvector. 0 is an eigenvalue of Lsym with eigenvector D1/2I.

      5 Lsym and Lrw are positive semidefinite and have n non‐negative real‐valued eigenvalues 0 = λ1≤,….≤λn.

Proof. Part (1) can be proved similarly to Part (1) of Proposition 5.1.

      Part (2) can be seen immediately by multiplying the eigenvalue equation L_sym w = λw with D^−1/2 from the left and substituting u = D^−1/2 w.

      Part (3) follows directly by multiplying the eigenvalue equation L_rw u = λu with D from the left.

      Part (4): The first statement is obvious as L_rwI = 0, the second statement follows from (2).

      Part (5): The statement about L_sym follows from (1), and then the statement about L_rw follows from (2).

      Part (5): The statement about L_sym follows from (1), and then the statement about L_rw follows from (2).

Appendix 5.B Graph Fourier Transform

      Graph signals: A graph signal is a collection of values defined on a complex and irregular structure modeled as a graph. In this appendix, a graph is represented as , where is the set of vertices (or nodes) and W is the weight matrix of the graph in which an element w_ij represents the weight of the directed edge from node j to node i. A graph signal is represented as an

      N‐dimensional vector f = [f(1), f(2), …, f(N)]^T ∈ ℂ^N, where f(i) is the value of the graph signal at node i and is the total number of nodes in the graph.

      Directed Laplacian: As discussed in Appendix 5.A, the graph Laplacian for undirected graphs is a symmetric difference operator L=D − W, where D is the degree matrix of the graph, and W is the weight matrix of the graph. In the case of directed graphs (or digraphs), the weight matrix W of a graph is not symmetric. In addition, the degree of a vertex can be defined in two ways: in‐degree and out‐degree. The in‐degree of a node i is estimated as , whereas the out‐degree of the node i can be calculated as . We consider an in‐degree matrix and define the directed Laplacian L of a graph as

      (5.B.1)

where D_in= diag is the in‐degree matrix. Figure 5.B.1 shows an example of weighted directed graph, with the corresponding matrices [68]. The Laplacian for a directed graph is not symmetric; nevertheless, it follows some important properties: (i) the sum of each row is zero, and hence λ = 0 is certainly an eigenvalue, and (ii) real parts of the eigenvalues are non‐negative for a graph with positive edge weights.

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,

Скачать книгу