I was reading the following paper: here. In it, it talks about spectral graph convolutions and says:
We consider spectral convolutions on graphs defined as the multiplication of a signal $x \in R^N$ (a scalar for every node) with a filter $g_{\theta}$ $=$ $\text{diag} (\theta)$ parameterized by $\theta \in R^{N}$ in the Fourier domain, i.e.: $ g_{\theta} * x = U g_{\theta} U^Tx $. We can understand $ g_{\theta}$ as a function of the eigenvalues of $L$, i.e. $g_{\theta}(\Lambda)$
So far, it makes sense. $U^T x$ is the graph Fourier transform of the signal $x$, then we multiply by $ g_{\theta}$ in the Fourier domain as: $FT(f * g) = F(\omega)G(\omega)$. Then we have the multiplication by $U$ in the front to represent the inverse (graph) Fourier transform.
Then the paper lists some reasons why using the above convolution equation may not be practical in reality:
- Evaluating the above equation is computationally expensive; multiplying with eigenvector matrix $U$ is $O(N^2)$
- Computing eigendecomposition of $L$ may be too expensive for an arbitrarily large graph
- etc.
and then the paper says:
To circumvent this problem, it was suggested in Hammond et al. (2011) that $g_{\theta}(\Lambda)$ can be well-approximated by a truncated expansion in terms of Chebyshev polynomials $T_k (x)$ up to $K^{\text{th}}$ order: $$ g_{\theta '}(\Lambda) \approx \sum_{k = > 0}^{K} \theta_k ' T_k(\tilde{\Lambda}) $$
with a rescaled $\tilde{\Lambda} = \frac{2}{\lambda_{\text{max}}}\Lambda − I_N$. $\lambda_{\text{max}}$ denotes the largest eigenvalue of $L$. $\theta ′ \in R^K$ is now a vector of Chebyshev coefficients. The Chebyshev polynomials are recursively defined as $T_k(x) = 2xT_{k−1}(x) − T_{k−2}(x)$, with $T_0(x) = 1$ and $T_1(x) = x$. The reader is referred to Hammond et al. (2011) for an in-depth discussion of this approximation. Going back to our definition of a convolution of a signal $x$ with a filter $g_{\theta '}$, we now have: $$ g_{\theta '} * x \approx \sum_{k=0}^{K} \theta_k ′ T_k (\tilde{L}) x$$ with $\tilde{L} = \frac{2}{\lambda_{\text{max}}}L − I_N$ ; as can easily be verified by noticing that $(U \Lambda U^T)^k = U \Lambda^k U^T $
Question: What happened to the terms $U^T$ and $U$ which take the (graph) Fourier transform and invert it respectively?
Attempt: Does it have something to do with what is mentioned in the last line about noticing that $(U \Lambda U^T)^k = U \Lambda^k U^T $? I might guess that we use that because a k-th order Chebyshev polynomial will have $\Lambda ^k$ (and lower powers) present in the equation and thus the $U^T$ and $U$ mean that we can write the convolution equation in terms of the Laplacian matrix $L$
