On the eigenspectrum of the gram matrix and the generalization error of kernel-PCA

In this paper, the relationships between the eigenvalues of the m/spl times/m Gram matrix K for a kernel /spl kappa/(/spl middot/,/spl middot/) corresponding to a sample x/sub 1/,...,x/sub m/ drawn from a density p(x) and the eigenvalues of the corresponding continuous eigenproblem is analyzed. The differences between the two spectra are bounded and a performance bound on kernel principal component analysis (PCA) is provided showing that good performance can be expected even in very-high-dimensional feature spaces provided the sample eigenvalues fall sufficiently quickly.

• Publication year

  2005

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2005-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2005.850052
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Kernel Methods for Pattern Analysis

  2004cited by this paper
• Rademacher and Gaussian Complexities: Risk Bounds and Structural Results

  2003influential reference
• Introduction to Support Vector Machines

  2002cited by this paper
• VARIATIONAL CHARACTERIZATION OF EIGENVALUES OF NONLINEAR EIGENPROBLEMS

  2002cited by this paper
• On the Concentration of Spectral Properties

  2001cited by this paper
• Link Analysis, Eigenvectors and Stability

  2001cited by this paper
• The Effect of the Input Density Distribution on Kernel-based Classifiers

  2000cited by this paper
• CONCENTRATION OF THE SPECTRAL MEASURE FOR LARGE MATRICES

  2000cited by this paper
• On the concentration of eigenvalues of random symmetric matrices

  2000cited by this paper
• On the distribution of the largest principal component

  2000cited by this paper
• Random matrix approximation of spectra of integral operators

  2000cited by this paper
• Authoritative sources in a hyperlinked environment

  1999cited by this paper
• A sharp concentration inequality with applications

  1999cited by this paper
• Numerical Treatment of the Integral Equations

  1999cited by this paper
• UCI Repository of machine learning databases

  1998cited by this paper
• The Anatomy of a Large-Scale Hypertextual Web Search Engine

  1998cited by this paper
• Kernel PCA and De-Noising in Feature Spaces

  1998cited by this paper
• Gaussian regression and optimal finite dimensional linear models

  1997cited by this paper
• New concentration inequalities in product spaces

  1996cited by this paper
• UCI Repository of Machine Learning Databases

  1996cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• ON WIELANDT'S INEQUALITY AND ITS APPLICATION TO THE ASYMPTOTIC DISTRIBUTION OF THE EIGENVALUES OF A RANDOM SYMMETRIC MATRIX

  1991cited by this paper
• Probability in Banach Spaces: Isoperimetry and Processes

  1991cited by this paper
• Surveys in Combinatorics, 1989: On the method of bounded differences

  1989cited by this paper
• The Numerical Treatment of Integral Equations

  1978cited by this paper
• Asymptotic distribution of the sample roots for a nonnormal population

  1976cited by this paper
• WEIGHTED SUMS OF CERTAIN DEPENDENT RANDOM VARIABLES

  1967cited by this paper
• ASYMPTOTIC THEORY FOR PRINCIPAL COMPONENT ANALYSIS

  1963cited by this paper
• The Distribution of the Latent Roots of the Covariance Matrix

  1960cited by this paper
• TESTS OF SIGNIFICANCE FOR THE LATENT ROOTS OF COVARIANCE AND CORRELATION MATRICES

  1956cited by this paper

• DeepWeightFlow: Re-Basined Flow Matching for Generating Neural Network Weights

  2026cites this paper
• Intrinsic dimensionality of molecular properties.

  2025cites this paper
• Time-Varying Gaussian Process Bandit Optimization with Experts: No-Regret in Logarithmically-Many Side Queries

  2025cites this paper
• A Geometric Analysis of PCA

  2025cites this paper
• On the study of frequency control and spectral bias in Wavelet-Based Kolmogorov Arnold networks: A path to physics-informed KANs

  2025cites this paper
• Efficient Estimation of Kernel Matrix Spectral Norm using Random Features

  2025cites this paper
• Contextures: Representations from Contexts

  2025cites this paper
• On the Eigenstructure of the Fisher Information Matrix and Its Role in Generalization Error

  2025cites this paper
