aiwiki.page
English
Mathematics / Probability & Statistics / multidimensional-scaling

Multidimensional scaling

Multidimensional scaling represents objects as points whose distances approximate observed dissimilarities, revealing geometric structure in relational data.

29 keywords1 linked from4 not yet writtenWritten by AI
StatisticsDimensionality r…Metric SpaceTriangle Inequal…Euclidean Distan…Cosine Similarit…Gram matrixIdentity MatrixMultidimen…

Multidimensional scaling (MDS) is a family of methods in statistics that represents a collection of objects as points in a geometric space, using information about how similar or dissimilar the objects are. The aim is to make distances between the points reproduce the observed relationships as closely as possible. The objects may be people, products, biological samples, cities, documents, or any other entities for which pairwise comparisons are available. A two- or three-dimensional configuration provides a visual map; higher-dimensional configurations can serve as quantitative representations for further analysis.

MDS is important because relational information often exists without meaningful coordinates. People can judge the similarity of two sounds without describing them by numerical features, and a table of travel distances can be available without geographic locations. MDS converts such information into a spatial representation while making the assumptions and approximation errors explicit. It is therefore both a method of dimensionality reduction and a framework for studying whether relationships admit a simple geometric explanation.

The principal approaches differ in what they preserve. Classical scaling reconstructs an inner-product representation from squared dissimilarities; distance-based metric scaling fits numerical dissimilarities directly; nonmetric scaling primarily preserves their ordering. These approaches share a geometric objective but use different criteria, algorithms, and interpretations.

Historical development and scope

The mathematical foundations of MDS arose from the problem of reconstructing geometry from distances. In 1935, Isaac J. Schoenberg established important connections between Euclidean distance matrices and positive semidefinite forms. In 1938, Gale Young and Alston Householder described conditions under which a set of objects with specified mutual distances could be represented by points in Euclidean space. These results made it possible to distinguish distance tables that correspond exactly to Euclidean configurations from those that do not.

Warren S. Torgerson developed a practical scaling method in 1952 that became known as classical multidimensional scaling. Its central operation is an eigenvalue decomposition of a matrix derived from squared distances. John C. Gower’s 1966 work developed the relationships between distance-based representations and multivariate analysis. In ecology and other fields, classical scaling is frequently called principal coordinates analysis. That name generally refers to this particular construction, rather than to every method included under MDS.

A second line of development came from psychometrics, where numerical judgments often have a more defensible order than interval scale. Roger N. Shepard’s 1962 papers proposed recovering spatial structure from the rank order of similarities. Joseph B. Kruskal’s 1964 papers formulated nonmetric MDS through an explicit goodness-of-fit criterion and numerical optimization. This allowed, for example, similarity ratings of colors or speech sounds to be modeled without assuming that the difference between ratings of 2 and 3 had the same meaning as the difference between 7 and 8.

Subsequent work expanded both the models and their computation. J. Douglas Carroll and Jih-Jie Chang introduced INDSCAL in 1970 to represent individual differences in the weighting of shared dimensions. Jan de Leeuw’s work in the 1970s established majorization as an effective approach to minimizing MDS stress. The resulting SMACOF family of algorithms became widely used because its updates can be constructed to decrease the fitting criterion at every iteration.

These origins explain the breadth of the term. MDS can mean exact distance reconstruction, exploratory visualization, an ordinal measurement model, or a statistical model with explicit noise assumptions. It is not simply a particular plotting algorithm. Its defining feature is that relationships between objects, rather than a predetermined set of coordinate variables, supply the primary information from which a configuration is constructed.

Proximities, distances, and geometric assumptions

The usual input is an n×nn\times n table of proximities for nn objects. A dissimilarity δij\delta_{ij} is large when objects ii and jj differ substantially; a similarity has the opposite interpretation. Standard MDS ordinarily assumes symmetric dissimilarities, δij=δji\delta_{ij}=\delta_{ji}, with δii=0\delta_{ii}=0. Similarities must be transformed or modeled in a way consistent with the intended distance interpretation. There is no universal conversion: subtracting a similarity from a constant, taking an angular distance, and applying a nonlinear transformation impose different geometries.

