PaperlayerView exact revision on arXiv

Source-linked AI summary

A survey of dimensionality reduction techniques

C. O. S. Sorzano, J. Vargas, A. Pascual Montano

arXiv:1403.2877v1stat.MLcs.LGq-bio.QM

TL;DR

High-throughput experiments create highly redundant, high-dimensional datasets that challenge statistical analysis. This review categorizes dimensionality-reduction techniques and explains their mathematical properties and foundations. It covers diverse approaches, including PCA-related methods, factorization, tensor methods, sparse representations, and manifold methods, while defining explicit scope boundaries.

  • Problem

    High-throughput experiments produce hundreds or thousands of measurements, creating high-dimensional datasets in which much information is redundant and reduction is needed without significant information loss.

  • Method

    The review categorizes dimensionality-reduction techniques and synthesizes their mathematical properties and foundations across projection, factorization, tensor, sparse-representation, and manifold approaches.

  • Results

    The review presents a broad mathematical overview spanning PCA and SVD, rotated and localized PCA, non-negative factorization, tensor analysis, sparse dictionaries, and manifold methods.

  • Takeaways & Limitations

    Dimensionality reduction is presented as a family of mathematically distinct techniques whose representations can emphasize approximation, interpretability, sparsity, or nonlinear structure.

  • Takeaways & Limitations

    The review excludes specialized time-series techniques and class-aware methods designed to preserve class separability.

Abstract

from arXiv · show

Experimental life sciences like biology or chemistry have seen in the recent decades an explosion of the data available from experiments. Laboratory instruments become more and more complex and report hundreds or thousands measurements for a single experiment and therefore the statistical methods face challenging tasks when dealing with such high dimensional data. However, much of the data is highly redundant and can be efficiently brought down to a much smaller number of variables without a significant loss of information. The mathematical procedures making possible this reduction are called dimensionality reduction techniques; they have widely been developed by fields like Statistics or Machine Learning, and are currently a hot research topic. In this review we categorize the plethora of dimension reduction techniques available and give the mathematical insight behind them.

1. Introduction

High-throughput experiments produce high-dimensional datasets, often with many more variables than observations and substantial redundancy. This review surveys dimensionality-reduction techniques and their mathematical foundations, while excluding class-aware and specialized time-series methods.

  • Motivation: High-throughput instruments generate hundreds or thousands of measurements per experiment, producing datasets that can contain more variables than observations.Examples include microarrays with thousands of genes measured across dozens of samples, as well as imaging, mass spectrometry, time-series, search, and text data.
  • Motivation: Dimensionality reduction either retains relevant original variables or constructs fewer variables as combinations of the inputs.The latter approach exploits redundancy while aiming to preserve essentially the same information.
  • Scope and contribution: The review provides an up-to-date overview of the mathematical properties and foundations of dimensionality-reduction techniques.Feature-selection methods are outside this review and are covered by other cited surveys.
  • Scope and contribution: The review excludes time-series methods that exploit frequential content or signal-specific dictionaries because they are not usually applied to general-purpose data reduction.Wavelets use fixed dictionaries and sparsification, whereas empirical mode decomposition constructs a dictionary adapted to each signal.
  • Scope and contribution: The review also excludes methods that use observation classes to preserve class separability, including Fisher’s Linear Discriminant Analysis.This boundary is stated as a consistency choice for the review.
  • Formal setup: Formally, the data consist of N observations x_n in dimension M, mapped by χ = T(x) to dimension m while retaining as much information as possible.The review also discusses approximate reconstruction and ε-stability, which concerns relative preservation of pairwise Euclidean distances.

2. Methods based on Statistics and Information Theory

