# Dimension in Locally Linear Embedding (LLE)

I am using LLE to do nonlinear dimensionality reduction. In my understanding, in the step 3, the eigendecomposition problem is with respect to the matrix M which has the dimension NxN (N is the number of points in training set). And the eigenvectors are the low dimensional embedding for the training point. However, there can be up to N eigenvectors that the embedding can even lie in a higher dimensional space (N>m, m is the original dimension of the training examples).

Why it is the case?

And if I want to find the pre-image of the low-dimensional embedding or the approximation error for the data point (the part of infomation that is lost when the data is represented by the low-dimensional embedding), is there any available algorithm?

Thank you!

there can be up to N eigenvectors that the embedding can even lie in a higher dimensional space (N>m, m is the original dimension of the training examples).

Why it is the case?

If you're specifically asking why this can happen, then you answered it yourself - that's the property of this matrix.

Of course whether this makes sense is a completely different question - for example in this article authors write

As discussed in Appendix A, in the unusual case where the neighbors outnumber the input dimensionality 213 , the least squares problem for finding the weights does not have a unique solution, and a regularization term— for example, one that penalizes the squared magnitudes of the weights—must be added to the reconstruction cost.

And if I want to find the pre-image of the low-dimensional embedding or the approximation error for the data point (the part of infomation that is lost when the data is represented by the low-dimensional embedding), is there any available algorithm?

What do you mean by this 'information'? The problem with nonlinear dimensionality reduction is that there is no single measure that is used by all of the algorithms, and most of them are designed to preserve different kinds of structure (for example even algorithms that try to preserve local structure (as LLE) like Isomap use different loss).