Fast Classical Scaling

Multidimensional-scaling (MDS) is a dimensionality reduction tool used for information analysis, data visualization and manifold learning. Most MDS procedures find embedding of data points in low dimensional Euclidean (flat) domains, such that distances between the points are as close as possible to given inter-points dissimilarities. We present an efficient solver for Classical Scaling, a specific MDS model, by extrapolating the information provided by distances measured from a subset of the points to the rest. The computational and space complexities of the new MDS procedures are be thereby reduced from quadratic to quasi-linear in the number of data points. Incorporating both local and global information about the data allows us to construct a low rank approximation to the inter-geodesic distances between the data points. As a by-product, the proposed method allows for efficient computation of geodesic distances. Finally, we show how to apply our method to two geometric analysis applications and obtain state of the art results.