mlsanityData to 14 Oct 2026

Entrywise error bounds for low-rank approximations of kernel matrices

arXiv 2405.14494 ↗First posted 23 May 2024math.ST cs.LG stat.THcited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper, we derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition (or singular value decomposition). While this approximation is well-known to be optimal with respect to the spectral and Frobenius norm error, little is known about the statistical behaviour of individual entries. Our error bounds fill this gap. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues, which takes inspiration from the field of Random Matrix Theory. Finally, we validate our theory with an empirical study of a collection of synthetic and real-world datasets.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 21 of its 107 references that are in the map. First posted on arXiv 23 May 2024.

Builds on

21 of 107 references.

References · 21

  1. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  2. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  3. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 112
  4. 2013Revisiting the Nystrom Method for Improved Large-Scale Machine Learningcited by 77
  5. 2017A statistical interpretation of spectral embedding: the generalised random dot product graphcited by 55
  6. 2014Distinguishing cause from effect using observational data: methods and benchmarkscited by 33
  7. 2018Approximation beats concentration? An approximation view on inference with smooth radial kernelscited by 33
  8. 2017Near-optimal bounds for phase synchronizationcited by 32
  9. 2023On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domainscited by 31
  10. 2017Rates of Convergence of Spectral Methods for Graphon Estimationcited by 28
  11. 2023Generalization in Kernel Regression Under Realistic Assumptionscited by 27
  12. 2013Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embeddingcited by 23
9 more
  1. 2017Estimating Mixed Memberships with Sharp Eigenvector Deviationscited by 22
  2. 2014Kernel Mean Shrinkage Estimatorscited by 16
  3. 2017Unperturbed: spectral analysis beyond Davis-Kahancited by 16
  4. 2016Bayesian Learning of Kernel Embeddingscited by 15
  5. 2016Greedy Column Subset Selection: New Bounds and Distributed Algorithmscited by 13
  6. 2018Network Representation Using Graph Root Distributionscited by 12
  7. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 10
  8. 2018Relative concentration bounds for the spectrum of kernel matricescited by 4
  9. 2019Affine Invariant Covariance Estimation for Heavy-Tailed Distributionscited by 3

Built on by

Not cited yet.