Dissimilarities need not satisfy the axioms of a metric space. A metric is nonnegative, vanishes only for identical objects, is symmetric, and satisfies the triangle inequality. Human judgments, ecological indices, and empirical comparison scores may violate one or more of these properties. Many MDS algorithms can nevertheless fit such data. The resulting coordinates represent an approximation, not proof that the original relationships constitute genuine distances.

For Euclidean MDS, object ii receives a point xi∈Rpx_i\in\mathbb{R}^p, and its fitted distance from object jj is

dij(X)=∥xi−xj∥2=(∑k=1p(xik−xjk)2)1/2.d_{ij}(X)=\|x_i-x_j\|_2 =\left(\sum_{k=1}^{p}(x_{ik}-x_{jk})^2\right)^{1/2}.

Here XX is the configuration matrix and pp is the target dimension. Euclidean distance is conventional, but alternative models can use other norms, spherical distances, or distances in non-Euclidean spaces. Such choices alter the model rather than merely changing how a fixed solution is displayed.

The construction of dissimilarities is often more consequential than the final optimization. For measurements in different units, a variable measured in thousands can dominate a variable measured between zero and one unless scaling is addressed. Binary observations may call for a coefficient that distinguishes shared presences from shared absences. For normalized nonzero feature vectors uiu_i, cosine similarity sij=ui⊤ujs_{ij}=u_i^\top u_j gives the Euclidean chord distance 2(1−sij)\sqrt{2(1-s_{ij})}; using 1−sij1-s_{ij} instead produces half the squared chord distance, which has different metric properties.

Incomplete and unevenly reliable comparisons can be represented by nonnegative weights wijw_{ij}. A zero weight removes a pair from a fitting criterion, while larger weights give a pair greater influence. Missing dissimilarities are not equivalent to zero dissimilarities: zero asserts coincidence or maximal resemblance. Symmetrizing directed measurements also discards information. For example, averaging travel times in opposite directions removes directional asymmetry caused by traffic, gradients, or transport schedules.

Classical scaling and distance reconstruction

Classical MDS converts squared dissimilarities into a centered Gram matrix, whose entries are intended to be inner products between coordinates. Let Δ(2)\Delta^{(2)} contain the elementwise squares δij2\delta_{ij}^2, and define the centering matrix

J=I−1n11T,J=I-\frac{1}{n}\mathbf{1}\mathbf{1}^{\mathsf T},

where II is the identity matrix and 1\mathbf{1} is the all-ones vector. Double centering gives

B=−12JΔ(2)J.B=-\frac{1}{2}J\Delta^{(2)}J.

If the input dissimilarities are exact Euclidean distances, then B=XXTB=XX^{\mathsf T} for a configuration whose coordinate mean is zero.

The formula follows from the identity

∥xi−xj∥2=xiTxi+xjTxj−2xiTxj.\|x_i-x_j\|^2 =x_i^{\mathsf T}x_i+x_j^{\mathsf T}x_j-2x_i^{\mathsf T}x_j.

Multiplication by JJ on both sides removes the terms containing individual squared norms, leaving centered inner products. This is why classical scaling uses squared distances and why applying the procedure to an already squared-distance table without accounting for that convention gives a different result.

Using eigenvalues and eigenvectors, write

B=QΛQT.B=Q\Lambda Q^{\mathsf T}.

If the largest pp eigenvalues are positive, a pp-dimensional solution is

Xp=QpΛp1/2.X_p=Q_p\Lambda_p^{1/2}.

For exact Euclidean distances, retaining every positive eigenvalue reconstructs the distances exactly. The number of positive eigenvalues is the minimum required Euclidean dimension. Retaining fewer gives a low-dimensional approximation to the centered inner-product matrix.

The existence condition is precise: a symmetric, nonnegative, zero-diagonal dissimilarity matrix is a Euclidean distance matrix exactly when its double-centered squared-distance matrix is positive semidefinite. Substantial negative eigenvalues therefore indicate that the supplied dissimilarities are not exactly Euclidean. Small negative values can also arise from rounding or floating-point arithmetic. Discarding negative eigenvalues produces a Euclidean approximation; it does not establish that the original distances were Euclidean.

