Sketching the Heat Kernel: Using Gaussian Processes to Embed Data
This paper introduces a novel, non-deterministic method for embedding data in low-dimensional Euclidean space based on computing realizations of a Gaussian process depending on the geometry of the data. This type of embedding first appeared in (Adler et al, 2018) as a theoretical model for a generic manifold in high dimensions. In particular, we take the covariance function of the Gaussian process to be the heat kernel, and computing the embedding amounts to sketching a matrix representing the heat kernel. The Karhunen-Lo\`eve expansion reveals that the straight-line distances in the embedding approximate the diffusion distance in a probabilistic sense, avoiding the need for sharp cutoffs and maintaining some of the smaller-scale structure. Our method demonstrates further advantage in its robustness to outliers. We justify the approach with both theory and experiments.
Code (0)
등록된 구현이 없습니다.
Tasks
Gaussian ProcessesMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Atlas Gaussian processes on restricted domains and point clouds
In real-world applications, data often reside in restricted domains with unknown boundaries, or as high-dimensional point clouds lying on a lower-dimensional, nontrivial, unknown manifold. Traditional Gaussian Processes …
Gaussian ProcessesPoint CloudsCost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs
This work discusses tensor network embeddings, which are random matrices ($S$) with tensor network structure. These embeddings have been used to perform dimensionality reduction of tensor network structured inputs $x$ an…
Dimensionality ReductionTensor DecompositionAccumulations of Projections--A Unified Framework for Random Sketches in Kernel Ridge Regression
Building a sketch of an n-by-n empirical kernel matrix is a common approach to accelerate the computation of many kernel methods. In this paper, we propose a unified framework of constructing sketching methods in kernel …
Computational EfficiencyregressionIntrinsic Gaussian Processes on Manifolds and Their Accelerations by Symmetry
Amidst the growing interest in nonparametric regression, we address a significant challenge in Gaussian processes(GP) applied to manifold-based predictors. Existing methods primarily focus on low dimensional constrained …
Gaussian ProcessesregressionNewton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. Randomized sketching has emerged as a powerful technique for constructing estimates o…