# Compute the $k$ largest eigenvector in spectral clustering

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

• 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. Oct 26, 2018 at 3:33
• @jason in the past I've used rARPACK (cran.r-project.org/web/packages/rARPACK/index.html) for this
– jld
Oct 26, 2018 at 3:36
• @jld cool, is it faster than eig() in matlab? the question may be weird since they are different programming language. Oct 26, 2018 at 3:37
• @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
– jld
Oct 26, 2018 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>
...