Spectral convergence of the connection Laplacian from random samples

DOI10.1093/IMAIAI/IAW016zbMATH Open1386.94055arXiv1306.1587OpenAlexW2963954124MaRDI QIDQ4603718FDOQ4603718

H.-T. Wu, A. Singer

Publication date: 19 February 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: Spectral methods that are based on eigenvectors and eigenvalues of discrete graph Laplacians, such as Diffusion Maps and Laplacian Eigenmaps are often used for manifold learning and non-linear dimensionality reduction. It was previously shown by Belkin and Niyogi cite{belkin_niyogi:2007} that the eigenvectors and eigenvalues of the graph Laplacian converge to the eigenfunctions and eigenvalues of the Laplace-Beltrami operator of the manifold in the limit of infinitely many data points sampled independently from the uniform distribution over the manifold. Recently, we introduced Vector Diffusion Maps and showed that the connection Laplacian of the tangent bundle of the manifold can be approximated from random samples. In this paper, we present a unified framework for approximating other connection Laplacians over the manifold by considering its principle bundle structure. We prove that the eigenvectors and eigenvalues of these Laplacians converge in the limit of infinitely many independent random samples. We generalize the spectral convergence results to the case where the data points are sampled from a non-uniform distribution, and for manifolds with and without boundary.

Full work available at URL: https://arxiv.org/abs/1306.1587

zbMATH Keywords

diffusion mapsgraph connection Laplacianprincipal bundlevector diffusion mapsorientable diffusion mapsvector diffusion distance

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Spectral problems; spectral geometry; scattering theory on manifolds (58J50) Sampling theory in information and communication theory (94A20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Weak convergence and empirical processes. With applications to statistics
• Diffusion maps
• Consistency of spectral clustering
• Embedding Riemannian manifolds by their heat kernel
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• From graph to manifold Laplacian: the convergence rate
• \(C^1\) isometric imbeddings
• Vector diffusion maps and the connection Laplacian
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Learning Theory
• The imbedding problem for Riemannian manifolds
• Orientability and diffusion maps
• A Cheeger Inequality for the Graph Connection Laplacian
• Viewing Angle Classification of Cryo-Electron Microscopy Images Using Eigenvectors
• Alternating projection, ptychographic imaging and phase synchronization
• Embedding Riemannian manifolds by the heat kernel of the connection Laplacian
• Graph connection Laplacian methods can be made robust to noise
• Representation theoretic patterns in three-dimensional cryo-electron microscopy. II: The class averaging problem
• Learning Theory
• Geometry of manifolds.
• Local Linear Regression on Manifolds and Its Geometric Interpretation
• Non-asymptotic analysis of tangent space perturbation

Cited In (39)

• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Variational Limits of $k$-NN Graph-Based Functionals on Data Clouds
• A Geometrical Method for Low-Dimensional Representations of Simulations
• Data-driven efficient solvers for Langevin dynamics on manifold in high dimensions
• Explore Intrinsic Geometry of Sleep Dynamics and Predict Sleep Stage by Unsupervised Learning Techniques
• Uniform upper bounds on Courant sharp Neumann eigenvalues of chain domains
• Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
• Modified Virtual Grid Difference for Discretizing the Laplace--Beltrami Operator on Point Clouds
• Point Integral Method for Solving Poisson-Type Equations on Manifolds from Point Clouds with Convergence Guarantees
• Consistency of modularity clustering on random geometric graphs
• Ricci curvature and the manifold learning problem
• Graph approximations to the Laplacian spectra
• Convergence of the point integral method for Laplace-Beltrami equation on point cloud
• Construction and Monte Carlo estimation of wavelet frames generated by a reproducing kernel
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Title not available (Why is that?)
• The diffusion geometry of fibre bundles: horizontal diffusion maps
• A graph discretized approximation of semigroups for diffusion with drift and killing on a complete Riemannian manifold
• Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
• Title not available (Why is that?)
• Lipschitz Regularity of Graph Laplacians on Random Data Clouds
• Embeddings of Riemannian manifolds with finite eigenvector fields of connection Laplacian
• Approximations of the connection Laplacian spectra
• Think globally, fit locally under the manifold setup: asymptotic analysis of locally linear embedding
• The SPDE approach to Matérn fields: graph representations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Latent common manifold learning with alternating diffusion: analysis and applications
• Analysis of $p$-Laplacian Regularization in Semisupervised Learning
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• Manifold embeddings by heat kernels of connection Laplacian
• A Metric on Directed Graphs and Markov Chains Based on Hitting Probabilities
• Continuum Limits of Nonlocal $p$-Laplacian Variational Problems on Graphs
• Harmonic Extension on The Point Cloud
• Spectral convergence of graph Laplacian and heat kernel reconstruction in \(L^\infty\) from random samples
• Recovering Hidden Components in Multimodal Data with Composite Diffusion Operators
• An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
• A Convergent Point Integral Method for Isotropic Elliptic Equations on a Point Cloud
• Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs

This page was built for publication: Spectral convergence of the connection Laplacian from random samples

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603718)