# How does Chebyshev approximation of spectral convolution work?

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$$

• I can't understand the equation you pasted from the given paper. Can you please phase this question in your own words and use latex to write equations? Sep 10, 2021 at 8:02
• Hi @SwaksharDeb - the equations were written in Latex. Have fixed the few areas where the '>' character made it into the equations (meant for the block quote). The question can be summarized as: how did the Chebyshev function of $\tilde{\Lambda}$ into a function of L Sep 10, 2021 at 20:11