Machine Learning & Signals Learning

11 Dimensionality Reduction

Common motivations: visualization in two or three dimensions, noise reduction, decorrelation of features, lossy compression, and mitigating the curse of dimensionality before downstream classification or regression.

11.1 Characterization

11.1.1 Local vs. global structure

The methods in this chapter are compared by how well they preserve the local and global structure of the data:

• • Local structure is the geometry of small neighbourhoods: which points are close to which, the shape of a single cluster, fine-grained variation within a group. Preserving local structure means that points that were near each other in \(\mathbb {R}^N\) remain near each other in \(\mathbb {R}^K\).

• • Global structure is the large-scale layout: relative positions of clusters, overall spread, and the distances between distant points. Preserving global structure means that clusters that were far apart in \(\mathbb {R}^N\) remain far apart, and their relative arrangement is maintained.

Both aspects are illustrated on the same five-cluster ring dataset in Fig. 11.1. Panels (a) and (b) define the two notions on the original data; panels (c) and (d) show the two failure modes a low-dimensional embedding can fall into when the goals come into conflict. The trade-off is unavoidable: mapping \(\mathbb {R}^N\) to \(\mathbb {R}^K\) with \(K\ll N\) must discard some pairwise-distance information, and which distances survive is dictated by the criterion the embedding optimises.

11.1.2 General Features

Deterministic vs. stochastic fits

A method is deterministic if it returns the same embedding every time it is run on a given dataset; it is stochastic if the result depends on a random initialisation or a randomised optimiser, so successive runs of the same code on the same data produce different layouts. Determinism matters when the embedding is used as a fixed preprocessing step in a pipeline (the same input must always give the same output) and for the reproducibility of published figures. Stochastic methods are usually made reproducible by fixing a random seed.

Embedding new points

A method embeds new points if, after fitting on a training set, it can place unseen samples in the same coordinate system without re-running the optimisation. This is essential when the low-dimensional representation is part of a deployed system (e.g., a learned 2D map onto which test or streaming data must be plotted). Methods that lack this property must be re-fit from scratch whenever the dataset changes, which makes them suitable mainly for one-off visualisation rather than for reusable preprocessing.

Supervised vs. unsupervised

A dimensionality-reduction method is unsupervised if it uses only the inputs \(\bx _1,\ldots ,\bx _M\) and supervised if it also uses the targets \(\by _1,\ldots ,\by _M\) to choose the embedding. Unsupervised methods optimise a purely geometric criterion (variance, neighbour structure), so they may discard directions that have low variance but are highly informative about \(\by \).

11.2 Principal Component Analysis (PCA)

11.2.1 Mean as a zero-dimensional representation

The simplest dimensionality reduction maps every data point to a single point \(\mathbf {c}\in \mathbb {R}^N\). The choice that minimizes the sum of squared distances,

\begin{equation} \mathbf {c}^\star = \argmin _{\mathbf {c}} \sum _{i=1}^{M}\|\bx _i-\mathbf {c}\|^2, \end{equation}

is the sample mean

\begin{equation} \bmu = \frac {1}{M}\sum _{i=1}^{M}\bx _i. \end{equation}

We use \(K\) to denote the dimension of the approximation: a single point has dimension \(K=0\), a line \(K=1\), a plane \(K=2\), and so on. The sample mean is therefore the best \(K=0\) approximation of the dataset (Fig. 11.2).

11.2.2 Definition

Intuition For \(K\ge 1\), PCA fits the data with a \(K\)-dimensional subspace through the sample mean (a line for \(K=1\), a plane for \(K=2\), and so on). This subspace is oriented along the directions in which the data spreads the most. The first such direction is the line that best fits the centered points; the second is perpendicular to the first and captures the next-largest spread; and so on (Fig. 11.3).

Objective To turn this picture into a computation, we need a formula for the reconstruction \(\hat \bx _i\) of each data point on the subspace. Write it as \(\hat \bx _i=\mathbf {c}+\bW _K\bz _i\), where \(\mathbf {c}\in \mathbb {R}^N\) is a point the subspace passes through, the columns of \(\bW _K\in \mathbb {R}^{N\times K}\) are the \(K\) direction vectors of the subspace (unit-length and mutually perpendicular), and \(\bz _i\in \mathbb {R}^K\) holds the coordinates of point \(i\) within it. With this parametrization, the same squared-distance criterion as in the \(K=0\) case becomes

\begin{equation} \label {eq-pca-objective} (\mathbf {c}^\star ,\bW _K^\star ,\{\bz _i^\star \}) = \argmin _{\substack {\mathbf {c},\,\bW _K,\,\{\bz _i\}\\ \bW _K^T\bW _K=\bI _K}} \sum _{i=1}^{M}\bigl \|\bx _i-(\mathbf {c}+\bW _K\bz _i)\bigr \|^2. \end{equation}

