# Graph Fourier transform: the adjoint notation for the eigenbasis matrix

I already asked this question here but there is no response. I'd like to ask this question in signal processing domain.

It is well-known that for a real symmetric matrix $$L$$ (here, graph Laplacian) one can write the eigenvalue decomposition as

$$L = U \Lambda U^{\mathsf T},$$ where $$U$$ is a real eigenvector matrix. Moreover, in graph signal processing papers, including the great paper by Shuman et al. (cf. page 4), the adjoint (complex conjugate) of $$U$$ is used to define the graph Fourier transform $$\mathcal{F}_{G}$$ as $$\hat{x} = \mathcal{F}_{G} x = U^{*}x,$$ where $$x$$ is the signal in vector form and $$U^{*}$$ is the complex conjugate of $$U$$.

I am curious to know is there any specific reason for using the notation of complex conjugate since $$U$$ is real?

• Unless you demand that $L$ is non-degenerate, $U$ is not necessarily real. There is a choice for a basis that makes $U$ real, but that's not the only choice in this case. Also, using a slightly more general statement that also holds in other cases is never a bad idea. It's always a good idea to use the complex conjugate transpose instead of the transpose, because it is the correct generalization for complex numbers and many real valued problems require complex solutions because only the complex numbers have algebraic closure. – Jazzmaniac Aug 13 '20 at 9:54

You terminology is something I am not used to.

$$\hat{x} = \mathcal{F}_{G} x$$

If by $$\hat{x}$$ you mean the DFT (complex except very special cases), $$x$$ is your input (real or complex), and $$\mathcal{F}_{G}$$ is the matrix composed of the sinusoidal basis vectors, then your assertion that $$U$$ is real is dubious. $$\mathcal{F}_{G}$$ is most certainly not. With the proper normalizattion:

$$\mathcal{F}_{G}^{-1} = \mathcal{F}_{G}^{*}$$

Now, for a known $$x$$ where $$\hat{x}$$ is known to be complex, how can $$U$$ be real?

Since they are using the complex conjugate, I would say that U is expected to also be capable of being complex. I have not read the paper so I don't know where you picked up that assumption.

• $\hat{x}$ is the graph Fourier transform of $x$ not DFT! – Amin Jul 20 '19 at 3:55
• @Amin Okay, I guess I have something else to study. – Cedron Dawg Jul 20 '19 at 4:05
• @Amin It seems you are not alone in asking that. Check out the comments: johndcook.com/blog/2016/02/09/… Maybe you should pose your question there, but the other guy didn't get an answer. The only papers I could find were behind the IEEE paywall and, sorry, I won't support them. – Cedron Dawg Jul 20 '19 at 4:16
• It is ambiguous for me why we need complex conjugate there. – Amin Jul 20 '19 at 4:31