Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifold

L. SaulS. Roweis

article2003JMLR1,583 citations

Introduces Locally Linear Embedding (LLE), an unsupervised algorithm that recovers the underlying global geometry of high-dimensional data without local minima by solving an efficient sparse eigenvalue problem that preserves local linear relationships.

Listen

Modern data processing frequently encounters high-dimensional signals, such as digital images or speech recordings, that are computationally expensive to process and difficult to analyze. While standard linear techniques like Principal Component Analysis (PCA) and Multidimensional Scaling (MDS) are widely used for dimensionality reduction due to their computational simplicity and lack of local minima, they fail to capture complex, nonlinear structures where data points lie along curved geometric manifolds.

The main objective of the article is to demonstrate and evaluate Locally Linear Embedding (LLE), an unsupervised learning algorithm that maps high-dimensional data into a lower-dimensional global coordinate system while preserving local neighborhood geometry.

To achieve this, the article outlines a three-step procedure: identifying the nearest neighbors for each data point, calculating linear weights that best reconstruct each point from its neighbors, and finding low-dimensional coordinates that preserve these local reconstruction weights. The authors evaluate this approach across synthetic mathematical manifolds and real-world image datasets, ranging from 961 to 15,960 examples and up to 65,664 dimensions, benchmarked against linear methods and tested in pattern recognition tasks.

The primary findings demonstrate that LLE successfully recovers true nonlinear degrees of freedom, such as facial pose, expression, and translation across noisy backgrounds, where PCA maps distant points onto one another and distorts the geometry. Second, the algorithm avoids iterative local minima by reducing the optimization to standard linear equations and a sparse eigenvalue problem, which computes low-dimensional coordinates efficiently. For instance, computing a 20-dimensional embedding for 15,960 high-resolution images took approximately 2.5 hours on a single workstation. Third, when used as a front-end feature extractor for handwritten digit classification, low-dimensional LLE features achieve significantly lower classification error rates than PCA features, though performance gains plateau once the number of extracted features approaches the local neighborhood size.

These results show that organizations can achieve the superior representational accuracy of nonlinear modeling without the severe computational costs, hyperparameter tuning, and convergence risks typical of neural networks or iterative hill-climbing algorithms. The sparse formulations enable scaling to large production datasets, offering a practical tool for visual indexing, data compression, and preprocessing pipelines.

Practitioners should implement LLE when data has clear local continuity, ensuring graph connectivity checks are performed before embedding disconnected components. For production deployments with unseen query points, teams should implement the non-parametric nearest-neighbor interpolation or parametric Gaussian mixture models outlined in the article. Further tuning or alternative methods like Isomap are recommended if global geodesic distance preservation is critical or if the dataset exhibits non-uniform dimensionality across different regions.

Confidence in these findings is high for well-sampled, smooth data manifolds. However, decision-makers must exercise caution when applying LLE to sparsely sampled data, manifolds with varying intrinsic dimensionality (such as connected multi-scale structures), or closed topologies like spheres, where the algorithm may collapse distant data points into adjacent embedding locations.

University of Pennsylvania University of Toronto data compression eigenvalue problem eigenvalues manifold learning nonlinear dimensionality reduction unsupervised learning

ArrowLuo/LLE_Algorithm Saul et al (2003).pdf

Paper: Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Mikhail Belkin et al. (2001). Introduces spectral manifold learning via graph Laplacians to preserve local neighborhood geometry, providing the foundational conceptual paradigm that Locally Linear Embedding complements.
Paper: A Tutorial on Principal Component Analysis, Jonathon Shlens (2014). Provides a comprehensive tutorial on linear dimensionality reduction and eigenvector decomposition in PCA, the primary classical baseline whose failure on curved manifolds motivates LLE.
Paper: Distance Metric Learning with Application to Clustering with Side-Information, Eric P. Xing et al. (2002). Presents early foundational formulations of metric learning under local pairwise constraints, contextualizing LLE's approach to neighborhood-based geometry optimization.
Paper: Similarity Search in High Dimensions via Hashing, Aristides Gionis et al. (1999). Explains efficient high-dimensional nearest-neighbor search, which is the necessary first computational step in constructing LLE's local neighborhood graphs.

