Читать книгу Graph Spectral Image Processing - Gene Cheung - Страница 13

Denote by W ∈ R^N×N an adjacency matrix, where the (i, j)th entry is W_i,j = w_i,j. Next, denote by D ∈ R^N×N a diagonal degree matrix, where the (i, i)th entry is D_i,i = j W_i,j. A combinatorial graph Laplacian matrix L is L = D − W (Shuman et al. 2013). Because L is real and symmetric, one can show, via the spectral theorem, that it can be eigen-decomposed into:

[I.2]

where Λ is a diagonal matrix containing real eigenvalues λ_k along the diagonal, and U is an eigen-matrix composed of orthogonal eigenvectors u_i as columns. If all edge weights w_i,j are restricted to be positive, then graph Laplacian L can be proven to be positive semi-definite (PSD) (Chung 1997)², meaning that λ_k ≥ 0, ∀k and xLx ≥ 0, ∀x. Non-negative eigenvalues λ_k can be interpreted as graph frequencies, and eigenvectors U can be interpreted as corresponding graph Fourier modes. Together they define the graph spectrum for graph G.

The set of eigenvectors U for L collectively form the GFT (Shuman et al. 2013), which can be used to decompose a graph signal x into its frequency components via α = Ux. In fact, one can interpret GFT as a generalization of known discrete transforms like the Discrete Cosine Transform (DCT) (see Shuman et al. 2013 for details).

Note that if the multiplicity m_k of an eigenvalue λ_k is larger than 1, then the set of eigenvectors that span the corresponding eigen-subspace of dimension m_k is non-unique. In this case, it is necessary to specify the graph spectrum as the collection of eigenvectors U themselves.

If we also consider negative edge weights w_i,j that reflect inter-pixel dissimilarity/anti-correlation, then graph Laplacian L can be indefinite. We will discuss a few recent works (Su et al. 2017; Cheung et al. 2018) that employ negative edges in later chapters.