APPLIED MATH SEMINAR

Name:   Dan Kushnir, Yale University

Title:     Multilevel Methods for Data Analysis

When/where:    Tuesday, October 21st, 4:15 p.m., AKW 200

Abstract:         
Multigrid solvers proved very efficient for solving massive systems of equations in various fields. These solvers are based on iterative relaxation schemes together with the approximation of the "smooth" error function on a coarser level (grid). We present two efficient multilevel eigensolvers for solving massive eigenvalue problems that emerge in data analysis tasks. The first solver, a version of classical algebraic multigrid (AMG), is applied to eigen-problems arising in clustering, image segmentation, and dimensionality reduction, demonstrating an order of magnitude speedup compared to the popular Lanczos algorithm. The second solver is based on a new, much more accurate interpolation scheme. It enables calculating very inexpensively a large number of eigenvectors.

If time allows I will also present a different multilevel approach for data clustering. This multilevel clustering algorithm approximately minimizes a graph-cut functional, as in spectral clustering, yet it is not based on an explicit computation of eigenvectors. Furthermore, in parallel to the clustering process, multiscale data properties are computed and utilized to induce coherent clusters. We demonstrate our algorithm performance on various challenging synthetic examples, on real astrophysical data sets of galaxies in 3D and on Turbulence data.

Joint work with Prof. Achi Brandt and Dr. Meirav Galun.