how do I compute the eigenvectors for spectral clustering from a singular value decomposition?

Question

I am implementing spectral clustering following A tutorial on spectral clustering. After preparing the Laplacian matrix $L^{n \times n}$, I compute the Singular Value Decomposition $U \Sigma V^{*}$. From $\Sigma$ I extract the eigenvalues, and I choose $k$ (which according to the paper are the $k$ smallest ones) with the eigengap heuristic. Now, the algorithm (page 7) requires to compute the first $k$ eigenvectors $u_{1}, ..., u_{k}$ of the generalized eigenproblem $L u = \lambda D u$, which basically means the first eigenvectors of $L$. From this, I need to build the matrix $N \in R^{n \times k}$ containing the vectors $u_{1},...,u_{k}$ as columns. My question is, given the computed SVD, how do I build $N$, hence the first k eigenvectors of $L$?

Answer 1

The singular value decomposition of a symmetric matrix with real entries (such as the Laplacian of a graph) is just its eigendecomposition: $$L = P D P^t$$ where $D$ is a diagonal matrix with the eigenvalues of $L$ along the diagonal and $P$ is the matrix whose columns are the corresponding eigenvectors of $L$.