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?

  • $\begingroup$ 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. $\endgroup$
    – Jazzmaniac
    Aug 13, 2020 at 9:54

1 Answer 1


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.

  • $\begingroup$ $\hat{x}$ is the graph Fourier transform of $x$ not DFT! $\endgroup$
    – Amin
    Jul 20, 2019 at 3:55
  • 1
    $\begingroup$ @Amin Okay, I guess I have something else to study. $\endgroup$ Jul 20, 2019 at 4:05
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 20, 2019 at 4:16
  • $\begingroup$ It is ambiguous for me why we need complex conjugate there. $\endgroup$
    – Amin
    Jul 20, 2019 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.