Nonparametric Adapative Partitioning Alogorithm

A probability density estimation method developed in MATLAB.

The Non-parametric Adaptive Partitioning and Stitching (NAPS) algorithm is a method which estimates the Probability Density Function (PDF) of univariant data (x) for applications to large data sets. The primary goal was to create an approach that requires no a prior knowledge of the underlying PDF and to create an efficient algorithm suited for High Performance Computing (HPC) applications.

The algorithm starts by calculating a ration of sparse/dense differences (Δx) in a sample from the data set based on a data driven windowing function (w).

The ratio determines whether a partition should be made in the original sample. This sub-routine is applied to the original sample and any subsequent partitioned data sub-samples.

The partitioning sub-routine is applied in a recursive tree search untile all optimal paritions are determined and a set of "n" sub-samples are found.

An example of the PDF estimated using the NAPS algorithm is shown for a tri-modal normal PDF.

(Left) The PDF estimates found for all sub-samples (Right) The resultant PDF after the stitching all sub-sample estimates together.

A strength of the NAPS algorithm is the ability to accurately estimate more “exotic” PDFs.

An example estimate of a Beta PDF with a = 0.5 and b = 0.5 for a samples size of 2^17.