Manifold learning with bi-stochastic kernels

Abstract

In this paper we answer the following question: what is the infinitesimal generator of the diffusion process defined by a kernel that is normalized such that it is bi-stochastic with respect to a specified measure? More precisely, under the assumption that data is sampled from a Riemannian manifold we determine how the resulting infinitesimal generator depends on the potentially nonuniform distribution of the sample points, and the specified measure for the bi-stochastic normalization. In a special case, we demonstrate a connection to the heat kernel. We consider both the case where only a single data set is given, and the case where a data set and a reference set are given. The spectral theory of the constructed operators is studied, and Nyström extension formulas for the gradients of the eigenfunctions are computed. Applications to discrete point sets and manifold learning are discussed.

18 pages, 5 figures

Cited by in corpus (12)

• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Sinkformers: Transformers with Doubly Stochastic Attention
• Localized Fourier Analysis for Graph Signal Processing
• Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation
• Convergence of Graph Laplacian with kNN Self-tuned Kernels
• Data-driven discovery of quasiperiodically driven dynamics
• Local Two-Sample Testing over Graphs and Point-Clouds by Random-Walk Distributions
• Conditional expectation using compactification operators
• Scaling positive random matrices: concentration and asymptotic convergence
• Spectral Flow on the Manifold of SPD Matrices for Multimodal Data Processing
• A probabilistic approach to drift estimation from stochastic data
• A low discrepancy sequence on graphs