Paper: Locality Preserving Projections, Xiaofei He et al. (2003). Develops Locality Preserving Projections to yield a linear, out-of-sample projective mapping that preserves the local neighborhood manifolds targeted by LLE.
Paper: Graph Embedding and Extensions: A General Framework for Dimensionality Reduction, Shuicheng Yan et al. (2007). Unifies manifold learning algorithms, explicitly reformulating LLE alongside Laplacian Eigenmaps and Isomap under a general graph-embedding framework.
Paper: Neighbourhood Components Analysis, Jacob Goldberger et al. (2004). Builds on neighborhood preservation principles introduced in LLE to learn continuous linear projections that optimize nearest-neighbor classification.
Paper: Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples, Mikhail Belkin et al. (2006). Extends unsupervised manifold learning geometry into a semi-supervised learning framework by penalizing variations along the data manifold.
Paper: Face recognition using Laplacianfaces, Xiaofei He et al. (2005). Applies locality-preserving manifold embeddings directly to face recognition, demonstrating practical classification benefits over standard linear subspaces.
Paper: Dimensionality Reduction by Learning an Invariant Mapping, Raia Hadsell et al. (2006). Generalizes neighborhood manifold preservation to non-linear parametric deep mappings capable of directly mapping new unseen test points via contrastive loss.
Paper: UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, Leland McInnes et al. (2018). Advances modern non-linear manifold dimension reduction by combining local neighborhood topology preservation with Riemannian geometry and fuzzy simplicial sets.
Paper: Graph Regularized Nonnegative Matrix Factorization for Data Representation, Deng Cai et al. (2011). Incorporates local manifold graph regularization into non-negative matrix factorization to ensure parts-based representations respect underlying geometric structure.
Paper: Accelerating t-SNE using tree-based algorithms, Laurens van der Maaten (2014). Scales neighbor-embedding non-linear dimensionality reduction methods to massive datasets using efficient tree-based spatial approximations.
Paper: Geometric Deep Learning: Going beyond Euclidean data, Michael M. Bronstein et al. (2016). Surveys geometric deep learning architectures that generalize manifold and graph representation learning into deep neural network paradigms.

Cover for Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifold

Abstract

The problem of dimensionality reduction arises in many fields of information processing, including machine learning, data compression, scientific visualization, pattern recognition, and neural computation. Here we describe locally linear embedding (LLE), an unsupervised learning algorithm that computes low dimensional, neighborhood preserving embeddings of high dimensional data. The data, assumed to be sampled from an underlying manifold, are mapped into a single global coordinate system of lower dimensionality. The mapping is derived from the symmetries of locally linear reconstructions, and the actual computation of the embedding reduces to a sparse eigenvalue problem. Notably, the optimizations in LLE—though capable of generating highly nonlinear embeddings—are simple to implement, and they do not involve local minima. In this paper, we describe the implementation of the algorithm in detail and discuss several extensions that enhance its performance. We present results of the algorithm applied to data sampled from known manifolds, as well as to collections of images of faces, lips, and handwritten digits. These examples are used to provide extensive illustrations of the algorithm's performance—both successes and failures—and to relate the algorithm to previous and ongoing work in nonlinear dimensionality reduction.

Topics

data compression eigenvalue problem eigenvalues handwritten digit recognition high dimensional data locally linear embedding nonlinear dimensionality reduction optimization reconstruction scientific visualization

Keywords

manifold learning nonlinear dimensionality reduction unsupervised learning low-dimensional manifolds spectral clustering local coordinate systems multidimensional scaling principal component analysis intrinsic dimensionality

2. Algorithm
3. Examples
4. Implementation
4.1 Step 1: Neighborhood Search
4.2 Step 2: Constrained Least Squares Fits
4.3 Step 3: Eigenvalue Problem
5. Extensions
5.1 LLE from Pairwise Distances
5.2 Convex Reconstructions
5.3 Estimating the Intrinsic Dimensionality, d
5.4 Enforcing the Intrinsic Dimensionality, d
6. From embeddings to mappings
6.1 Non-parametric Model
6.2 Parametric Model
7. Discussion
7.1 Early Motivation
7.2 Related and Ongoing Work
7.3 Summary
Acknowledgements
Appendix A. EM Algorithm for Mixture of Linear Models
References

Knowls

Knowl 1 — Locally Linear Embedding Algorithm
algorithm
Locally Linear Embedding (LLE) is an unsupervised, non-parametric algorithm that maps high-dimensional data lying on or near a low-dimensional manifold into a single global coordinate system of lower dimensionality while preserving local neighborhood geometries.
Input: Dataset of $N$ data vectors $X = \{\vec{X}_1, \vec{X}_2, \dots, \vec{X}_N\} \subset \mathbb{R}^D$ , target embedding dimension $d < D$ , number of nearest neighbors per point $K$ , regularization parameter $\Delta \ll 1$
Output: Low-dimensional embedded coordinates $Y = \{\vec{Y}_1, \vec{Y}_2, \dots, \vec{Y}_N\} \subset \mathbb{R}^d$
for each data point $\vec{X}_i$ do
    Identify the $K$ nearest neighbors of $\vec{X}_i$ based on Euclidean distance, denoted $\{\vec{\eta}_{i,1}, \dots, \vec{\eta}_{i,K}\}$
    Form the $K \times K$ local Gram matrix $G^{(i)}$ with entries $G_{jk}^{(i)} = (\vec{X}_i - \vec{\eta}_{i,j}) \cdot (\vec{X}_i - \vec{\eta}_{i,k})$
    Regularize $G^{(i)} \leftarrow G^{(i)} + \frac{\Delta^2}{K} \text{Tr}(G^{(i)}) I_K$
    Solve the linear system $\sum_{k=1}^K G_{jk}^{(i)} w_{ik} = 1$ for unnormalized weights
    Normalize weights $W_{ij} = \frac{w_{ij}}{\sum_{k=1}^K w_{ik}}$ for all $j$ in the neighborhood of $\vec{X}_i$ , and set $W_{ij} = 0$ otherwise
