Speaker: Avner Halevy (NWC)

Title: Towards Dimensionality Reduction: Convergence of Discrete Approximations of the Laplace-Beltrami Operator


Laplacian Eigenmaps, a geometrically motivated algorithm for dimensionality reduction, is based on the assumption that high-dimensional data tends to lie on a low-dimensional manifold. Eigenfunctions of the Laplace-Beltrami operator on this manifold give rise to smooth mappings into low-dimensional space, which are faithful to the geometry of the manifold. The computation of a low-dimensional representation is therefore reduced to finding these eigenfunctions. However, the manifold and the operator are not available. Instead, we only have a finite collection of data points which are assumed to have been sampled from the manifold. The main challenge is then to construct discrete approximations of the Laplace-Beltrami operator. Until recently, convergence of these approximations, in various senses, to the true operator, had not been proven. In this talk, I shall present several results in this direction, which establish firm foundations for this algorithm. I shall also describe a new method for constructing such a discrete approximation, with certain advantages, which is also guaranteed to converge.