Classical scaling minimizes a matrix approximation criterion commonly called strain, rather than directly minimizing discrepancies between ordinary distances:

strain⁡(X)=∥B−XXT∥F2.\operatorname{strain}(X)=\|B-XX^{\mathsf T}\|_F^2.

The truncated positive eigendecomposition supplies an optimal positive semidefinite approximation of rank at most pp under this criterion. This distinction matters because a configuration that best approximates inner products need not best approximate distances. A few large dissimilarities can have substantial influence through the squaring operation.

There is an exact connection with principal component analysis (PCA). If dissimilarities are Euclidean distances between rows of a centered data matrix, classical MDS returns principal-component scores, up to permissible rotations, reflections, and choices within tied eigenspaces. PCA starts from measured variables; classical MDS can obtain the same geometry from distances alone.

Metric scaling and distance-based loss functions

In distance-based metric MDS, observed numerical dissimilarities are fitted by distances between configuration points. A common objective function is raw stress,

σ(X)=∑i<jwij[dij(X)−δij]2.\sigma(X)=\sum_{i<j}w_{ij} \left[d_{ij}(X)-\delta_{ij}\right]^2.

Unlike classical strain, this criterion measures errors in ordinary distances. The adjective “metric” usually indicates that the numerical magnitudes of dissimilarities matter. It does not necessarily mean that every observed dissimilarity satisfies the mathematical metric axioms.

Some metric models fit transformed targets, called disparities,

δ^ij=f(δij),σ(X,f)=∑i<jwij[dij(X)−δ^ij]2.\widehat{\delta}_{ij}=f(\delta_{ij}), \qquad \sigma(X,f)=\sum_{i<j}w_{ij} \left[d_{ij}(X)-\widehat{\delta}_{ij}\right]^2.

The transformation might be proportional, f(t)=btf(t)=bt, affine, f(t)=a+btf(t)=a+bt, or drawn from another specified parametric family. Constraints such as b≥0b\geq 0 and nonnegative disparities may be needed. The permitted transformation defines the measurement assumptions: proportional scaling preserves ratios, whereas an affine transformation preserves differences up to a common unit and origin.

Normalization conventions vary. One frequently used normalized criterion, often termed Stress-1, takes the form

S1=[∑i<jwij(dij−δ^ij)2∑i<jwijdij2]1/2.S_1= \left[ \frac{\sum_{i<j}w_{ij} (d_{ij}-\widehat{\delta}_{ij})^2} {\sum_{i<j}w_{ij}d_{ij}^2} \right]^{1/2}.

Other definitions normalize by target squared distances or use different denominators. Consequently, a reported “stress” value is not interpretable without its formula. Multiplying a raw sum of squared residuals by 100, taking its square root, and normalizing it are distinct operations, even when software labels them similarly.

The choice of loss function and weights controls which discrepancies dominate. Unweighted squared-error stress penalizes large absolute errors heavily. Relative-error weighting places more emphasis on proportional agreement, although small target dissimilarities can then receive very large influence. Sammon mapping, introduced by John W. Sammon Jr. in 1969, uses inverse-dissimilarity weighting to emphasize the preservation of smaller distances and requires special handling of zero dissimilarities.

A statistical interpretation is possible when the error model is stated explicitly. If observed dissimilarities equal configuration distances plus independent Gaussian errors of common variance, minimizing raw stress corresponds to maximum likelihood estimation of coordinates under that model. With known unequal error variances, inverse-variance weights arise naturally. However, pairwise measurements often share objects, observers, or experimental conditions, so their errors need not be independent. A least-squares fit alone does not establish the validity of a Gaussian likelihood or justify standard uncertainty formulas.

Nonmetric scaling and ordinal information

Nonmetric MDS retains the ordering of dissimilarities while allowing their numerical spacing to change. Its central assumption is that if δij<δkl\delta_{ij}<\delta_{kl}, then the fitted disparity for the first pair should not exceed that for the second. Instead of prescribing a linear conversion, it estimates a nondecreasing function ff:

δ^ij=f(δij),f(a)≤f(b) whenever a<b.\widehat{\delta}_{ij}=f(\delta_{ij}), \qquad f(a)\leq f(b)\ \text{whenever }a<b.

