Can I read How Can Classical Multidimensional Scaling Go Wrong? on EtoBox?

How Can Classical Multidimensional Scaling Go Wrong? by Sonthalia, Rishi; Van Buskirk, Gregory; Raichel, Benjamin; Gilbert, Anna C. is a scholarly article available to read on EtoBox.

What is How Can Classical Multidimensional Scaling Go Wrong? about?

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 c

Author

Sonthalia, Rishi; Van Buskirk, Gregory; Raichel, Benjamin; Gilbert, Anna C.

Published

2021

Language

EN