Statistical and information-theoretic dimensionality-reduction methods use criteria such as representation error, probability models, and structural constraints. The section covers quantization, clustering extensions, robust objectives, kernels, and methods for preserving neighborhood organization.

  • Statistical and information-theoretic criteria: Information-theoretic methods extend statistical approaches by capturing nonlinear relationships, handling interval and categorical variables together, and often remaining invariant to monotonic transformations.These methods reduce data according to statistical or information-theoretic criteria.
  • Vector quantization: Vector quantization reduces each observation to one of K class labels and represents that class with a representative vector.The assignment-and-reconstruction scheme maps M dimensions to one label and approximates the input using the corresponding representative.
  • Vector quantization: K-means minimizes reconstruction error over representatives and assignments, with one-hot assignment constraints and a Frobenius-norm formulation.The objective is combinatorial, although heuristics can reduce its computational cost.
  • Probabilistic extensions: Under a spherical Gaussian generative model, the vector-quantization objective yields maximum-likelihood estimates of the class-center vectors.Mixture models generalize this framework by estimating class-specific covariance matrices and prior probabilities with Expectation-Maximization.
  • Probabilistic extensions: Fuzzy K-means replaces hard assignments with membership values between 0 and 1 whose memberships sum to one for each observation.This produces a soft version of vector quantization.
  • Robust and nonlinear variants: K-means is strongly affected by outliers because it uses a quadratic objective; L1-based K-medians and robust losses are proposed alternatives.A robust vector-quantization loss can use Φ(x)=x^α with α about 0.5 to reduce sensitivity to outliers.
  • Robust and nonlinear variants: Kernel vector-quantization methods map inputs nonlinearly into a higher-dimensional space, where spherical neighborhoods correspond to richer, non-spherical neighborhoods in the original space.The mapping expands dimensionality before quantization rather than reducing it at that intermediate stage.
  • Limitations and neighborhood structure: Class labels do not preserve relative distances between observations, because their numeric ordering is arbitrary.Within each label, observations are closer to their own representative than to other representatives, yielding a Voronoi partition; neighborhood-structured methods address the limitation.

2.2 PCA

PCA finds a least-squares linear subspace whose orthogonal directions capture as much data variance as possible, then represents observations by their projections onto that subspace. The section also relates PCA to SVD, decorrelation, rotations, sparse variants, and locally fitted subspaces.

  • PCA finds the single best least-squares subspace of a specified dimension for zero-mean observations.
  • The reduced representation consists of projections onto m orthonormal directions, compactly written as χ = W^t x.
  • The PCA solution uses the m eigenvectors associated with the largest covariance-matrix eigenvalues, maximizing explained variance with m variables.
  • The resulting feature vectors have identity covariance, so the different PCA features are decorrelated.
  • The truncated SVD approximation is the matrix that best approximates the data in Frobenius norm, matching the PCA objective.
  • Rotations can improve component interpretability without changing the spanned subspace, while Cluster-PCA represents clusters with centroids and local orthogonal bases.

2.3 Principal curves, surfaces and manifolds

Principal curves, surfaces, and manifolds extend linear PCA to data organized along curved or locally structured geometries. They fit nonlinear representations through regression, smoothing, kernels, and regularization, but involve bias and tuning limitations.

  • PCA can poorly approximate data following curved structures, whereas transforming such data can make a one-component linear representation suitable.
  • Principal curves: Principal curves define the best nonlinear regression curve through conditional expectations of observations projected onto each curve parameter.
  • Principal curves: Unit-speed parameterization is required so the principal curve function can be uniquely determined.
  • Principal curves: Finite observations require approximating the expectation, commonly using kernel estimates or splines; spline fitting regularizes curvature but makes λ difficult to choose.
  • Principal surfaces and manifolds: Principal surfaces extend the curve construction to two dimensions, while regularized manifolds penalize unsmooth functions through a homogeneous invariant operator.
  • Principal surfaces and manifolds: Kernel expansions control manifold shape through coefficient vectors and kernel locations, while the dimension of χ still controls dimensionality reduction; periodic kernels can learn circular manifolds.

2.4 Generative Topographic Mapping

