Exploring Local Linear Embedding (LLE): Preserving Local Structure in Data

When dealing with high-dimensional data, visualizing and understanding the underlying structure can be quite challenging. Local Linear Embedding (LLE) is a powerful technique designed to tackle this issue by preserving local relationships while projecting data into a lower-dimensional space. In this blog, we’ll explore LLE in detail, including its mathematical formulation and how it works through an illustrative example.

What is Local Linear Embedding (LLE)?

Local Linear Embedding (LLE) is a non-linear dimensionality reduction technique that aims to preserve the local relationships between data points. The core idea behind LLE is that each data point can be represented as a linear combination of its neighbors. By capturing these local linear structures, LLE provides a low-dimensional representation that retains the intrinsic geometry of the data.

How Does LLE Work?

LLE involves three main steps:

• Find Neighbors: Identify the local neighbors for each data point.
• Compute Weights: Calculate the weights that best reconstruct each data point from its neighbors.
• Compute Low-Dimensional Embedding: Use these weights to compute a low-dimensional embedding that preserves local relationships.

Mathematical Formulation

Step 1: Find Neighbors

Identify Neighbors:

Given a set of data points \(\mathbf{X} = \{ \mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n \}\), where each \(\mathbf{x}_i \in \mathbb{R}^d\) is a data point in the original \(d\)-dimensional space, find the \(k\)-nearest neighbors for each point. Let \(\mathcal{N}_i\) denote the set of \(k\)-nearest neighbors for \(\mathbf{x}_i\).

Step 2: Compute Weights

Reconstruction Error:

For each data point \(\mathbf{x}_i\), reconstruct it as a linear combination of its neighbors:

\[ \mathbf{x}_i \approx \sum_{j \in \mathcal{N}_i} w_{ij} \mathbf{x}_j \]

The goal is to find weights \(w_{ij}\) that minimize the reconstruction error:

\[ E_i = \|\mathbf{x}_i - \sum_{j \in \mathcal{N}_i} w_{ij} \mathbf{x}_j\|^2 \]

Compute Weights:

Set up and solve the following optimization problem to find the weights:

\[ \text{minimize} \quad \sum_{i=1}^n E_i = \sum_{i=1}^n \left\| \mathbf{x}_i - \sum_{j \in \mathcal{N}_i} w_{ij} \mathbf{x}_j \right\|^2 \]

Subject to the constraints:

\[ \sum_{j \in \mathcal{N}_i} w_{ij} = 1 \quad \text{for all } i \]

The weights \(w_{ij}\) are found by solving the following constrained optimization problem:

\[ \mathbf{w}_i = \arg\min \left\| \mathbf{x}_i - \mathbf{X}_{\mathcal{N}_i} \mathbf{w}_i \right\|^2 \]

where \(\mathbf{X}_{\mathcal{N}_i}\) is the matrix of neighbors of \(\mathbf{x}_i\).

This involves solving a quadratic programming problem, which can be expressed in matrix form:

\[ \mathbf{w}_i = \text{argmin} \left\| \mathbf{x}_i - \mathbf{X}_{\mathcal{N}_i} \mathbf{w}_i \right\|^2 \]

Subject to \(\mathbf{1}^T \mathbf{w}_i = 1\), where \(\mathbf{1}\) is a vector of ones.

Form the Sparse Weight Matrix:

Combine the weights for all data points into a sparse weight matrix \(W\), where each entry \(W_{ij}\) represents the weight assigned to \(\mathbf{x}_j\) when reconstructing \(\mathbf{x}_i\).

Step 3: Compute Low-Dimensional Embedding

Construct the Covariance Matrix:

Formulate the matrix \(M\) where:

\[ M = (I - W)^T (I - W) \]

Here, \(I\) is the identity matrix and \(W\) is the weight matrix.

Solve the Eigenvalue Problem:

Solve the eigenvalue problem for the matrix \(M\):

\[ M \mathbf{Y} = \Lambda \mathbf{Y} \]

Find the eigenvalues \(\Lambda\) and eigenvectors \(\mathbf{Y}\).

Select the Top Eigenvectors:

Choose the \(k\) smallest eigenvalues and their corresponding eigenvectors from \(\mathbf{Y}\). These eigenvectors represent the coordinates of the data points in the lower-dimensional space.

Low-Dimensional Embedding:

The low-dimensional coordinates of the data points are given by:

\[ \mathbf{Y} = \text{matrix of the selected eigenvectors} \]

Example: Applying LLE

Step 1: Find Neighbors

Data Points:

Suppose we have the following 2D data points:

\[ \mathbf{X} = \begin{bmatrix} 1 & 2 \\ 2 & 3 \\ 3 & 3 \\ 4 & 2 \\ 5 & 1 \end{bmatrix} \]

Compute Nearest Neighbors:

Let’s choose \(k = 2\). Find the 2-nearest neighbors for each data point and construct the adjacency matrix.

Step 2: Compute Weights

Reconstruction Weights:

For a data point \(\mathbf{x}_i\), find its weights \(w_{ij}\) for reconstructing \(\mathbf{x}_i\) from its neighbors. This involves solving the quadratic optimization problem described.

Example weights matrix \(W\):

\[ W = \begin{bmatrix} 0 & 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 & 0 \\ 0.5 & 0.5 & 0 & 0 & 0 \\ 0 & 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 0 & 0.5 & 0.5 \end{bmatrix} \]

Step 3: Compute Low-Dimensional Embedding

Construct Matrix \(M\):

Compute \(M = (I - W)^T (I - W)\).

Eigenvalue Decomposition:

Perform eigenvalue decomposition on \(M\).

Suppose the decomposition yields eigenvalues \(\Lambda\) and eigenvectors \(\mathbf{Y}\).

Low-Dimensional Coordinates:

Select the eigenvectors corresponding to the smallest eigenvalues to form the low-dimensional embedding matrix \(\mathbf{Y}\).

Example 2D embedding:

\[ \mathbf{Y} = \begin{bmatrix} -0.4 & 0.6 \\ -0.2 & 0.4 \\ 0.1 & 0.2 \\ 0.3 & -0.4 \\ 0.2 & -0.2 \end{bmatrix} \]

Here, each row of \(\mathbf{Y}\) represents the coordinates of the corresponding data point in the 2D embedding space.

Summary

LLE captures local relationships in high-dimensional data by reconstructing each data point from its neighbors and embedding the data based on these reconstructions.

Steps: Find neighbors, compute weights, and derive the low-dimensional embedding using the weight matrix and eigenvalue decomposition.

Applications: LLE is effective for data lying on a low-dimensional manifold, where preserving local structures is crucial.

By leveraging LLE, you can uncover the intrinsic geometry of your data, making it easier to visualize and analyze complex datasets.