3
$\begingroup$

I have a question about the definition of the graph Fourier transform. Let me start with definition.

Let $A$ be the adjacency matrix of a graph $G$ with vertex set $V = \{1, 2, \dots, n\}$. The Laplacian matrix of $G$ is defined as $L = D - A$, where $D$ is a diagonal degree matrix with $d_{ii} = deg(i)$. Let $\varphi_1, \dots, \varphi_n$ be an orthonormal eigenbasis of $L$ and $\lambda_1, \dots, \lambda_n$ be the corresponding eigenvalues. Let $f$ be a $V \rightarrow \mathbb{R}$ function. The graph Fourier transform is defined as \begin{equation} \hat{f}(\lambda_i) = \langle f, \varphi_i \rangle = \sum\limits_{k = 1}^n f(k) \varphi_i^*(k) \end{equation}

My question is: what happens if $\lambda_i = \lambda_{i + 1}$? It seems to me that this definition could give two different values for $\hat{f}(\lambda_i)$. Is it guaranteed that $\sum\limits_{k = 1}^n f(k) \varphi_i^*(k) = \sum\limits_{k = 1}^n f(k) \varphi_{i+1}^*(k)$?

EDIT: I have no problem with choosing an orthonormal eigenbasis even if there are eigenvalues with multiplicity bigger than $1$. My problem arises only after the eigenvectors are chosen. Suppose that $\lambda_i = \lambda_{i + 1} = 3$. Then I have two different formulas for $\hat{f}(3)$:

\begin{equation} \hat{f}(3) = \sum\limits_{k = 1}^n f(k) \varphi_i^*(k) \end{equation} and \begin{equation} \hat{f}(3) = \sum\limits_{k = 1}^n f(k) \varphi_{i+1}^*(k) \end{equation}

I think there are two possibilities:

  1. The two quantities above are the same: $\sum\limits_{k = 1}^n f(k) \varphi_i^*(k) = \sum\limits_{k = 1}^n f(k) \varphi_{i+1}^*(k)$. I can't see why this would be true.

  2. I misunderstand something about the definition.

$\endgroup$
  • $\begingroup$ when there are degenerate eigenvalues the eigenvectors are not uniquely defined; for $d$ identical eigenvalues you have a $d$-dimensional eigenspace and you are free to choose any $d$ independent vectors in that space as your basis. $\endgroup$ – Carlo Beenakker Jun 4 '19 at 10:44
  • $\begingroup$ I have no problem with choosing an orthonormal eigenbasis even if there are eigenvalues with multiplicity bigger than $1$. My problem arises only after the eigenvectors are chosen. If $\lambda_i = \lambda_{i + 1} = 3$, then I have two different formulas for $\hat{f}(3)$. I've edited the question, hope it makes my problem clearer. $\endgroup$ – Hanna Gábor Jun 4 '19 at 11:34
1
$\begingroup$

I saw the definition I mentioned in the question in many places. (E.g. here.) In Graph Structured Data Viewed Through a Fourier Lens the definition is different: \begin{equation} \hat{f}(i) = <f, \varphi_i> = \sum\limits_{k = 1}^n f(k) \varphi_i^*(k) \end{equation} This answers my question. :)

$\endgroup$

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.