Locally Linear Embedding in R

Introduction

Welcome to the fascinating world of Locally Linear Embedding (LLE), a vital tool in our dimensionality reduction toolbox. Unlike linear techniques like Principal Component Analysis (PCA), LLE shines at preserving local neighborhood structure in high-dimensional data. In this lesson, we’ll unpack the LLE algorithm, discuss when to use it, and contrast it with PCA. We’ll implement it in R, using ggplot2 for visualization and a small helper we’ll write to run LLE.

What is Locally Linear Embedding and its Use Cases?

LLE preserves relationships within local neighborhoods while reducing dimensionality, capturing twists and turns in non-linear manifolds (e.g., images, pose, genomics). Like reading a street map vs. a bird’s-eye projection: PCA may distort local distances, whereas LLE maintains them.

Understanding the Theory Behind LLE

\min_{W}\;\sum_{i=1}^{N}\left\|x_i-\sum_{j\in N(i)} W_{ij}x_j\right\|^2 \quad\text{s.t.}\quad \sum_{j\in N(i)}W_{ij}=1

Breaking down the LLE Algorithm: Generating the Data

We’ll use the Swiss Roll—a classic 3D manifold that’s hard for linear methods but perfect for LLE. R# ---- Swiss Roll & LLE in R (from scratch) ---- # install.packages(c("ggplot2")) # run once if needed library(ggplot2) # Generate Swiss Roll data (like sklearn.datasets.make_swiss_roll) generate_swiss_roll <- function(n_samples = 1500, noise = 0.05, seed = 42) { set.seed(seed) t <- 1.5 * pi * (1 + 2 * runif(n_samples)) h <- 21 * runif(n_samples) X <- cbind( x = t * cos(t) + rnorm(n_samples, sd = noise), y = h + rnorm(n_samples, sd = noise), z = t * sin(t) + rnorm(n_samples, sd = noise) ) list(X = X, color = t) } n_samples <- 1500 noise <- 0.05 swiss <- generate_swiss_roll(n_samples, noise, seed = 42) X <- swiss$X color <- swiss$color# ---- Swiss Roll & LLE in R (from scratch) ---- # install.packages(c("ggplot2")) # run once if needed library(ggplot2) # Generate Swiss Roll data (like sklearn.datasets.make_swiss_roll) generate_swiss_roll <- function(n_samples = 1500, noise = 0.05, seed = 42) { set.seed(seed) t <- 1.5 * pi * (1 + 2 * runif(n_samples)) h <- 21 * runif(n_samples) X <- cbind( x = t * cos(t) + rnorm(n_samples, sd = noise), y = h + rnorm(n_samples, sd = noise), z = t * sin(t) + rnorm(n_samples, sd = noise) ) list(X = X, color = t) } n_samples <- 1500 noise <- 0.05 swiss <- generate_swiss_roll(n_samples, noise, seed = 42) X <- swiss$X color <- swiss$color

Applying Locally Linear Embedding (in R)

M=(I-W)^\top(I-W)

Applying PCA for Comparison

R # PCA (linear baseline) pca_fit <- prcomp(X, center = TRUE, scale. = FALSE) X_pca <- pca_fit$x[, 1:2, drop = FALSE] # PCA (linear baseline) pca_fit <- prcomp(X, center = TRUE, scale. = FALSE) X_pca <- pca_fit$x[, 1:2, drop = FALSE]

Data Visualization

We’ll compare the original Swiss Roll projection (x vs z) with LLE and PCA in 2D. R df <- rbind(data.frame(x = X[,1], y = X[,3], color = color, method = "Original (x vs z)"), data.frame(x = X_lle[,1], y = X_lle[,2], color = color, method = "LLE (k=12)"), data.frame(x = X_pca[,1], y = X_pca[,2], color = color, method = "PCA")) library(ggplot2) p <- ggplot(df, aes(x, y, color = color)) + geom_point(size = 0.8) + scale_color_viridis_c() + facet_wrap(~ method, scales = "free") + labs(title = "Dimensionality Reduction using LLE and PCA", x = "Component 1", y = "Component 2") + theme_minimal(base_size = 14) + theme(panel.background = element_rect(fill = "white", color = NA), plot.background = element_rect(fill = "white", color = NA), strip.background = element_rect(fill = "white", color = NA), plot.title = element_text(face = "bold", size = 16, hjust = 0.5), strip.text = element_text(face = "bold", size = 14)) df <- rbind(data.frame(x = X[,1], y = X[,3], color = color, method = "Original (x vs z)"), data.frame(x = X_lle[,1], y = X_lle[,2], color = color, method = "LLE (k=12)"), data.frame(x = X_pca[,1], y = X_pca[,2], color = color, method = "PCA")) library(ggplot2) p <- ggplot(df, aes(x, y, color = color)) + geom_point(size = 0.8) + scale_color_viridis_c() + facet_wrap(~ method, scales = "free") + labs(title = "Dimensionality Reduction using LLE and PCA", x = "Component 1", y = "Component 2") + theme_minimal(base_size = 14) + theme(panel.background = element_rect(fill = "white", color = NA), plot.background = element_rect(fill = "white", color = NA), strip.background = element_rect(fill = "white", color = NA), plot.title = element_text(face = "bold", size = 16, hjust = 0.5), strip.text = element_text(face = "bold", size = 14)) You should see LLE unfold the roll into a smooth 2D strip, while PCA tends to smear/overlap the manifold because it’s linear. Look at example below:

Comparing Reconstruction Errors

We can compute the LLE reconstruction error directly from the weights (same objective as Step 1) and the PCA reconstruction error as the fraction of variance not explained by the first two PCs. R# LLE reconstruction error: sum_i ||x_i - sum_j w_ij x_j||^2 recon_err_lle <- function(X, W) { Xhat <- W %*% X sum(rowSums((X - Xhat)^2)) } lle_reconstruction_error <- recon_err_lle(X, lle_fit$W) # PCA reconstruction error: 1 - (variance explained by first 2 PCs) expl <- summary(pca_fit)$importance["Proportion of Variance", 1:2] pca_reconstruction_error <- 1 - sum(expl) cat(sprintf("LLE Reconstruction Error: %.4e\n", lle_reconstruction_error)) cat(sprintf("PCA Reconstruction Error: %.4f\n", pca_reconstruction_error))# LLE reconstruction error: sum_i ||x_i - sum_j w_ij x_j||^2 recon_err_lle <- function(X, W) { Xhat <- W %*% X sum(rowSums((X - Xhat)^2)) } lle_reconstruction_error <- recon_err_lle(X, lle_fit$W) # PCA reconstruction error: 1 - (variance explained by first 2 PCs) expl <- summary(pca_fit)$importance["Proportion of Variance", 1:2] pca_reconstruction_error <- 1 - sum(expl) cat(sprintf("LLE Reconstruction Error: %.4e\n", lle_reconstruction_error)) cat(sprintf("PCA Reconstruction Error: %.4f\n", pca_reconstruction_error)) (Exact values vary with noise and sample size, but LLE should be very low; PCA typically leaves notable error on Swiss Roll.)

Lesson Summary and Practice

Congratulations! You’ve explored Locally Linear Embedding (LLE) and contrasted it with PCA using the Swiss Roll dataset. You saw how LLE preserves local neighborhood structure and effectively unfolds a non-linear manifold into 2D, while PCA—being linear—cannot capture these curved relationships.