Very Fast Multivariate Kernel Density Estimation via Computational Geometry

• Activity Number: 116
• Type: Topic Contributed
• Date/Time: Monday, August 4, 2003 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Computing
• Author(s): Alexander G. Gray*+ and Andrew Moore
• Companies: Carnegie Mellon University and Carnegie Mellon University
• Keywords: computation ; kernel density estimation ; nonparametric ; density estimation ; algorithm ; large datasets

Abstract

To date, the use of nonparametric methods has been limited by their computational intractibility for all but the smallest datasets, particularly when cross-validation procedures are accounted for. By introducing powerful techniques from computational geometry to this problem, we present an algorithm for multivariate kernel density estimation which reduces the cost of estimating the density at a query point from O(N) to O(1), or constant time complexity, i.e., its cost does not depend on the dataset size. Furthermore, unlike preceding work, it does not scale exponentially in the dimension D. Empirically and analytically we show that the method achieves dramatic efficiencies superior to those of previous algorithmic approaches including binning methods and the FFT, in terms of both dataset size and dimensonality. Additionally, the algorithm guarantees accuracy within any tolerance specified by the user, has no indirect parameters (such as a number of grid points) to tune, naturally admits estimation at arbitrary query points, and works for all common kernel choices interchangeably.