Collaborative Research: Robust Algorithms for Interpolation and Extrapolation in Manifold Learning

This proposal is concerned with computational methodologies for manifold-based nonlinear dimension reduction. We deal with unsupervised as well as semi-supervised problems with the goal of developing theoretical tools for analyzing and better understanding the performance and behaviors of manifold learning algorithms in those settings. Intellectual Merit. Manifold learning approaches for nonlinear dimension reduction are based on the assumption that the high-dimensional data are in the proximity of a low-dimensional nonlin- ear manifold, and this low-dimensional structure can be computed by aggregating local geometric information from data sampled from the manifold. The proposal focuses on the following four research topics: 1. deeper understanding of the performance, limitations and stability issues of manifold learning methods such as LTSA through matrix-analytic analysis of the spectral properties of the alignment matrices; 2. preconditioning and regularization techniques that improve the numerical performance of existing manifold learning algorithms; 3. designing robust implementations to eectively deal with data noises, including outliers; and 4. considering manifold learning in the context of semi-supervised learning especially active learning settings, leading to very interesting optimization problems of both intrinsic and practical signicance. These works will build a solid theoretical foundations for the manifold learning algorithms. Broader Impacts. The discoveries from this proposed research are expected to impact a wide range areas of applications. Computing compact representation of high-dimensional data repre- sents a very challenging statistical learning problem, and manifold learning has become a very active research eld aiming at discovering hidden structures from the statistical and geometric reg- ularity inherent in many high-dimensional data. Our proposed theoretical tools and computational methods have the promise of signicantly expanding the applicability and functionality of existing and new manifold learning methods and thus advancing the state of the art in nonlinear dimen- sion reduction research. The proposed research lies at the interface between applied mathematics, computational science, and machine learning applications and provides an ideal setting for research cross-fertilization and collaboration as well as training of graduate students in interdisciplinary research. The list of the applications areas that can benet from the ndings of the proposed re- search is numerous including machine vision, speech processing, computational biology, molecular dynamics simulations and scientic visualization. We anticipate to release publicly available soft- ware which will disseminate the research results and promote applications of nonlinear dimension reduction methodology to real-world problems.