Multidimensional scaling

More technically, MDS refers to a set of related ordination techniques used in information visualization, in particular to display the information contained in a distance matrix. It is a form of non-linear dimensionality reduction.

Given a distance matrix with the distances between each pair of objects in a set, and a chosen number of dimensions, N, an MDS algorithm places each object into N-dimensional space (a lower-dimensional representation) such that the between-object distances are preserved as well as possible. For N = 1, 2, and 3, the resulting points can be visualized on a scatter plot.

Core theoretical contributions to MDS were made by James O. Ramsay of McGill University, who is also regarded as the founder of functional data analysis.

Types

MDS algorithms fall into a taxonomy, depending on the meaning of the input matrix:

Classical multidimensional scaling

It is also known as Principal Coordinates Analysis (PCoA), Torgerson Scaling or Torgerson–Gower scaling. It takes an input matrix giving dissimilarities between pairs of items and outputs a coordinate matrix whose configuration minimizes a loss function called strain, which is given by $${\displaystyle {\text{Strain}}_D(x_1,x_2,...,x_n)=(\frac{\sum _{i,j}(b_{ij}-x_i^T{x}_j{)}^2}{\sum _{i,j}{b}_{ij}^2}{)}^{1/2},}$$ where ${\displaystyle x_i}$ denote vectors in N-dimensional space, ${\displaystyle x_i^T{x}_j}$ denotes the scalar product between ${\displaystyle x_i}$ and ${\displaystyle x_j}$, and ${\displaystyle b_{ij}}$ are the elements of the matrix ${\displaystyle B}$ defined on step 2 of the following algorithm, which are computed from the distances.

Steps of a Classical MDS algorithm:

Classical MDS uses the fact that the coordinate matrix ${\displaystyle X}$ can be derived by eigenvalue decomposition from $B=X{X}^{\prime }$. And the matrix $B$ can be computed from proximity matrix $D$ by using double centering.

1. Set up the squared proximity matrix $D^{(2)}=[d_{ij}^2]$
2. Apply double centering: $B=-\frac{1}{2}C{D}^{(2)}C$ using the centering matrix $C=I-\frac{1}{n}{J}_n$, where $n$ is the number of objects, $I$ is the $n\times n$ identity matrix, and $J_n$ is an $n\times n$ matrix of all ones.
3. Determine the $m$ largest eigenvalues ${\lambda }_1,{\lambda }_2,...,{\lambda }_m$ and corresponding eigenvectors $e_1,e_2,...,e_m$ of $B$ (where $m$ is the number of dimensions desired for the output).
4. Now, $X=E_m{\mathrm{\Lambda }}_m^{1/2}$ , where $E_m$ is the matrix of $m$ eigenvectors and ${\mathrm{\Lambda }}_m$ is the diagonal matrix of $m$ eigenvalues of $B$.

Classical MDS assumes metric distances. So this is not applicable for direct dissimilarity ratings.

Metric multidimensional scaling (mMDS)

It is a superset of classical MDS that generalizes the optimization procedure to a variety of loss functions and input matrices of known distances with weights and so on. A useful loss function in this context is called stress, which is often minimized using a procedure called stress majorization. Metric MDS minimizes the cost function called “stress” which is a residual sum of squares:

${\displaystyle {\text{Stress}}_D(x_1,x_2,...,x_n)=\sqrt{\sum _{i\ne j=1,...,n}(d_{ij}-\Vert x_i-x_j\Vert {)}^2}.}$

Metric scaling uses a power transformation with a user-controlled exponent $p$: $d_{ij}^p$ and $-d_{ij}^{2p}$ for distance. In classical scaling $p=1.$ Non-metric scaling is defined by the use of isotonic regression to nonparametrically estimate a transformation of the dissimilarities.

Non-metric multidimensional scaling (NMDS)

In contrast to metric MDS, non-metric MDS finds both a non-parametric monotonic relationship between the dissimilarities in the item-item matrix and the Euclidean distances between items, and the location of each item in the low-dimensional space.

Let ${\displaystyle d_{ij}}$ be the dissimilarity between points ${\displaystyle i,j}$. Let ${\displaystyle {\hat{d}}_{ij}=\Vert x_i-x_j\Vert }$ be the Euclidean distance between embedded points ${\displaystyle x_i,x_j}$.

