Efficient Non-parametric Estimation of Probability Density Functions

Accurate and fast estimation of probability density functions is crucial forsatisfactory computational performance in many scientific problems. When thetype of density is known a priori, then the problem becomes statisticalestimation of parameters from the observed values. In the non-parametric case,usual estimators make use of kernel functions. If $X_j, ~ j=1,2, \\ldots , n$is a sequence of i.i.d. random variables with estimated probability densityfunction $f_n$, in the kernel method the computation of the values $\\,f_n(X_1), f_n(X_2), \\ldots , f_n(X_n) \\,$ requires $O(n^2)$ operations, sinceeach kernel needs to be evaluated at every $X_j$. We propose a sequence ofspecial weight functions for the non-parametric estimation of $f$ whichrequires almost linear time: if $m$ is a slowly growing function thatincreases without bound with $n$, our method requires only $O(m^2 \\/ n)$arithmetic operations. We derive conditions for convergence under a number ofmetrics, which turn out to be similar to those required for the convergence ofkernel based methods. We also discuss experiments on different distributionsand compare the efficiency and the accuracy of our computations with kernelbased estimators for various values of $n$ and $m$.