Efficient Inter-Geodesic Distance Computation and Fast Classical Scaling.

Area of Science:

• Data Science
• Machine Learning
• Computational Geometry

Background:

• Multidimensional Scaling (MDS) is crucial for dimensionality reduction, data visualization, and manifold learning.
• Traditional MDS methods embed data in Euclidean spaces, aiming to preserve inter-point dissimilarities.
• Existing methods often face computational challenges with large datasets due to quadratic complexity.

Purpose of the Study:

• To present an efficient solver for classical scaling, a specific MDS model.
• To reduce the computational and space complexity of MDS algorithms.
• To enable effective analysis of large-scale datasets through improved dimensionality reduction.

Main Methods:

• Developed a novel solver for classical Multidimensional Scaling (MDS).
• Extrapolated distance information from a data subset to the entire dataset.
• Constructed a low-rank approximation of inter-geodesic distances using local and global data information.

Main Results:

• Reduced computational and space complexity from quadratic to quasi-linear.
• Achieved efficient embedding of data points in low-dimensional Euclidean domains.
• Enabled efficient computation of geodesic distances as a byproduct.

Conclusions:

• The proposed method offers a significant computational advantage for Multidimensional Scaling.
• This advancement facilitates scalable data visualization and manifold learning.
• The technique provides an efficient way to compute geodesic distances, valuable in various data analysis contexts.