| Abstract: |
| With the aim of inferring probability density functions from limited observed samples, density estimation via discrepancy based sequential partition (DSP) has been proposed to learn an adaptive piecewise constant approximation defined on a binary sequential partition of the underlying domain, where the star discrepancy is adopted to measure the uniformity of particle distribution. However, the calculation of the star discrepancy is NP-hard. We use heuristic algorithms such as SA, TA, and PT to accelerate the computation of the star discrepancy, and find that TA exhibits the best convergence speed. Furthermore, star discrepancy does not satisfy the reflection invariance and rotation invariance either. To this end, we use the mixture discrepancy and the comparison of moments as a replacement of the star discrepancy, leading to the density estimation via mixture discrepancy based sequential partition (DSP-mix) and density estimation via moments based sequential partition (MSP), respectively. Both DSP-mix and MSP are computationally tractable and exhibit the reflection and rotation invariance. Numerical experiments in reconstructing the $d$-D mixture of Gaussians and Betas with $d = 2-30$ demonstrate that both DSP-mix and MSP run approximately ten times faster than DSP while maintaining the same accuracy. |
|