|
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]
|
