3
$\begingroup$

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

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$). $\endgroup$
    – marcorossi
    Nov 20, 2013 at 0:10
  • $\begingroup$ @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. $\endgroup$
    – krishnab
    Feb 9, 2019 at 6:02
  • $\begingroup$ Sorry to nitpick here, but it's not entirely correct. The SVD of a symmetric real-valued matrix is only equal to the eigendecomposition if the matrix is positive semi-definite. This is the case for the Graph Laplacian. If the matrix is not positive semi-definite then the eigenvalues can be negative. In turn, singular values are always nonnegative. $\endgroup$
    – Sibylse
    Dec 12, 2020 at 17:14

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.