Classical Multidimensional Scaling MDS

Classical MDS [4], sometimes referred to as metric MDS, shares many similar properties to PCA, as shown by the example low-dimensional embedding in Fig. 2.2b. Whereas PCA seeks to find the subspace that maximally preserves variance, MDS seeks to preserve pairwise distances in the low-dimensional space. As such, MDS takes as input a matrix, S, of squared pairwise distances  

The squared distance matrix in its raw form is not positive semi-definite, so cannot be used as the feature matrix for spectral dimensionality reduction. Therefore, it needs to be converted to a Gram, or inner-product, matrix through the following transformation  

Both PCA and Classical MDS give rise to the same low-dimensional embedding and the Gram matrix (Eq. 2.4) has the same rank and eigenvalues up to a constant factor as the feature (covariance) matrix of PCA [5]. 

---