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

To emphasize, the eigendecomposition of the graph operator will need complexity in general. In other words, we can reduce the complexity if we can assume graph signals on the underlying graph are bandlimited. Suppose that the signal is K-bandlimited, which is typically defined as

[1.50]

where ||·||₀ represents the number of non-zero elements, i.e. pseudo-norm. Here, without loss of generality, we can assume the first K GFT coefficients are non-zero:

[1.51]

With the GFT basis U, it is equivalently represented as

[1.52]

where × represents some possible non-zero elements and

[1.53]

A partial eigendecomposition proposed in literature gives the following approximation of L:

[1.54]

Evaluating only requires K (< N) eigenvectors and eigenvalues, which is significantly less than that obtained using the full eigendecomposition. In general, its computational complexity will be .