Graph Spectral Image Processing. Gene Cheung

equation [1.13]) is usually not localized in the vertex domain, because eigenvectors often have global support on the graph. Therefore, localizing graph filter response, both in the vertex and graph frequency domains, has been studied extensively (Shuman et al. 2013; Shuman et al. 2016b; Sakiyama et al. 2016). In fact, the localization of graph spectral filters can be controlled using polynomial filtering.

      Polynomial graph filters are defined as follows:

[1.55]

      where c_k is the kth order coefficient of the polynomial. It is known that each row of L^k collects its k-hop neighborhood; therefore, equation [1.55] is exactly the K-hop localized in the vertex domain. Note that L^k can be represented as

[1.56]

      Here, we utilized the orthogonality of U. We can rewrite equation [1.55] by using equation [1.56] as:

      [1.57]

      Consequently, the polynomial graph filter has the following graph frequency response:

      [1.58]

      Especially, the output signal in the vertex domain is given by

[1.59]

This indicates that we do not need to compute specific eigenvalues and eigenvectors for just calculating y. Specifically, we need to evaluate Lx, L²x,..., L^Kx. Calculating Lz, where z is an arbitrary vector, requires complexity. Additionally, is required for computing c_kL^kx (and it is repeated K times). As a result, the entire complexity will be . It is usually much lower than the partial eigendecomposition. In general, therefore, the number of edges is a dominant factor affecting the complexity.

      Suppose that a fast computation is required for the spectral response of a graph filter , which is not a polynomial. Based on equation [1.59], we can approximate the output y if is satisfactorily approximated by a polynomial.

      Any polynomial approximation methods, e.g. Taylor expansion, are possible for the above-mentioned polynomial filtering. In GSP, Chebyshev polynomial approximation is implemented frequently. The Chebyshev expansion gives an approximate minimax polynomial, i.e. the maximum approximation error can be reduced.

      The approximated version of h(L)x by the Kth order shifted Chebyshev polynomial, h_Cheb(L)x, is given by Shuman et al. (2013); Hammond et al. (2011)

[1.60]

      and it has the recurrence property:

      [1.61]

      with . The kth Chebyshev coefficient c_k is defined as

      [1.62]

      for k = 0,...,K, where P is the number of sampling points used to compute the Chebyshev coefficients and is usually set to P = K + 1. The approximated filter in equation [1.60] is clearly a Kth order polynomial of λ. As a result, it is K-hop localized in the vertex domain, as previously mentioned (Shuman et al. 2011; Hammond et al. 2011).

      The approximation error for the Chebyshev polynomial has been well studied in the context of numerical computation (Vetterli et al. 2014; Phillips 2003):

      THEOREM 1.1.– Let K be the polynomial degree of the Chebyshev polynomial and assume that has (K + 1) continuous derivatives on [−1, 1]. In this case, the upper bound of the error is given as follows:

      [1.63]

      1.6.6. Krylov subspace method

      The Krylov subspace of an arbitrary square matrix and a vector x is defined as follows:

      [1.64]

      The Krylov subspace method, in terms of GSP, refers to filtering, i.e. evaluating an arbitrary filtered response h(W)x, realized in a Krylov subspace . Many methods to evaluate h(W)x in a Krylov subspace have been proposed, mainly in computational linear algebra and numerical computation (Golub and Van Loan 1996). A famous approximation method is the Arnoldi approximation, which is given by

      [1.65]

      where h(H_K) is evaluating h(·) for the upper Heisenberg matrix H_K, which is obtained by using the Arnoldi process. Furthermore, H_K is expected to be much smaller than the original matrix; therefore, evaluating h(H_K) using full eigendecomposition will be feasible and light-weighted.

1.7. Conclusion

      This chapter introduces the filtering of graph signals performed in the graph frequency domain. This is a key ingredient of graph spectral image processing presented in the following chapters. The design methods of efficient and fast graph filters and filter banks, along with fast GFT (such attempts can be found in Girault et al. (2018); Lu and Ortega (2019)), are still a vibrant area of GSP: the chosen graph filters directly affect the quality of processed images. This chapter only provided a brief overview of graph spectral filtering. Please refer to the references for more details.