Multidimensional Scaling

Many of the examples in the book are taken from the area of multidimensional scaling (MDS). In this appendix we describe the basic MDS notation and terminology. Our approach to MDS is based on Kruskal [1964ab], using terminology and notation of De Leeuw [1977] and De Leeuw and Heiser [1982]. For a more recent and more extensive discussion of MDS see Borg and Groenen [2005].

The data in an MDS problem consist of information about the dissimilarities between pairs of $n$ objects. Dissimilarities are like distances, in the sense that they give some information about physical or psychological closeness, but they need not satisfy any of the distance axioms. In metric MDS the dissimilarity between objects $i$ and $j$ is a given number $\delta_{ij}$, usually positive and symmetric, with possibly some of the dissimilarities missing. In non-metric MDS we only have a partial order on some or all of the $n^2$ dissimilarities. We want to represent the $n$ objects as $n$ points in a metric space in such a way that the distances between the points approximate the dissimilarities between the objects.

An MDS loss function is typically of the form $\sigma(X,\Delta)=\|\Delta-D(X)\|$ for some norm, or pseudo-norm, on the space of $n\times n$ matrices. Here $X$ are the $n$ points in the metric space, with $D(X)$ the symmetric, non-negative, and hollow matrix of distances. The MDS problem is to minimize loss over all mappings $X$ and all feasible $\Delta$. In the metric MDS problems $\Delta$ is fixed at the observed data, in non-metric MDS any monotone transformation of $\Delta$ is feasible.

The definition of MDS we have given leaves room for all kinds of metric spaces and all kinds of norms to measure loss. In almost all applications both in this book and elsewhere, we are interested in Euclidean MDS, where the metric space is $\mathbb{R}^p$, and in loss functions that use the (weighted) sum of squares of residuals $r_{ij}(X,\Delta)$. Thus the loss function has the general form $$\sigma(X,\Delta)= \sum_{i=1}^n\sum_{j=1}^n w_{ij}^{\ }r_{ij}^2(X,\Delta),$$ where $X$ is an $n\times p$ matrix called the configuration.

The most popular choices for the residuals are $$\begin{align*} R_1(X,\Delta)&=\Delta-D(X),\\ R_2(X,\Delta)&=\Delta^2-D^2(X),\\ R_0(X,\Delta)&=\log\Delta-\log D(X),\\ R_S(X,\Delta)&=-\frac12 J_n(\Delta^2-D^2(X))J_n. \end{align*}$$ Here $\Delta^2$ and $\log\Delta$ are elementwise transformations of the dissimilarities, with corresponding transformations $D^2$ and $\log D$ of the distances. In $R_S$ we use the centering operator $J_n=I-\frac{1}{n}ee'$. For Euclidean distances, and centered $X$, $$R_S(X,\Delta)=\Gamma(\Delta)-XX',$$ with $\Gamma(\Delta)\mathop{=}\limits^{\Delta}-\frac12 J_n\Delta^2J_n$. Metric Euclidean MDS, using $R_S$ with unit weights, means finding the best rank $p$ approximation to $\Gamma(\Delta)$, which can be done finding the $p$ dominant eigenvalues and corresponding eigenvectors. This is also known as Classical MDS [Torgerson, 1958].

The loss function $\sigma_1$ that uses $R_1$ is called stress [Kruskal, 1964ab], the function $\sigma_2$ that uses $R_2$ is sstress [Takane et al, 1977], and loss $\sigma_S$ that uses $R_S$ is strain [De Leeuw and Heiser, 1982]. $R_0$ has been nameless so far, but it has been proposed by Ramsay [1977]. Because of its limiting properties (see below), we will call it strull.

Both $R_1$ ant $R_2$ are obviously special cases of $$R_r(X,\Delta)=\Delta^r-D^r(X),$$ for which the corresponding loss function $\sigma_r$ is called r-stress. Because $$\lim_{r\rightarrow 0}\frac{R_r(X,\Delta)}{r}= \log\Delta-\log D(X)$$ we see that $\sigma_0$ is a limiting case of $\frac{1}{r^2}\sigma_r$.

There is some matrix notation that is useful in dealing with Euclidean MDS. Suppose $e_i$ and $e_j$ are unit vectors, with all elements equal to zero, except one element which is equal to one. Then $$d_{ij}^2(X)=(e_i-e_j)'XX'(e_i-e_j)=\mathbf{tr}\ X'A_{ij}X=\mathbf{tr}\ A_{ij}C(X),$$ where $A_{ij}\mathop{=}\limits^{\Delta}(e_i-e_j)(e_i-e_j)'$ and $C(X)\mathop{=}\limits^{\Delta}XX'$. If we define $$A^{*p}_{ij}\mathop{=}\limits^{\Delta}\underbrace{A_{ij}\oplus\cdots\oplus A_{ij}}_{p\text{ times}},$$ and $\overline{x}=\mathbf{vec}(X)$ then $d_{ij}^2(X)=\overline{x}'A^{*p}_{ij}\overline{x}$, which allows us to work with vectors in $\mathbb{R}^{np}$ instead of matrices in $\mathbb{R}^{n\times p}$.