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!
 A: 
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).
