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

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

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$.
• that is pretty interesting, i didn't know. my problem, however, is how to compute the first $k$ eigenvectors of $L$. in particular, the first $k$ eigenvectors (where by first we mean related to the $k$ smallest eigenvalues) of length $n$ (given $L$ being $n \times n$). Nov 20, 2013 at 0:10
• @marcorossi Sorry for the late reply. But as Paul suggests, the matrix $P$ gives all of the eigenvectors corresponding to the eigenvalues along the diagonal of $D$. So you can find the row of $D$ that corresponds to the second smallest eigenvalue, and then the corresponding column of $P$ that represents the eigenvector. Once you have the eigenvector, you can use k-means to identify the clusters in the nodes and that gives you the partition. Feb 9, 2019 at 6:02