4  Distances, Dimensionality Reduction, and (Non-)Linear Embeddings

Chapter Aim

Chapters 02 and 03 built the statistical foundation for preprocessing high-dimensional biological data: generative assumptions motivate normalization, variance stabilization, residuals, and log-ratio transformations. Chapter 04 takes the next step: after preprocessing, observations are treated as points in a high-dimensional space, and we ask whether their geometry reveals structure.

The term geometry is used deliberately. A PCA plot, an MDS plot, a t-SNE embedding, or a UMAP embedding is not a neutral picture of the data. It is the result of a sequence of modeling and preprocessing choices: a representation is chosen, distances or similarities are computed, and a lower-dimensional representation is optimized. The same biological samples can therefore look different under different transformations and distances. This variability is a statistical property of the analysis pipeline.

In this chapter, distances, PCA scores, and embeddings are computed from a chosen analysis representation, not directly from raw counts unless explicitly stated. Row \(i\) is written as \(x_i^\top \in \mathbb{R}^{1\times p}\), or equivalently \(x_i\in\mathbb{R}^p\) when it is used as a column vector in formulas.

TipNotation convention

Notation follows the shared convention in the notation chapter. Vectors are columns by default, row vectors are written with transposes, and dimensions should be checked whenever matrices are multiplied, transformed, modeled, or decomposed.

NoteMain external reference

The main book references are MSMB Multivariate Analysis, for matrices, SVD, PCA, biplots, and weighted PCA, and MSMB Heterogeneous Data, for ordination, MDS, batch effects, and nonlinear local methods. For visual interpretation, see MSMB Data Visualization. The exercises most closely linked to this chapter are Exercise Sheet 03, which works through Aitchison distance, MDS, Bray-Curtis dissimilarity, and t-SNE/UMAP examples, and Exercise Sheet 04, which connects PCA, neighborhood graphs, UMAP, t-SNE, and clustering workflows (Exercise Sheet 03 2026; Exercise Sheet 04 2026).

Learning Goals

After this chapter, students should be able to explain why distance choices encode statistical assumptions, distinguish a metric distance from a more general dissimilarity, choose distances appropriate for transformed continuous data, count data, binary data, and compositions, derive PCA from centering and the singular value decomposition, compute classical MDS from a distance matrix, interpret non-metric MDS as rank-preserving ordination, explain ISOMAP as graph-geodesic MDS, and describe what t-SNE and UMAP optimize without treating their plots as direct evidence of biological clusters.

4.1 Geometry Starts With Preprocessing

A common exploratory workflow is: compute distances between observations, produce a low-dimensional embedding, and inspect whether the resulting display suggests groups, gradients, outliers, or batch effects. The mathematical version is the map

\[\begin{equation} C \longrightarrow X \longrightarrow D \longrightarrow H. \label{eq:ch04-geometry-workflow} \end{equation}\]

Here \(C\) is the raw count matrix, \(X\) is the normalized and transformed analysis matrix, \(D\in\mathbb{R}^{n\times n}\) is a matrix of pairwise dissimilarities between observations, and \(H\in\mathbb{R}^{n\times k}\) is a low-dimensional representation, usually with \(k=2\) or \(k=3\) for visualization. The row \(h_i^\top\) contains the embedded coordinates of observation \(i\).

This sequence is useful because it separates two different questions. Chapter 03 asked how the data should be transformed so that noise and scale are handled responsibly. Chapter 04 asks how similarity should be measured once the observations are on that scale. For RNA-seq counts, a log-like or variance-stabilized \(X\) often makes Euclidean geometry more meaningful. For microbiome compositions, a CLR-transformed \(X\) gives Euclidean distances the interpretation of Aitchison distances. For binary mutation profiles, a distance that treats shared zeros carefully may be more appropriate than Euclidean distance. Thus, the distance is not chosen after the statistics are finished; it is part of the statistical modeling chain.

4.2 Distances And Dissimilarities

