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

The previous subsection proposes that we can alleviate the heavy computational burden by assuming the bandlimitedness of the graph signal. However, this requires the assumption on the signal model prior to filtering, but the signal is not bandlimited in general.

In many application scenarios, we often only need the evaluation of x with a given (linear) matrix function h(L). That is, the eigenvalues and eigenvectors themselves are often unnecessary. The polynomial approximation methods introduced here enable us to calculate an approximation of y = h(L)x without the (partial) decomposition of the variation operator.

Another advantage of filtering using a polynomial filter function is the vertex localization. The local filtering could capture local variations of pixel values, which are generally preferable. In contrast, filtering in the graph frequency domain (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]