• Eigenvalue distribution of some random matrices

  2025cites this paper
• Dextr: Zero-Shot Neural Architecture Search with Singular Value Decomposition and Extrinsic Curvature

  2025cites this paper
• Spectrally Transformed Kernel Regression

  2024cites this paper
• On the Statistical Complexity of Estimating VENDI Scores from Empirical Data

  2024cites this paper
• Sparse multiple kernel learning: Minimax rates with random projection

  2024cites this paper
• Do Vendi Scores Converge with Finite Samples? Truncated Vendi Score for Finite-Sample Convergence Guarantees

  2024cites this paper
• Generalisation bounds for kernel PCA through PAC‐Bayes learning

  2024cites this paper
• Extending Kernel Testing To General Designs

  2024cites this paper
• Coarse-grained quantum state tomography with optimal POVM construction

  2024cites this paper
• Fourier warm start for physics-informed neural networks

  2024cites this paper
• Distribution Free Domain Generalization

  2023cites this paper
• Dimension reduction and redundancy removal through successive Schmidt decompositions

  2023cites this paper
• A Distribution Free Truncated Kernel Ridge Regression Estimator and Related Spectral Analyses

  2023cites this paper
• On Uniform Consistency of Spectral Embeddings

  2023cites this paper
• Operator theory, kernels, and feedforward neural networks

  2023cites this paper
• Basis operator network: A neural network-based model for learning nonlinear operators via neural basis

  2023cites this paper
• Learning operators for identifying weak solutions to the Navier-Stokes equations

  2023cites this paper
• On Generalization Bounds for Projective Clustering

  2023cites this paper
• Modify Training Directions in Function Space to Reduce Generalization Error

  2023cites this paper
• Intelligent camouflage pattern generating in internet of things

  2022cites this paper
• of the Bernoulli Society for Mathematical Statistics and Probability Volume Twenty Eight Number Two May 2022

  2022cites this paper
• Kernel PCA for multivariate extremes

  2022cites this paper
• Understanding and Leveraging Overparameterization in Recursive Value Estimation

  2022cites this paper
• Bandwidth Enables Generalization in Quantum Kernel Models

  2022cites this paper
• Double information preserving canonical correlation analysis

  2022cites this paper
• Adaptive Classification Using Incremental Linearized Kernel Embedding

  2022cites this paper
• Statistical analysis of Mapper for stochastic and multivariate filters

  2022cites this paper
• Non-asymptotic properties of spectral decomposition of large Gram-type matrices and applications

  2022cites this paper
• Nonparametric Testing Under Randomized Sketching

  2021cites this paper
• TEC: Tensor Ensemble Classifier for Big Data

  2021cites this paper
• Sketched quantile additive functional regression

  2021cites this paper
• Kernel PCA with the Nyström method

  2021influential citation
• Kernel PCA with the Nystr\"om method

  2021influential citation
• Uniform Function Estimators in Reproducing Kernel Hilbert Spaces

  2021cites this paper
• On the Role of Optimization in Double Descent: A Least Squares Study

  2021cites this paper
• Statistical Depth Meets Machine Learning: Kernel Mean Embeddings and Depth in Functional Data Analysis

  2021cites this paper
• Statistical Optimality and Computational Efficiency of Nyström Kernel PCA

  2021influential citation
• Bi-adapting kernel learning for unsupervised domain adaptation

  2020cites this paper
• Model Reduction and Neural Networks for Parametric PDEs

  2020cites this paper
• Emergent behaviour in a system of industrial plants detected via manifold learning

  2020cites this paper
• Upper and Lower Bounds on the Performance of Kernel PCA

  2020influential citation
• On the eigenvector bias of Fourier feature networks: From regression to solving multi-scale PDEs with physics-informed neural networks

  2020influential citation
• Convergence of Sparse Variational Inference in Gaussian Processes Regression

  2020cites this paper
• Predicting Training Time Without Training

  2020cites this paper
• Reproducing kernels based schemes for nonparametric regression

  2020cites this paper
• Frequency Bias in Neural Networks for Input of Non-Uniform Density

  2020cites this paper
• Submitted to the Annals of Statistics CONCENTRATION OF KERNEL MATRICES WITH APPLICATION TO KERNEL SPECTRAL CLUSTERING By Arash

  2020cites this paper
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping

  2019cites this paper
