4
$\begingroup$

I learnt that I can look at the eigenspectrum of the kernel matrices computed by nonlinear spectral techniques in order to estimate the intrinsic dimensionality of a data-set. I use drtoolbox (The Matlab Toolbox for Dimensionality Reduction) to compute the laplacian eigenmaps of the data and the output is the low-dimensional representation of the data. How can I estimate the intrinsic dimensionality from this representation? Or, how can I know how "good" is my embedding?

How does the process reveal the intrinsic dimensionality of the manifold? (we assumed the data does lie there)

$\endgroup$

1 Answer 1

3
$\begingroup$

Since this method is based on eigen decomposition you can look at the eigenvalues and do some sort of eigen gap or spectral gap analysis to determine how many vectors contribute significantly to the laplacian matrix. This is an estimate of the intrinsic dimensionality but it depends on how the neighbor hood graph was constructed (ie choice of k in k nearest neighbors) which may be an issue.

You can also multiply the eigen vectors and values back together and see how closely the original laplacian matrix is preserved in terms of squared error or other metric. This is roughly equivalent to seeing how well the neighbor graph of the data is preserved and again depends on k.

Some care is required. Ie where D is the degree matrix and A is the adjacancy matrix if you are looking at L = D-A you need to look at the smallest non zero eigen values and corresponding vectors but if you are looking at L = D^(-1/2) A D^(-1/2) (the normalized laplacian) you need to look at the largest eigenvalues. (Note: the eigenvectors vectors should theoretically be the same and the values only transformed by 1-v but in practice this depends on quirks of the eigensolver.)

Additionally choice of eigen solver is important especially when you are interested in small eigenvalues and only a few vectors. Locally Optimal Block Preconditioned Conjugate Gradient Method (LOBPCG) generally works well since it lets you focus on a few of the smallest or largest eigenvectors while just calling the standard eigensolver in R or matlab doesn't.

I'm not familiar with the package you list but hopefully it gets all of this right ...if not it should be easy enough to implement you're own version of this method.

As a final note, often times in this sort of analysis is somewhat heuristic and the choice of dimension is driven by other factors (ie, the need to make a two dimensional plot or a preexisting estimate of dimensionality based on how the data was derived). Even hyper parameters like choice of k may be chosen simply because they give an pleasing two dimensional plot of the data.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.