I will also be presenting the paper "Nonlinear Dimensionality Reduction by Locally Linear Embedding", which comes right after "A Global Geometric Framework for Nonlinear Dimensionality Reduction" (Science, Volume 290, pages 2323-2326).

I think this is a very neat idea - using an existing technique with a new distance measure. It seems to get very good results (once I was able to make sense of the organization of the figures - their organizational scheme is still unknown to me). Its application does however seem fairly limited in that the data must lend itself to description by geodesic distances, though that may not really differ much from data that is well suited to dimensionality reduction.

I wonder how well this does in the situation where the data is a set of clusters that may have reasonable distances within them but are widely separated in space.

The isomap technique is I think one of the coolest developments in dimensionality reduction in recent times. I am not such a big fan of LLE, but then that is just a matter of personal taste. I find the idea of approximating distances between points using the geodesic distances to be ubercool. As for the applicability of the idea itself, Given the fact that data very frequently is represented in a much larger space than the one it lives in, mostly because the space that it lives in is a nonlinear manifold and the only way to represent the data in a linear space is to imbed it in a really large number of dimensions (e.g. faces) or that the raw data comes to you in high dimensional yet highly constrained form, this technique can give you dimensionality reduction while still preserving the pairwise distances between the points. Ofcourse this means that whatever meaning the individual dimensions had in the original data is lost.

Hello,
This may totally not make any sense, however:The paper states that LLE performs a linear mapping(consisting of a translation, rotation, and re-scaling(affine!!!)) from a high dimensional space to a manifold of a much less dimention. Since many manifolds may look the same, after the affine transformation, does that mean that the high dimensional space, can be mapped not to 1 but to many different lower dimension manifolds?
Andrew

Andrew, the mapping that any of these methods construct are data dependent, so even though there are an infinite mappings from three dimensions to one dimensions, the exact mapping chosen in the case of PCA depends on the direction of the principal axis of the data.

I think it is a simple yet great idea to use the concept of geodesic distances as a measure distance instead of the euclidean distance. The paper however doesnt talk about the criterion for selecting K. It would have been a good idea to figure out the the value of k that should be chosen looking at the data itself.