# Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning

arXiv: https://arxiv.org/abs/1810.09569 · HTML: https://mlsanity.com/paper/1810.09569/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2018.

## Built on by (most cited first, 9 of 9)

- [Linearized Wasserstein dimensionality reduction with approximation guarantees](https://mlsanity.com/paper/2302.07373/) (2023)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Structured Sampling for Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2412.10664/) (2024)
- [Bespoke multiresolution analysis of graph signals](https://mlsanity.com/paper/2507.19181/) (2025)
- [When Embedding Models Meet: Procrustes Bounds and Applications](https://mlsanity.com/paper/2510.13406/) (2025)
- [A Dual Basis Approach for Structured Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2505.18414/) (2025)
- [Computationally Efficient Learning of Statistical Manifolds](https://mlsanity.com/paper/2103.11773/) (2021)
- [Embedding Functional Data: Multidimensional Scaling and Manifold Learning](https://mlsanity.com/paper/2208.14540/) (2022)
- [Factorized Fusion Shrinkage for Dynamic Relational Data](https://mlsanity.com/paper/2210.00091/) (2022)

## Abstract (arXiv)

One of the common tasks in unsupervised learning is dimensionality reduction, where the goal is to find meaningful low-dimensional structures hidden in high-dimensional data. Sometimes referred to as manifold learning, this problem is closely related to the problem of localization, which aims at embedding a weighted graph into a low-dimensional Euclidean space. Several methods have been proposed for localization, and also manifold learning. Nonetheless, the robustness property of most of them is little understood. In this paper, we obtain perturbation bounds for classical scaling and trilateration, which are then applied to derive performance bounds for Isomap, Landmark Isomap, and Maximum Variance Unfolding. A new perturbation bound for procrustes analysis plays a key role.