3
$\begingroup$

Classic MDS (cMDS or PCoA) preserves global distances, characteristic of linear techniques. However, metric MDS seeks to minimize a cost function (stress), while non-metric MDS (nMDS) preserves only the ranking of dissimilarities between points. It seems to me these techniques produce a kind of embedding, which would be nonlinear, but both cMDS and nMDS are listed as linear techniques in this article. Conversely, Wikipedia describes MDS in general as a form of nonlinear dimensionality reduction.

It is possible to use a nonlinear kernel in MDS to preserve smaller distances, as in the case of a Sammon mapping. This is definitely a nonlinear technique.

So: are multidimensional scaling and its variants considered linear or nonlinear dimensionality reduction techniques, and why?

$\endgroup$
5
  • $\begingroup$ "but both cMDS and nMDS are listed as linear techniques in this article" -- where exactly? $\endgroup$
    – amoeba
    Jul 30, 2019 at 11:05
  • $\begingroup$ It clearly lists nMDS as nonlinear in "Tip 1". $\endgroup$
    – amoeba
    Jul 30, 2019 at 11:06
  • $\begingroup$ The article itself seems to be contradictory. NMDS is not classified as nonlinear in table 1 in the same paper. $\endgroup$
    – sara-es
    Jul 31, 2019 at 13:22
  • $\begingroup$ Oh I see. So it's just an unfortunate typo in the Table 1. $\endgroup$
    – amoeba
    Jul 31, 2019 at 13:33
  • 1
    $\begingroup$ I might write-up a proper answer later, but I wouldn't call t-SNE/nMDS/etc "nonlinear", I think it's sloppy. They should rather be called "nonparametric". See here stats.stackexchange.com/questions/142960 about this distinction. cMDS is called "linear" because it's equivalent to PCA but it's actually an abuse of terminology. $\endgroup$
    – amoeba
    Jul 31, 2019 at 13:39

2 Answers 2

1
$\begingroup$

According to the information I know, I think Metric-MDS just construct the distance matrix by using Euclidian distance, which is a linear transformation. But Non-Metric-MDS redefines the distance between the data using rank order of distances, which is a nonlinear transformation.

$\endgroup$
0
$\begingroup$

Classic MDS is a linear dimensionality reduction technique. One may confirm its linearity by finding a transformation matrix $\mathbf W \in \mathbb R^{d \times d'}$ such that $\mathbf Z = \mathbf W^\top \mathbf X$, where $\mathbf X \in \mathbb R^{d \times m}$ is the collection of samples in original space, and $\mathbf Z$ the samples in reduced space.

Let the inner product matrix $\mathbf B = \mathbf X^\top \mathbf X = \mathbf V\boldsymbol\Lambda\mathbf V^\top$. By classic MDS, one may find $\mathbf Z = \boldsymbol\Lambda_\ast^{1/2}\mathbf V_\ast^\top \in \mathbb R^{d^\ast \times m}$, where $\boldsymbol\Lambda_\ast$ is a diagonal matrix containing $d^\ast$ largest (positive) eigenvalues of $\mathbf B$ and corresponding eigenvector matrix $\mathbf V_\ast$. In addition, let $\mathbf U\tilde{\boldsymbol\Lambda}\mathbf U^\top$ be the eigenvalue decomposition of $\mathbf X\mathbf X^\top$. One is able to show that $\mathbf X^\top\mathbf X$ and $\mathbf X\mathbf X^\top$ share the same nonzero eigenvalues, and that for any nonzero eigenvalue, the corresponding eigenvectors of the two matrices satisfy $\boldsymbol v = C X^\top\boldsymbol u$, where $C$ is an arbitrary constant. Therefore, $\mathbf Z$ can be written as $\boldsymbol\Lambda_\ast^{1/2}\mathbf C^\top\mathbf U_\ast^\top \mathbf X$, where $\mathbf C$ is an arbitrary diagonal matrix. This way, the transformation matrix $\mathbf W = \mathbf U_\ast\mathbf C\boldsymbol\Lambda_\ast^{1/2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.