[author]Arvind Agarwal, Chad Brubaker, Hal Daumé III, Jeff M. Phillips and Suresh Venkatasubramanian [/author]
Submitted.

Abstract:
Multidimensional scaling (MDS) is one of the most popular methods for reducing the dimensionality of data. As data sizes have grown, the space and time limitations of traditional MDS algorithms have become more pronounced, and extensive research has gone into designing methods for performing MDS that scale to larger data sets. However, these approaches generally start with a matrix decomposition approach to solving MDS. This matrix decomposition is expensive in time and space, and thus the approaches focus on trying to approximate the decomposition using Nyström methods to solve a smaller matrix decomposition problem.

In this paper, we present a new approach to scalable MDS that combines adaptive sampling methods, multi-pass streaming algorithms, and multi-core extensions, and gives a much better error-time tradeoff than prior approaches. Our approach uses a nonlinear projection technique that was recently developed for MDS and avoids expensive matrix decompositions, from which it derives much of its space and time efficiency.

This method allows us to perform MDS feasibly and accurately on data sets of the order of hundreds of thousands of points. While this is still not “enormous”, it is orders of magnitude larger (for similar error rates) than previous known methods. In addition, because of the underlying approach we use, this method generalizes to many variants of MDS (using robust error metrics, in non-Euclidean spaces) that have never been studied at scale.

Tags: CCF 0953066