Machine Learning/Learning Center/Dimensionality Reduction/Locally Linear Embedding

Locally Linear Embedding (LLE)

Master how LLE preserves local linear reconstruction relationships. Learn the algorithm that finds local neighborhoods, computes reconstruction weights, and solves for low-dimensional coordinates.

Module 8 of 9

Advanced Level

90-120 min

What is Locally Linear Embedding?

Locally Linear Embedding (LLE) is a nonlinear dimensionality reduction method that preserves local linear relationships. Unlike Isomap which preserves global geodesic distances, LLE focuses on preserving how each sample can be reconstructed as a linear combination of its neighbors.

Core Assumption

Each sample $x_i$ can be reconstructed from its local neighborhood using linear weights $w_{ij}$ . These reconstruction weights should be preserved in the low-dimensional embedding.

x_i \approx \sum_{j \in Q_i} w_{ij} x_j

Where $Q_i$ is the neighborhood of $x_i$ .

LLE Algorithm Steps

The complete LLE algorithm:

Step 1

Find Local Neighborhoods

For each sample $x_i$ , find its k nearest neighbors $Q_i = \{x_j \mid j \in \text{neighbor indices}\}$ based on Euclidean distance.

Step 2

Compute Reconstruction Weights

Solve for weights $w_{ij}$ that minimize reconstruction error:

\min_{w_{ij}} \sum_{i=1}^m \left\|x_i - \sum_{j \in Q_i} w_{ij} x_j\right\|^2

Subject to $\sum_{j \in Q_i} w_{ij} = 1$ (normalization constraint).

Step 3

Preserve Weights in Low Dimensions

Find low-dimensional coordinates $z_i$ that preserve the reconstruction weights:

\min_{z_i} \sum_{i=1}^m \left\|z_i - \sum_{j \in Q_i} w_{ij} z_j\right\|^2

Reconstruction Weight Computation

For each sample $x_i$ , the reconstruction weights have a closed-form solution:

Define the local covariance matrix:

C_{jk} = (x_i - x_j)^T (x_i - x_k)

The weights are:

w_{ij} = \frac{\sum_{k \in Q_i} C_{jk}^{-1}}{\sum_{l,s \in Q_i} C_{ls}^{-1}}

This ensures the weights sum to 1 and minimize reconstruction error.

Solving for Low-Dimensional Coordinates

The optimization problem in Step 3 can be solved via eigenvalue decomposition:

Define matrix $M = (I - W)^T (I - W)$ where $W$ is the weight matrix. The optimization becomes:

\min_Z \text{tr}(Z M Z^T) \quad \text{s.t. } Z Z^T = I

Solution: Take the bottom $d'$ eigenvectors of $M$ (excluding the smallest eigenvalue which is 0). These form the rows of $Z^T$ .

Advantages and Limitations

Advantages

• Preserves local geometry
• Robust to noise
• Computationally efficient
• No global distance computation
• Works well for Swiss roll data

Limitations

• May not preserve global structure
• Sensitive to neighborhood size k
• Requires sufficient local density
• Difficult to project new samples

Next Module