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$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$.
-
$\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$ 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$– krishnabFeb 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$– SibylseDec 12, 2020 at 17:14