Now, for each choice of the embedded points ${\displaystyle x_i}$ and is a monotonically increasing function ${\displaystyle f}$, define the "stress" function:

${\displaystyle S(x_1,...,x_n;f)=\sqrt{\frac{\sum _{i<j}(f(d_{ij})-{\hat{d}}_{ij}{)}^2}{\sum _{i<j}{\hat{d}}_{ij}^2}}.}$

The factor of ${\displaystyle \sum _{i<j}{\hat{d}}_{ij}^2}$ in the denominator is necessary to prevent a "collapse". Suppose we define instead ${\displaystyle S=\sqrt{\sum _{i<j}(f(d_{ij})-{\hat{d}}_{ij}{)}^2}}$, then it can be trivially minimized by setting ${\displaystyle f=0}$, then collapse every point to the same point.

A few variants of this cost function exist. MDS programs automatically minimize stress in order to obtain the MDS solution.

The core of a non-metric MDS algorithm is a twofold optimization process. First the optimal monotonic transformation of the proximities has to be found. Secondly, the points of a configuration have to be optimally arranged, so that their distances match the scaled proximities as closely as possible.

NMDS needs to optimize two objectives simultaneously. This is usually done iteratively:

1. Initialize ${\displaystyle x_i}$ randomly, e. g. by sampling from a normal distribution.
2. Do until a stopping criterion (for example, ${\displaystyle S<ϵ}$)
   1. Solve for ${\displaystyle f=\arg \underset{f}{min}S(x_1,...,x_n;f)}$ by isotonic regression.
   2. Solve for ${\displaystyle x_1,...,x_n=\arg \underset{x_1,...,x_n}{min}S(x_1,...,x_n;f)}$ by gradient descent or other methods.
3. Return ${\displaystyle x_i}$ and ${\displaystyle f}$

Louis Guttman's smallest space analysis (SSA) is an example of a non-metric MDS procedure.

Generalized multidimensional scaling (GMDS)

An extension of metric multidimensional scaling, in which the target space is an arbitrary smooth non-Euclidean space. In cases where the dissimilarities are distances on a surface and the target space is another surface, GMDS allows finding the minimum-distortion embedding of one surface into another.

Super multidimensional scaling (SMDS)

An extension of MDS, known as Super MDS, incorporates both distance and angle information for improved source localization. Unlike traditional MDS, which uses only distance measurements, Super MDS processes both distance and angle-of-arrival (AOA) data algebraically (without iteration) to achieve better accuracy.

The method proceeds in the following steps:

1. Construct the Reduced Edge Gram Kernel: For a network of ${\displaystyle N}$ sources in an ${\displaystyle \eta }$-dimensional space, define the edge vectors as ${\displaystyle v_i=x_m-x_n}$. The dissimilarity is given by ${\displaystyle k_{i,j}=⟨v_i,v_j⟩}$. Assemble these into the full kernel ${\displaystyle K=V{V}^T}$, and then form the reduced kernel using the ${\displaystyle N-1}$ independent vectors: ${\displaystyle \overline{K}=[V{]}_{(N-1)\times \eta }[V{]}_{(N-1)\times \eta }^T}$,
2. Eigen-Decomposition: Compute the eigen-decomposition of ${\displaystyle \overline{K}}$,
3. Estimate Edge Vectors: Recover the edge vectors as ${\displaystyle \hat{V}=(U_{M\times \eta }{\mathrm{\Lambda }}_{\eta \times \eta }^{\odot \frac{1}{2}}{)}^T}$,
4. Procrustes Alignment: Retrieve ${\displaystyle \hat{V}}$ from ${\displaystyle V}$ via Procrustes Transformation,
5. Compute Coordinates: Solve the following linear equations to compute the coordinate estimates ${\displaystyle \left(\begin{array}{c}1|{\mathbf{0}}_{1\times N-1}\\ {\mathbf{[}\mathbf{C}\mathbf{]}}_{N-1\times N}\end{array}\right)\cdot \left(\begin{array}{c}{\mathbf{x}}_1\\ [\mathbf{X}{]}_{N-1\times \eta }\end{array}\right)=\left(\begin{array}{c}{\mathbf{x}}_1\\ [\mathbf{V}{]}_{N-1\times \eta }\end{array}\right),}$

This concise approach reduces the need for multiple anchors and enhances localization precision by leveraging angle constraints.