# Is multidimensional scaling (PCoA) a linear dimensionality reduction technique?

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?

• "but both cMDS and nMDS are listed as linear techniques in this article" -- where exactly? Jul 30, 2019 at 11:05
• It clearly lists nMDS as nonlinear in "Tip 1". Jul 30, 2019 at 11:06
• The article itself seems to be contradictory. NMDS is not classified as nonlinear in table 1 in the same paper. Jul 31, 2019 at 13:22
• Oh I see. So it's just an unfortunate typo in the Table 1. Jul 31, 2019 at 13:33
• 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. Jul 31, 2019 at 13:39

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}$$.