Efficient Inter-Geodesic Distance Computation and Fast Classical Scaling
- 25 October 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 42 (1) , 74-85
Abstract
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.Keywords
All Related Versions
Funding Information
- Israel Ministry of science (3-14719)
- Technion Hiroshi Fujiwara Cyber Security Research Center
- Israel Cyber Directorate
This publication has 34 references indexed in Scilit:
- Spectral multidimensional scalingProceedings of the National Academy of Sciences, 2013
- Walking On Broken Mesh: Defect‐Tolerant Geodesic Distances and ParameterizationsComputer Graphics Forum, 2011
- CUR matrix decompositions for improved data analysisProceedings of the National Academy of Sciences, 2009
- Fast exact and approximate geodesics on meshesACM Transactions on Graphics, 2005
- On bending invariant signatures for surfacesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Texture mapping using surface flattening via multidimensional scalingIEEE Transactions on Visualization and Computer Graphics, 2002
- The self-organizing mapNeurocomputing, 1998
- Computing Discrete Minimal Surfaces and Their ConjugatesExperimental Mathematics, 1993
- A numerical solution to the generalized mapmaker's problem: flattening nonconvex polyhedral surfacesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1989
- A note on two problems in connexion with graphsNumerische Mathematik, 1959