Time: Tuesday, September 22, 2015
2:00pm
MTH1311

Speaker: Professor Nathaniel Strawn (Georgetown University)

Title: Non-Asymptotic Bounds for Geometric Multiresolution Analysis

Abstract: Geometric Multiresolution Analysis (GMRA) is an efficient procedure which combines two primitives to create an approximation to a dataset: partitioning and Principal Component Analysis. In this talk, we exhibit nearly minimax optimal finite sample probabilistic bounds for the mean square error (MSE) of the GMRA procedure of Allard, Chen, and Maggioni for ``noisy manifold'' models. To do so, we independently show that ''good'' partitions with respect to a base probability distribution produce GMRAs satisfying an MSE bound, and then show that partitions constructed from running the cover trees algorithm of Beygelzimer et al. are ``good'' with high probability if the base probability distribution is a "noisy manifold." This is joint work with Stanislav Minsker of UC Southern California and Mauro Maggioni of Duke University.