Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approach
Preprint
Abstract
We propose a kernel-spectral embedding algorithm for learning low-dimensional nonlinear structures from high-dimensional and noisy observations, where the datasets are assumed to be sampled from an intrinsically low-dimensional manifold and corrupted by high-dimensional noise. The algorithm employs an adaptive bandwidth selection procedure which does not rely on prior knowledge of the underlying manifold. The obtained low-dimensional embeddings can be further utilized for downstream purposes such as data visualization, clustering and prediction. Our method is theoretically justified and practically interpretable. Specifically, we establish the convergence of the final embeddings to their noiseless counterparts when the dimension and size of the samples are comparably large, and characterize the effect of the signal-to-noise ratio on the rate of convergence and phase transition. We also prove convergence of the embeddings to the eigenfunctions of an integral operator defined by the kernel map of some reproducing kernel Hilbert space capturing the underlying nonlinear structures. Numerical simulations and analysis of three real datasets show the superior empirical performance of the proposed method, compared to many existing methods, on learning various manifolds in diverse applications.Keywords
All Related Versions
This publication has 57 references indexed in Scilit:
- Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace–Beltrami OperatorFoundations of Computational Mathematics, 2019
- Spectral Algorithms for Tensor CompletionCommunications on Pure and Applied Mathematics, 2018
- The spectral norm of random inner-product kernel matricesProbability Theory and Related Fields, 2018
- Vector diffusion maps and the connection LaplacianCommunications on Pure and Applied Mathematics, 2012
- Learning Theory Estimates via Integral Operators and Their ApproximationsConstructive Approximation, 2007
- From graph to manifold Laplacian: The convergence rateApplied and Computational Harmonic Analysis, 2006
- Statistical properties of kernel principal component analysisMachine Learning, 2006
- Reproducing Kernel Hilbert Spaces in Probability and Statistics2004
- Silhouettes: A graphical aid to the interpretation and validation of cluster analysisJournal of Computational and Applied Mathematics, 1987
- A Short Introduction to Perturbation Theory for Linear Operators1982