Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering

URL

Notes

Abstract

we propose a geometrically motivated algorithm for constructing a representation for data sampled from a low dimensional manifold embedded in a higher dimensional space ()

data points are in euclidean space (some higher dimensional space) and it might be from an underlying manifold (a lower dimensional space)

gray scale n x n images of a fixed object taken with a moving camera yield data points in rn: n2 . However , the intrinsic dimensionality of the space of all images of t he same object is the number of degrees of freedom of the camera - in fact the space has the natural structure of a manifold embedded in rn: n2 ()

assumption is that the object / scene is not changing. then the degrees of freedom of the camera is all that matters.

degrees of freedom of camera is the intrinsic dimension of the space of images (which then is the dimensions of the manifold).

The Laplacian of the graph obtained from the data points may be viewed as an approximation to the Laplace-Beltrami operator defined on the manifold ()

Laplace-Beltrami operator is for manifolds which does a similar operation as Laplacian does for graphs.

The locality preserving character of the Laplacian Eigenmap algorithm makes it relatively insensitive to outliers and noise. A byproduct of this is that the algorithm implicitly emphasizes the natural clusters in the data (2)

1 The Algorithm

Laplacian Eigenmap Algorithm.

k points Xl , ... , Xk in ]]{ I (2)

Step 1. [Constru cting th e Graph] We put an edge between nodes i and j if Xi and Xj are "close" (2)

two variations: (2)

(a) [-neighborhoods. [parameter [ E ]]{] Nodes i and j are connected by an edge if Ilxi - Xj 112 < f (2)

(b) n nearest neighbors. [parameter n E 1'::1] Nodes i and j are connected by an edge if i is among n nearest neighbors of j or j is among n nearest neighbors of i (2)

Step 2. [Choosing the weights] (2)

two variations for weighting the edges: (2)

(a) Heat kernel. [param eter t E ]]{]. If nodes i and j are connected (2)

(b) Simple-minded. [No parameters]. W ij = 1 if and only if vertices i an d j are connected by an edge. (2)

Step 3. [Eigenmaps] Assume the graph G, constructed above, is connected , otherwise proceed with Step 3 for each connected component (2)

Compute eigenvalues and eigenvectors for the generalized eigenvector (3)

D is diagonal weight matrix (3)

L = D - W is the Laplacian matrix (3)

Yo , ... , Y k -1 be the solutions of equation 1, ordered according to their eigenvalues with Yo having the smallest eigenvalue (in fact 0). The image of X i under the embedding into the lower dimensional space :Il{m is given by (y1 ( i) , . . . , ym (i)). (3)

2 Justification

Consider the problem of mapping the weighted connected graph G to a line so that connected points stay as close together as possible (3)

line is a vector in R of dimension 1

2.1 The Laplace-Beltrami Operator