end for
Construct the sparse $N \times N$ cost matrix $M = (I_N - W)^T (I_N - W)$
Compute the bottom $d+1$ eigenvectors of $M$ corresponding to the $d+1$ smallest eigenvalues
Discard the bottom eigenvector (eigenvalue 0, which corresponds to the uniform unit vector)
Set the remaining $d$ eigenvectors as the rows (or columns) defining the embedded coordinates $\vec{Y}_i \in \mathbb{R}^d$ for each point $i \in \{1, \dots, N\}$
return $Y$
The algorithm requires $O(D N^2)$ time in the worst case for neighbor discovery (reducible to $O(D N \log N)$ using spatial tree data structures), $O(D N K^3)$ time to compute the local linear reconstruction weights, and subquadratic time in $N$ for computing the sparse bottom eigenvectors using iterative sparse eigensolvers.
Knowl 2 — Constrained Linear Reconstruction and Gram Matrix Regularization
equation
In Locally Linear Embedding (LLE), the local geometry around each high-dimensional data vector $\vec{X}_i \in \mathbb{R}^D$ is characterized by the linear coefficients $W_{ij}$ that best reconstruct $\vec{X}_i$ from its $K$ nearest neighbors $\vec{\eta}_j$ ( $j = 1, \dots, K$ ). The reconstruction error is minimized under the constraint that the weights sum to one ( $\sum_j W_{ij} = 1$ ) and vanish for non-neighbors:

$\varepsilon = \left\| \vec{X}_i - \sum_{j=1}^K W_{ij} \vec{\eta}_j \right\|^2 = \sum_{j=1}^K \sum_{k=1}^K W_{ij} W_{ik} G_{jk}$

where $G$ is the local $K \times K$ Gram matrix with entries:

$G_{jk} = (\vec{X}_i - \vec{\eta}_j) \cdot (\vec{X}_i - \vec{\eta}_k)$

The optimal weights are given analytically in closed form by:

$W_{ij} = \frac{\sum_{k=1}^K G_{jk}^{-1}}{\sum_{l=1}^K \sum_{m=1}^K G_{lm}^{-1}}$

When $K > D$ or the neighborhood points are degenerate, $G$ is singular or ill-conditioned. The matrix is conditioned by adding a trace-scaled regularization term:

$G_{jk} \leftarrow G_{jk} + \delta_{jk} \left(\frac{\Delta^2}{K}\right) \text{Tr}(G)$

where $\delta_{jk}$ is the Kronecker delta, $\text{Tr}(G)$ is the trace of $G$ , and $\Delta \ll 1$ is a small regularization constant (e.g., $\Delta = 0.1$ ). This regularization penalizes large weights and favors uniformly distributed reconstruction weights.
Knowl 3 — Global Embedding Optimization and Sparse Cost Matrix
equation
In Locally Linear Embedding (LLE), once the reconstruction weights $W_{ij}$ are fixed, the low-dimensional coordinates $\vec{Y}_i \in \mathbb{R}^d$ for all $N$ data points are found by minimizing the embedding cost function:

$\Phi(Y) = \sum_{i=1}^N \left\| \vec{Y}_i - \sum_{j=1}^N W_{ij} \vec{Y}_j \right\|^2 = \sum_{i=1}^N \sum_{j=1}^N M_{ij} (\vec{Y}_i \cdot \vec{Y}_j)$

where the $N \times N$ matrix $M$ is symmetric, positive semidefinite, and defined by:

$M_{ij} = \delta_{ij} - W_{ij} - W_{ji} + \sum_{k=1}^N W_{ki} W_{kj} \quad \Longleftrightarrow \quad M = (I - W)^T (I - W)$

To make the embedding well-posed and invariant to translation, rotation, and scaling, the outputs $\vec{Y}_i$ are constrained to have zero mean and unit covariance:

$\sum_{i=1}^N \vec{Y}_i = \vec{0}, \qquad \frac{1}{N} \sum_{i=1}^N \vec{Y}_i \vec{Y}_i^T = I_{d \times d}$

