Greedy Algorithms for Dirac Mixture Approximation of Arbitrary Probability Density Functions

Greedy procedures for suboptimal Dirac mixture approximation of an arbitrary probability density function are proposed, which approach the desired density by sequentially adding one component at a time. Similar to the batch solutions proposed earlier, a distance measure between the corresponding cumulative distributions is minimized by selecting the corresponding density parameters. This is due to the fact, that a distance between the densities is typically not well defined for Dirac mixtures. This paper focuses on the Cramer-von Mises distance, a weighted integral quadratic distance measure between the true distribution and its approximation. In contrast to the batch solutions, the computational complexity is much lower and grows only linearly with the number of components. Computational savings are even greater, when the required number of components, e.g., the minimum number of components for achieving a given quality measure, is not a priori known and must be searched for as well. The performance of the proposed sequential approximation approach is compared to that of the optimal batch solution.