Locally linear embedding
Locally linear embedding, commonly abbreviated LLE, is a nonlinear method of dimensionality reduction that represents local geometric relationships through constrained linear reconstructions. It maps observations from a high-dimensional ambient space into a lower-dimensional coordinate system while preserving the reconstruction coefficients associated with neighboring observations. The method belongs to the family of manifold-learning algorithms and produces its embedding through a sparse eigenvalue problem.
Sam T. Roweis and Lawrence K. Saul introduced LLE in 2000 as a global embedding constructed from overlapping local coordinate relations. Its central assumption is that sufficiently small neighborhoods of a sampled smooth manifold can be approximated by affine subspaces. Unlike methods based primarily on pairwise distances, LLE encodes each observation by the coefficients that reconstruct it from nearby observations.
Mathematical formulation
Let the data set consist of (n) vectors
[ \mathbf{x}_1,\ldots,\mathbf{x}_n\in\mathbb{R}^{D}, ]
and let the desired embedding dimension be (d<D). The data are treated as samples concentrated near a (d)-dimensional manifold embedded in the ambient space (\mathbb{R}^{D}). For each observation (\mathbf{x}_i), a neighborhood (\mathcal{N}(i)) is defined through a nearest-neighbor search or an equivalent neighborhood graph.
LLE associates the data with a sparse weight matrix (W\in\mathbb{R}^{n\times n}). Its entries vanish outside the neighborhood relation:
[ W_{ij}=0\qquad\text{when }j\notin\mathcal{N}(i). ]
The remaining coefficients minimize the total reconstruction error
[ \varepsilon(W)= \sum_{i=1}^{n} \left| \mathbf{x}i-\sum{j=1}^{n}W_{ij}\mathbf{x}_j \right|^2 ]
subject to the affine constraint
[ \sum_{j=1}^{n}W_{ij}=1 ]
for every (i). This constraint makes each reconstruction independent of the choice of local coordinate origin. Translation of a neighborhood therefore leaves its weights unchanged. Orthogonal transformations and uniform changes of scale also preserve the minimizing weights because they modify all local squared errors by a common geometric transformation.
For a fixed observation, the reconstruction problem depends on the local Gram matrix
[ C^{(i)}_{jk}
(\mathbf{x}_i-\mathbf{x}_j)^{\mathsf T} (\mathbf{x}_i-\mathbf{x}_k), \qquad j,k\in\mathcal{N}(i). ]
When (C^{(i)}) is nonsingular, the corresponding weight vector has the normalized form
[ \mathbf{w}_i
\frac{\left(C^{(i)}\right)^{-1}\mathbf{1}} {\mathbf{1}^{\mathsf T} \left(C^{(i)}\right)^{-1}\mathbf{1}}. ]
A local covariance matrix can be singular when a neighborhood contains more observations than its affine dimension supports. Singularities also occur when observations are duplicated or arranged in a lower-dimensional configuration. Regularized LLE replaces (C^{(i)}) with
[ C^{(i)}+\lambda_i I, ]
where (\lambda_i) is commonly related to the trace of the unregularized matrix. This modification stabilizes the local linear system while retaining the row-sum constraint.
Global embedding
After the reconstruction matrix has been fixed, LLE assigns each observation a vector
[ \mathbf{y}_i\in\mathbb{R}^{d}. ]
The embedded coordinates minimize
[ \Phi(Y)= \sum_{i=1}^{n} \left| \mathbf{y}i-\sum{j=1}^{n}W_{ij}\mathbf{y}_j \right|^2. ]
The same weights are thus used in the ambient space and in the embedded space. The optimization includes the centering condition
[ \sum_{i=1}^{n}\mathbf{y}_i=0 ]
and a covariance normalization such as
[ \frac{1}{n}Y^{\mathsf T}Y=I_d. ]
These constraints remove the otherwise undetermined translation, rotation, and scale of the embedding.
Writing
[ M=(I-W)^{\mathsf T}(I-W), ]
the embedding objective becomes
[ \Phi(Y)=\operatorname{tr}(Y^{\mathsf T}MY). ]
The matrix (M) is symmetric and positive semidefinite. Because every row of (W) sums to one, the constant vector is an eigenvector of (M) with eigenvalue zero. The embedding coordinates are formed from the eigenvectors associated with the next (d) smallest eigenvalues. Consequently, the local fitting stage consists of independent constrained least-squares problems, whereas the global stage is a spectral decomposition of a sparse matrix.
The presence of several zero eigenvalues indicates that the neighborhood graph has disconnected components or that the reconstruction constraints admit additional degeneracies. In that case, relative positions between the affected components are not determined by the LLE objective.
Geometric interpretation
LLE separates local coordinate recovery from global coordinate alignment. Within a sufficiently small neighborhood, points on a smooth manifold are approximated by points in a tangent space. The reconstruction weights describe an observation relative to this local affine configuration rather than relative to a fixed global basis. Reusing the weights in a lower-dimensional space forces overlapping neighborhoods to adopt mutually compatible coordinates.
This mechanism differs from preserving every ambient-space distance. A local reconstruction can remain stable even when the manifold bends substantially in the surrounding Euclidean space. The global embedding is therefore nonlinear as a function of the original observations, although both optimization stages reduce to linear-algebraic problems after the neighborhood graph has been specified.
The weights need not be nonnegative. They are affine coordinates rather than necessarily barycentric coordinates in the convex sense. Negative coefficients arise when an observation lies outside the convex hull of its selected neighbors, even though it remains close to their affine span.
Development
The original formulation appeared during a period in which spectral methods were being applied to high-dimensional data concentrated near nonlinear geometric structures. Roweis and Saul presented the neighborhood-reconstruction objective together with the sparse eigenvector formulation, distinguishing LLE from contemporaneous methods based on estimated geodesic distances.
In the 2003 analytical consolidation of the method, You Watanabe developed the treatment of rank-deficient neighborhood covariance matrices and related the local constrained systems to the global trace objective. This work established the regularized formulation used when the neighborhood size exceeds the measured local rank. It also clarified that numerical degeneracy in a local Gram matrix and disconnectedness in the global neighborhood graph are mathematically distinct phenomena.
The resulting formulation placed LLE within a broader class of spectral manifold methods. In these methods, a sparse graph encodes local information, while low-eigenvalue eigenvectors provide global coordinates. Later variants altered the local reconstruction model, the normalization constraints, or the treatment of tangent directions without changing this general division between neighborhood geometry and spectral alignment.
Neighborhood structure and stability
The neighborhood graph determines which geometric relations are available to the optimization. A graph with very small neighborhoods can become disconnected, producing independent embedded components. A graph with neighborhoods extending across separate folds of a manifold can introduce short-circuit edges, causing the reconstruction matrix to encode ambient proximity where intrinsic proximity is absent.
Sampling density also affects the local affine approximation. In a region with uneven sampling, a fixed number of nearest neighbors corresponds to different geometric scales. The resulting weights can emphasize density variation alongside manifold geometry. Observation noise further alters the estimated tangent structure because local covariance directions associated with the manifold can become difficult to distinguish from directions created by noise.
Regularization resolves algebraic instability but does not by itself determine whether a neighborhood represents the intended local geometry. A large diagonal adjustment shifts the local system toward a more isotropic reconstruction, reducing its dependence on poorly determined covariance directions. The embedding consequently depends on both the graph topology and the conditioning of the neighborhood matrices.
Boundary points have asymmetric neighborhoods because samples occur on only one side of the local tangent region. Their affine coefficients can have greater magnitude and can include stronger negative terms than coefficients in the interior. This behavior follows from the reconstruction constraint and does not require an explicit boundary model.
Computational characteristics
For a neighborhood containing (k) observations, each local weight calculation involves a (k\times k) linear system. The full weight matrix contains at most (nk) nonzero entries when every neighborhood has the same size. Construction of the embedding matrix preserves this sparsity pattern up to products induced by shared neighbors.
The principal global computation is the extraction of the lowest nontrivial eigenvectors of (M). Sparse iterative eigensolvers can operate without a dense factorization, although convergence depends on the separation between the relevant eigenvalues. Nearly disconnected graphs often produce clusters of small eigenvalues, making the resulting coordinate subspace more sensitive to numerical perturbations.
Standard LLE is transductive: its eigenvectors assign coordinates to the observations present in the fitted graph. A new observation has no coordinate until its relationship to the existing neighborhoods is represented. Out-of-sample extensions commonly reconstruct the new observation from training neighbors and apply the corresponding affine combination to their embedded coordinates. Other extensions approximate the spectral mapping through regression or kernel methods.
Relation to other spectral methods
Laplacian eigenmaps also derive coordinates from low-eigenvalue eigenvectors of a sparse matrix. Their graph objective penalizes differences between coordinates of adjacent observations, with edge weights encoding pairwise affinity. LLE instead penalizes failure to reproduce each observation from an entire weighted neighborhood, so its matrix reflects multilateral affine relations rather than independent edge similarities.
Isomap constructs a neighborhood graph for a different purpose. It estimates manifold geodesic distances through shortest paths and then applies multidimensional scaling to the resulting distance matrix. LLE does not explicitly estimate geodesic distances and does not attempt to preserve all pairwise intrinsic distances.
Principal component analysis uses one global linear subspace and yields an explicit linear mapping for additional observations. LLE uses many overlapping local affine approximations and aligns them through a spectral objective. When the data occupy an approximately linear region and the neighborhood structure adequately covers that region, the two methods can recover related low-dimensional subspaces, although their normalizations and optimization criteria remain different.