Central Limit Theorems for Classical Multidimensional Scaling

Abstract

Classical multidimensional scaling is a widely used method in dimensionality reduction and manifold learning. The method takes in a dissimilarity matrix and outputs a low-dimensional configuration matrix based on a spectral decomposition. In this paper, we present three noise models and analyze the resulting configuration matrices, or embeddings. In particular, we show that under each of the three noise models the resulting embedding gives rise to a central limit theorem. We also provide compelling simulations and real data illustrations of these central limit theorems. This perturbation analysis represents a significant advancement over previous results regarding classical multidimensional scaling behavior under randomness.

arXiv comment26 pages, 6 figures

References in corpus (5)

• Matrix estimation by Universal Singular Value Thresholding
• Localization from Incomplete Noisy Distance Measurements
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• Principal component analysis for big data
• Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion