|
DRUM >
College of Computer, Mathematical & Physical Sciences >
Computer Science >
Technical Reports of the Computer Science Department >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1903/3020
|
| Title: | Fast Computation of Sums of Gaussians in High Dimensions |
| Authors: | Raykar, Vikas Chandrakant
Yang, Changjaing
Duraiswami, Ramani
Gumerov, Nail |
| Type: | Technical Report |
| Issue Date: | 15-Nov-2005 |
| Series/Report no.: | UM Computer Science Department
CS-TR-4767
UMIACS-TR-2005-69 |
| Abstract: | Evaluating sums of multivariate Gaussian kernels is a key computational task in many problems in computational statistics and
machine learning. The computational cost of the direct evaluation of such sums scales as the product of the number of kernel
functions and the evaluation points. The fast Gauss transform proposed by Greengard and Strain (1991) is a $\epsilon$-exact
approximation algorithm that reduces the computational complexity of the evaluation of the sum of $N$ Gaussians at $M$ points
in $d$ dimensions from $\mathcal{O}(MN)$ to $\mathcal{O}(M+N)$. However, the constant factor in $\mathcal{O}(M+N)$ grows
exponentially with increasing dimensionality $d$, which makes the algorithm impractical for dimensions greater than three. In
this paper we present a new algorithm where the constant factor is reduced to asymptotically polynomial order. The reduction
is based on a new multivariate Taylor's series expansion (which can act both as a local as well as a far field expansion... |
| URI: | http://hdl.handle.net/1903/3020 |
| Appears in Collections: | Technical Reports of the Computer Science Department
Technical Reports from UMIACS
|
Files in This Item:
| File |
Description |
Size | Format | No. of Downloads |
|---|
| CS-TR-4767.pdf | | 2356Kb | Adobe PDF | 885 | View/Open |
|
Show full item record
All items in DRUM are protected by copyright, with all rights reserved.
|
