Diffusion Maps : Using the Semigroup Property for Parameter Tuning

Diffusion maps (DM) [4] are used in machine-learning to achieve dimension reduction for data that are assumed to be sampled from a lower-dimensional manifold within a higherdimensional setting; they are related to other kernel eigenmap methods such as Laplacian eigenmaps [1], local linear embedding [10], Hessian eigenmaps [6] and local tangent space alignment [12]. The basic idea is simple: diffusion on a manifold is governed by the semigroup generated by the manifold's Laplace-Beltrami operator; the spectral analysis of the diffusion operator thus provides information about the manifold that can be used to provide a lower-dimensional parametrization for the data that also removes "noise" from the data inconsistent with the manifold hypothesis. One can (approximately) simulate a random walk or diffusion process on the (unknown) manifold by taking small steps within the data set according to probabilities estimated from the distances between data points.