abstract:
The Gauss transform is an important tool with many applications in, e.g., image manipulation, option pricing, and data mining including classification, regression and density estimation. The discret Gauss transform (DGT) in $d$-dimensional space corresponds to a matrix-vector multiplication involving $O(N \cdot M)$ operations, where $N$ is the number of source points and $M$ the number of evaluation points. Several methods for the rapid approximation of the DFGT have been developed to reduce the runtime complexity from $O(N \cdot M)$ to $O(N+M)$.
We present a new approach based on the dual-tree method that aims at combining the advantages of the previous methods. Computational results with synthetic as well as real-world data for up to 60 dimensions show competitive performance. |