Research map / Learning theory and algorithms / Matrix and tensor methods
Entrywise error bounds for low-rank approximations of kernel matrices
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives entrywise (max-norm) error bounds for truncated eigendecomposition low-rank approximations of kernel matrices, via a delocalisation result for small-eigenvalue eigenvectors of kernel matrices with non-zero mean and dependent entries.
Problem
Entrywise error of best rank-d approximations (truncated eigendecomposition/SVD) of kernel matrices is poorly understood, although spectral and Frobenius errors are well characterised.
Approach
Bounds the max-norm error of the truncated eigendecomposition by sum of tail eigenvalues times the squared sup-norm of tail eigenvectors, and proves complete delocalisation of those eigenvectors for kernel matrices using a principal-minor eigenvector identity, a new concentration lemma for the distance between a non-zero-mean random vector and a subspace, and relative eigenvalue concentration.
Key results
- Under polynomial eigenvalue decay, entrywise error O(n^{-(alpha-1)/alpha} log n) with rank d = Omega(n^{1/alpha}) holds with overwhelming probability.
- Under exponential eigenvalue decay, entrywise error O(n^{-1}) is achieved with poly-log rank d > log^{1/gamma}(n^{1/beta}).
- Empirically, max entrywise error decays quickly with rank for low-dimensional datasets but slowly for high-dimensional 20 Newsgroups and Zebrafish, even for smooth RBF kernels.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use smoother Matérn kernels instead of the less-smooth Matérn kernel | Truncated SVD kernel-matrix approximation · GMM, Abalone, Wine Quality, MNIST | maximum entrywise error | Helped |
| Increase kernel smoothness | Truncated SVD kernel-matrix approximation · GMM, Abalone, Wine Quality, MNIST | maximum entrywise error decay rate | Helped |
| Apply the approximation to high-dimensional data, including 20 Newsgroups and Zebrafish | Truncated SVD kernel-matrix approximation · 20 Newsgroups, Zebrafish | maximum entrywise error | Hurt |
| Increase rank from d = 2500 to d = 3000 | Truncated SVD kernel-matrix approximation · 20 Newsgroups | maximum entrywise error | Helped |
Surprising findings
- Even for the smooth RBF kernel, maximum entrywise error decays very slowly on high-dimensional datasets (20 Newsgroups, Zebrafish), suggesting theory does not carry over to high dimensions.
- 20 Newsgroups shows a sharp drop in max entrywise error between d=2500 and d=3000 not visible in Frobenius error.
Limitations
- Analysis restricted to the low-dimensional regime with fixed input dimension p.
- Requires positive semi-definite continuous bounded kernels; verifying eigenfunction sup-norm and regularity assumptions under general distributions is difficult.
- Unclear whether the bounds are tight or the truncated eigendecomposition is entrywise optimal.
Experimental setup
Datasets: GMM (synthetic) Abalone Wine Quality MNIST 20 Newsgroups Zebrafish
Benchmarks: GMM Abalone Wine Quality MNIST 20 Newsgroups Zebrafish
Metrics: maximum entrywise error Frobenius norm error
Baselines: random projection low-rank approximation (JL-based)
Builds on: Eckart-Young-Mirsky theorem Talagrand's inequality Johnson-Lindenstrauss lemma
Closest papers by meaning
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.90)
- Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products (NeurIPS 2023 · similarity 0.88)
- Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? (NeurIPS 2017 · similarity 0.88)
- Faster Kernel Matrix Algebra via Density Estimation (ICML 2021 · similarity 0.88)
- Perturbation Bounds for Low-Rank Inverse Approximations under Noise (NeurIPS 2025 · similarity 0.88)
- Coherence-free Entrywise Estimation of Eigenvectors in Low-rank Signal-plus-noise Matrix Models (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.