Exact Cluster Recovery via Classical Multidimensional Scaling
This work addresses a theoretical gap for researchers using MDS in clustering applications, offering foundational insights for downstream analyses, though it is incremental in extending existing MDS theory.
The paper tackles the problem of analyzing the statistical performance of classical multidimensional scaling (MDS) for clustering noisy data, providing theoretical conditions under which exact cluster recovery is achieved with high probability, supported by near-sharp scaling conditions in simulations.
Classical multidimensional scaling is an important dimension reduction technique. Yet few theoretical results characterizing its statistical performance exist. This paper provides a theoretical framework for analyzing the quality of embedded samples produced by classical multidimensional scaling. This lays the foundation for various downstream statistical analyses, and we focus on clustering noisy data. Our results provide scaling conditions on the sample size, ambient dimensionality, between-class distance, and noise level under which classical multidimensional scaling followed by a distance-based clustering algorithm can recover the cluster labels of all samples with high probability. Numerical simulations confirm these scaling conditions are near-sharp. Applications to both human genomics data and natural language data lend strong support to the methodology and theory.