Setting \(K=0\) removes the \(\bW _K\bz _i\) term and recovers the mean problem.

Solution Solving (11.3) splits into two steps: locating the subspace (choosing \(\mathbf {c}^\star \)) and orienting it (choosing \(\bW _K^\star \)). Both are read off the data through the sample mean and the sample covariance matrix. Let \(\bX \in \mathbb {R}^{M\times N}\) be the data matrix (rows are samples). Center it by subtracting the sample mean,

\begin{equation} \tilde \bX = \bX - \bOne \bmu ^T,\qquad \bmu = \frac {1}{M}\sum _{i=1}^{M}\bx _i, \end{equation}

and form the sample covariance matrix

\begin{equation} \bS = \frac {1}{M-1}\tilde \bX ^T\tilde \bX . \end{equation}

The best subspace passes through the sample mean, so \(\mathbf {c}^\star =\bmu \). Its directions are the top \(K\) eigenvectors of \(\bS \): \(\bW _K^\star =[\bw _1,\ldots ,\bw _K]\), where the eigenvectors \(\bw _1,\ldots ,\bw _N\) are ordered by decreasing eigenvalue \(\lambda _1\ge \lambda _2\ge \cdots \ge \lambda _N\ge 0\). Each eigenvalue \(\lambda _i\) equals the variance of the data along \(\bw _i\), so picking the top \(K\) eigenvectors picks the \(K\) directions of largest spread, which matches the geometric picture from the intuition above. The eigendecomposition itself is reviewed in the appendix.

Encoding and decoding Once the directions \(\bW _K\) are fixed, each data point is encoded as

\begin{equation} \bz = \bW _K^T(\bx -\bmu ) \in \mathbb {R}^K \end{equation}

and reconstructed as

\begin{equation} \hat \bx = \bmu + \bW _K\bz . \end{equation}

For \(K=0\) this collapses to \(\hat \bx =\bmu \), the zero-dimensional approximation. For \(K\ge 1\), no other \(K\)-dimensional subspace through \(\bmu \) gives a smaller reconstruction error in (11.3).

Computation. In practice PCA is computed from the singular value decomposition of \(\tilde \bX \) rather than by forming \(\bS \) explicitly. SVD is more numerically stable, especially when features are nearly collinear or \(N\) is large.

PCA can also be viewed as a linear autoencoder with a single hidden layer of width \(K\) and tied weights; this connection is taken up again in the chapter on neural networks.

11.2.3 Choosing the number of components

The fraction of variance explained by component \(i\) is \(\lambda _i/\sum _j\lambda _j\). The cumulative explained variance by the top \(K\) components is

\begin{equation} \mathrm {EV}(K) = \frac {\sum _{i=1}^{K}\lambda _i}{\sum _{j=1}^{N}\lambda _j}\times 100\%. \end{equation}

Two common heuristics for picking \(K\) are: (i) the smallest \(K\) such that \(\mathrm {EV}(K)\) exceeds a target threshold (typically 90% or 95%), and (ii) the elbow of the scree plot, where the variance ratio drops sharply (Fig. 11.5).

PCA is deterministic, embeds new points trivially via \(\bz _{\mathrm {new}}=\bW _K^\top (\bx _{\mathrm {new}}-\bmu )\), and is unsupervised: it does not use the target \(\by \), so it may discard directions that are low-variance but discriminative.

Practical notes

• • Scale sensitivity: when input features are in different units, standardise them first (or apply PCA to the correlation matrix instead of the covariance matrix); otherwise the largest-variance feature dominates.

• • Use in supervised pipelines: validate the chosen \(K\) with cross-validation rather than picking it from the scree plot alone.

• • Lossy compression and denoising: dropping the small-eigenvalue components removes the directions of smallest variance, which often correspond to noise (eigenfaces are a classical example).

• • For visualization and clustering: PCA tends to preserve global (inter-cluster) geometry but distorts local (intra-cluster) structure.

11.3 t-SNE

t-SNE (t-distributed stochastic neighbor embedding) is a popular tool for visualizing complex data in 2D or 3D. Instead of trying to keep the exact mathematical distances between points like PCA does, t-SNE simply tries to group similar data points together while pushing dissimilar points far apart.

t-SNE is stochastic and does not embed new points: each call re-runs the optimization from a random initialisation, and the resulting layout cannot be reused to place unseen samples without refitting on the combined data.

Hyper-parameter: Perplexity The main control knob is perplexity, typically set between 5 and 50. Think of this as the number of close neighbors each point cares about. If your plot looks like a cloud, adjusting the perplexity is the best way to uncover hidden structure.

11.4 UMAP

