PCA-Based Out-of-Sample Extension for Dimensionality Reduction

Abstract

Dimensionality reduction methods are very common in the field of high dimensional data analysis. Typically, algorithms for dimensionality reduction are computationally expensive. Therefore, their applications for the analysis of massive amounts of data are impractical. For example, repeated computations due to accumulated data are computationally prohibitive. In this paper, an out-of-sample extension scheme, which is used as a complementary method for dimensionality reduction, is presented. We describe an algorithm which performs an out-of-sample extension to newly-arrived data points. Unlike other extension algorithms such as Nyström algorithm, the proposed algorithm uses the intrinsic geometry of the data and properties for dimensionality reduction map. We prove that the error of the proposed algorithm is bounded. Additionally to the out-of-sample extension, the algorithm provides a degree of the abnormality of any newly-arrived data point.

Cited by in corpus (5)

• Approximation of Functions over Manifolds: A Moving Least-Squares Approach
• Non-Parametric Estimation of Manifolds from Noisy Data
• Spectral Embedding Norm: Looking Deep into the Spectrum of the Graph Laplacian
• Convergence rates of vector-valued local polynomial regression
• Properties of Laplacian Pyramids for Extension and Denoising