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.



Graph Fourier transform definition
I saw the definition I mentioned in the question in many places. (E.g. [here](http://www.norbertwiener.umd.edu/Research/lectures/2014/MBegue_Prelim.pdf).) In [Graph Structured Data Viewed Through a Fourier Lens](http://digitalassets.lib.berkeley.edu/techreports/ucb/text/EECS-2013-209.pdf) 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. :)