Subject to these constraints, the optimal embedding coordinates correspond to the bottom $d+1$ eigenvectors of $M$ ordered by increasing eigenvalues. The smallest eigenvector is a constant vector with eigenvalue zero (enforcing the zero-mean translation constraint) and is discarded; the next $d$ eigenvectors provide the $d$ embedding dimensions. Because the matrix $M$ factorizes as $(I-W)^T(I-W)$ , matrix-vector multiplication $M\vec{v}$ can be computed without explicitly constructing $M$ via two successive sparse multiplications: $\vec{u} = \vec{v} - W\vec{v}$ , followed by $M\vec{v} = \vec{u} - W^T\vec{u}$ .
Knowl 4 — Non-Parametric Out-of-Sample Extension for LLE
algorithm
To embed a novel high-dimensional test input $\vec{x} \in \mathbb{R}^D$ without recomputing the entire eigensystem across the dataset, or to map an arbitrary embedding coordinate $\vec{y} \in \mathbb{R}^d$ back to the input space $\mathbb{R}^D$ , Locally Linear Embedding uses a non-parametric nearest-neighbor interpolation.
Forward Mapping (Input Space to Embedding Space):
Input: Novel test input $\vec{x} \in \mathbb{R}^D$ , training inputs $\{\vec{X}_1, \dots, \vec{X}_N\}$ , training embedding coordinates $\{\vec{Y}_1, \dots, \vec{Y}_N\}$ , number of neighbors $K$
Output: Embedded coordinate $\vec{y} \in \mathbb{R}^d$
Identify the $K$ nearest neighbors of $\vec{x}$ among $\{\vec{X}_1, \dots, \vec{X}_N\}$ , denoted $\{\vec{\eta}_1, \dots, \vec{\eta}_K\}$ with corresponding embeddings $\{\vec{y}_{\eta_1}, \dots, \vec{y}_{\eta_K}\}$
Compute the linear weights $w_1, \dots, w_K$ that minimize $\|\vec{x} - \sum_{j=1}^K w_j \vec{\eta}_j\|^2$ subject to $\sum_{j=1}^K w_j = 1$
Compute the embedded coordinate $\vec{y} = \sum_{j=1}^K w_j \vec{y}_{\eta_j}$
return $\vec{y}$
Inverse Mapping (Embedding Space to Input Space):
Input: Embedded query point $\vec{y} \in \mathbb{R}^d$ , training embedding coordinates $\{\vec{Y}_1, \dots, \vec{Y}_N\}$ , training inputs $\{\vec{X}_1, \dots, \vec{X}_N\}$ , number of neighbors $K$
Output: Reconstructed point $\vec{x} \in \mathbb{R}^D$
Identify the $K$ nearest neighbors of $\vec{y}$ among $\{\vec{Y}_1, \dots, \vec{Y}_N\}$ , denoted $\{\vec{\psi}_1, \dots, \vec{\psi}_K\}$ with corresponding high-dimensional vectors $\{\vec{x}_{\psi_1}, \dots, \vec{x}_{\psi_K}\}$
Compute the linear weights $w_1, \dots, w_K$ that minimize $\|\vec{y} - \sum_{j=1}^K w_j \vec{\psi}_j\|^2$ subject to $\sum_{j=1}^K w_j = 1$
Compute the reconstructed input $\vec{x} = \sum_{j=1}^K w_j \vec{x}_{\psi_j}$
return $\vec{x}$
Knowl 5 — Parametric Manifold Mapping via Gaussian Mixture of Conditional Linear Models
model/method
A parametric, continuous, and invertible mapping between the high-dimensional input space $\mathbb{R}^D$ and the low-dimensional embedding space $\mathbb{R}^d$ can be learned from LLE input-output pairs $\{(\vec{x}_n, \vec{y}_n)\}_{n=1}^N$ using a mixture of conditional Gaussian linear models with $M$ components. The joint probability density is:

$P(\vec{x}, \vec{y}, z) = P(\vec{x} \mid \vec{y}, z) P(\vec{y} \mid z) P(z)$

$P(\vec{y} \mid z) = |\Sigma_z|^{-1/2} (2\pi)^{-d/2} \exp\left( -\frac{1}{2} [\vec{y} - \vec{\nu}_z]^T \Sigma_z^{-1} [\vec{y} - \vec{\nu}_z] \right)$

$P(\vec{x} \mid \vec{y}, z) = |\Psi_z|^{-1/2} (2\pi)^{-D/2} \exp\left( -\frac{1}{2} [\vec{x} - \Lambda_z \vec{y} - \vec{\mu}_z]^T \Psi_z^{-1} [\vec{x} - \Lambda_z \vec{y} - \vec{\mu}_z] \right)$

where $z \in \{1, \dots, M\}$ is a discrete mixture index with prior $P(z)$ , $\vec{\nu}_z \in \mathbb{R}^d$ and $\Sigma_z \in \mathbb{R}^{d \times d}$ are the component mean and full covariance in the embedding space, $\Lambda_z \in \mathbb{R}^{D \times d}$ is the factor loading matrix, $\vec{\mu}_z \in \mathbb{R}^D$ is the mean offset in input space, and $\Psi_z \in \mathbb{R}^{D \times D}$ is a diagonal covariance matrix.

The parameters are estimated via the Expectation-Maximization (EM) algorithm using posterior component responsibilities $\gamma_{zn} = P(z \mid \vec{x}_n, \vec{y}_n)$ and normalized weights $\omega_{zn} = \gamma_{zn} / \sum_{n'} \gamma_{zn'}$ :

$\vec{\nu}_z \leftarrow \sum_n \omega_{zn} \vec{y}_n$

$\Sigma_z \leftarrow \sum_n \omega_{zn} [\vec{y}_n - \vec{\nu}_z][\vec{y}_n - \vec{\nu}_z]^T$

$\Lambda_z \leftarrow \left( \sum_n \omega_{zn} \vec{x}_n (\vec{y}_n - \vec{\nu}_z)^T \right) \Sigma_z^{-1}$

$\vec{\mu}_z \leftarrow \sum_n \omega_{zn} [\vec{x}_n - \Lambda_z \vec{y}_n]$

