![](https://csdnimg.cn/release/download_crawler_static/10901364/bg5.jpg)
Laplacian Eigenmaps 1377
(b) Simple-minded (no parameters (t =∞)). W
ij
= 1 if vertices i
and j are connected by an edge and W
ij
= 0 if vertices i and
j are not connected by an edge. This simplification avoids the
need to choose t.
3. Step 3 (eigenmaps). Assume the graph G, constructed above, is con-
nected. Otherwise, proceed with step 3 for each connected component.
Compute eigenvalues and eigenvectors for the generalized eigenvec-
tor problem,
Lf = λDf, (2.1)
where D is diagonal weight matrix, and its entries are column (or
row, since W is symmetric) sums of W, D
ii
=
j
W
ji
. L = D − W is
the Laplacian matrix. Laplacian is a symmetric, positive semidefinite
matrix that can be thought of as an operator on functions defined on
vertices of G.
Let f
0
,...,f
k−1
be the solutions of equation 2.1, ordered according
to their eigenvalues:
Lf
0
= λ
0
Df
0
Lf
1
= λ
1
Df
1
···
Lf
k−1
= λ
k−1
Df
k−1
0 = λ
0
≤ λ
1
≤···≤λ
k−1
.
We leave out the eigenvector f
0
corresponding to eigenvalue 0 and use
the next m eigenvectors for embedding in m-dimensional Euclidean
space:
x
i
→ (f
1
(i),...,f
m
(i)).
3 Justification
3.1 Optimal Embeddings. Let us first show that the embedding pro-
vided by the Laplacian eigenmap algorithm preserves local information
optimally in a certain sense.
The following section is based on standard spectral graph theory. (See
Chung, 1997, for a comprehensive reference.)
Recall that given a data set, we construct a weighted graph G = (V, E)
with edges connecting nearby points to each other. For the purposes of
this discussion, assume the graph is connected. Consider the problem of
mapping the weighted graph G to a line so that connected points stay as close
together as possible. Let y = (y
1
, y
2
,...,y
n
)
T
be such a map. A reasonable