Locally linear embedding (LLE) assumes that the vector representation of a node ni, let's call it Vi, must be a linear combination of the vector representations of the neighbors of i, N(i). It is encoded into the following equation, where the adjacency matrix is denoted by the letter M:
Vi = ∑j∈N(i) Mij × Vj
Finding an embedding is hence reduced to an optimization problem where you are finding the vectors Vi such that the distance between Vi and the linear combination of its neighbors is as small as possible. In mathematical terms, we end up with a least-squares minimization problem, where the function to minimize is as follows:
Φ(V) = ∑i (Vi - ∑j∈N(i) Mij × Vj )²
This problem contains many variables since the unknown variables are the components of the Vi vectors – hence N×d. However, it can be shown that the solutions to this problem are the first d+1 eigenvectors of the matrix M'...