$[\Psi_z]_{ii} \leftarrow \sum_n \omega_{zn} [\vec{x}_n - \Lambda_z \vec{y}_n - \vec{\mu}_z]_i^2$

$P(z) \leftarrow \frac{\sum_n \gamma_{zn}}{\sum_{z'} \sum_{n'} \gamma_{z' n'}}$

Mapping between spaces is achieved by conditional expectations: $\vec{y}^* = \mathbb{E}[\vec{y} \mid \vec{x}^*]$ or $\vec{x}^* = \mathbb{E}[\vec{x} \mid \vec{y}^*]$ .
Knowl 6 — LLE Computation from Pairwise Distances
model/method
When input vectors $\vec{X}_i$ are unavailable and only pairwise squared distances between data points are known, LLE computes the local Gram matrix $G$ directly using multidimensional scaling (MDS) dot-product recovery on each local neighborhood.

Let a data point and its $K$ nearest neighbors be indexed by $i, j \in \{0, 1, \dots, K\}$ , where index $0$ denotes the center point $\vec{x}$ and indices $1, \dots, K$ denote its neighbors $\vec{\eta}_1, \dots, \vec{\eta}_K$ . Let $S$ be the symmetric $(K+1) \times (K+1)$ matrix containing pairwise squared Euclidean distances among these points: $S_{ij} = \|\vec{x}_i - \vec{x}_j\|^2$ .

Assuming the $K+1$ points are centered at the origin, their inner products $\rho_{ij} = \vec{x}_i \cdot \vec{x}_j$ are obtained by double centering:

$\rho_{ij} = \frac{1}{2} \left[ \frac{1}{K+1} \sum_{k=0}^K (S_{ik} + S_{kj}) - \frac{1}{(K+1)^2} \sum_{k=0}^K \sum_{l=0}^K S_{kl} - S_{ij} \right]$

The entries of the $K \times K$ local Gram matrix $G_{ij} = (\vec{x} - \vec{\eta}_i) \cdot (\vec{x} - \vec{\eta}_j)$ (for $i, j \in \{1, \dots, K\}$ ) are then derived directly from the inner products:

$G_{ij} = \rho_{00} - \rho_{i0} - \rho_{0j} + \rho_{ij}$

Once $G$ is computed, reconstruction weights and embedding coordinates are calculated following the standard LLE formulation.
Knowl 7 — Enforcing Target Manifold Dimensionality via Gram Matrix Truncation
model/method
To bias LLE toward discovering an embedding of a specified intrinsic dimensionality $d$ and suppress noisy or spurious degrees of freedom, the local Gram matrix $G$ computed at each neighborhood can be projected into its dominant $d$ -dimensional subspace prior to calculating reconstruction weights.

For a point with $K$ neighbors, let $G = (\vec{x} - \vec{\eta}_j) \cdot (\vec{x} - \vec{\eta}_k)$ be the $K \times K$ Gram matrix. The neighbors are projected into the $d$ -dimensional subspace of maximal variance by performing singular value decomposition on $G$ and truncating to its $d$ largest eigenvalues and corresponding eigenvectors:

$G_{\text{proj}} = \sum_{m=1}^d \lambda_m \vec{v}_m \vec{v}_m^T$

where $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_d$ are the top $d$ eigenvalues of $G$ and $\vec{v}_m$ are the associated orthonormal eigenvectors. The reconstruction weights $W_{ij}$ are then computed using the minimum-norm least-squares solution to the linear system on the rank- $d$ matrix $G_{\text{proj}}$ . This truncates the effective rank of $G$ to $d$ while retaining the full local neighborhood size $K$ ( $K > d$ ).
Knowl 8 — Convex Reconstruction Constraints in LLE
model/method
Standard LLE constrains the reconstruction weights for each point to sum to one ( $\sum_j W_{ij} = 1$ ), which allows both positive and negative weights. In the convex formulation of LLE, an additional nonnegativity constraint $W_{ij} \ge 0$ is imposed, restricting all weights to the interval $[0, 1]$ and forcing each data point's reconstruction to lie inside the convex hull of its nearest neighbors.

The optimal weights under this constraint are obtained by solving a quadratic programming problem for each data point:

$\min_{\vec{w}} \sum_{j=1}^K \sum_{k=1}^K w_j w_k G_{jk} \quad \text{subject to} \quad \sum_{j=1}^K w_j = 1 \quad \text{and} \quad w_j \ge 0 \quad (\forall j)$

where $G$ is the local Gram matrix. The nonnegativity constraint increases robustness against outliers and prevents unbounded reconstruction weights, but can degrade reconstruction fidelity for points located on the outer boundary of a curved manifold that fall outside the convex hull of their neighbors.
Knowl 9 — Empirical Classification Performance of LLE Features versus PCA on Digit Recognition
empirical result
When used as a dimensionality reduction front-end for supervised classification on the USPS handwritten digit dataset ( $N=11000$ total images, $16 \times 16$ grayscale pixels, $D=256$ , split evenly into 5500 training and 5500 testing examples across 10 digit classes), LLE features with $K=18$ neighbors outperform Principal Component Analysis (PCA) features at low embedding dimensions ( $d \le 10$ ) on both K-Nearest Neighbor (K-NN) and Softmax regression classifiers.

