Complexity bounds for continuum versions of eigenfunction-embedding algorithms

  • Jim Portegies (MPI MiS, Leipzig)
A3 02 (Seminar room)


To recognize nonlinear structure in data sets, certain algorithms, such as the Eigenmaps and Diffusion Maps algorithms, use eigenfunctions of the Laplace operator on data graphs to embed the data in a low-dimensional Euclidean space. We study continuum versions of these algorithms. In particular, we derive bounds on their complexity, in that we show that the number of eigenfunctions needed only depends on the dimension, a Ricci curvature lower bound, the injectivity radius and the volume. To get an explicit bound, we need a quantitative estimate on the $C^\alpha$ Harmonic Radius that was introduced by Anderson and Cheeger.

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail