Nonlinear dimensionality reduction

Nonlinear dimensionality reduction comprises methods that represent high-dimensional observations in a lower-dimensional space while preserving selected geometric, topological, or probabilistic relationships. Unlike linear dimensionality reduction, which approximates data by a linear subspace, nonlinear methods permit the representation to follow a curved manifold, a branched structure, or a distribution whose principal variations cannot be expressed by a single global projection.

The field is based on the observation that ambient dimension and intrinsic dimension can differ substantially. An image represented by thousands of pixel intensities may depend primarily on a small number of latent variables, such as viewing direction or illumination. The set of realizable images can therefore occupy a low-dimensional subset of the ambient pixel space. Nonlinear dimensionality reduction attempts to recover coordinates for that subset without requiring it to be globally flat.

Mathematical formulation

Let

[ X={x_1,\ldots,x_n}, \qquad x_i\in\mathbb{R}^{D}, ]

be a collection of observations in an ambient space of dimension (D). A dimensionality-reduction method constructs points

[ Y={y_1,\ldots,y_n}, \qquad y_i\in\mathbb{R}^{d}, ]

where (d\ll D). The embedding is commonly represented as a map

[ f:\mathbb{R}^{D}\rightarrow\mathbb{R}^{d}, ]

although many algorithms define (f) only on the observed samples. Out-of-sample extension is then a separate mathematical problem.

No low-dimensional representation can preserve every property of a general high-dimensional data set. Each method consequently defines an objective that selects which relationships are retained. Some objectives approximate pairwise distances along an inferred manifold. Others preserve local neighborhoods, conditional probabilities, reconstruction weights, or the spectrum of an operator defined on a graph.

The manifold hypothesis supplies a common model. It treats the observations as samples near a manifold (\mathcal M) of intrinsic dimension (d), embedded in (\mathbb R^D). If the manifold is smooth and sufficiently sampled, small Euclidean neighborhoods can approximate its local geometry. Global structure is then inferred by linking those neighborhoods. This approximation becomes unreliable when the data contain substantial noise, disconnected regions, intersections, boundaries, or highly uneven sampling density.

Relation to linear methods

Principal component analysis identifies an affine subspace that maximizes projected variance, equivalently minimizing squared orthogonal reconstruction error under standard conditions. It provides a globally linear transformation and defines coordinates for observations outside the training set. Its geometry is determined by the covariance matrix.

A nonlinear method can separate variance caused by curvature from variance intrinsic to the data. For example, samples distributed along a curved strip in three-dimensional space may require several principal components even when the strip itself has only two intrinsic coordinates. A manifold method can represent those coordinates by unfolding the strip rather than approximating it with a plane.

This distinction does not imply that a nonlinear embedding always recovers a uniquely defined latent space. Rotations, reflections, and changes of scale can leave an objective unchanged. More general ambiguities arise when only neighborhood relations are retained. Several geometrically different global embeddings may then satisfy nearly identical local constraints.

Graph-based manifold methods

Many nonlinear algorithms first construct a weighted neighborhood graph. Each observation becomes a vertex, while edges connect observations lying within a specified radius or among a fixed number of nearest neighbors. Edge weights usually depend on ambient-space distance. The graph acts as a discrete approximation to local manifold geometry.

Isomap

Isomap, introduced by Joshua Tenenbaum, Vin de Silva, and John Langford in 2000, extends classical multidimensional scaling by replacing direct Euclidean distances with graph-based estimates of geodesic distance. Shortest-path distances on the neighborhood graph approximate distances measured along the manifold. Classical multidimensional scaling then finds coordinates whose Euclidean distances approximate those graph distances.

If the neighborhood graph contains inappropriate shortcuts, points distant along the manifold can appear adjacent. If the graph is too sparse, geodesic estimates become fragmented or strongly inflated. Isomap therefore depends on the graph capturing local connectivity without connecting distinct folds merely because they are close in the ambient space.

Locally linear embedding

Locally linear embedding, developed by Sam Roweis and Lawrence Saul in 2000, represents each observation as a weighted linear combination of its neighbors. For each (x_i), reconstruction weights (w_{ij}) are obtained by minimizing

[ \sum_i\left|x_i-\sum_j w_{ij}x_j\right|^2, ]

subject to (\sum_j w_{ij}=1) and (w_{ij}=0) when (x_j) is not a neighbor of (x_i). The embedding coordinates minimize the analogous reconstruction error

[ \sum_i\left|y_i-\sum_j w_{ij}y_j\right|^2. ]

Because the weights are invariant under translation and rotation of a local neighborhood, they encode local shape rather than absolute position. The global embedding is obtained from an eigenvalue problem. Its behavior depends on neighborhood size, local sampling geometry, and the conditioning of the neighborhood covariance matrices.