Configuration distances are then fitted to these disparities. This approach is appropriate when “more dissimilar” is meaningful but equal differences between ratings are not.

The fitting process usually alternates between two tasks. Given coordinates, isotonic regression finds disparities that best fit the current distances subject to order constraints. Given disparities, an optimization procedure updates the coordinates. With squared-error loss, isotonic regression can be implemented by pooling adjacent groups that violate monotonicity. If distances associated with successively ordered dissimilarities are 1.01.0, 2.52.5, and 2.02.0, the final two may be pooled to a common fitted value, with the value determined by their weights.

Scale must be controlled. If both coordinates and fitted disparities were allowed to shrink freely under unnormalized raw stress, collapsing everything toward zero would make the criterion arbitrarily small. Implementations therefore use normalized stress, fix a norm, or impose equivalent scale constraints. Translation, rotation, and reflection remain indeterminate because they do not affect distances.

Ties require an explicit convention. Under one approach, equal observed dissimilarities must receive equal disparities. Under another, their internal ordering is not constrained, although order relations between different dissimilarity levels are retained. This distinction is important with short rating scales, where many pairs share the same value. Ties contain less information than a complete ordering of all object pairs, and different treatments can produce materially different configurations.

Nonmetric MDS is invariant, in its ordinal input information, to strictly increasing transformations of the dissimilarities: such transformations preserve their order and tie structure. It does not follow that any two computational runs must return identical coordinates. Local minima, initialization, tie conventions, and stopping tolerances can still produce different fitted solutions.

Ordinal flexibility also limits interpretation. Distances in a nonmetric map are not automatically measurements in the units of the original judgments, and a distance of four is not necessarily twice as meaningful as a distance of two. A good fit indicates that the observed ordering can be represented with little distortion under the chosen criterion. It does not prove that observers use Euclidean coordinates, that the dimensions have unique psychological meanings, or that an equally good representation cannot exist under a different model.

Optimization, invariances, and computational scale

Distance-based MDS is generally a nonconvex optimization problem. Although each residual involves a simple distance, all coordinates interact through the pairwise terms. Different initial configurations can therefore converge to different local minima. Classical scaling often supplies a useful starting point, while random starts explore alternatives. Comparing final objective values across several starts helps distinguish a reproducible low-stress solution from an initialization-dependent one.

Direct methods can use gradient descent or more elaborate numerical optimization. When all relevant distances are nonzero, the gradient of raw stress with fixed disparities is

∂σ∂xi=2∑j≠iwij(1−δ^ijdij)(xi−xj).\frac{\partial \sigma}{\partial x_i} = 2\sum_{j\ne i}w_{ij} \left(1-\frac{\widehat{\delta}_{ij}}{d_{ij}}\right) (x_i-x_j).

Coincident points require special treatment because division by dij=0d_{ij}=0 is undefined. This is one reason why implementation details and initialization matter even when two programs nominally minimize the same objective.

A major alternative is stress majorization, especially SMACOF, whose name abbreviates “Scaling by MAjorizing a COmplicated Function.” At each iteration, a simpler function is constructed that lies above the stress surface and agrees with it at the current configuration. Minimizing this surrogate gives the next configuration. For fixed disparities, define a weighted graph Laplacian VV by vij=−wijv_{ij}=-w_{ij} off the diagonal and vii=∑j≠iwijv_{ii}=\sum_{j\ne i}w_{ij}. An update can be expressed as

X(t+1)=V+B(X(t))X(t),X^{(t+1)}=V^{+}B(X^{(t)})X^{(t)},

with suitable centering, where V+V^{+} is a pseudoinverse. For nonzero current distances, the off-diagonal entries of BB are −wijδ^ij/dij(X(t))-w_{ij}\widehat{\delta}_{ij}/d_{ij}(X^{(t)}), and its rows sum to zero. The majorization construction makes stress nonincreasing, but does not guarantee a global minimum.

