[ Search | Site Map | Contact ]

Center for Scientific Computation and Mathematical Modeling

Research Activities > Programs > Fast Approximate Algorithms > Ramani Duraiswami

Fast Multipole Method, Tree-Code and Related Approximate Algorithms.
Trading Exactness for Efficiency.

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

An Improved Fast Gauss Transform and Applications

Dr. Ramani Duraiswami

UMIACS at University of Maryland

Abstract:   Evaluating sums of multivariate Gaussians is a common computational task in many areas of science, and especially in the recently popular kernel methods in computer vision, pattern recognition, and learning. The fast Gauss transform (FGT), based on the Fast Multipole Method (FMM), has successfully accelerated the summations from quadratic running time to linear time for low-dimensional problems. Unfortunately, the cost of a direct extension of the FGT to higher-dimensional problems grows exponentially with dimension (the curse of dimensionality).

We introduce an improved version of the fast Gauss transform to efficiently estimate sums of Gaussians in higher dimensions. Our proposed algorithm incorporates three innovations that dramatically improve the performance: a multivariate Taylor expansion scheme, a pyramid-like data structure to store and manipulate the expansions, and an adaptive space subdivision technique based on the k-center algorithm. These innovations result in an algorithm that is much faster and has been demonstrated in dimensions up to ten.

The fast Gauss transform has been applied to the kernel density estimation (KDE), and more specifically to the mean shift algorithm for clustering, where it improves the quadratic complexity of each iteration. We present results from computer vision (segmentation, tracking) and pattern recognition (classification) that use the improved FGT.

(Supported by NSF. Joint Work with Changjiang Yang, Nail Gumerov and Larry Davis) [LECTURE SLIDES]