Laplacian Eigenmap

Definition

The Laplacian eigenmap is an embedding preserving local information optimally.

Algorithm

Consider a set of data points ${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n\in {\mathbb{R}}^l$. Make an Adjacency Matrix with Gaussian Radial Basis Function Kernel $\mathbf{A}=(a_{ij}):=\exp (-||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2/c)$ where $c>0$ is a scale parameter.

Construct a Laplacian Matrix using the Adjacency Matrix. The following options are available.

• Unnormalized Laplacian Matrix $L=D-A$
• Random Walk Normalized Laplacian Matrix ${\mathbf{L}}^{\text{rw}}={\mathbf{D}}^{-1}\mathbf{L}$
• Symmetrically Normalized Laplacian Matrix ${\mathbf{L}}^{\text{sym}}={\mathbf{D}}^{-1/2}\mathbf{L}{\mathbf{D}}^{-1/2}$

Construct the matrix $\mathbf{Z}=[{\mathbf{z}}_1,{\mathbf{z}}_2,\dots ,{\mathbf{z}}_m]$ whose columns are eigenvectors corresponding to the $m$-smallest eigenvalues of the Laplacian Matrix. It is the result of Laplacian eigenmap ${\mathbf{x}}_i\in {\mathbb{R}}^l\to [{\mathbf{z}}_2,{\mathbf{z}}_3,\dots ,{\mathbf{z}}_m{]}_i\in {\mathbb{R}}^m$ where $m\le l$, and ${\mathbf{z}}_1$ is intentionally omitted because it corresponds to the trivial solution (constant vector).