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? 
 A: 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.
A: 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 = X^\top\boldsymbol u$. Therefore, $\mathbf Z$ can be written as $\boldsymbol\Lambda_\ast^{1/2}\mathbf U_\ast^\top \mathbf X$. This way, the transformation matrix $\mathbf W = \mathbf U_\ast\boldsymbol\Lambda_\ast^{1/2}$.
