View article

Nonparametric density estimation has broad applications in computational finance especially in cases where high frequency data are available. However, the technique is often intractable, given the run times necessary to evaluate a density. We present a new and efficient algorithm based on multipole techniques. Given the n kernels that estimate the density, current methods take O(n) time directly to sum the kernels to perform a single density query. In an on-line algorithm where points are continually added to the density, the cumulative O(n ² ) running time for n queries makes it very costly, if not impractical, to compute the density for large n . Our new Multipole-accelerated On-line Density Estimation (MODE) algorithm is general in that it can be applied to any kernel (in arbitrary dimensions) that admits a Taylor series expansion. The running time for a density query reduces to O (logn …