Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionSimilar Papers 제목 키워드 기반
Unperturbed: spectral analysis beyond Davis-Kahan
Classical matrix perturbation results, such as Weyl's theorem for eigenvalues and the Davis-Kahan theorem for eigenvectors, are general purpose. These classical bounds are tight in the worst case, but in many settings su…
ClusteringMinimax Optimality of Classical Scaling Under General Noise Conditions
We establish the consistency of classical scaling under a broad class of noise models, encompassing many commonly studied cases in literature. Our approach requires only finite fourth moments of the noise, significantly …
An RSSI-based Wireless Sensor Node Localisation using Trilateration and Multilateration Methods for Outdoor Environment
Localisation can be defined as estimating or finding a position of the node. There are two techniques in localisation, which are range-based and range-free techniques. This paper focusses on the Received Signal Strength …
Object TrackingGeometric bias in eigenspace perturbation under random heterogeneous noise
Spectral methods rely fundamentally on the stability of principal eigenspaces under random perturbations. Classically, this stability is quantified by the Davis-Kahan and Wedin theorems, which bound the eigenspace error …
Symmetrized Robust Procrustes: Constant-Factor Approximation and Exact Recovery
The classical $\textit{Procrustes}$ problem is to find a rigid motion (orthogonal transformation and translation) that best aligns two given point-sets in the least-squares sense. The $\textit{Robust Procrustes}$ problem…
TranslationWord Translation