Multidimensional Scaling

Definition

Multidimensional Scaling (MDS) is a non-linear dimensional reduction method. It aims to represent high-dimensional data in a lower-dimensional space while preserving the pairwise distances

Algorithm

MDS

1. Find a low-dimensional $\mathbf{y}$ that minimizes the difference in the pairwise distance of points. $\underset{\mathbf{y}}{\mathrm{argmin}}\sum _{i=1}^n\sum _{j\ne i=1}^n[d(x_i,x_j)-d(y_i,y_j){]}^2$ where $x_i$ is a data point vector,$d(\cdot ,\cdot )$ is a distance function.

Local MDS

1. Build a set of nearby pairs $N=\{(i,j)|x_j\in N_i\text{or}{x}_i\in N_j\}$ where $N_i$ is the set of the k-nearest neighbors of $x_i$
2. Find a low-dimensional $\mathbf{y}$ that minimizes the difference in the local pairwise distance of points. $\underset{\mathbf{y}}{\mathrm{argmin}}\sum _{(i,j)\in N}[d(x_i,x_j)-d(y_i,y_j){]}^2+\sum _{(i,j)\notin N}\lambda [D-d(y_i,y_j){]}^2$ where $x_i$ is a data point vector,$d(\cdot ,\cdot )$ is a distance function, $D$ is a matrix with very large value, and $\lambda$ is a small value weight often $\frac{1}{D}$.