On the Eigenspectrum of the Gram Matrix and the Generalization Error of Kernel-PCA
IEEE Transactions on Information TheoryPublished 28 June 2005
John Shawe‐Taylor, Chris K. Williams, Nello Cristianini, Jaz Kandola
Citations151
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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.
Abstract
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.
Keywords
Computer ScienceMathematicsEngineering
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
Journal of the ACMAuthoritative sources in a hyperlinked environment
9,060 Citations1999Jon Kleinberg
This work proposes and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure, and has connections to the eigenvectors of certain matrices associated with the link graph.
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
Cambridge University Press eBooksKernel Methods for Pattern Analysis
6,598 Citations2004John Shawe‐Taylor, Nello Cristianini
This book provides an easy introduction for students and researchers to the growing field of kernel-based pattern analysis, demonstrating with examples how to handcraft an algorithm or a kernel for a new specific application, and covering all the necessary conceptual and mathematical tools to do so.
Journal of the American Statistical AssociationProbability Inequalities for Sums of Bounded Random Variables
4,750 Citations1963Wassily Hoeffding
ePrints Soton (University of Southampton)An Introduction to Support Vector Machines
4,120 Citations2000Nello Cristianini, John Shawe‐Taylor
Lecture notes in computer scienceRademacher and Gaussian Complexities: Risk Bounds and Structural Results
2,111 Citations2001Peter L. Bartlett, Shahar Mendelson
This work investigates the use of certain data-dependent estimates of the complexity of a function class called Rademacher and Gaussian complexities and proves general risk bounds in terms of these complexities in a decision theoretic setting.
Cambridge University Press eBooksOn the method of bounded differences
1,428 Citations1989Colin McDiarmid
Probability in Banach Spaces
1,414 Citations1991Michel Ledoux, Michel Talagrand
Probability in Banach Spaces: Isoperimetry and Processes
1,276 Citations1991Michel Ledoux, Michel Talagrand
The Annals of Mathematical StatisticsAsymptotic Theory for Principal Component Analysis
1,153 Citations1963T. W. Anderson
Journal of the American Statistical AssociationProbability Inequalities for Sums of Bounded Random Variables
1,127 Citations1963Wassily Hoeffding
Kernel PCA and De-Noising in Feature Spaces
828 Citations1998Sebastian Mika, Bernhard Schölkopf +4 more
This work presents ideas for finding approximate pre-images, focusing on Gaussian kernels, and shows experimental results using these pre- images in data reconstruction and de-noising on toy examples as well as on real world data.
Inventiones mathematicaeNew concentration inequalities in product spaces
517 Citations1996Michel Talagrand
BiometrikaTESTS OF SIGNIFICANCE FOR THE LATENT ROOTS OF COVARIANCE AND CORRELATION MATRICES
343 Citations1956D. N. Lawley
Electronic Communications in ProbabilityConcentration of the Spectral Measure for Large Matrices
244 Citations2000Alice Guionnet, Ofer Zeitouni
It is derived that concentration inequalities for functions of the empirical measure of eigenvalues for large, random, self adjoint matrices, with not necessarily Gaussian entries, are derived.
Link analysis, eigenvectors and stability
203 Citations2001Andrew Y. Ng, Alice X. Zheng +1 more
This paper addresses the question of when HITS and PageRank can be expected to give stable rankings under small perturbations to the hyperlink patterns, using tools from matrix perturbation theory and Markov chain theory.
Random Structures and AlgorithmsA sharp concentration inequality with applications
184 Citations2000Stéphane Boucheron, G�bor Lugosi +1 more
The Annals of Mathematical StatisticsThe Distribution of the Latent Roots of the Covariance Matrix
163 Citations1960A. T. James
BernoulliRandom Matrix Approximation of Spectra of Integral Operators
154 Citations2000Vladimir Koltchinskii, Evarist Giné +1 more
Israel Journal of MathematicsOn the concentration of eigenvalues of random symmetric matrices
140 Citations2002Noga Alon, Michael Krivelevich +1 more
The Effect of the Input Density Distribution on Kernel-based Classifiers
139 Citations2000Christopher K. I. Williams, Matthias Seeger
Gaussian process ; Nystroem approximation Reference EPFL-CONF-161323 Record created on 2010-12-02, modified on 2016-08-09.
BiometrikaAsymptotic distribution of the sample roots for a nonnormal population
124 Citations1976Christine Waternaux
The Annals of StatisticsOn Wielandt's Inequality and Its Application to the Asymptotic Distribution of the Eigenvalues of a Random Symmetric Matrix
116 Citations1991Morris L. Eaton, David E. Tyler
Aston Publications Explorer (Aston University)Gaussian regression and optimal finite dimensional linear models
84 Citations1997Huaiyu Zhu, Christopher K. I. Williams +2 more
On the Distribution of the Largest Principal Component
43 Citations2000Iain M. Johnstone
The MIT Press eBooksOn the Concentration of Spectral Properties
32 Citations2002John Shawe‐Taylor, Nello Cristianini +1 more
The residuals when data is projected into a subspace is shown to be reliably estimated on a random sample of points as can the sum of the tail of eigenvalues.