Dimension Reduction Taxonomy - 9. Manifold Learning II: LLE and Spectral Methods

9. Manifold Learning II: LLE and Spectral Methods

Locally Linear Embedding (LLE) and Laplacian Eigenmaps are non-linear methods based on local linearity and graph Laplacians. LLE preserves local reconstruction weights, while Laplacian Eigenmaps uses the graph Laplacian to preserve local neighborhoods.

This figure shows the conceptual process of Locally Linear Embedding (LLE). On the left, we see a high-dimensional manifold shaped like a "Swiss roll" (a common benchmark for manifold learning). The points are colored to indicate their position along the manifold. LLE assumes that each point and its neighbors lie on a locally linear patch of the manifold. It computes reconstruction weights that express each point as a linear combination of its neighbors, and then finds a low-dimensional embedding that preserves these weights. The result, shown on the right, is the "unfolded" 2D embedding where the colors reveal the underlying structure. LLE is particularly effective for data with continuous, smooth variations, such as images of a rotating object or a person walking. It preserves the local distances and topology, making it a valuable tool for visualization and feature extraction. Unlike t-SNE, which is stochastic, LLE has a deterministic solution derived from eigenvalue decomposition, but it is sensitive to the choice of the neighborhood size k.

9.1 Locally Linear Embedding (LLE)

LLE has three steps: 1) Find k-nearest neighbors. 2) Compute reconstruction weights W minimizing:

subject to $\underset{j}{\Sigma }{W}_{ij}=1$. 3) Find low-dimensional coordinates Y minimizing:

The reconstruction weights are computed by solving a least-squares problem for each point. The constraint that the weights sum to 1 ensures that the solution is translation-invariant. The low-dimensional coordinates are obtained by computing the eigenvectors of the sparse matrix M = (I-W)^T(I-W), corresponding to the smallest non-zero eigenvalues. LLE is computationally efficient for datasets up to a few thousand points, but it scales poorly to very large datasets due to the eigenvalue decomposition. The choice of k is critical; a common heuristic is to set k to be greater than the intrinsic dimension of the data.

9.2 Laplacian Eigenmaps

Laplacian Eigenmaps constructs a graph with weights:

It solves the generalized eigenvalue problem:

where L is the Laplacian. The eigenvectors with the smallest non-zero eigenvalues give the embedding.

Laplacian Eigenmaps is based on spectral graph theory. The graph Laplacian L = D - W (where D is the degree matrix) represents the local neighborhood structure. The eigenvectors of the Laplacian provide a low-dimensional embedding that preserves local distances. The parameter σ controls the scale of the heat kernel; a small σ makes the graph highly localized. Laplacian Eigenmaps is computationally similar to LLE but can handle larger graphs due to sparse eigensolvers. It is often used as a preprocessing step for clustering (spectral clustering) and for semi-supervised learning, where the graph structure is used to propagate labels.

9.3 Applications

• Visualization of complex scientific data.
• Motion capture data analysis.
• Image manifold unfolding.
• Spectral clustering.

Both LLE and Laplacian Eigenmaps are powerful tools for exploratory analysis of high-dimensional data. In motion capture, LLE can be used to understand the low-dimensional manifold of human poses, enabling motion synthesis and recognition. In image processing, these methods can unfold manifolds of object poses, such as a rotating face or a walking person. Spectral clustering, which uses the eigenvectors of the Laplacian for clustering, is a direct application of Laplacian Eigenmaps and is widely used in community detection and image segmentation.

Strengths and limitations