Fast Algorithms for Nonparametric Curve Estimation

Naive implementations of local polynomial fits and kernel estimators require almost O(n 2) operations. In this article two fast O(n) algorithms for nonparametric local polynomial fitting are presented. They are based on updating normal equations. Numerical stability is guaranteed by controlling ill-conditioned situations for small bandwidths and data-tuned restarting of the updating procedure. Restarting at every output point results in a moderately fast but highly stable O(n 7/5) algorithm. Applicability of algorithms is evaluated for estimation of regression curves and their derivatives. The idea is also applied to kernel estimators of regression curves and densities.