Fast Classical Scaling
Authors:
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Locality Constrained Dictionary Learning for Nonlinear Dimensionality ReductionIEEE Signal Processing Letters, 2013
- CUR matrix decompositions for improved data analysisProceedings of the National Academy of Sciences, 2009
- Numerical Geometry of Non-Rigid Shapes2009
- SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding2006
- Hessian eigenmaps: Locally linear embedding techniques for high-dimensional dataProceedings of the National Academy of Sciences, 2003
- Image spaces and video trajectories: using Isomap to explore video sequences2003
- Perceptual Metrics for Image Database Navigation2001
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- Computing geodesic paths on manifoldsProceedings of the National Academy of Sciences, 1998
- Computing Discrete Minimal Surfaces and Their ConjugatesExperimental Mathematics, 1993