# 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?

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 at 3:55
• @Amin Okay, I guess I have something else to study. – Cedron Dawg Jul 20 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 at 4:16
• It is ambiguous for me why we need complex conjugate there. – Amin Jul 20 at 4:31