Nonlinear Dimensionality Reduction by Locally Linear Embedding

Looking for more research papers to read, I scanned my Hands-On Machine Learning notes for the many papers that were referenced there. This is one of those papers. These papers are mainly on machine learning and deep learning topics.

Reference Nonlinear Dimensionality Reduction by Locally Linear Embedding Paper

DOWNLOAD TEX

Date Created: 25 10, 2025

Last Edited: 23 26, 2025

1 31

Introduction

Many areas of science depend on explanatory data analysis and visualization. The need to analyze large amounts of multivariate data raises the fundamental problem of dimensionality reduction: how to discover compact representations of high-dimensional data. This paper produces locally linear embedding (LLE). an unsupervised learning algorithm that computes low-dimensional, neighborhood preserving embeddings of high-dimensional inputs. Unlike clustering methods for local dimensionality reduction, LLE maps its inputs into a single global coordinate system of lower dimensionality, and its optimizations do not involve local minima. By exploiting the local symmetries of linear reconstructions, LLE is able to learn the global structure of nonlinear manifolds, such as those generated by images or faces or documents of text.

To compare and classify high dimensional observations depends on crucially modeling the nonlinear geometry of the low dimensional manifolds on which the data often lies. Scientistis interested in explanatory analysis or visualization of multivariate data face a similar problem in dimensionality reduction. The problem, shown below, involves mapping high-dimensional inputs into a low-dimensional ”description” space with as many coordinates as observed modes of variability.

Previous approaches to this problem, based on multidimensional scaling (MDS) have computed embeddings that attempt to preserve pairwise distances between data points. In this paper, a different approach is used called locally linear embeddings (LLE) that eliminates the need to estimate pairwise distances between widely separated data points. Unlike previous methods, LLE recovers global nonlinear structure from locally linear fits.

Notes

The LLE algorithm is based on simple geometric intuitions. Suppose the data consist of $N$ real-values vectors ${\vec{X}}_{i}$ , each of dimensionality $D$ , sampled from some underlying manifold. Provided there is sufficient data, we expect each data point and its neighbors to lie on or close to a locally linear patch of manifold. We characterize the local geometry of these patches by linear coefficients that reconstruct each data point from its neighbors. Reconstruction errors are measured by

ϵ (W) = \sum_{i} | {\vec{X}}_{i} - \sum_{j} W_{ij} {\vec{X}}_{i} |

which adds up the squared distances between all the data points and their reocnstructiuons. The weights $W_{ij}$ summarize the contribution of the $j$ th data point to the $i$ th reconstruction. To compute the weights $W_{ij}$ , we minimize the cost function subject to two constraints: first, that each data point ${\vec{X}}_{i}$ is reconstructed only from its neighbors, enforcing $W_{ij} = 0$ if ${\vec{X}}_{j}$ does not belong to the set of neighbors of ${\vec{X}}_{i}$ ; second, that the rows of the weight matrix sum to one $\sum_{j} W_{ij} = 1$ . The optimal weights $W_{ij}$ subject to these constraints are found by solving a least-squares problem.

The constrained weights that minimize these reconstruction errors obey an important symmetry: for any particular data point, they are invariant to rotations, rescalings, and translations of that data point and its neighbors. By symmetry, it follows that the reconstruction weights characterize intrinsic geometric properties of each neighborhood, as opposed to properties that depend on a particular frame of reference.

Suppose that the data lie on or near a smooth nonlinear manifold of lower dimensionality $d < < D$ . To a good approximation then, there exists a linear mapping - consisting of a translation, rotation, and rescaling - that maps the high-dimensional coordinates of each neighborhood to global internal coordinates on the manifold. By design, the construction weights $W_{ij}$ reflect the intrinsic geometric properties of the data that are invariant to exactly such transformations. We therefore expect their characterization of local geometry in the orginal data space to be equally valid for local patches on the manifold. In particular, the same weights $W_{ij}$ that reconstruct the $i$ th data point in $D$ dimensions should also reconstruct its embedded manifold coordinates in $d$ dimensions.

LLE constructs a neighborhood-preserving mapping based on the above idea. In the final step of the algorithm, each high-dimensional observation ${\vec{X}}_{i}$ is mapped to a low-dimensional vector ${\vec{Y}}_{i}$ represneting global internal coordinates on the manifold. This is done by choosing $d$ -dimensional coordinates ${\vec{Y}}_{i}$ to minimize cost function

Φ (Y) = \sum_{i} {| {\vec{Y}}_{i} - \sum_{j} W_{ij} {\vec{Y}}_{j} |}^{2}

The LLE algorithm only has one free parameter: the number of neighbors, $K$ . Once neighbors are chosen the weights and coordinates are computed using standard methods in linear algebra.

Nonlinear Dimensionality Reduction by Locally Linear Embedding

Introduction

Notes

Comments

User Comments

Inserting Custom HTML:

Basics:

Inserting Code Expressions:

Inserting $\Large{LaTeX}$ Expressions:

SVG Icon Search

AI Code Generation

The Sanitization of HTML