Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels

2018/02/26 by Yining Wang, Yi Wu, Wang, Yining +3
Computer Science · Mathematics · #Advanced Statistical Methods and Models #Bayesian Methods and Mixture Models #Computation (stat.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1802.09578

openalex publication_date 2018/02/26 · openalex created_date 2020/09/08 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Finding frequent items in data streams
• Local Linear Regression Smoothers and Their Minimax Efficiencies
• Ideal spatial adaptation by wavelet shrinkage

Related

• Robust Local Polynomial Regression with Similarity Kernels
• Simple Local Polynomial Density Estimators
• A new adaptive local polynomial density estimation procedure on complicated domains
• Nonparametric estimation of the conditional distribution at regression\n boundary points
• Local polynomial regression and variable selection