Generative Topographic Mapping models observed high-dimensional data as noisy images of lower-dimensional latent points mapped through a nonlinear function. Its estimation uses a discrete latent grid, uniform prior probabilities, and likelihood-based objective minimization.

  • GTM assumes observations are noisy versions of a nonlinear mapping from low-dimensional vectors χ into a higher-dimensional space.
  • The nonlinear mapping uses the same kernel-based form as the principal-manifold construction and can be regularized.
  • The latent χ vectors are assumed to lie on a discrete grid containing K points with a uniform prior over grid points.
  • Under Gaussian or spherical noise, maximum-likelihood estimation reduces to minimizing the GTM objective J_GTM.

2.5 Self‐Organizing Maps

Self-Organizing Maps reduce data by assigning observations to representative classes arranged on a predefined manifold, preserving neighborhood relationships in the feature space. Extensions such as GTM and Neural Gas add statistical modeling or adaptive topology learning.

  • GTM: GTM generalizes SOMs within a statistical framework by maximizing the likelihood of observing the data.Unlike SOM’s discrete grid assignment, GTM uses a continuous mapping function.
  • Kohonen’s SOMs: SOM labels are constrained to a manifold, so nearby feature-space classes remain nearby in the input space.This topological constraint can create representatives that correspond to no actual input point.
  • Kohonen’s SOMs: SOM assigns each observation to its closest representative on a regular grid, then updates representatives using neighborhood-weighted assignments.Neighboring classes receive weaker updates than the winning class, and the process iterates until convergence.
  • Neural Gas: Neural Gas learns neighborhood topology automatically, allowing adaptation to manifolds with locally different intrinsic dimensionality.Its edges appear and disappear according to an aging strategy.

2.6 Elastic maps, nets, principal graphs and principal trees

Elastic maps and nets represent data with low-dimensional node networks that balance fidelity to observations with smoothness and regularity. Related spectral methods instead preserve inner products through eigenvalue decompositions, with MDS and PCA spanning equivalent spaces under stated conditions.

  • Elastic maps and nets: Elastic maps associate each low-dimensional node with a high-dimensional representative and combine data fidelity with regularity within the network.Their objective includes similarity to observations and smoothness constraints among neighboring nodes.
  • Elastic maps and nets: Neighbor smoothness is enforced both by favoring similar neighboring representatives and by keeping each representative near its neighbors’ average.Elastic nets can add or delete nodes adaptively to fit the data structure.
  • Spectral methods: MDS constructs a lower-dimensional feature matrix from the leading eigenvalues of the Gram matrix.The resulting representation best preserves input inner products in Frobenius norm.
  • Spectral methods: For m ≤ η, the spaces spanned by MDS and PCA are identical up to rotation, and MDS can use only a Gram or distance matrix.Here η is the common rank bound of the Gram and covariance matrices.
  • Kernel PCA: Kernel PCA captures nonlinear relationships by mapping inputs into a higher-dimensional space where standard PCA may become more linear.Kernel inner products avoid explicitly constructing the transformed vectors and their covariance matrix.

2.8 Kernel Entropy Component Analysis

Kernel Entropy Component Analysis generalizes PCA by selecting directions according to information measured through Rényi’s quadratic entropy rather than variance alone. The surrounding robust-PCA approaches address sensitivity to outliers through robust objectives, estimates, ranks, or kernels.

  • Kernel Entropy Component Analysis: Rényi’s quadratic entropy measures input information through the expectation of the squared probability density, which can be estimated with a Parzen kernel estimator.The estimator and entropy calculation can be expressed using a Gram matrix.
  • Kernel Entropy Component Analysis: Kernel Entropy Component Analysis selects eigenvectors with the largest entropy contributions rather than simply choosing those with the largest eigenvalues.It is presented as an information-theoretic generalization of PCA.
  • Robust PCA: Outliers can distort PCA by dominating estimates of the data mean and covariance, motivating robust PCA methods.Robust PCA replaces or modifies the standard objective, including with robust mean and covariance estimates.
  • Robust PCA: Robust PCA variants use L1 objectives, robust estimators, rank-transformed observations, or kernels to reduce sensitivity to outliers.Examples include projection-based M-estimators, weighted PCA, and correntropy-based approaches.
  • Robust PCA: Minimum Covariance Determinant methods remove observations with the highest outlyingness before performing PCA on the remaining data.The procedure first estimates covariance from a subset selected for minimum covariance determinant.

