Abstract for the talk at 16.09.2014 (14:00 h)Special Seminar
Jim Portegies (MPI MIS, Leipzig)
Complexity bounds for continuum versions of eigenfunction-embedding algorithms
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α Harmonic Radius that was introduced by Anderson and Cheeger.