9.2110 min read

Multidimensional Scaling

Multidimensional Scaling (MDS) reconstructs coordinates from only pairwise distances. Given the squared distance matrix $D$ with $D_{ij} = \|\mathbf{a}_i - \mathbf{a}_j\|^2$ , the double-centering formula $G = -\frac{1}{2}HDH$ (where $H = I - \frac{1}{N}\mathbf{1}\mathbf{1}^\top$ ) recovers the Gram matrix $G = A^\top A$ .

Once $G$ is recovered, spectral decomposition gives principal coordinates — exactly as in Section 9.20. MDS works for any Euclidean distance matrix; if $G$ has negative eigenvalues, the distances are non-Euclidean and only an approximate embedding is possible.

Formal View

Theorem 9.8 (MDS) — Multidimensional Scaling

Given squared pairwise distances

D_{ij} = \|\mathbf{a}_i - \mathbf{a}_j\|^2

, the Gram matrix is recovered by double-centering:

G = -\tfrac{1}{2} H D H, \quad H = I_N - \tfrac{1}{N}\mathbf{1}\mathbf{1}^\top.

Principal coordinates follow from

G = V\Lambda_G V^\top

Why This Matters

MDS recovers spatial coordinates from purely relational data.

Psychometrics: recover a map of perceived similarities from subjective ratings.
Phylogenetics: reconstruct evolutionary coordinates from sequence distances.
Social networks: embed nodes from graph distances.

Learning Resources

Multidimensional scaling explained

StatQuest

Step-by-step MDS and how double-centering recovers coordinates.

15 min

MDS and PCA connection

MIT OpenCourseWare

MDS as a generalization of PCA to distance data.

45 min

Quiz

Question 1

Double-centering $G = -\frac{1}{2}HDH$ converts the squared distance matrix into:

Question 2

MDS can reconstruct coordinates from pairwise distances without ever knowing the original feature vectors.

Common Mistakes

Forgetting the centering matrix $H$ — using $-\frac{1}{2}D$ without $H$ gives wrong results.
Expecting MDS to work for non-Euclidean distances — $G$ will have negative eigenvalues and embedding is only approximate.