Understanding non-linear dimensionality reduction algorithm (locally linear embedding) I have a question about Locally Linear Embedding. I am trying to study this algorithm and implement it for better understanding. I have read An Introduction to Locally Linear Embedding. However, I don't think I really understood this algorithm. There are several questions I want to ask.


I understand that this algorithm takes some high dimensional data set and reduce it into lower dimensional data set while keeping some geometric features of the original data set. In the article, they use S-shape manifold, sample data from the manifold and reduce it into lower dimension. So I see from the picture that each region on the manifold specified by colors are conserved. But I don't think I understood why do we need this kind of reduction. I don't think it is guaranteed that any data set can be reduced to two or three dimension so that we can visualize the original data set which means how the geometric features are conserved. Can anyone explain this with some example?
I don't really understand how this algorithm can be implemented. The paper shows the reconstruction error $\epsilon(W)=\sum_i \left| X_i - \sum_jW_{ij}X_j \right|^2$ and saysThe weights summarize the contribution of the jth data point to ith reconstruction. I don't understand what this sentence means and how the weight matrix $W_{ij}$ can be constructed. Each $X_i$ represents each column in the data?? Then how can I understand $\sum_jW_{ij}X_j$?? Can anyone explain this?
The paper says that the data reduced into lower dimension can be constructed by the closest points of each data points. How is this work?


Thank you
To answer your first question:

Usually we want to reduce the dimension, because dealing with high-dimensional data is a pain: (a) algorithms for dealing with high-dimensional data tend to have higher computational complexity, and (b) high-dimensional data is hard to visualize and hard to understand.  If you can reduce the dimension without significant loss of effectiveness of the subsequent computational task, that can be useful.