Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels
This work addresses a computational bottleneck for researchers and practitioners in statistics and machine learning dealing with large datasets, though it is incremental as it builds on existing methods.
The paper tackles the quadratic time complexity of local polynomial regression, which limits its use in large-scale data analysis, by introducing an algorithm using multi-dimensional binary indexed trees to achieve near-linear time and space complexity, with simulation results confirming its efficiency and effectiveness.
Local polynomial regression (Fan and Gijbels 1996) is an important class of methods for nonparametric density estimation and regression problems. However, straightforward implementation of local polynomial regression has quadratic time complexity which hinders its applicability in large-scale data analysis. In this paper, we significantly accelerate the computation of local polynomial estimates by novel applications of multi-dimensional binary indexed trees (Fenwick 1994). Both time and space complexity of our proposed algorithm is nearly linear in the number of input data points. Simulation results confirm the efficiency and effectiveness of our proposed approach.