• Statistical properties of Kernel Prinicipal Component Analysis

  2019cites this paper
• Sharp Theoretical Analysis for Nonparametric Testing under Random Projection

  2019cites this paper
• Learning and transferring motion style using Sparse PCA

  2019cites this paper
• Principal component analysis for multivariate extremes

  2019cites this paper
• Rates of Convergence for Sparse Variational Gaussian Process Regression

  2019cites this paper
• Gain with no Pain: Efficient Kernel-PCA by Nyström Sampling

  2019cites this paper
• Risk Bounds for Learning Multiple Components with Permutation-Invariant Losses

  2019cites this paper
• WLAN Indoor Intrusion Detection Based on Deep Signal Feature Fusion and Minimized-MKMMD Transfer Learning

  2019cites this paper
• High-probability bounds for the reconstruction error of PCA

  2019cites this paper
• The smallest eigenvalues of random kernel matrices: Asymptotic results on the min kernel

  2019cites this paper
• Relative concentration bounds for the spectrum of kernel matrices

  2018cites this paper
• Streaming Kernel PCA with Õ(√n) Random Features

  2018cites this paper
• ST ] 3 1 M ar 2 01 7 Robust Principal Component Analysis in Hilbert spaces

  2018cites this paper
• Signal-to-noise ratio in reproducing kernel Hilbert spaces

  2018cites this paper
• Design Manifolds Capture the Intrinsic Complexity and Dimension of Design Spaces

  2017cites this paper
• Random Discretization of the Finite Fourier Transform and Related Kernel Random Matrices

  2017cites this paper
• Robust PCA and pairs of projections in a Hilbert space

  2017cites this paper
• Statistical Analysis and Parameter Selection for Mapper

  2017influential citation
• Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off

  2017cites this paper
• Statistical Consistency of Kernel PCA with Random Features

  2017cites this paper
• Compressive Statistical Learning with Random Feature Moments

  2017cites this paper
• GRAPHICAL MODELS FOR HIGH DIMENSIONAL DATA WITH GENOMIC APPLICATIONS

  2017influential citation
• On metric and statistical properties of topological descriptors for geometric data. (Sur les propriétés métriques et statistiques des descripteurs topologiques pour les données géométriques)

  2017cites this paper
• Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks

  2017cites this paper
• Nonasymptotic upper bounds for the reconstruction error of PCA

  2016cites this paper
• Kernel Learning and Applications in Wireless Localization by Qiaojun Wang Dissertation Director :

  2016cites this paper
• Un test statistique pour la détection d'anomalies basé sur l'erreur de reconstruction de l'ACP à noyau

  2016cites this paper
• Stochastic Optimization for Kernel PCA

  2016cites this paper
• Robust Principal Component Analysis in Hilbert spaces

  2016influential citation
• Multi-view dimensionality reduction via canonical random correlation analysis

  2016cites this paper
• Learning and Mapping onto Manifolds with Applications to Patch-based Image Processing

  2016cites this paper
• Kernel learning and applications in wireless localization

  2016cites this paper
• Bernoulli Robust dimension-free Gram operator estimates

  2016cites this paper
• Canonical sparse cross-view correlation analysis

  2016cites this paper
• Robust dimension-free Gram operator estimates

  2015cites this paper
• Explicit Embeddings for Nearest Neighbor Search with Mercer Kernels

  2015cites this paper
• A Dimension-Independent Generalization Bound for Kernel Supervised Principal Component Analysis

  2015cites this paper
• Kernel Manifold Alignment for Domain Adaptation

  2015cites this paper
• Spectral Norm of Random Kernel Matrices with Applications to Privacy

  2015cites this paper
• Convergence of Laplacian spectra from random samples

  2015cites this paper
• The Efficiency of Density Deconvolution

  2015cites this paper
• Generalization bounds for random samples in Hilbert spaces

  2015cites this paper
• Subspace Learning with Partial Information

  2014cites this paper
• Compressed sensing and dimensionality reduction for unsupervised learning. (Échantillonnage compressé et réduction de dimension pour l'apprentissage non supervisé)

  2014cites this paper