[Paper Summary Lec_08-09] - 2 A Global Geometric Framework for Nonlinear Dimensionality Reduction

"A Global Geometric Framework for Nonlinear Dimensionality Reduction," 

Joshua B. Tenenbaum, Vin de Silva, John C. Langford, 2000. 



This work aims to solve the dimension reduction task as the previous one,
([Paper Summary Lec_08-09] -1 Nonlinear dimensionality reduction by locally linear embedding)
the goal is to uncover the underlying nonlinear structure of data and remain there characteristic while performing dimension reduction process. It aims to solve those tasks traditional PCA and MDS methods can not solved well.

Their approach builds on classical MDS ( http://en.wikipedia.org/wiki/Multidimensional_scaling ) but seeks to preserve the intrinsic geometry of the data, as captured in the geodesic manifold instances between all pairs of data points.


The toy example of this work is also the "swiss roll" as the previous one, as shown in the following figure

A is the original data distribution, and the goal is to measure the distance as the blue line shows.

B is the neighborhood structure between near data points.

C is the unrolling structure this work aims to find.

They formulate the problem as three step:


The first step determines which points are neighbors on the manifold M, based on the distances d_X(i,j) between pairs of points i,j in the input space X.


The second step, Isomap estimates the geodesic distances d_M(i,j) between all pairs of points on the manifold M by computing their shortest path distances d_G(i,j) in the graph G.

The final step applies classical MDS to the matrix of graph distances D_G={d_G(i,j)}, constructing an embedding of the data in a d-dimensional Euclidean space Y that best preserves the manifold’s estimated intrinsic geometry (Fig. 3C) by minimizing this cost function

Where D_Y denotes the matrix of Euclidean distances and ||A||_L2 is the L2 matrix norm.
And the tao operator converts distances to inner products


Here is the overview of this algorithm

And below is some experiment result of some classes of images, which interpolations along straight lines in the Isomap coordinate space (analogous to the blue line in Fig. 3C)