Title: Manifold learning using kernel density estimation and local principal component analysis
Authors: Kitty Mohammed - University of Washington (United States)
Hariharan Narayanan - TIFR (India) [presenting]
Abstract: The problem of recovering a $d$ dimensional manifold $M$ when provided with noiseless samples from $M$ is considered. There are many algorithms (e.g., Isomap) that are used in practice to fit manifolds and thus reduce the dimensionality of a given data set. Ideally, the estimate $Mput$ of $M$ should be an actual manifold of a certain smoothness; furthermore, $Mput$ should be arbitrarily close to $M$ in Hausdorff distance given a large enough sample. Generally speaking, existing manifold learning algorithms do not meet these criteria. An algorithm has been previously developed whose output is provably a manifold. The key idea is to define an approximate squared-distance function (asdf) to $M$. Then, $Mput$ is given by the set of points where the gradient of the asdf is orthogonal to the subspace spanned by the largest $n-d$ eigenvectors of the Hessian of the asdf. As long as the asdf meets certain regularity conditions, $Mput$ is a manifold that is arbitrarily close in Hausdorff distance to $M$. Two asdfs are defined which can be calculated from the data. It is shown that they meet the required regularity conditions. The first asdf is based on kernel density estimation, and the second is based on estimation of tangent spaces using local principal component analysis.