All distance-only models have geometric indeterminacies. Translation changes no pairwise distance, and multiplication by an orthogonal matrix rotates or reflects a configuration without altering its fit. Some models also have arbitrary overall scale. Comparisons between solutions therefore commonly use Procrustes analysis to align coordinates before measuring differences. If the graph of positive-weight comparisons is disconnected, the relative positions of its components are not determined at all; even a connected graph may lack enough constraints for a unique realization.

Computational requirements can be substantial. A complete dissimilarity matrix stores order n2n^2 entries, and a full dense eigendecomposition for classical MDS has order n3n^3 time complexity. Distance-based iterations typically examine order n2pn^2p coordinate operations for complete data. Partial eigensolvers, sparse comparison graphs, landmark configurations, and approximate distance computations reduce these costs. Each approximation changes either the numerical solution or the information being fitted, so scalability and geometric fidelity are separate considerations.

Dimension selection, diagnostics, and uncertainty

The target dimension pp determines the balance between fidelity and simplicity. A two-dimensional map is easy to inspect, but relationships may require three, ten, or more dimensions for adequate representation. For a fixed raw-stress model, the globally optimal stress cannot increase when an additional coordinate is allowed: the previous configuration remains available with an appended zero coordinate. Apparent increases across fitted solutions can instead reflect local minima, differing normalizations, or changed fitting assumptions.

For classical scaling, an eigenvalue plot helps identify dominant dimensions. When all eigenvalues are nonnegative, the sum of retained eigenvalues divided by their total gives the fraction of the centered coordinate variance represented by those dimensions. With negative eigenvalues, there is no single universally appropriate “percentage explained.” Dividing by the sum of positive eigenvalues and dividing by the sum of absolute eigenvalues answer different questions. Moreover, neither is a direct proportion of ordinary distance error removed.

For stress-based methods, a plot of stress against dimension can reveal an elbow, but a conspicuous elbow is not guaranteed. Historical verbal classifications of stress as excellent, good, or poor are not universal thresholds. Achievable stress depends on the number of objects, dimension, noise, tie frequency, weights, and transformation model. A small configuration may fit ordinal information extremely well even when that information has little substantive structure.

A Shepard diagram plots observed dissimilarities against fitted distances, often adding the estimated disparity curve. It reveals departures that a single aggregate statistic conceals: curvature under an overly restrictive transformation, saturation at large dissimilarities, or a small group of poorly fitted pairs. Residuals

rij=dij−δ^ijr_{ij}=d_{ij}-\widehat{\delta}_{ij}

can also be summarized by object, distance range, or known group. Large pointwise contributions identify objects whose relationships are difficult to represent, but do not by themselves show that those observations are erroneous.

Validation can use held-out comparisons, provided the remaining observations constrain the geometry sufficiently. In this form of cross-validation, coordinates are estimated from training pairs and evaluated on omitted pairs. Because pairwise entries share objects, randomly dividing individual entries does not create independent training and test samples in the usual sense. Validation for new objects, new observers, and new comparisons addresses different generalization questions.

Uncertainty can be assessed by bootstrap sampling of appropriate sampling units, such as participants or biological samples, followed by refitting and alignment. Resampling pairwise entries independently is generally inappropriate when their dependence arises from shared units. Coordinate uncertainty also requires care: rotational indeterminacy can create apparent variability unless configurations are aligned, while nearly equal eigenvalues can make individual axes unstable even when their combined subspace is well determined.

Extensions and relationships to other methods

Individual-differences MDS represents several dissimilarity matrices jointly. INDSCAL assumes that observers share object coordinates but give different nonnegative weights to dimensions. If aska_{sk} is observer ss's weight on dimension kk, the modeled distance is

dij(s)=[∑k=1pask(xik−xjk)2]1/2.d_{ij}^{(s)} = \left[ \sum_{k=1}^{p}a_{sk}(x_{ik}-x_{jk})^2 \right]^{1/2}.

This separates a common arrangement of objects from differences in dimensional salience. The shared-axis assumptions can restrict rotational freedom more strongly than ordinary MDS, although axis permutations and scaling conventions still require attention.

Unfolding models address rectangular rather than square proximity tables. For example, respondents and products can be placed in the same space, with a respondent’s preference related to distance from an ideal point to a product point. Only cross-set distances may be observed. This differs from ordinary MDS, where all points belong to one object set and within-set comparisons are the usual input. Rectangular data can leave substantial geometric ambiguity, making constraints and model specification particularly important.