Key empirical findings from the test set evaluation:
1. For small numbers of features ( $d \in [1, 8]$ ), LLE yields substantially lower classification test error rates than PCA. For example, at $d=2$ , LLE test error is approximately $35\%$ (Softmax) and $55\%$ (K-NN), compared to over $60\%$ and $70\%$ respectively for PCA.
2. Performance crossover: As the number of extracted features $d$ approaches the neighborhood parameter $K=18$ , LLE error rates saturate around $10\%$ (K-NN) and $12\%$ (Softmax), whereas PCA error rates continue to decline monotonically, crossing over to achieve lower error than LLE beyond $d \approx 15$ .
3. Baseline: Direct K-NN classification applied to the raw $D=256$ input space without dimensionality reduction yields a test error rate of $7.6\%$ (using 4 nearest neighbors).
Knowl 10 — Failure Modes and Topological Limitations of LLE
limitation
Locally Linear Embedding exhibits specific failure modes arising from its purely local reconstruction objective and reliance on graph connectivity:
1. Undersampling and Disconnected Graphs: LLE contains only attractive local reconstruction forces and lacks explicit global repulsive terms between non-neighbors. If the data manifold is undersampled or the neighborhood graph is weakly connected, coupling between distant points is attenuated, causing LLE to map faraway inputs to nearby outputs in the low-dimensional embedding space ("short-circuiting").
2. Topological Restrictions: LLE assumes the manifold is locally linear and globally embeddable in $\mathbb{R}^d$ . Manifolds that do not admit a uniformly continuous flat embedding to Euclidean space (such as closed manifolds without boundary like the sphere $S^2$ or torus $T^2$ ) cannot be unrolled faithfully without excluding patches or introducing metric distortions.
3. Variable Intrinsic Dimensionality: When applied to datasets consisting of structures with non-uniform dimensionality across different regions (e.g., a 3D barbell containing 3D volumes connected by a 1D rod), LLE with a fixed neighborhood size $K$ fails to recover a globally consistent and faithful embedding.

Coverage note — Omitted qualitative visualization experiments on synthetic S-curve, face translation, and lip motion video datasets, as well as general background comparisons with Isomap and Laplacian Eigenmaps, as their core mathematical principles and algorithmic implications are fully captured in the extracted knowls.

References

