Linear Time Algorithm for Positive Kernel Smoothing with Application toNonparametric Probability Density Estimation

摘要

We present computational methods for positive kernel smoothing of piecewise linear data over uniform meshes. These methods or algorithms complete their work in an amount of time proportional to the amount of data present. The kernel used here is a B-spline which can be of arbitrarily high smoothness. The smoothed result or approximation may therefore also be as smooth as desired. The algorithms automatically evaluate the smooth approximation over any arbitrary mesh, including the original one if desired. Part of the reason why this smoothing may be done so efficiently stems from the fact that the kernel is never actually obtained or used explicitly. These methods lead naturally to consideration of smoothing the discrete cumulative distribution function corresponding to an ordered set of values of a random variable-a situation in which the original mesh is naturally always nonuniform. In this nonparametric estimation of a density, the use of a positive kernel is important, because the resulting integral smoothing operator is a monotone operator. In addition, derivatives of the smooth approximation may be obtained trivially. (AN).