Lorenzo Rosasco, Mikhail Belkin, Ernesto De Vito.
Year: 2010, Volume: 11, Issue: 30, Pages: 905−934
A large number of learning algorithms, for example, spectral clustering, kernel Principal Components Analysis and many
manifold methods are based on estimating eigenvalues and eigenfunctions of operators defined
by a similarity function or a kernel, given empirical data. Thus for the analysis of algorithms, it is an important
problem to be able to assess the quality of such approximations.
The contribution of our paper is two-fold:
1. We use a technique based on a concentration inequality for Hilbert spaces to provide new much simplified proofs for a number of results in spectral approximation.
2. Using these methods we provide several new results for estimating spectral properties of the graph Laplacian operator extending and strengthening results from von Luxburg et al. (2008).