  Multidimensional scaling (MDS) is a dimensionality reduction tool used for
information analysis, data visualization and manifold learning. Most MDS
procedures embed data points in low-dimensional Euclidean (flat) domains, such
that distances between the points are as close as possible to given inter-point
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 remainder. The computational and
space complexities of the new MDS methods are 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 of
the inter-geodesic distances between the data points. As a by-product, the
proposed method allows for efficient computation of geodesic distances.
