In Spectral Clustering, we need to compute the top $k$ largest eigenvector of normalized $L$.

$$L = D^{-\frac{1}{2}}SD^{-\frac{1}{2}}$$

In Andrew NG's paper, L is not positive definite (unless using $I-L$), which means the eigenvalue can be negative.

we need to compute the top $k$ largest eigenvector of $L$

my question is that we want the eigenvector of $k$ largest eigenvalues by magnitude (e.g. absolute of eigenvalue) or just by value?


Suppose $(\lambda, x)$ is an eigenpair of $L$. Then $$ Lx = \lambda x \\ \implies -Lx = -\lambda x\\ \implies x - Lx = x - \lambda x \\ \implies (I-L)x = (1-\lambda)x $$ so $(1-\lambda, x)$ is an eigenpair of $I- L$. If you accept that we want eigenvectors of the smallest eigenvalues when using $I-L$ then this means we'll want the top eigenvectors of $L$ (in actual value, not in absolute value).

  • $\begingroup$ I see. Is there any fast way to compute those $k$ eigenvector? We can perform eigen-decomposition of $L$, but it is expensive. All we need is just those $K$ eigenvector, if exist fast algorithm. Thanks. $\endgroup$ – jason Oct 26 '18 at 3:33
  • $\begingroup$ @jason in the past I've used rARPACK (cran.r-project.org/web/packages/rARPACK/index.html) for this $\endgroup$ – jld Oct 26 '18 at 3:36
  • $\begingroup$ @jld cool, is it faster than eig() in matlab? the question may be weird since they are different programming language. $\endgroup$ – jason Oct 26 '18 at 3:37
  • $\begingroup$ @jason sorry I've never used matlab so I couldn't say for sure. My guess is that in every case these functions are all wrapping around the same core libraries like LAPACK and ARPACK, and R and matlab (I think) are both interpreted languages, so you'd probably see similar performance so long as you use an algorithm that appropriate for your matrix (e.g. if it's sparse take advantage of that) but again that's just a guess $\endgroup$ – jld Oct 26 '18 at 3:43

You can use C++/Eigen to get $k$ eigenvectors corresponding to the largest signed eigenvalues of $L$ (which is what you want) as follows:

#include <Eigen/Dense>
Eigen::SelfAdjointEigenSolver<Eigen::MatrixXf> solver(n);
Eigen::MatrixXf X = solver.eigenvectors().rowwise().reverse().block(0,0,n,k);

Note that I reverse the eigenvectors since they are given to us in ascending order.


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.