Metric MDS begins with a distance matrix with
The objective of metric MDS is to find a configuration of points in
-dimensional space from the distances between the points such that the
coordinates of the points along the dimensions
yield a Euclidean
distance matrix whose elements are as close as possible
to the elements of the given distance matrix .
15.2.1 The Classical Solution
The classical solution is based on a distance matrix that
from a Euclidean geometry.
is Euclidean if for some points
The following result tells us whether a distance matrix is Euclidean or
is the centering matrix.
is Euclidean if and only if
is positive semidefinite.
is the distance matrix of a data matrix
is called the inner product matrix.
The task of MDS is to find the original Euclidean coordinates from
a given distance matrix.
Let the coordinates of points in a dimensional Euclidean
space be given by ()
the coordinate matrix and assume
The Euclidean distance between the -th and -th points is given by:
The general term of is given by:
It is possible to derive from the known squared distances
, and then from
the unknown coordinates.
Centering of the coordinate matrix implies that
. Summing (15.3) over , over , and over and , we find:
Solving (15.3) and (15.4) gives:
Define the matrix as , and observe that:
The inner product matrix can be expressed as:
is the matrix
The rank of is then
As required in Theorem 15.1 the matrix is symmetric,
positive semidefinite and of
rank , and hence it has non-negative eigenvalues and zero
can now be written as:
, the diagonal
matrix of the eigenvalues of
, the matrix
of corresponding eigenvectors.
Hence the coordinate matrix containing the point
configuration in is given by:
The number of desired dimensions is small in order to
provide practical interpretations, and
is given by the rank of or the number of nonzero
If is positive semidefinite, then the
number of nonzero eigenvalues gives the number of eigenvalues required for
representing the distances .
The proportion of variation explained by dimensions is given by
It can be used for the choice of .
If is not positive semidefinite
we can modify (15.13) to
In practice the eigenvalues are almost always unequal to zero.
To be able to represent the objects in a space with dimensions
as small as possible we may modify the distance matrix to:
where is determined such that the inner product matrix becomes
positive semidefinite with a small rank.
In some situations we do not start with distances but
The standard transformation (see Chapter 11)
from a similarity matrix to a distance matrix
, then the distance matrix
is Euclidean with centered inner product matrix
Suppose that the () data matrix is centered so
equals a multiple of the covariance matrix .
Suppose that the eigenvalues
are distinct and non zero. Using the duality
Theorem 8.4 of factorial analysis
we see that
are also eigenvalues of
when is the Euclidean distance matrix
between the rows of . The -dimensional solution
to the metric MDS problem is thus given by the first principal components
Let be a data matrix with some inter-point
distance matrix . The objective of MDS is thus to find
, a representation of in a lower dimensional
whose inter-point distance matrix
is not far from . Let
be a orthogonal matrix where
represents a projection
of on the column space of ; in other words,
may be viewed as a fitted configuration of in
. A measure of discrepancy between and
is given by
Among all projections
is projected onto its first
We see therefore that the metric MDS is identical to principal factor analysis
as we have defined it in Chapter 8.
Metric MDS starts with a distance matrix .
The aim of metric MDS is to construct a map in Euclidean space that corresponds
to the given distances.
A practical algorithm is given as:
- start with distances
- find the eigenvalues
and the associated
where the eigenvectors are normalized
- Choose an appropriate number of dimensions (ideally )
- The coordinates of the points in the Euclidean space are given by
for and .
Metric MDS is identical to principal components analysis.