Spectral convergence of the connection Laplacian from random samples

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

Authors: A. Singer, H.-T. Wu 

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

Recommendations

• Convergence of Laplacian spectra from random samples
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Towards a theoretical foundation for Laplacian-based manifold methods
• Spectral convergence of graph Laplacian and heat kernel reconstruction in \(L^\infty\) from random samples
• Graph Laplacians and their convergence on random neighborhood graphs

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

• Weak convergence and empirical processes. With applications to statistics
• Diffusion maps
• Title not available (Why is that?)
• Consistency of spectral clustering
• Embedding Riemannian manifolds by their heat kernel
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Orientability and diffusion maps
• A Cheeger Inequality for the Graph Connection Laplacian
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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 (44)

• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Lipschitz regularity of graph Laplacians on random data clouds
• 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
• Analysis of \(p\)-Laplacian regularization in semisupervised learning
• Point Integral Method for Solving Poisson-Type Equations on Manifolds from Point Clouds with Convergence Guarantees
• Consistency of modularity clustering on random geometric graphs
• A metric on directed graphs and Markov chains based on hitting probabilities
• Ricci curvature and the manifold learning problem
• Graph approximations to the Laplacian spectra
• Continuum limits of nonlocal \(p\)-Laplacian variational problems on graphs
• Convergence of the point integral method for Laplace-Beltrami equation on point cloud
• A convergent point integral method for isotropic elliptic equations on a 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
• Recovering hidden components in multimodal data with composite diffusion operators
• A geometrical method for low-dimensional representations of simulations
• The diffusion geometry of fibre bundles: horizontal diffusion maps
• Variational limits of \(k\)-NN graph-based functionals on data clouds
• A graph discretized approximation of semigroups for diffusion with drift and killing on a complete Riemannian manifold
• Learning Theory
• Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
• Convergence of Laplacian eigenmaps and its rate for submanifolds with singularities
• Modified virtual grid difference for discretizing the Laplace-Beltrami operator on point clouds
• Vector diffusion maps and the connection Laplacian
• 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
• Learning by unsupervised nonlinear diffusion
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• Manifold embeddings by heat kernels of connection Laplacian
• Towards a theoretical foundation for Laplacian-based manifold methods
• Harmonic Extension on The Point Cloud
• On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms
• Convergence of Laplacian spectra from random samples
• Spectral convergence of graph Laplacian and heat kernel reconstruction in \(L^\infty\) from random samples
• An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
• 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)