Central limit theorems for the eigenvalues of graph Laplacians on data clouds

• URL: http://arxiv.org/abs/2507.18803v1
• Date: Thu, 24 Jul 2025 21:03:20 GMT
• Title: Central limit theorems for the eigenvalues of graph Laplacians on data clouds
• Authors: Chenghui Li, Nicolás García Trillos, Housen Li, Leo Suchan,
• Abstract summary: We consider the Laplacian operator $Delta_n$ associated to an $varepsilon$-sqrt graph over $X_n$.<n>A formal argument allows us to interpret this variance as the dissipation of a suitable energy with respect to the Fisher-Rao geometry.<n>A statistical interpretation of the geometric variance in terms of a Cramer-Rao lower bound for the estimation of the eigenvalues of certain weighted Laplace-Beltrami operator.
• Score: 6.993491018326815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given i.i.d.\ samples $X_n =\{ x_1, \dots, x_n \}$ from a distribution supported on a low dimensional manifold ${M}$ embedded in Eucliden space, we consider the graph Laplacian operator $\Delta_n$ associated to an $\varepsilon$-proximity graph over $X_n$ and study the asymptotic fluctuations of its eigenvalues around their means. In particular, letting $\hat{\lambda}_l^\varepsilon$ denote the $l$-th eigenvalue of $\Delta_n$, and under suitable assumptions on the data generating model and on the rate of decay of $\varepsilon$, we prove that $\sqrt{n } (\hat{\lambda}_{l}^\varepsilon - \mathbb{E}[\hat{\lambda}_{l}^\varepsilon] )$ is asymptotically Gaussian with a variance that we can explicitly characterize. A formal argument allows us to interpret this asymptotic variance as the dissipation of a gradient flow of a suitable energy with respect to the Fisher-Rao geometry. This geometric interpretation allows us to give, in turn, a statistical interpretation of the asymptotic variance in terms of a Cramer-Rao lower bound for the estimation of the eigenvalues of certain weighted Laplace-Beltrami operator. The latter interpretation suggests a form of asymptotic statistical efficiency for the eigenvalues of the graph Laplacian. We also present CLTs for multiple eigenvalues and through several numerical experiments explore the validity of our results when some of the assumptions that we make in our theoretical analysis are relaxed.

Related papers

• Minimax Rates for the Estimation of Eigenpairs of Weighted Laplace-Beltrami Operators on Manifolds [7.639886528552829]
  We study the problem of estimating eigenpairs of elliptic differential operators from samples of a distribution $rho$ supported on a manifold $M$.<n>We find that eigenpairs of graph Laplacians induce regularity manifold estimators with an error of approximation that, up to logarithmic corrections, matches our lower bounds.
  arXiv  Detail & Related papers  (2025-05-30T19:19:25Z)
• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  We develop and analyze data subsampling techniques for Poisson regression. In particular, we consider the Poisson generalized linear model with ID- and square root-link functions.
  arXiv  Detail & Related papers  (2024-10-30T10:09:05Z)
• A kernel-based analysis of Laplacian Eigenmaps [1.5229257192293204]
  We study the spectral properties of the associated empirical graph Laplacian based on a Gaussian kernel. Our main results are non-asymptotic error bounds, showing that the eigenvalues and eigenspaces of the empirical graph Laplacian are close to the eigenvalues and eigenspaces of the Laplace-Beltrami operator of $mathcalM$.
  arXiv  Detail & Related papers  (2024-02-26T11:00:09Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  Existing theories on deep nonparametric regression have shown that when the input data lie on a low-dimensional manifold, deep neural networks can adapt to intrinsic data structures. This paper introduces a relaxed assumption that input data are concentrated around a subset of $mathbbRd$ denoted by $mathcalS$, and the intrinsic dimension $mathcalS$ can be characterized by a new complexity notation -- effective Minkowski dimension.
  arXiv  Detail & Related papers  (2023-06-26T17:13:31Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
  arXiv  Detail & Related papers  (2021-04-26T15:03:08Z)
• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation [16.891059233061767]
  We study the spectral convergence of graph Laplacian to the Laplace-Beltrami operator. Data are uniformly sampled on a $d$-dimensional manifold. We prove new point-wise and Dirichlet form convergence rates for the density-corrected graph Laplacian.
  arXiv  Detail & Related papers  (2021-01-25T03:22:18Z)
• Random Geometric Graphs on Euclidean Balls [2.28438857884398]
  We consider a latent space model for random graphs where a node $i$ is associated to a random latent point $X_i$ on the Euclidean unit ball. For certain link functions, the model considered here generates graphs with degree distribution that have tails with a power-law-type distribution.
  arXiv  Detail & Related papers  (2020-10-26T17:21:57Z)
• Lipschitz regularity of graph Laplacians on random data clouds [1.2891210250935146]
  We prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues.
  arXiv  Detail & Related papers  (2020-07-13T20:43:19Z)
• GO Hessian for Expectation-Based Objectives [73.06986780804269]
  GO gradient was proposed recently for expectation-based objectives $mathbbE_q_boldsymbolboldsymbolgamma(boldsymboly) [f(boldsymboly)]$. Based on the GO gradient, we present for $mathbbE_q_boldsymbolboldsymbolgamma(boldsymboly) [f(boldsymboly)]$ an unbiased low-variance Hessian estimator, named GO Hessian.
  arXiv  Detail & Related papers  (2020-06-16T02:20:41Z)
• Spectral density estimation with the Gaussian Integral Transform [91.3755431537592]
  spectral density operator $hatrho(omega)=delta(omega-hatH)$ plays a central role in linear response theory. We describe a near optimal quantum algorithm providing an approximation to the spectral density.
  arXiv  Detail & Related papers  (2020-04-10T03:14:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.