Towards Spectral Convergence of Locally Linear Embedding on Manifolds with Boundary

• URL: http://arxiv.org/abs/2501.09572v1
• Date: Thu, 16 Jan 2025 14:45:53 GMT
• Title: Towards Spectral Convergence of Locally Linear Embedding on Manifolds with Boundary
• Authors: Andrew Lyons,
• Abstract summary: We study the eigenvalues and eigenfunctions of a differential operator that governs the behavior of the unsupervised learning algorithm known as Locally Linear Embedding. We show that a natural regularity condition on the eigenfunctions imposes a consistent boundary condition and use the Frobenius method to estimate pointwise behavior.
• Score: 0.0
• License:
• Abstract: We study the eigenvalues and eigenfunctions of a differential operator that governs the asymptotic behavior of the unsupervised learning algorithm known as Locally Linear Embedding when a large data set is sampled from an interval or disc. In particular, the differential operator is of second order, mixed-type, and degenerates near the boundary. We show that a natural regularity condition on the eigenfunctions imposes a consistent boundary condition and use the Frobenius method to estimate pointwise behavior. We then determine the limiting sequence of eigenvalues analytically and compare them to numerical predictions. Finally, we propose a variational framework for determining eigenvalues on other compact manifolds.

Related papers

• Simple Relative Deviation Bounds for Covariance and Gram Matrices [34.99810116340191]
  We provide non-asymptotic, relative deviation bounds for the eigenvalues of empirical covariance and gram matrices. Our results provide sharper control across the spectrum.
  arXiv  Detail & Related papers  (2024-10-08T07:28:56Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Eigenvalue sensitivity from eigenstate geometry near and beyond arbitrary-order exceptional points [0.0]
  Systems with an effectively non-Hermitian Hamiltonian display an enhanced sensitivity to parametric and dynamic perturbations. This sensitivity can be quantified by the phase rigidity, which mathematically corresponds to the eigenvalue condition number. I derive an exact nonperturbative expression for this sensitivity measure that applies to arbitrary eigenvalue configurations.
  arXiv  Detail & Related papers  (2023-07-12T16:36:39Z)
• Convex Bounds on the Softmax Function with Applications to Robustness Verification [69.09991317119679]
  The softmax function is a ubiquitous component at the output of neural networks and increasingly in intermediate layers as well. This paper provides convex lower bounds and concave upper bounds on the softmax function, which are compatible with convex optimization formulations for characterizing neural networks and other ML models.
  arXiv  Detail & Related papers  (2023-03-03T05:07:02Z)
• Quantitative deterministic equivalent of sample covariance matrices with a general dependence structure [0.0]
  We prove quantitative bounds involving both the dimensions and the spectral parameter, in particular allowing it to get closer to the real positive semi-line. As applications, we obtain a new bound for the convergence in Kolmogorov distance of the empirical spectral distributions of these general models.
  arXiv  Detail & Related papers  (2022-11-23T15:50:31Z)
• Sensitivity of non-Hermitian systems [0.0]
  We describe a method to find the eigenvalues of one-dimensional one-band models with arbitrary boundary conditions. By stacking one-dimensional chains, we use the derived results to find corresponding conditions for insensitivity for some two-dimensional systems with periodic boundary conditions in one direction.
  arXiv  Detail & Related papers  (2022-06-17T19:16:07Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• A Szeg\H{o} type theorem and distribution of symplectic eigenvalues [0.0]
  We study the properties of stationary G-chains in terms of their generating functions. We derive an expression for the entropy rate of stationary quantum Gaussian processes.
  arXiv  Detail & Related papers  (2020-06-21T15:37:52Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)

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.