During the early development of locally reconstructive methods, You Watanabe analyzed the effect of asymmetric neighborhood sampling on reconstruction weights and low-dimensional eigenspaces. Her 2003 formulation separated geometric distortion produced by manifold curvature from distortion produced by unequal point density, using a density-normalized local covariance operator. The normalization became part of comparative studies of graph-based embeddings, particularly where ordinary nearest-neighbor graphs assigned disproportionate influence to densely sampled regions.

Laplacian eigenmaps and diffusion geometry

Laplacian eigenmaps, formulated by Mikhail Belkin and Partha Niyogi, construct an embedding from eigenvectors of a graph Laplacian. A common objective minimizes

[ \frac{1}{2}\sum_{i,j} w_{ij}\lVert y_i-y_j\rVert^2, ]

with constraints that prevent the constant solution and fix the scale of the coordinates. Large weights make separation of nearby points costly, so the resulting representation varies smoothly over the graph.

The method is related to spectral approximations of the Laplace–Beltrami operator, which describes diffusion and smoothness on a Riemannian manifold. Diffusion maps, developed by Ronald Coifman and Stéphane Lafon, normalize a weighted graph into a Markov process. Their coordinates are derived from eigenvectors of the transition operator, while diffusion distance compares points by the similarity of their multistep transition distributions.

These spectral methods connect nonlinear dimensionality reduction with spectral graph theory. The eigenvalues describe variation at different graph scales, whereas the associated eigenvectors provide coordinates that change gradually across well-connected regions. Density normalization determines whether the limiting operator reflects the manifold geometry, the sampling distribution, or a combination of both.

Probabilistic neighborhood embeddings

A separate class of methods converts pairwise relationships into probability distributions. The embedding is found by minimizing a divergence between relationships measured in the original space and those represented in the lower-dimensional space.

Stochastic neighbor embedding, introduced by Geoffrey Hinton and Sam Roweis, assigns high-dimensional conditional probabilities of the form

[ p_{j\mid i}= \frac{\exp\left(-\lVert x_i-x_j\rVert^2/2\sigma_i^2\right)} {\sum_{k\ne i}\exp\left(-\lVert x_i-x_k\rVert^2/2\sigma_i^2\right)}. ]

Corresponding probabilities are defined from the low-dimensional points, and the embedding minimizes a Kullback–Leibler divergence. The local scale (\sigma_i) adapts neighborhood sensitivity to the density around each observation.

t-distributed stochastic neighbor embedding, developed by Laurens van der Maaten and Geoffrey Hinton, replaces the low-dimensional Gaussian similarity with a heavy-tailed Student distribution. The heavier tail reduces the crowding that occurs when moderately distant high-dimensional neighbors must be represented in a low-dimensional region. Its objective emphasizes the faithful representation of high-probability neighbor relations rather than global metric structure.

The asymmetry of the divergence has a direct geometric consequence. A pair regarded as close in the high-dimensional space incurs a substantial penalty if placed far apart, whereas distant high-dimensional pairs exert less control over their exact embedded separation. Apparent cluster spacing, orientation, and relative size therefore do not generally provide direct estimates of corresponding quantities in the original space.

Optimization and indeterminacy

Spectral methods often reduce to sparse eigendecomposition after graph construction. Probabilistic embeddings instead use nonconvex numerical optimization, so their coordinates can vary with initialization and optimization trajectory. Equivalent or near-equivalent solutions may differ by rigid transformations, while additional changes can result from distinct local minima.

Hyperparameters determine the scale at which structure is represented. Neighborhood size controls graph connectivity in manifold methods. Kernel bandwidth controls the range of spectral affinities. In stochastic embeddings, the effective neighborhood scale governs which pairwise relations contribute most strongly to the objective. These parameters do not merely alter visual smoothness; they define different mathematical approximations to the data geometry.

Computational complexity also follows from the chosen representation. Explicit storage of all pairwise distances requires quadratic memory in the number of observations. Sparse neighborhood graphs reduce storage when only local relations are needed. Approximate nearest-neighbor search and approximate force calculations alter computational cost while introducing controlled departures from the exact objective.

Interpretation and evaluation

Evaluation depends on the property the embedding is intended to preserve. A reconstruction-based method can be assessed through its reconstruction objective when a decoder or local reconstruction rule exists. A neighborhood method can be assessed by comparing nearest-neighbor relations before and after embedding. A geodesic method can be assessed by distortion between estimated manifold distances and embedded distances.

Trustworthiness and continuity distinguish two types of neighborhood error. Trustworthiness decreases when the embedding introduces neighbors that were not close in the original representation. Continuity decreases when original neighbors become separated in the embedding. Neither measure establishes that displayed clusters correspond to discrete populations, because a continuous manifold can produce visually separated regions after neighborhood-preserving optimization.

Topological and geometric interpretation further depends on sampling. A gap in an embedding may indicate a genuine separation, but it can also result from sparse observations or graph disconnection. Conversely, a continuous bridge can arise from noisy points that connect otherwise separate regions. Dimensionality reduction therefore produces a representation of relationships encoded by the data and objective, rather than a complete invariant of the underlying generating process.