A distance between two observations is a function \(d(x_i,x_{i'})\) that assigns a nonnegative number to a pair of rows. Collecting all pairwise distances gives

\[\begin{equation} D=(d_{ii'})_{i,i'=1}^n, \qquad d_{ii'}=d(x_i,x_{i'}). \label{eq:ch04-distance-matrix} \end{equation}\]

If the columns rather than the rows are compared, we write the feature distance matrix as \(D_f\in\mathbb{R}^{p\times p}\). This distinction matters: distances between samples answer a different question than distances between genes, taxa, proteins, or peaks.

Mathematically, a metric distance satisfies four properties:

\[\begin{equation} \begin{aligned} &d(x_i,x_{i'})\geq 0,\\ &d(x_i,x_{i'})=0 \Longleftrightarrow x_i=x_{i'},\\ &d(x_i,x_{i'})=d(x_{i'},x_i),\\ &d(x_i,x_{i''})\leq d(x_i,x_{i'})+d(x_{i'},x_{i''}). \end{aligned} \label{eq:ch04-metric-properties} \end{equation}\]

These are nonnegativity, identity of indiscernibles, symmetry, and the triangle inequality. Many useful biological dissimilarities do not satisfy all four properties. We still use them, but we should call them dissimilarities rather than distances when the distinction matters. This becomes important for methods such as classical MDS, because non-Euclidean dissimilarities can produce negative eigenvalues and distorted low-dimensional coordinates.

For transformed continuous data, the default distance is often Euclidean:

\[\begin{equation} d_{\mathrm{E}}(x_i,x_{i'}) = \|x_i-x_{i'}\|_2 = \left\{ \sum_{j=1}^p (x_{ij}-x_{i'j})^2 \right\}^{1/2}. \label{eq:ch04-euclidean-distance} \end{equation}\]

Euclidean distance is natural when differences along the feature axes are meaningful and comparable. It is also the geometry behind ordinary PCA. But if one gene has much larger variance than all others, Euclidean distance will be dominated by that gene. A common response is to center and scale columns before computing distances. If \(\bar{x}_{\cdot j}\) and \(\hat{\sigma}_j\) are the empirical mean and standard deviation of feature \(j\), the standardized value is

\[\begin{equation} x^{\mathrm{std}}_{ij} = \frac{x_{ij}-\bar{x}_{\cdot j}}{\hat{\sigma}_j}. \label{eq:ch04-standardized-feature} \end{equation}\]

Euclidean distance on standardized features is equivalent to a weighted Euclidean distance on centered features:

\[\begin{equation} d_{\mathrm{WE}}(x_i,x_{i'}) = \left\{ (x_i-x_{i'})^\top \Omega (x_i-x_{i'}) \right\}^{1/2}, \qquad \Omega=\operatorname{diag}\left(\hat{\sigma}_1^{-2},\ldots,\hat{\sigma}_p^{-2}\right). \label{eq:ch04-weighted-euclidean-distance} \end{equation}\]

Here \(\Omega\) is a feature-weight matrix. Standardization can be helpful when features are measured on comparable biological scales but have different variances. It can be harmful when high-variance features are precisely the features that carry the biological signal. This is why preprocessing and distance choice should be stated explicitly in every analysis.

Correlation and cosine dissimilarities emphasize direction rather than absolute magnitude. The row-centered correlation dissimilarity is

\[\begin{equation} d_{\mathrm{cor}}(x_i,x_{i'}) = 1- \frac{ \sum_{j=1}^p (x_{ij}-\bar{x}_{i\cdot})(x_{i'j}-\bar{x}_{i'\cdot}) }{ \left\{\sum_{j=1}^p (x_{ij}-\bar{x}_{i\cdot})^2\right\}^{1/2} \left\{\sum_{j=1}^p (x_{i'j}-\bar{x}_{i'\cdot})^2\right\}^{1/2} }, \label{eq:ch04-correlation-dissimilarity} \end{equation}\]

where \(\bar{x}_{i\cdot}=p^{-1}\sum_{j=1}^p x_{ij}\). The cosine dissimilarity is

\[\begin{equation} d_{\mathrm{cos}}(x_i,x_{i'}) = 1- \frac{x_i^\top x_{i'}}{\|x_i\|_2\|x_{i'}\|_2}. \label{eq:ch04-cosine-dissimilarity} \end{equation}\]

Cosine dissimilarity is common when the angle between expression profiles matters more than the magnitude. In single-cell workflows it is sometimes used after normalization and PCA because residual library-size or total-expression effects can otherwise influence Euclidean neighborhoods. Correlation and cosine dissimilarities are useful, but they are not interchangeable with Euclidean distance: they change the question from “how far apart are these observations?” to “how similar are their profiles up to centering or scaling?”

For nonnegative abundance data, especially ecological and microbiome data, Bray-Curtis dissimilarity is widely used. For \(x_{ij}\geq 0\),

\[\begin{equation} d_{\mathrm{BC}}(x_i,x_{i'}) = \frac{ \sum_{j=1}^p |x_{ij}-x_{i'j}| }{ \sum_{j=1}^p (x_{ij}+x_{i'j}) }. \label{eq:ch04-bray-curtis-dissimilarity} \end{equation}\]

Equivalently, because \(|a-b|=a+b-2\min(a,b)\) for \(a,b\geq 0\),

\[\begin{equation} d_{\mathrm{BC}}(x_i,x_{i'}) = 1- \frac{ 2\sum_{j=1}^p \min(x_{ij},x_{i'j}) }{ \sum_{j=1}^p x_{ij}+\sum_{j=1}^p x_{i'j} }. \label{eq:ch04-bray-curtis-overlap-form} \end{equation}\]

This form makes the ecological interpretation clear: two observations are similar when they share many abundances. Bray-Curtis is a dissimilarity, not a fully metric Euclidean distance. It is often sensible for nonnegative count-like or relative-abundance data, but it does not by itself solve the compositional problem discussed in Chapters 02 and 03.

For compositions, the more principled geometry is Aitchison geometry. If \(\pi_i\in\Delta^{p-1}\) is a strictly positive composition, its centered log-ratio transform is

\[\begin{equation} \operatorname{clr}(\pi_i)_j = \log \pi_{ij} - \frac{1}{p}\sum_{\ell=1}^p \log \pi_{i\ell}, \qquad j=1,\ldots,p. \label{eq:ch04-clr-transform} \end{equation}\]

The Aitchison distance between two positive compositions is Euclidean distance after CLR transformation:

\[\begin{equation} d_{\mathrm{A}}(\pi_i,\pi_{i'}) = \left\| \operatorname{clr}(\pi_i) - \operatorname{clr}(\pi_{i'}) \right\|_2. \label{eq:ch04-aitchison-distance} \end{equation}\]

This is the distance used in Exercise Sheet 03 for 16S data after CLR transformation (Exercise Sheet 03 2026). It is also the natural continuation of the multinomial, Dirichlet-multinomial, and logistic-normal composition models from Chapter 02. Zeros must be handled before applying the logarithm, usually by a clearly stated pseudocount, zero-replacement method, or feature-filtering rule.

For binary data, such as presence-absence features or mutation indicators, the relevant geometry can be different again. If \(x_{ij}\in\{0,1\}\), the Hamming distance counts mismatches:

\[\begin{equation} d_{\mathrm{Ham}}(x_i,x_{i'}) = \sum_{j=1}^p \mathbf{1}\{x_{ij}\neq x_{i'j}\}. \label{eq:ch04-hamming-distance} \end{equation}\]

The Jaccard dissimilarity ignores shared absences and compares the number of mismatches among features present in at least one of the two observations:

\[\begin{equation} d_{\mathrm{Jac}}(x_i,x_{i'}) = 1- \frac{ \sum_{j=1}^p \mathbf{1}\{x_{ij}=1,\ x_{i'j}=1\} }{ \sum_{j=1}^p \mathbf{1}\{x_{ij}=1\ \text{or}\ x_{i'j}=1\} }. \label{eq:ch04-jaccard-dissimilarity} \end{equation}\]

This distinction is important for sparse binary biological data: if most genes are not mutated, most proteins are not detected, or most taxa are absent, shared zeros can dominate Hamming distance without carrying much biological information.

4.3 From Distances To Similarities And Graphs

Some methods work with distances, while others work with similarities, kernels, or neighborhood graphs. A common way to turn Euclidean distances into similarities is the Gaussian kernel

\[\begin{equation} K_{ii'} = \exp\left( - \frac{d_{\mathrm{E}}(x_i,x_{i'})^2}{2\tau^2} \right), \qquad \tau>0. \label{eq:ch04-gaussian-kernel} \end{equation}\]

The parameter \(\tau\) controls the scale at which observations are considered similar. A small \(\tau\) emphasizes very local neighborhoods; a large \(\tau\) makes the similarity more global.

Modern single-cell workflows often construct a \(q\)-nearest-neighbor graph rather than working with all pairwise distances directly. Let \(\mathcal{N}_q(i)\) denote the set of the \(q\) nearest neighbors of observation \(i\) under a chosen distance. A simple directed adjacency matrix is

\[\begin{equation} A_{ii'} = \mathbf{1}\{i'\in\mathcal{N}_q(i)\}, \qquad A\in\{0,1\}^{n\times n}. \label{eq:ch04-knn-adjacency} \end{equation}\]

The nodes of this graph are observations, usually cells or samples. This graph view is the bridge from Chapter 04 to Chapter 05 on clustering: graph-based clustering methods do not cluster the original matrix directly; they cluster a graph whose edges were determined by preprocessing, dimension reduction, and a distance choice.

4.4 PCA As Linear Dimension Reduction

Principal component analysis is the basic linear method for summarizing high-dimensional continuous data. It is most meaningful when \(X\) is already on a scale where Euclidean geometry is sensible. For count data, this usually means that \(X\) is log-transformed, variance-stabilized, residualized, or otherwise transformed as in Chapter 03.

PCA begins by centering each feature. Let

\[\begin{equation} \bar{x} = \frac{1}{n}X^\top \mathbf{1}_n \in\mathbb{R}^{p}, \label{eq:ch04-column-mean-vector} \end{equation}\]

where \(\mathbf{1}_n\) is the \(n\)-vector of ones. The centered matrix is

\[\begin{equation} X_c = X-\mathbf{1}_n\bar{x}^\top \in\mathbb{R}^{n\times p}. \label{eq:ch04-centered-matrix} \end{equation}\]

If the features should contribute on comparable variance scales, one may instead use \(X_s=X_c S_x^{-1}\) with

\[\begin{equation} S_x = \operatorname{diag}(\hat{\sigma}_1,\ldots,\hat{\sigma}_p). \label{eq:ch04-feature-scaling-matrix} \end{equation}\]

In this chapter, \(X_c\) denotes centered data and \(X_s\) denotes centered and scaled data. We write the PCA equations for \(X_c\), but the same formulas apply to \(X_s\) if scaling is chosen.

The first principal loading is the unit vector \(u\in\mathbb{R}^p\) that maximizes the variance of the projected observations:

\[\begin{equation} p_1 = \underset{u\in\mathbb{R}^{p}:\ \|u\|_2=1}{\operatorname{argmax}} \ \|X_cu\|_2^2 = \underset{u\in\mathbb{R}^{p}:\ \|u\|_2=1}{\operatorname{argmax}} \ u^\top X_c^\top X_c u. \label{eq:ch04-first-pc-optimization} \end{equation}\]

Subsequent principal loadings solve the same problem subject to orthogonality constraints. Computationally, PCA is obtained from the singular value decomposition

\[\begin{equation} X_c = U\Sigma V^\top, \label{eq:ch04-svd} \end{equation}\]

where \(r=\operatorname{rank}(X_c)\), \(U\in\mathbb{R}^{n\times r}\) has orthonormal columns, \(V\in\mathbb{R}^{p\times r}\) has orthonormal columns, and \(\Sigma=\operatorname{diag}(\sigma_1,\ldots,\sigma_r)\) with \(\sigma_1\geq\cdots\geq\sigma_r>0\).

Following the notation fixed for this lecture script, the rank-\(k\) PCA approximation is written as

\[\begin{equation} X_c \approx T_k P_k^\top, \qquad T_k=U_k\Sigma_k\in\mathbb{R}^{n\times k}, \qquad P_k=V_k\in\mathbb{R}^{p\times k}. \label{eq:ch04-pca-factorization} \end{equation}\]

The rows of \(T_k\) are the PCA scores or observation coordinates. The columns of \(P_k\) are the loadings or feature directions. This convention keeps observation coordinates and feature weights dimensionally distinct.

The variance explained by component \(k\) is proportional to \(\sigma_k^2\). The fraction of total centered variance explained by component \(k\) is

\[\begin{equation} \operatorname{PVE}_k = \frac{\sigma_k^2}{\sum_{\ell=1}^{r}\sigma_\ell^2}. \label{eq:ch04-pca-proportion-variance-explained} \end{equation}\]

The cumulative fraction explained by the first \(k\) components is

\[\begin{equation} \operatorname{CPVE}_k = \frac{\sum_{\ell=1}^{k}\sigma_\ell^2}{\sum_{\ell=1}^{r}\sigma_\ell^2}. \label{eq:ch04-pca-cumulative-variance-explained} \end{equation}\]

PCA is often introduced as finding directions of maximal variance, but an equivalent view is reconstruction. Among all rank-\(k\) matrices, the truncated SVD gives the best approximation to \(X_c\) in squared-error loss:

\[\begin{equation} T_kP_k^\top = \underset{\operatorname{rank}(M)\leq k}{\operatorname{argmin}} \ \|X_c-M\|_F^2. \label{eq:ch04-eckart-young} \end{equation}\]

This is why PCA is so useful as a denoising and visualization tool. It summarizes the dominant linear variation in \(X_c\). But it also explains the limitation: PCA is optimized for Euclidean squared-error reconstruction, not for preserving every biological distinction. If a biological signal is nonlinear, sparse, weak relative to technical variation, or present only in rare cell types, it may not dominate the first two principal components.

For Euclidean distances, PCA and classical MDS are closely related. If one applies classical MDS to Euclidean distances computed from centered data, the resulting principal coordinates are equivalent to PCA scores up to rotation and sign changes. This equivalence is one reason that PCA, SVD, biplots, and related multivariate methods are treated together in MSMB Multivariate Analysis.

4.5 Classical MDS And PCoA

Multidimensional scaling starts from a distance or dissimilarity matrix rather than directly from the feature matrix. Given \(D=(d_{ii'})\in\mathbb{R}^{n\times n}\), the goal is to find coordinates \(H\in\mathbb{R}^{n\times k}\) such that distances in the embedding approximate the original dissimilarities:

\[\begin{equation} \|h_i-h_{i'}\|_2 \approx d_{ii'}, \qquad 1\leq i<i'\leq n. \label{eq:ch04-mds-distance-goal} \end{equation}\]

Classical MDS, also called principal coordinates analysis (PCoA), proceeds by converting squared distances into an estimated centered inner-product matrix. Let

\[\begin{equation} J = I_n-\frac{1}{n}\mathbf{1}_n\mathbf{1}_n^\top \label{eq:ch04-centering-matrix} \end{equation}\]

be the centering matrix, and let \(D^{\circ 2}\) denote elementwise squaring:

\[\begin{equation} \left(D^{\circ 2}\right)_{ii'} = d_{ii'}^2. \label{eq:ch04-squared-distance-matrix} \end{equation}\]

The classical MDS matrix is

\[\begin{equation} B = -\frac{1}{2} JD^{\circ 2}J. \label{eq:ch04-classical-mds-gram} \end{equation}\]

If \(D\) is a Euclidean distance matrix, then \(B\) is the centered Gram matrix of the original points. We then compute the eigendecomposition

\[\begin{equation} B = Q\Lambda Q^\top, \label{eq:ch04-mds-eigendecomposition} \end{equation}\]

where the eigenvalues are ordered from largest to smallest. If the first \(k\) eigenvalues are positive, the \(k\)-dimensional classical MDS coordinates are

\[\begin{equation} H_k = Q_k\Lambda_k^{1/2} \in\mathbb{R}^{n\times k}. \label{eq:ch04-classical-mds-coordinates} \end{equation}\]

For Euclidean distances, this reconstructs the original centered geometry in enough dimensions. For non-Euclidean dissimilarities, negative eigenvalues can occur. They are not just numerical inconvenience; they indicate that the dissimilarities cannot be represented exactly as Euclidean distances. In practice, PCoA plots often keep the leading positive axes and report how much of the positive eigenspectrum they explain.

The proportion of positive eigenspectrum represented by coordinate \(k\) is

\[\begin{equation} \operatorname{PCoA\text{-}PVE}_k = \frac{\lambda_k}{\sum_{\ell:\lambda_\ell>0}\lambda_\ell}, \qquad \lambda_k>0. \label{eq:ch04-pcoa-variance-explained} \end{equation}\]

Exercise Sheet 03 applies this workflow to Aitchison distances between microbiome samples, where the first two PCoA axes explain only a moderate part of the total variation (Exercise Sheet 03 2026). A two-dimensional display is therefore not equivalent to a complete low-dimensional description.

4.6 Non-Metric MDS

Classical MDS tries to preserve numerical dissimilarities. Non-metric MDS (NMDS) relaxes this requirement. It assumes that the ranks of the dissimilarities are more trustworthy than their absolute values. In NMDS, one seeks coordinates \(H\in\mathbb{R}^{n\times k}\) and a monotone function \(f\) such that

\[\begin{equation} \|h_i-h_{i'}\|_2 \approx f(d_{ii'}). \label{eq:ch04-nmds-monotone-goal} \end{equation}\]

A common stress criterion is

\[\begin{equation} \operatorname{Stress}(H) = \left[ \frac{ \sum_{i<i'} \left( \|h_i-h_{i'}\|_2 - f(d_{ii'}) \right)^2 }{ \sum_{i<i'} \|h_i-h_{i'}\|_2^2 } \right]^{1/2}. \label{eq:ch04-nmds-stress} \end{equation}\]

The function \(f\) is constrained to be monotone, so if \(d_{ii'}<d_{\ell m}\), then \(f(d_{ii'})\leq f(d_{\ell m})\). NMDS is popular in community ecology because ecological dissimilarities often have meaningful orderings even when their numerical scale is hard to interpret. The optimization is non-convex, axes are arbitrary, and repeated runs may differ. Stress values and sensitivity checks are therefore part of the analysis.

The practical distinction between PCoA and NMDS is simple. PCoA asks whether the actual dissimilarities can be represented by Euclidean coordinates. NMDS asks whether the rank order of dissimilarities can be represented by Euclidean coordinates. Exercise Sheet 03 explicitly contrasts these two views for Aitchison distances (Exercise Sheet 03 2026).

4.7 The High-Dimensional Problem

Distances in high dimensions can become less informative. One simple way to see this is to consider independent standardized noise features. Let

\[\begin{equation} X_{ij}\sim \mathcal{N}(0,1) \qquad \text{independently for } j=1,\ldots,p. \label{eq:ch04-independent-standard-normal-features} \end{equation}\]

For two independent observations \(X_i\) and \(X_{i'}\), the squared Euclidean distance is

\[\begin{equation} \|X_i-X_{i'}\|_2^2 = \sum_{j=1}^p (X_{ij}-X_{i'j})^2. \label{eq:ch04-squared-distance-random} \end{equation}\]

Since \(X_{ij}-X_{i'j}\sim\mathcal{N}(0,2)\), its expectation is

\[\begin{equation} \mathbb{E}\left[ \|X_i-X_{i'}\|_2^2 \right] = 2p. \label{eq:ch04-expected-squared-distance} \end{equation}\]

As \(p\) grows, distances can concentrate around their typical value unless there is structured signal. This does not mean high-dimensional distance analysis is useless. It means that feature selection, transformation, dimensionality reduction, denoising, and biological prior knowledge often determine whether the geometry is informative. This is why single-cell workflows commonly compute variable features, scale data, run PCA, and then construct neighbor graphs in PCA space rather than in the full raw feature space.

4.8 Nonlinear Embeddings

PCA and classical MDS are global linear or Euclidean methods. Nonlinear embedding methods aim to preserve local neighborhoods when the data may lie near a curved low-dimensional structure. A standard Swiss-roll example makes the issue visible: Euclidean distances through the ambient space may not reflect distances along the underlying manifold.

The generic nonlinear embedding problem can be written as

\[\begin{equation} H = f_{\theta}(X), \qquad H\in\mathbb{R}^{n\times k}, \qquad k\ll p. \label{eq:ch04-nonlinear-embedding-map} \end{equation}\]

Unlike PCA, most nonlinear embeddings do not produce a simple loading matrix that tells us how each feature contributes to each axis. The coordinates are optimized to satisfy a neighborhood-preservation objective. Consequently, axis labels such as “UMAP1” and “t-SNE2” should not be interpreted like principal components.

4.8.1 ISOMAP

ISOMAP is one of the clearest examples of manifold learning because it modifies classical MDS in only one essential way (Tenenbaum et al. 2000). Instead of applying MDS to direct Euclidean distances, it first approximates distances along the data manifold by shortest-path distances on a neighborhood graph. The method is motivated by situations where the ambient distance \(\|x_i-x_{i'}\|_2\) cuts through empty space, while the meaningful distance follows a curved surface.

Let \(\mathcal{N}_q(i)\) denote the \(q\) nearest neighbors of observation \(i\) under a chosen input distance \(d\). ISOMAP constructs a weighted graph with edge weights

\[\begin{equation} a_{ii'} = \begin{cases} d(x_i,x_{i'}), & i'\in\mathcal{N}_q(i)\ \text{or}\ i\in\mathcal{N}_q(i'),\\ \infty, & \text{otherwise}. \end{cases} \label{eq:ch04-isomap-neighborhood-graph} \end{equation}\]

The graph-geodesic distance between two observations is then the shortest-path distance

\[\begin{equation} d_{\mathrm{geo}}(x_i,x_{i'}) = \min_{\gamma:i\leadsto i'} \sum_{(u,v)\in\gamma} a_{uv}, \label{eq:ch04-isomap-geodesic-distance} \end{equation}\]

where \(\gamma:i\leadsto i'\) ranges over all paths in the neighborhood graph from \(i\) to \(i'\). Classical MDS is then applied to the matrix of squared graph-geodesic distances. With \(D_{\mathrm{geo}}^{(2)}=(d_{\mathrm{geo}}(x_i,x_{i'})^2)_{i,i'=1}^n\) and \(J=I_n-n^{-1}\mathbf{1}\mathbf{1}^\top\), the ISOMAP inner-product matrix is

\[\begin{equation} B_{\mathrm{ISO}} = -\frac{1}{2}J D_{\mathrm{geo}}^{(2)} J. \label{eq:ch04-isomap-inner-product} \end{equation}\]

The final coordinates are obtained from the leading positive eigenvalues and eigenvectors of \(B_{\mathrm{ISO}}\), exactly as in classical MDS. This makes ISOMAP conceptually useful: it separates the nonlinear part, which is the graph-geodesic distance construction, from the embedding part, which is ordinary spectral decomposition.

The method is sensitive to the neighborhood size \(q\). If \(q\) is too small, the graph may become disconnected and geodesic distances are undefined between components. If \(q\) is too large, the graph contains shortcuts and the method collapses back toward ordinary Euclidean MDS. In high-dimensional biological data, ISOMAP is therefore best read as a geometric idea and diagnostic tool rather than as a default visualization method: preprocessing, denoising, and neighborhood construction strongly determine the result.

4.8.2 t-SNE

t-distributed stochastic neighbor embedding (t-SNE) converts distances into probability distributions over pairs of observations and then finds low-dimensional coordinates whose pairwise probabilities are similar (Maaten and Hinton 2008). For each observation \(i\), high-dimensional similarities are often defined as conditional probabilities

\[\begin{equation} p_{i'|i} = \frac{ \exp\left(-\|x_i-x_{i'}\|_2^2/(2\tau_i^2)\right) }{ \sum_{\ell\neq i} \exp\left(-\|x_i-x_{\ell}\|_2^2/(2\tau_i^2)\right) }, \qquad p_{i|i}=0. \label{eq:ch04-tsne-conditional-probabilities} \end{equation}\]

The bandwidth \(\tau_i\) is chosen separately for each observation so that the effective neighborhood size matches a user-specified perplexity. If \(P_i\) denotes the conditional distribution over neighbors of observation \(i\), the perplexity is

\[\begin{equation} \operatorname{Perp}(P_i) = 2^{-\sum_{i'\neq i}p_{i'|i}\log_2 p_{i'|i}}. \label{eq:ch04-tsne-perplexity} \end{equation}\]

Low perplexity emphasizes very local structure; high perplexity allows broader neighborhoods to influence the embedding. Exercise Sheet 03 varies this parameter on the Moignard single-cell data and shows how the apparent cluster structure changes (Exercise Sheet 03 2026).

The conditional probabilities are symmetrized:

\[\begin{equation} p_{ii'} = \frac{p_{i'|i}+p_{i|i'}}{2n}. \label{eq:ch04-tsne-symmetric-probabilities} \end{equation}\]

In the low-dimensional embedding, t-SNE uses a heavy-tailed Student-type kernel:

\[\begin{equation} q_{ii'} = \frac{ \left(1+\|h_i-h_{i'}\|_2^2\right)^{-1} }{ \sum_{\ell\neq m} \left(1+\|h_\ell-h_m\|_2^2\right)^{-1} }, \qquad q_{ii}=0. \label{eq:ch04-tsne-low-dimensional-probabilities} \end{equation}\]

The objective is the Kullback-Leibler divergence from \(P\) to \(Q\):

\[\begin{equation} \operatorname{KL}(P\|Q) = \sum_{i\neq i'} p_{ii'} \log\left( \frac{p_{ii'}}{q_{ii'}} \right). \label{eq:ch04-tsne-kl-objective} \end{equation}\]

The asymmetry of this objective is important. If two points are close in the high-dimensional probability distribution, t-SNE strongly penalizes placing them far apart in the embedding. If two points are far apart in high dimensions, it is less concerned with their exact low-dimensional distance. This is why t-SNE is powerful for local cluster visualization but unreliable for interpreting global distances, cluster sizes, and empty space between clusters. Initialization and optimization details also matter; Kobak and Linderman emphasize that initialization can strongly affect apparent global structure in both t-SNE and UMAP (Kobak and Linderman 2021).

4.8.3 UMAP

Uniform manifold approximation and projection (UMAP) also begins with local neighborhoods, but it represents the high-dimensional data as a weighted graph and then optimizes a low-dimensional graph representation (McInnes et al. 2018). For each observation \(i\), let \(\rho_i\) be the distance to its nearest neighbor and let \(\tau_i>0\) be a local scale. For \(i'\in\mathcal{N}_q(i)\), a simplified form of the directed high-dimensional edge weight from \(i\) to \(i'\) is

\[\begin{equation} a_{ii'} = \exp\left( - \frac{\max\{0,d(x_i,x_{i'})-\rho_i\}}{\tau_i} \right). \label{eq:ch04-umap-directed-weight} \end{equation}\]

The local scale \(\tau_i\) is chosen so that the effective number of neighbors is controlled by the parameter \(q\), usually called n_neighbors in software. Directed weights are then combined into an undirected fuzzy graph, often using the probabilistic union

\[\begin{equation} w_{ii'}^{\mathrm{sym}} = a_{ii'}+a_{i'i}-a_{ii'}a_{i'i}. \label{eq:ch04-umap-symmetric-weight} \end{equation}\]

In the low-dimensional embedding, UMAP assigns a similarity to each pair of coordinates. A common parametric form is

\[\begin{equation} \tilde{w}_{ii'} = \left( 1+a\|h_i-h_{i'}\|_2^{2b} \right)^{-1}, \qquad a>0,\ b>0. \label{eq:ch04-umap-low-dimensional-weight} \end{equation}\]

The embedding minimizes a cross-entropy between high-dimensional graph weights and low-dimensional graph weights:

\[\begin{equation} \mathcal{L}_{\mathrm{UMAP}}(H) = \sum_{i<i'} \left[ w_{ii'}^{\mathrm{sym}} \log\left(\frac{w_{ii'}^{\mathrm{sym}}}{\tilde{w}_{ii'}}\right) + \left(1-w_{ii'}^{\mathrm{sym}}\right) \log\left( \frac{1-w_{ii'}^{\mathrm{sym}}}{1-\tilde{w}_{ii'}} \right) \right]. \label{eq:ch04-umap-cross-entropy} \end{equation}\]

This formula explains why UMAP is sensitive to the distance metric, the number of neighbors, the minimum-distance parameter, initialization, and random seed. The embedding is not a direct measurement. It is the outcome of graph construction and optimization. Becht and colleagues popularized UMAP for single-cell visualization, and later work has clarified how UMAP and t-SNE fit into a broader family of attraction-repulsion neighbor embedding methods (Becht et al. 2019; Böhm et al. 2023).

Exercise Sheet 03 compares UMAP distance metrics in a Seurat workflow, and Exercise Sheet 04 uses PCA and graph-based workflows that prepare the ground for clustering (Exercise Sheet 03 2026; Exercise Sheet 04 2026). The key lesson is not that one embedding is always better. It is that changing the metric changes the nearest-neighbor graph, and changing the graph changes the embedding.

4.9 Interpreting Embeddings

A two-dimensional embedding should be read as an exploratory summary. It can suggest structure worth modeling, but it is not itself a model-based test. Several interpretation rules are worth making explicit.

First, local neighborhoods are usually more trustworthy than global distances in t-SNE and UMAP. ISOMAP tries to preserve larger-scale graph-geodesic distances, but these distances are only meaningful if the neighborhood graph is a reasonable approximation to the underlying manifold. If two nearby cells have similar neighbors, that may indicate related transcriptional states. But the distance between two far-away islands, or the relative sizes of two islands, is not generally meaningful.

Second, visible clusters are not automatically biological populations. Batch effects, sequencing technology, library size, cell-cycle state, mitochondrial content, feature selection, and preprocessing can all create apparent separation. Exercise Sheet 03 illustrates this with microbiome MDS plots in which sequencing technology explains a major axis of variation (Exercise Sheet 03 2026).

Third, the scale of the input matters. Applying Euclidean PCA to raw counts is usually a poor default because large counts and library-size effects dominate the geometry. Applying Euclidean distance after CLR transformation has a compositional interpretation through Aitchison distance. Applying UMAP to PCA scores means the neighborhood graph is built in a denoised linear subspace, not in the original gene space.

Finally, embedding coordinates should be linked back to the original features and metadata. PCA loadings, feature correlations with coordinates, marker genes, batch labels, covariates, and external annotations connect a low-dimensional display to statistical analysis. In the multivariate workflow, dimension reduction is an intermediate representation for interrogating the data (MSMB Multivariate Analysis; MSMB Heterogeneous Data).

Summary

The central object of this chapter is the geometry induced by an analysis matrix \(X\). Distances and dissimilarities translate rows of \(X\) into pairwise comparisons. PCA summarizes dominant linear variation. Classical MDS and PCoA represent a distance matrix in Euclidean coordinates when possible. NMDS preserves ranks rather than raw dissimilarity values. ISOMAP applies classical MDS to shortest-path distances on a neighborhood graph. t-SNE and UMAP construct local probability or graph representations and optimize low-dimensional coordinates to preserve neighborhood structure.

Modeling, transformation, distance choice, and embedding form a single analysis chain. Chapter 02 describes plausible data-generating assumptions. Chapter 03 shows how those assumptions motivate transformations. Chapter 04 shows how transformed data become geometry. If the geometry is chosen without regard to the data type and preprocessing scale, the resulting display may be statistically misleading. If the geometry is chosen deliberately, embeddings become useful exploratory tools for forming hypotheses, diagnosing confounding, and preparing for clustering.

References

Becht, Etienne, Leland McInnes, John Healy, et al. 2019. “Dimensionality Reduction for Visualizing Single-Cell Data Using UMAP.” Nature Biotechnology 37 (1): 38–44. https://doi.org/10.1038/nbt.4314.
Böhm, Jan Niklas, Philipp Berens, and Dmitry Kobak. 2023. A Unifying Perspective on Neighbor Embeddings Along the Attraction-Repulsion Spectrum. https://arxiv.org/abs/2007.08902.
Exercise Sheet 03. 2026. Exercise Sheet 03 Solutions: Normalization and Low Dimensional Representation of 16S Sequencing. https://bio-datascience.github.io/ahbd/assets/exercises/AHDBD_SS26_Exercise03_Solution.html.
Exercise Sheet 04. 2026. Exercise Sheet 04 Solutions: Hierarchical Clustering and Graph-Based Clustering of High-Dimensional Biological Data. https://bio-datascience.github.io/ahbd/assets/exercises/AHDBD_SS26_Exercise04_Solution.html.
Kobak, Dmitry, and George C. Linderman. 2021. “Initialization Is Critical for Preserving Global Data Structure in Both t-SNE and UMAP.” Nature Biotechnology 39 (2): 156–57. https://doi.org/10.1038/s41587-020-00809-z.
Maaten, Laurens van der, and Geoffrey Hinton. 2008. “Visualizing Data Using t-SNE.” Journal of Machine Learning Research 9: 2579–605.
McInnes, Leland, John Healy, and James Melville. 2018. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. https://arxiv.org/abs/1802.03426.
Tenenbaum, Joshua B., Vin de Silva, and John C. Langford. 2000. “A Global Geometric Framework for Nonlinear Dimensionality Reduction.” Science 290 (5500): 2319–23. https://doi.org/10.1126/science.290.5500.2319.