Timezone: »

 
Poster
Fast High-dimensional Kernel Summations Using the Monte Carlo Multipole Method
Dongryeol Lee · Alexander Gray

Mon Dec 08 08:45 PM -- 12:00 AM (PST) @
in Posters »

We propose a new fast Gaussian summation algorithm for high-dimensional datasets with high accuracy. First, we extend the original fast multipole-type methods to use approximation schemes with both hard and probabilistic error. Second, we utilize a new data structure called subspace tree which maps each data point in the node to its lower dimensional mapping as determined by any linear dimension reduction method such as PCA. This new data structure is suitable for reducing the cost of each pairwise distance computation, the most dominant cost in many kernel methods. Our algorithm guarantees probabilistic relative error on each kernel sum, and can be applied to high-dimensional Gaussian summations which are ubiquitous inside many kernel methods as the key computational bottleneck. We provide empirical speedup results on low to high-dimensional datasets up to 89 dimensions.

[ PDF] 

Author Information

Dongryeol Lee (Independent Researcher)
Alexander Gray (Skytree Inc. and Georgia Tech)

More from the Same Authors