Why Multidimensional Scaling Fails?

Why MDS Fails in giving us Meaningful Embeddings:

MDS basically arranges points in 2D or lower dimension based on high dimensional pairwise distances.

The objective loss which it follows is:

where dij is distances at original higher dimension and yi -yj is the distance pair at low dimension preferably 2D.

Preserving high dimensional distances is usually a bad idea because it's not possible to preserve them (curse of dimensionality).

what's Curse of dimensionality Problem:

The common theme of these problems is that when the dimensionality increases, the volume of the space increases so fast that the available data become sparse. In order to obtain a reliable result, the amount of data needed often grows exponentially with the dimensionality. Also, organizing and searching data often relies on detecting areas where objects form groups with similar properties; in high dimensional data, however, all objects appear to be sparse and dissimilar in many ways, which prevents common data organization strategies from being efficient.

Now coming back to our topic

Let us see example of random generated data points from gaussian with unit variance and look at the distribution of their pairwise distances

As we are increasing the dimensions the distribution of pairwise distances are being shifting more away from the centre meaning the distances en up getting on higher ends.

So suppose if you want to have two points separated with large distances in 2D but in doing so there would be some points which are close together which have pairwise distances as zero which is not there at all in original dimension. So point here is you are trying to fit the green distribution with the blue one due to which MDS fails to produce meaningful embedding.

Embedding results on MNIST data seems pretty unseperable.

Another issue with MDS is it's quadratic memory and time complexity.

So how it have been dealt is Instead to preserving distances preserve nearest neighbour.

To check more on the idea please take a look on below paper

https://www.cs.toronto.edu/~hinton/absps/sne.pdf

Hope you like it!

Thanks