1.H. Attias. Independent factor analysis. Neural Computation, 11(4):803–851, 1999.
2.Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Society for Industrial and Applied Mathematics, Philadelphia, 2000.
3.M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 585–591, Cambridge, MA, 2002. MIT Press.
4.Y. Bengio, P. Vincent, and J.F. Paiement. Learning eigenfunctions of similarity: linking spectral clustering and kernel PCA. Technical Report 1232, Departement d'Informatique et Recherche Oprationnelle, Universite de Montreal, 2003.
5.D. Beymer and T. Poggio. Image representation for visual learning. Science, 272:1905, 1996.
6.C. Bishop, M. Svensen, and C. Williams. GTM: The generative topographic mapping. Neural Computation, 10:215, 1998.
7.C. M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, Oxford, 1996.
8.M. Brand. Charting a manifold. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, Cambridge, MA, 2003. MIT Press.
9.M. Brand and K. Huang. A unifying theorem for spectral embedding and clustering. In C. M. Bishop and B. J. Frey, editors, Proceedings of the Ninth International Workshop on Aritficial Intelligence and Statistics, Key West, FL, January 2003.
10.C. Bregler and S. Omohundro. Nonlinear image interpolation using manifold learning. In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems 7, pages 973–980, Cambridge, MA, 1995. MIT Press.
11.E. Cosatto and H. P. Graf. Sample-based synthesis of photo-realistic talking-heads. In Proceedings of Computer Animation, pages 103–110. IEEE Computer Society, 1998.
12.T. Cox and M. Cox. Multidimensional Scaling. Chapman & Hall, London, 1994.
13.P. Dayan, G. E. Hinton, R. M. Neal, and R. S. Zemel. The Helmholtz machine. Neural Computation, 7(5):889–904, 1995.
14.V. de Silva and J. Tenenbaum. Unsupervised learning of curved manifolds. In Proceedings of the MSRI workshop on nonlinear estimation and classification. Springer Verlag, 2002.
15.D. DeCoste. Visualizing Mercel kernel feature spaces via kernelized locally linear embedding. In Proceedings of the Eighth International Conference on Neural Information Processing (ICONIP-01), Shanghai, China, November 2001.
16.S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391–407, 1990.
17.D. DeMers and G.W. Cottrell. Nonlinear dimensionality reduction. In D. Hanson, J. Cowan, and L. Giles, editors, Advances in Neural Information Processing Systems 5, pages 580–587, San Mateo, CA, 1993. Morgan Kaufmann.
18.A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society B, 39:1–37, 1977.
19.D. L. Donoho and C. E. Grimes. When does Isomap recover the natural parameterization of families of articulated images? Technical Report 2002-27, Department of Statistics, Stanford University, August 2002.
20.D. L. Donoho and C. E. Grimes. Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Arts and Sciences, 100:5591–5596, 2003.
21.R. Durbin and D. Wilshaw. An analogue approach to the traveling salesman problem using an elastic net method. Nature, 326:689–691, 1987.
22.D.R. Fokkema, G.L.G. Sleijpen, and H.A. van der Vorst. Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils. SIAM Journal Scientific Computing, 20(1):94–125, 1998.
23.J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3:209–226, 1977.
24.K. Fukunaga and D. R. Olsen. An algorithm for finding intrinsic dimensionality of data. IEEE Transactions on Computers, 20(2):176–193, 1971.
25.Z. Ghahramani and G. E. Hinton. The EM algorithm for mixtures of factor analyzers. Technical Report CRG-TR-96-1 (revised February 1997), Department of Computer Science, University of Toronto, May 1996.
26.A. G. Gray and A. W. Moore. N-Body problems in statistical learning. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 521–527, Cambridge, MA, 2001. MIT Press.
27.J. H. Ham, D. D. Lee, and L. K. Saul. Learning high dimensional correspondences from low dimensional manifolds. Submitted for publication, 2003.
28.T. J. Hastie and W. Stuetzle. Principal curves and surfaces. Journal of the American Statistical Association, 84(406):502–516, 1989.
29.G. E. Hinton, P. Dayan, and M. Revow. Modeling the manifolds of handwritten digits. IEEE Transactions on Neural Networks, 8:65–74, 1997.
30.G. E. Hinton and M. Revow. Using mixtures of factor analyzers for segmentation and pose estimation. Unpublished, 1998.
31.G. E. Hinton and T. J. Sejnowski, editors. Unsupervised Learning and Map Formation: Foundations of Neural Computation. MIT Press, Cambridge, MA, 1999.
32.R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, 1990.
33.J. J. Hull. A database for handwritten text recognition research. IEEE Transaction on Pattern Analysis and Machine Intelligence, 16(5):550–554, May 1994.
34.A. Hyv¨arinen. Independent component analysis in the presence of gaussian noise by maximizing joint likelihood. Neurocomputing, 22:49–67, 1998.
35.P. Indyk. Dimensionality reduction techniques for proximity problems. In Proceedings of the Eleventh ACM-SIAM Symposium on Discrete Algorithms (SODA '00), pages 371–378, 2000.
36.I. T. Jolliffe. Principal Component Analysis. Springer-Verlag, New York, 1986.
37.G. G. Judge and T. T. Takayama. Inequality restrictions in regression analysis. Journal of the American Statistical Association, 61(313):166–181, March 1966.
38.N. Kambhatla and T. K. Leen. Dimension reduction by local principal component analysis. Neural Computation, 9:1493–1516, 1997.
39.D. R. Karger and M. Ruhl. Finding nearest neighbors in growth-restricted metrics. In Proceedings of the Thirty Fourth ACM Symposium on the Theory of Computing (STOC '02), pages 741–750, 2002.
40.B. Kegl. Intrinsic dimension estimation using packing numbers. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, Cambridge, MA, 2003. MIT Press.
41.H. Klock and J. Buhmann. Data visualization by multidimensional scaling: a deterministic annealing approach. Pattern Recognition, 33:651, 1999.
42.T. Kohonen. Self-organization and Associative Memory. Springer-Verlag, Berlin, 1988.
43.M. Kramer. Nonlinear principal component analysis using autoassociative neural networks. AIChE Journal, 37:233, 1991.
44.Y. LeCun, L. Bottou, G. Orr, and K.-R. M¨uller. Efficient backprop. In G. Orr and M¨uller K.-R., editors, Neural Networks: Tricks of the trade. Springer, 1998.
45.M. L. Littman, D. F. Swayne, N. Dean, and A. Buja. Visualizing the embedding of objects in Euclidean space. In H. J. N. Newton, editor, Computing Science and Statistics: Proceedings of the 24th Symposium on the Interface, pages 208–217. Interface Foundation of North America, 1992.
46.T. Martinetz and K. Schulten. Topology representing networks. Neural Networks, 7:507, 1994.
47.G. McLachlan and K. Basford. Mixture Models: Inference and Applications to Clustering. Marcel Dekker, 1988.
48.M. Meila and J. Shi. Learning segmentation by random walks. In S. A. Solla, T. K. Leen, and K.-R. M¨uller, editors, Advances in Neural Information Processing Systems 12, pages 873–879, Cambridge, MA, 2000. MIT Press.
49.A. W. Moore, A. Connolly, C. Genovese, A. Gray, L. Grone, N. Kanidoris II, R. Nichol, J. Schneider, A. Szalay, I. Szapudi, and L. Wasserman. Fast algorithms and efficient statistics: N-point correlation functions. In Proceedings of the MPA/MPE/ESO Conference on Mining the Sky, 2000.
50.A. Y. Ng, M. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 849–856, Cambridge, MA, 2002. MIT Press.
51.S. Omohundro. Five balltree construction algorithms. Technical Report TR-89-063, International Computer Science Institute, December 1989.
52.S. Omohundro. Bumptrees for efficient function, constraint, and classification learning. In R. Lippmann, J. Moody, and D. Touretzky, editors, Advances in Neural Information Processing 3, pages 693–699, San Mateo, CA, 1991. Morgan Kaufmann.
53.P. Perona and M. Polito. Grouping and dimensionality reduction by locally linear embedding. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 1255–1262, Cambridge, MA, 2002. MIT Press.
54.K. Pettis, T. Bailey, A. Jain, and R. Dubes. An intrinsic dimensionality estimator from near-neighbor information. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI, 1(1):25–37, 1979.
55.R. Pless and I. Simon. Embedding images in non-flat spaces. Technical Report WU-CS-01-43, Washington University, December 2001.
56.W. H. Press, S. E. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, 1993.
57.S. T. Roweis. EM algorthms for PCA and SPCA. In M. Kearns, M. Jordan, and S. Solla, editors, Advances in neural information processing systems 10, pages 626–632, Cambridge, MA, 1998. MIT Press.
58.S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323–2326, 2000.
59.S. T. Roweis, L. K. Saul, and G. E. Hinton. Global coordination of locally linear models. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 889–896, Cambridge, MA, 2002. MIT Press.
60.D. B. Rubin and D. T. Thayer. EM algorithms for ML factor analysis. Psychometrika, 47:69–76, 1982.
61.L. K. Saul and J. B. Allen. Periodic component analysis: an eigenvalue method for representing periodic structure in speech. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 807–813, Cambridge, MA, 2001. MIT Press.
62.L. K. Saul and M. G. Rahim. Maximum likelihood and minimum classification error factor analysis for automatic speech recognition. IEEE Transactions on Speech and Audio Processing, 8(2): 115–125, 1999.
63.B. Sch¨olkopf and A. J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, 2002.
64.B. Sch¨olkopf, A. J. Smola, and K.-R. M¨uller. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10:1299–1319, 1998.
65.H. S. Seung and D. D. Lee. The manifold ways of perception. Science, 290:2268–2269, 2000.
66.J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), pages 888–905, August 2000.
67.Y. Takane and F. W. Young. Nonmetric individual differences multidimensional scaling: an alternating least squares method with optimal scaling features. Psychometrika, 42:7, 1977.
68.R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 1972.
69.R. Tarjan. Data structures and network algorithms. In CBMS, volume 44. Society for Industrial and Applied Mathematics, 1983.
70.Y. W. Teh and S. T. Roweis. Automatic alignment of hidden representations. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, Cambridge, MA, 2003. MIT Press.
71.J. Tenenbaum. Mapping a manifold of perceptual observations. In M. I. Jordan, M. J. Kearns, and S. A. Solla, editors, Advances in Neural Information Processing Systems 10, pages 682–688, Cambridge, MA, 1998. MIT Press.
72.J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, 2000.
73.M. E. Tipping and C. M. Bishop. Mixtures of probabilistic principal component analysers. Neural Computation, 11(2):443–482, 1999.
74.J. J. Verbeek, N. Vlassis, and B. Kr¨ose. Coordinating mixtures of probabilistic principal component analyzers. Technical Report IAS-UVA-02-01, Computer Science Institute, University of Amsterdam, The Netherlands, February 2002a.
75.J.J. Verbeek, N. Vlassis, and B. Kr¨ose. A k-segments algorithm for finding principal curves. Pattern Recognition Letters, 23(8):1009–1017, 2002b.
76.N. Vlassis, Y. Motomura, and B. Kr¨ose. Supervised dimension reduction of intrinsically low-dimensional data. Neural Computation, 14(1):191–215, 2002.
77.Y. Weiss. Segmentation using eigenvectors: a unifying view. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pages 975–982, 1999.
78.C. K. I. Williams. On a connection between kernel PCA and metric multidimensional scaling. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 675–681, Cambridge, MA, 2001. MIT Press.
79.S. Yu and J. Shi. Grouping with directed relationships. In M. Figueiredo, J. Zerubia, and A. K. Jain, editors, Proceedings of the Third International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, (EMMCVPR-01), volume 2134 of Lecture Notes in Computer Science, pages 283–297. Springer, 2001.

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifold

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Locally Linear Embedding Algorithm

Knowl 2 — Constrained Linear Reconstruction and Gram Matrix Regularization

Knowl 3 — Global Embedding Optimization and Sparse Cost Matrix

Knowl 4 — Non-Parametric Out-of-Sample Extension for LLE

Knowl 5 — Parametric Manifold Mapping via Gaussian Mixture of Conditional Linear Models

Knowl 6 — LLE Computation from Pairwise Distances

Knowl 7 — Enforcing Target Manifold Dimensionality via Gram Matrix Truncation

Knowl 8 — Convex Reconstruction Constraints in LLE

Knowl 9 — Empirical Classification Performance of LLE Features versus PCA on Digit Recognition

Knowl 10 — Failure Modes and Topological Limitations of LLE

References

Source Code

Access the Paper