Dimensionality Reduction using Eigendecomposition

Dimensionality Reduction: Why we take Eigenvectors of the Similarity Matrix? . Michael Lin.

We have a similarity matrix $W$ (by definition of similarity metrics, it is symmetric positive definite).

Then we compute an eigenvector decomposition of $W$ to get $V D V^T$.

Here, $V$ and $D$ are $N \times N$ (thus so is $V^T$) for $N$ datapoints.

Because $W$ is symmetric positive definite, the columns of $V$ will be mutually orthogonal eigenvectors of $W$ (sorted from lowest eigenvalue to highest, left to right). The eigenvalues form the diagonal of the matrix $D$ (and zeros everywhere else), with the lowest eigenvector at $0,0$ and increasing down the diagonal.

We can truncate $V$ down to some arbitrary number of columns (e.g. the last two); this gives us the datapoint embeddings for the reduced space (e.g. if we take the last two columns, we are given the datapoint embeddings for a 2D space)