UMAP (uniform manifold approximation and projection) is a newer alternative to t-SNE. It targets the same goal (creating 2D or 3D plots of complex data) but uses a more efficient approach that gives it several major practical advantages.

Improvements over t-SNE:

• • Faster

• • Better preserves global structure.

• • Can place unseen samples on a previously fitted map without refitting.

Hyper-parameters UMAP gives you two main ways to control the final plot:

• • n_neighbors: Similar to t-SNE’s perplexity. A low number focuses on grouping tiny local details, while a high number forces the algorithm to look at the broader, global structure.

• • min_dist: Controls how tightly packed the points are allowed to be. Set it low (e.g., 0.1) if you want distinct, separated clusters; set it higher (e.g., 0.5) if you want to see the individual points without them overlapping too much.

11.5 PaCMAP

PaCMAP (pairwise controlled manifold approximation and projection) is a more recent visualisation method that explicitly aims to preserve both local clusters and global layout at the same time. It is built on top of the same general idea as UMAP, but with a different recipe for choosing which pairs of points the optimisation should care about.

The distinguishing idea of PaCMAP is to balance three types of point pairs in the loss function:

• • Near pairs: a few close neighbours of each point, used to keep local clusters tight.

• • Mid-near pairs: pairs that are not the closest, but not far either, used to anchor the medium-scale layout.

• • Further pairs: random distant pairs, used to push unrelated points apart.

By tuning the relative weight of these three types over the course of optimisation, PaCMAP recovers fine cluster structure without losing the big picture.

Hyper-parameter The main control is n_neighbors (size of the local neighbourhood, similar in spirit to UMAP’s n_neighbors or t-SNE’s perplexity). Defaults work well in most cases; the implementation also exposes ratios that control how many mid-near and further pairs are used per near pair, which usually do not need to be changed.

PaCMAP is stochastic, unsupervised, and embeds new points into an existing layout . As with the other nonlinear methods, absolute distances in a PaCMAP plot should not be over-interpreted, but the relative arrangement of clusters tends to be more trustworthy than in t-SNE.

11.6 Summary

How each method handles the local/global trade-off. The local vs. global distinction introduced at the start of the chapter (Fig. 11.1) is dictated by the criterion each method optimises. A loss built on overall variance or all pairwise distances (as in PCA) is dominated by the largest distances, so global layout is retained but within-cluster geometry is spent first when a direction is dropped. A loss built on neighbour relations (as in t-SNE) penalises only short-range errors, so within-cluster structure is preserved, but the optimiser is free to rearrange clusters because faraway distances do not enter the loss. Hybrid methods such as UMAP and PaCMAP mix near-neighbour and farther-pair terms in the loss, which is why their plots tend to keep clusters tight and their relative arrangement readable.

PCA is a linear projection, so it preserves global structure (large pairwise distances and overall spread) but compresses everything along the dropped directions, which often destroys fine local detail. t-SNE optimises a local objective, so it reveals clusters and within-cluster structure clearly but distorts global geometry: cluster sizes and inter-cluster distances in a t-SNE plot are not meaningful. UMAP sits between the two, recovering local structure similarly to t-SNE while retaining more of the global layout.

Figure 11.6 illustrates this on the handwritten-digits dataset (10 classes, 64 features): PCA shows heavy class overlap, while t-SNE and UMAP both separate the digit classes into compact clusters. Table 11.1 summarises how the four methods compare on the properties introduced earlier in Sec. 11.1.

Choosing a method

• • Use PCA as a default first step for small datasets. Its fit is a single SVD (seconds on \(M,N\sim 10^4\), scaling as \(\mathcal {O}(\min (MN^2,M^2N))\)), it has no random seed, and the same fitted projection \(\bW _K\) can be applied to streaming or test data. Use it as a preprocessor that decorrelates features and trims dimension before regression, classification, or clustering, and as a quick sanity-check plot. Its blind spots are that it is linear (it cannot unfold curved manifolds) and unsupervised (it may drop low-variance directions that are discriminative for \(\by \)).

• • Use t-SNE, UMAP, or PaCMAP when the goal is a 2D or 3D plot that reveals cluster structure that PCA hides. Prefer t-SNE only for small datasets (\(M\) up to a few thousand) where you mostly care about whether clusters exist. Prefer UMAP as the modern default for visualisation: it scales to millions of points, retains more of the global layout than t-SNE, and can embed new samples without refitting. Prefer PaCMAP when the relative arrangement of clusters carries meaning (hierarchies, smooth gradients between groups). In all three cases, treat absolute distances, cluster sizes, and inter-cluster gaps as not meaningful, fix the random seed for reproducibility, and verify that the layout is stable across a few seeds and hyper-parameter values before drawing conclusions.

Further Reading

• • Matlab Uniform Manifold Approximation and Projection (UMAP) for dimension reduction