Manifold learning from structured kernels and out of sample extensions - Salhov, Moshe (2014)
Diffusion Maps (DM) and other kernel methods are utilized for the analysis of high dimensional big data. The DM method uses a Markovian diffusion process to model and analyze data. This thesis proposes a combination of techniques aimed to extend kernel methods to reduce their associated computational complexity. In many cases, the performance of a spectral embedding based learning mechanism is limited due to two factors. The first factor is the use of a distance metric among the multidimensional data points in the kernel construction. The second factor is the computational complexity of the kernel construction and its spectral decomposition. To improve the first factor, this thesis proposes to extend the scalar relations used in kernel computational methodologies such as DM framework to matrix type computations, which can encompass multidimensional similarities between local neighborhoods of multidimensional data points on the manifold. Furthermore, the use of multidimensional similarities might result in a bigger kernel that significantly increases its computational complexity. In order to reduce the computational complexity, which is associated with both DM kernel or its proposed extension, this thesis proposes several dictionary based constructions to efficiently approximate the corresponding spectral decomposition efficiently of DM and its proposed patch based extension. This work is supplemented by providing an out-of-sample extension for vector fields.