2.10 Factor Analysis

Factor analysis models observed variables as generated from latent factors plus noise, making it closely related to PCA while explicitly estimating noise covariance. Its factorization is non-unique under orthogonal rotations, which can be used to obtain simpler factors.

  • Factor analysis: Factor analysis assumes observed data arise from unobserved latent factors through a linear model with additive noise.Without noise, the model coincides with PCA.
  • Factor analysis: The observed covariance decomposes into a factor contribution and the noise covariance, which must be estimated from the data.The loading matrix is obtained by factorizing the difference between these covariance matrices.
  • Factor analysis: Factor-analysis loadings are not unique because any orthogonal rotation produces the same covariance decomposition.The non-uniqueness is exploited to produce simpler factors, using rotation methods analogous to PCA.

2.11 Independent Component Analysis

Independent Component Analysis (ICA) seeks statistically independent factors, unlike PCA, which seeks uncorrelated factors. The review describes likelihood-, entropy-, and non-Gaussianity-based approaches for estimating these components.

  • ICA seeks independent factors by constraining all moments, whereas PCA seeks factors that are uncorrelated through second-order statistics.For Gaussian variables, decorrelation implies independence, but this does not generally hold for non-Gaussian variables.
  • Non-Gaussianity: Non-Gaussianity-based ICA exploits the central limit theorem by searching for transformations whose components maximize kurtosis or negentropy.Kurtosis can be sensitive to outliers, while negentropy is defined using a Kullback-Leibler divergence.
  • Non-Gaussianity: Projection pursuit searches for directions with non-Gaussian projections, while Non-Gaussian Component Analysis searches for an entire non-Gaussian linear subspace.The review presents projection pursuit as a special case related to ICA.
  • Maximum-likelihood (ML): Maximum-likelihood ICA estimates the mixing matrix by maximizing the likelihood of observations under assumed component distributions.When feature distributions are unknown, super-Gaussian and sub-Gaussian choices are commonly considered.
  • Maximum-likelihood (ML): Infomax maximizes the joint entropy of feature variables, equivalently minimizing their mutual information to promote independence.The review states that Infomax is equivalent to maximum likelihood when the neural-network nonlinearities match the assumed output distributions.

3. Methods based on Dictionaries

Dictionary-based methods represent the data matrix using atoms and their coefficients, with variants imposing non-negativity, sparsity, locality, robustness, or tensor structure. These constraints can make reduced representations more interpretable or better matched to structured data.

  • Dictionary methods decompose the data matrix into atoms and coefficients, generalizing SVD-related approaches and including vector quantization as an extreme case.The dictionary is a change-of-basis representation whose atoms combine to represent observations.
  • Non-negative Matrix Factorization: Non-negative Matrix Factorization constrains dictionary atoms and feature vectors to positive values, supporting additive and application-specific representations.This is particularly suited to naturally non-negative data such as text-related measurements.
  • Non-negative Matrix Factorization: Earth Mover’s Distance factorization minimizes transport-based distance between X and WU to improve robustness, especially for small samples.The distance is computed as the minimum cost of transforming one probability distribution into another.
  • Sparse representations: Sparse methods seek representations using as few dictionary atoms or nonzero features as possible, aiding interpretation of an observation’s atomic composition.Different regularizers promote sparse atoms, sparse feature vectors, or both.
  • Non-negative Matrix Factorization: Graph-regularized NMF preserves neighborhood structure by penalizing differences between reduced representations of nearby observations.It constructs a neighbor graph and adds a Laplacian regularization term to the reconstruction objective.
  • Principal Tensor Analysis and Non-negative Tensor Factorization: Non-negative tensor factorization extends NMF to multidimensional arrays while preserving locality associated with dimensions such as drug, gene, and time.Flattening tensors into matrices would make earlier methods applicable but could lose variable-specific locality.
  • Patch-based methods represent small signal or image pieces as combinations of atoms from an overcomplete dictionary.For an 8x8 image patch, the local vectors have dimension 64 while the dictionary contains more than 64 atoms.

