How can classical multidimensional scaling go wrong?
  Given a matrix $D$ describing the pairwise dissimilarities of a data set, a
common task is to embed the data points into Euclidean space. The classical
multidimensional scaling (cMDS) algorithm is a widespread method to do this.
However, theoretical analysis of the robustness of the algorithm and an
in-depth analysis of its performance on non-Euclidean metrics is lacking.
  In this paper, we derive a formula, based on the eigenvalues of a matrix
obtained from $D$, for the Frobenius norm of the difference between $D$ and the
metric $D_{\text{cmds}}$ returned by cMDS. This error analysis leads us to the
conclusion that when the derived matrix has a significant number of negative
eigenvalues, then $\|D-D_{\text{cmds}}\|_F$, after initially decreasing, will
eventually increase as we increase the dimension. Hence, counterintuitively,
the quality of the embedding degrades as we increase the dimension. We
empirically verify that the Frobenius norm increases as we increase the
dimension for a variety of non-Euclidean metrics. We also show on several
benchmark datasets that this degradation in the embedding results in the
classification accuracy of both simple (e.g., 1-nearest neighbor) and complex
(e.g., multi-layer neural nets) classifiers decreasing as we increase the
embedding dimension.
  Finally, our analysis leads us to a new efficiently computable algorithm that
returns a matrix $D_l$ that is at least as close to the original distances as
$D_t$ (the Euclidean metric closest in $\ell_2$ distance). While $D_l$ is not
metric, when given as input to cMDS instead of $D$, it empirically results in
solutions whose distance to $D$ does not increase when we increase the
dimension and the classification accuracy degrades less than the cMDS solution.