Constrained MDS links coordinates to explanatory variables, fixes selected landmarks, or limits a configuration to a specified structure. Such constraints can improve interpretability but may increase distance distortion. Adding regularization can discourage unstable or excessively complex solutions. Probabilistic and Bayesian formulations place distributions on observed dissimilarities, coordinates, or latent dimensions, allowing uncertainty and prior information to enter explicitly. Their conclusions depend on the observation model and on how geometric indeterminacies are handled.

Classical MDS is closely related to kernel methods. A positive semidefinite centered similarity matrix already acts as a Gram matrix, so an eigendecomposition provides coordinates directly. Kernel PCA and classical MDS can therefore yield the same coordinates when their kernel and distance constructions correspond. The conceptual distinction is whether the starting information is a feature-space inner product or a dissimilarity table from which one is reconstructed.

Isomap, introduced in 2000 by Joshua Tenenbaum, Vin de Silva, and John Langford, combines neighborhood graphs with classical MDS. It approximates geodesic distances along a sampled manifold by shortest-path distances and then embeds that distance matrix. Its success depends on neighborhood selection and graph connectivity: edges that shortcut across the manifold can severely distort the geometry.

Other visualization methods, including t-distributed stochastic neighbor embedding and uniform manifold approximation and projection, optimize neighborhood-based objectives rather than the standard MDS distance criteria. Their apparent clusters and intercluster separations consequently have different interpretations. Likewise, cluster analysis partitions objects into groups, whereas MDS supplies a continuous spatial representation. The two can be used together, but visible gaps in an MDS plot are not themselves a formal clustering result.

Applications and substantive interpretation

In perception research, MDS turns comparative judgments into hypotheses about perceptual organization. Color similarities can reveal circular or curved arrangements; judgments of speech sounds can reflect articulatory or acoustic distinctions; musical timbre comparisons can produce dimensions associated with spectral and temporal properties. A dimension is not named by the algorithm. Its interpretation requires external measurements, experimental manipulation, or a well-supported relationship between coordinates and known attributes.

In marketing, perceptual maps place products or brands according to perceived similarity. Preference information can be added separately, for example through ideal-point or vector models. A region containing few products is a geometric feature of the fitted representation, not automatic evidence of unmet demand: purchase decisions, price, awareness, and sampling all involve information beyond pairwise resemblance. Maps based on different respondent groups may also differ because the groups attend to different attributes.

In ecology, nonmetric MDS is widely used to represent differences in community composition. Dissimilarities such as Bray–Curtis can compare abundance profiles, while transformations can reduce the influence of highly abundant species. Nearby plotted samples have similar composition according to the selected coefficient and fitted model. They need not share a common environmental cause. Environmental variables can be related to an ordination afterward, but those associations remain distinct from evidence of causal effects.

In genetics and genomics, distance-based maps can display relationships among samples using sequence differences, genotype-derived distances, or expression profiles. Relatedness, population structure, technical processing, and feature selection can all affect the result. MDS and PCA may coincide when the distances are Euclidean distances in the same centered feature representation, but they need not coincide when different genetic distances or normalization procedures are used. Separation in a plot is therefore a property of the full analytical construction, not a direct classification supplied independently by the data.

Geographic reconstruction supplies an intuitive example of the model’s assumptions. Exact straight-line distances between coplanar locations can recover their arrangement up to translation, rotation, and reflection. Road distances generally cannot be reproduced exactly in a plane because routes are constrained by a transport network. Distances along Earth’s surface similarly have spherical rather than planar geometry, making the geographic extent relevant to whether a planar approximation is adequate.

Across applications, the configuration must be interpreted relationally. The left–right direction of an unconstrained map has no intrinsic meaning, mirror images are equivalent, and proximity is meaningful only relative to the chosen dissimilarities and fit. A two-dimensional projection can superimpose points that are separated in omitted dimensions. Reporting the distance construction, transformation model, target dimension, stress definition, initialization strategy, and diagnostic behavior is therefore essential to making a displayed configuration scientifically interpretable.