Multidimensional scaling

Remarks

The matrix $D$ is the matrix of Euclidean distances of some points in $\R^k$ exactly when $B$ is positive semidefinite of rank at most $k$. In that case classical scaling recovers the points up to a translation and an orthogonal transformation, since $B$ is then the Gram matrix of the centred points. Example: three points on a line at distances $d_{12} = d_{23} = 1$, $d_{13} = 2$. The centred configuration $-1, 0, 1$ has Gram matrix $B = \begin{pmatrix} 1 & 0 & -1 \\ 0 & 0 & 0 \\ -1 & 0 & 1 \end{pmatrix}$, with largest eigenvalue $2$ and eigenvector $(1, 0, -1)/\sqrt{2}$. Step 3 gives the coordinates $1, 0, -1$, the original points after a reflection. Non-example: if $d_{12} = d_{23} = 1$ and $d_{13} = 3$, the triangle inequality fails, so no points in any $\R^k$ realise $D$, and $B$ has a negative eigenvalue. Metric and non-metric scaling instead minimise a stress function, such as $\sum_{i < j} (d_{ij} - \abs{x_i - x_j})^2$, by iteration.