  Practical applications of kernel methods often use variable bandwidth
kernels, also known as self-tuning kernels, however much of the current theory
of kernel based techniques is only applicable to fixed bandwidth kernels. In
this paper, we derive the asymptotic expansion of these variable bandwidth
kernels for arbitrary bandwidth functions; generalizing the theory of Diffusion
Maps and Laplacian Eigenmaps. We also derive pointwise error estimates for the
corresponding discrete operators which are based on finite data sets;
generalizing a result of Singer which was restricted to fixed bandwidth
kernels. Our analysis reveals how areas of small sampling density lead to large
errors, particularly for fixed bandwidth kernels. We explain the limitation of
the existing theory to data sampled from compact manifolds by showing that when
the sampling density is not bounded away from zero (which implies that the data
lies on an open set) the error estimates for fixed bandwidth kernels will be
unbounded. We show that this limitation can be overcome by choosing a bandwidth
function inversely proportional to the sampling density (which can be estimated
from data) which allows us to control the error estimates uniformly over a
non-compact manifold. We numerically verify these results on non-compact
manifolds by constructing the generator of the Ornstein-Uhlenbeck process on a
real line and a two-dimensional plane using data sampled independently from the
respective invariant measures. We also verify our results on compact manifolds
by constructing the Laplacian on the unit circle and the unit sphere and we
show that the variable bandwidth kernels exhibit reduced sensitivity to
bandwidth selection and give better results for an automatic bandwidth
selection algorithm.
