Locally Linear Embedding

Definition

Locally linear embedding (LLE) is a non-linear dimensional reduction method that aims to preserve the intrinsic geometry of high-dimensional data in a lower-dimensional space.

Algorithm

1. Determine the k-nearest neighbors of each point

2. Compute a set of weights for each point that best approximates the point as a linear combination of its neighbors. $\underset{W}{\mathrm{argmin}}\sum _{i=1}^n[x_i-\sum _{j:x_i\in N_{x_i}}{W}_{ij}{x}_j{]}^2\text{subject to}\sum _{j:x_i\in N_{x_i}}{W}_{ij}=1,\forall i=1,\dots ,n$ where $x_i$ is a data point vector, $W$ is $n\times k$ matrix, and $N_{x_i}$ is the set of the neighbors of $x_i$

3. Find the low-dimensional embedding of points by solving Eigenvalue problem. Where each point is still described with the same linear combination of its neighbors. $\underset{\mathbf{y}}{\mathrm{argmin}}\sum _{i=1}^n[y_i-\sum _{j:x_i\in N_{x_i}}{W}_{ij}{y}_j{]}^2\text{subject to}\frac{1}{n}{\mathbf{y}}^{⊺}\mathbf{y}=I$ where $y_i$ is a vector has lower dimension than $x_i$, and $W$ is the matrix obtained by the step 2.

   In a matrix notation, the problem is written as $\underset{\mathbf{y}}{\mathrm{argmin}}{\mathbf{y}}^{⊺}M\mathbf{y}\text{subject to}\frac{1}{n}{\mathbf{y}}^{⊺}\mathbf{y}=I$ where $M=(I-W{)}^{⊺}(I-W)$

   By the Method of Lagrange Multipliers, the solution of the optimization problem is given as $M\mathbf{y}=\mathbf{y}\Lambda$ Therefore, $\mathbf{y}$ consists of eigenvectors corresponding to the $p$-smallest eigenvalues.