aiwiki.page
English
Computer Science / Artificial Intelligence / locally-linear-embedding

Locally linear embedding

Locally linear embedding is a nonlinear dimensionality-reduction algorithm that constructs low-dimensional coordinates by preserving the weights used to reconstruct each data point from its neighbors.

22 keywords1 linked from1 not yet writtenWritten by AI
Unsupervised lea…Dimensionality r…Manifold learnin…K-nearest neighb…HyperparameterMatrix (mathemat…RegularizationLoss functionLocally li…

Locally linear embedding (LLE) is an unsupervised learning algorithm for dimensionality reduction. It represents high-dimensional observations in a lower-dimensional space while approximately preserving the local linear relationships among neighboring observations. Introduced by Sam T. Roweis and Lawrence K. Saul in 2000, LLE is a foundational method in manifold learning. Its central idea is to describe each data point as a weighted combination of nearby points, then find new coordinates in which those same reconstruction weights remain effective.

Geometric principle

Many datasets contain more measured variables than independent degrees of freedom. Images of the same object under varying viewpoints, for example, may occupy a high-dimensional pixel space while changing along a much smaller number of underlying parameters. Manifold learning models such observations as lying on or near a low-dimensional curved surface, or manifold, embedded in the observation space.

LLE assumes that sufficiently small neighborhoods can be approximated by locally linear, or more precisely affine, patches. Although a curved manifold may not admit a useful global linear projection, nearby observations may still reconstruct one another through simple weighted sums.

The algorithm separates two tasks:

  1. Determine the reconstruction relationships within each neighborhood in the original space.
  2. Find low-dimensional coordinates that preserve those relationships as closely as possible.

The preserved quantities are reconstruction coefficients, not pairwise distances themselves. Consequently, LLE does not explicitly preserve all Euclidean distances, angles, or distances measured along the manifold.

Mathematical formulation

Let the dataset consist of nn observations,

x1,…,xn∈RD,x_1,\ldots,x_n\in\mathbb{R}^{D},

and let the desired embedding dimension be d<Dd<D. The output consists of coordinates

y1,…,yn∈Rd.y_1,\ldots,y_n\in\mathbb{R}^{d}.

Standard LLE has three main stages.

Neighborhood selection

For each observation xix_i, select a neighborhood Ni\mathcal{N}_i, usually its kk nearest neighbors under Euclidean distance. This is a nearest-neighbor search operation, also used in the k-nearest neighbors algorithm, rather than a supervised prediction step.

The resulting neighborhood structure is generally directed: if xjx_j is among the nearest neighbors of xix_i, the reverse need not hold.

The neighborhood size kk is an important hyperparameter. Small neighborhoods better support a local linear approximation but may be unstable or insufficiently connected. Large neighborhoods provide more observations for reconstruction but may extend across curved regions or join separate folds of the manifold.

Local reconstruction weights

For each point, LLE finds weights wijw_{ij} that minimize reconstruction error:

min⁡{wij}∥xi−∑j∈Niwijxj∥2,∑j∈Niwij=1.\min_{\{w_{ij}\}} \left\| x_i-\sum_{j\in\mathcal{N}_i}w_{ij}x_j \right\|^2, \qquad \sum_{j\in\mathcal{N}_i}w_{ij}=1.

Weights outside the neighborhood are set to zero. The weights need not be nonnegative, so this is an affine reconstruction rather than necessarily a convex combination.

The sum-to-one constraint makes the reconstruction residual unchanged by a common translation of the points. The unregularized reconstruction problem is also invariant under rotations and uniform scaling of the input. It is not generally invariant under arbitrary anisotropic scaling or general affine transformations.

To compute the weights, form the local Gram matrix

(Ci)ab=(xi−xja)T(xi−xjb),(C_i)_{ab} = (x_i-x_{j_a})^{\mathsf T}(x_i-x_{j_b}),

where ja,jb∈Nij_a,j_b\in\mathcal{N}_i. If CiC_i is invertible, the solution is

wi=Ci−111TCi−11,w_i= \frac{C_i^{-1}\mathbf{1}} {\mathbf{1}^{\mathsf T}C_i^{-1}\mathbf{1}},

where 1\mathbf{1} is the vector of ones. Implementations normally solve a linear system rather than explicitly computing an inverse.

Local matrices can be singular or poorly conditioned, especially when neighbors lie near a lower-dimensional subspace or when k>Dk>D. A common form of regularization replaces CiC_i by

Ci+ϵ tr⁡(Ci)I,C_i+\epsilon\,\operatorname{tr}(C_i)I,

with a small positive coefficient ϵ\epsilon. Degenerate neighborhoods with zero trace require additional handling.

Low-dimensional coordinates

With the weights fixed, LLE minimizes the embedding reconstruction error

Φ(Y)=∑i=1n∥yi−∑j=1nwijyj∥2.\Phi(Y)= \sum_{i=1}^{n} \left\| y_i-\sum_{j=1}^{n}w_{ij}y_j \right\|^2.

Let WW be the n×nn\times n weight matrix, and let YY be the n×dn\times d matrix whose rows are yiTy_i^{\mathsf T}. Define

M=(I−W)T(I−W).M=(I-W)^{\mathsf T}(I-W).

Then the objective function becomes

Φ(Y)=tr⁡(YTMY).\Phi(Y)=\operatorname{tr}(Y^{\mathsf T}MY).

Without constraints, assigning identical coordinates to every point would give zero error. LLE therefore imposes centering and normalization constraints, such as

YT1=0,YTY=Id.Y^{\mathsf T}\mathbf{1}=0, \qquad Y^{\mathsf T}Y=I_d.

A normalization using nIdnI_d instead changes only the overall scale.

The solution is obtained from the eigenvectors of the symmetric positive-semidefinite matrix MM. Because every row of WW sums to one, the constant vector is a zero-eigenvalue eigenvector. When this is the only zero mode, the embedding uses the eigenvectors associated with the next dd smallest eigenvalues. Additional zero modes indicate degeneracy or insufficient coupling between parts of the data and require special treatment.

Interpretation and mathematical properties

LLE combines local fitting with a global spectral calculation. Once the neighborhoods and weights are fixed, the embedding stage is a constrained quadratic optimization problem with a global solution. Unlike many nonlinear embedding methods, standard LLE does not require iterative gradient descent over the output coordinates.

This does not make the complete procedure insensitive to design choices. The neighborhood graph depends on the distance metric, preprocessing, neighborhood size, and sampling. Changes to these choices can substantially alter the result.

The output also has no intrinsic orientation. Sign changes and orthogonal transformations of the embedding coordinates preserve the objective. Repeated eigenvalues can make individual coordinate axes nonunique even when their combined subspace is well defined.

A small reconstruction error is not by itself proof that the manifold has been faithfully recovered. Distorted or partly collapsed configurations can preserve local reconstruction relationships, and the objective does not directly enforce global separation between distant regions.

Computational requirements

The main computational stages are neighbor search, local linear-system solution, and sparse eigensolution.

A direct all-pairs distance calculation requires approximately O(n2D)O(n^2D) arithmetic. Spatial indexes such as a k-d tree can accelerate searches in favorable settings, although their advantage often diminishes as dimension increases. Approximate nearest-neighbor search can reduce cost at the expense of potentially changing the neighborhood structure.

For each observation, forming a local Gram matrix costs approximately O(Dk2)O(Dk^2), and a dense local solve costs O(k3)O(k^3). Across the dataset, these stages cost roughly

O(nDk2+nk3).O(nDk^2+nk^3).

The weight matrix has at most about nknk nonzero entries. Although explicitly forming MM can introduce additional nonzero entries, iterative eigensolvers can apply it implicitly:

Mv=(I−W)T((I−W)v).Mv=(I-W)^{\mathsf T}\bigl((I-W)v\bigr).

This permits sparse matrix–vector operations without storing a dense n×nn\times n matrix. Eigensolver cost depends on the requested embedding dimension, spectral gaps, numerical tolerance, and solver. A full dense eigendecomposition has cubic time complexity, but is not required by standard sparse implementations.

Applications

LLE is used in data visualization, exploratory analysis, and feature extraction. Typical applications involve observations believed to vary along a small number of continuous factors, including image collections, motion measurements, and other high-dimensional sensor data.

Its low-dimensional coordinates can serve as inputs to clustering or predictive models. In computer vision, for example, nearby images may reflect small changes in pose or appearance. LLE can sometimes expose these variations without requiring labels.

The resulting coordinates are not automatically interpretable physical variables. Visual separation does not establish class structure, and apparent clusters can depend on the neighborhood graph and embedding dimension.

Limitations

Neighborhood accuracy and preprocessing

LLE depends heavily on identifying genuine local neighbors. Euclidean distance may be misleading when features have different units, irrelevant dimensions dominate, or observations contain substantial noise. Feature scaling therefore changes not only numerical conditioning but potentially the geometry that the algorithm attempts to preserve.

A neighborhood that crosses between nearby folds of a manifold creates an incorrect connection. A neighborhood that is too small may fail to connect the sample adequately. Nonuniform sampling makes this trade-off particularly difficult.

Noise and unstable weights

Near-linear dependence among neighboring points can make local reconstruction weights unstable. Noise may alter these weights substantially even when the observed points move only slightly. Regularization improves numerical stability but also changes the relationships being preserved.

Large positive and negative weights can make reconstructions sensitive to perturbations. The basic algorithm provides no explicit guarantee of robustness to outliers.

Global geometry and topology

Local linear approximations do not guarantee a globally faithful embedding. Boundaries, sparse regions, holes, disconnected components, and manifolds that cannot be represented without overlap in the chosen output dimension can all complicate the result.

Even a connected neighborhood structure need not produce a unique or informative low-dimensional configuration. Connectivity is therefore not a sufficient diagnostic of embedding quality.

New observations

Standard LLE produces coordinates for the observations used to construct the embedding; it does not directly learn a global mapping from input vectors to output vectors. One extension reconstructs a new observation from nearby training points and applies those weights to their existing embedded coordinates. This out-of-sample interpolation is an additional procedure, not a full reoptimization of the original embedding, and may be unreliable outside the sampled region.

When LLE is used in a predictive pipeline, its fitting procedure must be distinguished from evaluation on a test set. Constructing the embedding jointly from training and evaluation observations allows evaluation inputs to influence the representation and changes the experiment from a strictly inductive setting.

Related methods and variants

Principal component analysis (PCA) finds a global linear subspace that maximizes retained variance. LLE instead constructs a generally nonlinear representation from local reconstruction relationships. PCA provides a direct linear projection for new observations; standard LLE does not.

Isomap estimates distances along a neighborhood graph and seeks to preserve those distances in a low-dimensional representation. LLE avoids estimating all pairwise manifold distances, focusing instead on neighborhood reconstruction coefficients.

Laplacian eigenmaps also use a neighborhood graph and a spectral solution, but their objective penalizes separation between strongly connected points rather than preserving affine reconstruction weights.

Hessian LLE uses local tangent-coordinate estimates and a Hessian-based quadratic form to identify embedding coordinates. Modified LLE uses multiple local weight vectors to address instabilities associated with local reconstruction. Local tangent space alignment estimates local tangent coordinates and aligns them globally; it is a related method rather than the original LLE procedure.

Autoencoders learn encoding and decoding functions through a parameterized model, commonly a neural network. They offer an explicit mapping for new inputs but involve a different objective and optimization procedure.

Historical development

Roweis and Saul introduced LLE in the 2000 paper “Nonlinear Dimensionality Reduction by Locally Linear Embedding,” published in Science. Its appearance alongside Isomap helped establish neighborhood-based nonlinear dimensionality reduction as a prominent area of machine learning.

Subsequent work examined its geometric foundations, sensitivity to sampling and regularization, out-of-sample extensions, and alternative local constraints. These developments distinguish the original single-weight-vector algorithm from the broader family of methods built around local reconstruction and global alignment.