Transparent Gif

Department of Computer Science

University of California, Santa Barbara

Abstract

Efficient Non-parametric Estimation of Probability Density Functions

by: Omer Egecioglu and Ashok Srinivasan

Abstract:

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$.

Keywords:

Probability density, non-parametric estimation, convergence, kernelmethod, efficient algorithm.

Date:

October 1995

Document: 1995-19

XHTML Validation | CSS Validation
Updated 14-Nov-2005
Questions should be directed to: webmaster@cs.ucsb.edu