4. Methods based on projections

Projection-based methods reduce dimensionality by mapping observations onto subspaces or manifolds with selected properties. The review covers directions emphasizing non-Gaussianity, fast predefined or random projections, and manifold-based embeddings that preserve relationships.

  • Projection onto interesting directions: Projection pursuit identifies interesting directions, commonly those whose projected values are non-Gaussian, by maximizing kurtosis.The review treats projection pursuit as a special case of the ICA family.
  • Transform-based methods use predefined directions such as DCT or wavelets, while random mapping uses normalized zero-mean random vectors for rapid reduction.These approaches avoid the costly search for optimal orthogonal directions.
  • Random projections nearly conserve observation dot products in feature space at a computational cost that is only a small fraction of most dimensionality-reduction techniques.The near-orthogonality of random vectors underlies this similarity-preservation property.
  • Manifold methods project data onto a nearby manifold and unfold it, including Sammon projection, MDS, Isomap, Laplacian eigenmaps, and LLE.The review notes that these methods can be special cases of Kernel PCA under certain circumstances.
  • MDS and Sammon projection seek feature vectors whose output-space distances approximate distances in the original space.Classical MDS preserves inner products and is equivalent to PCA, while Sammon projection is related to Kernel PCA.

D D   , while Sammon projection minimizes

The review develops manifold-learning methods that preserve distances, neighborhoods, or local geometry through graph, eigenvalue, and reconstruction objectives. It also presents linear extensions that improve out-of-sample behavior.

  • Distance-preserving methods: Isomap applies MDS to geodesic distances computed as shortest paths in a neighborhood graph rather than Euclidean distances.Geodesic distance follows the manifold, whereas Euclidean distance follows the direct linear path.
  • Graph-based methods: Laplacian eigenmaps retain eigenvectors associated with the m smallest nonzero generalized eigenvalues of the graph Laplacian.Its objective minimizes distances between projected features connected by graph edges.
  • Locally Linear Embedding: LLE reconstructs each observation from its K-nearest neighbors and preserves the same reconstruction weights in the reduced space.The weights sum to 1 for every observation, and the reduced coordinates are obtained through an eigenvalue problem.
  • Manifold methods: Hessian eigenmaps replace the graph Laplacian with a graph Hessian, extending ISOMAP and Laplacian eigenmaps without requiring a convex subset of R^m.The method remains within the family of locally learned manifold techniques.
  • Latent Tangent Space Alignment: LTSA computes local PCA coordinates and aligns neighborhoods through shared translation and shape parameters in a common geometric framework.Its objective jointly optimizes the reduced coordinates and neighborhood alignment parameters.
  • Locality Preserving Projections: ISOMAP, Laplacian eigenmaps, LLE, and LTSA are defined only near training data and normally extrapolate poorly because their mappings are implicit.LPP addresses this issue by constraining the embedding to a linear projection of the input vectors.
  • Locality Preserving Projections: LPP uses a linear projection χ_n = A^t x_n while retaining the Laplacian eigenmaps goal function.Kernel and orthogonal variants extend the same projection framework.

5. Trends and Conclusions

Citation trends show a growing and increasingly nonlinear dimensionality-reduction field, with manifold and dictionary methods gaining prominence while established techniques retain specialized roles. PCA remains widely used, and the review concludes that diverse methods serve different application niches while pursuing simpler representations of the same information.

  • Citation interest in dimensionality reduction grew by a factor of 3 during the last decade.
  • Component-based techniques remain the most applied, but projections and dictionaries are gaining importance in response to nonlinear experimental data.
  • Vector quantization retained a nearly constant market share, while topology-preserving variants lost impact as manifold methods emerged; other techniques maintained niche applications.
  • Manifold analysis was the decade’s clear winner because it handles nonlinearities and adapts to local data structure; ISOMAP, Locally Linear Embedding, and Laplacian Eigenmaps were especially successful.
  • PCA remains preferred for its simplicity and intuitiveness, whereas Factor Analysis declined as a more constrained modeling approach.
Loading 1403.2877v1…