I am doing univariate non-parametric density estimation on a dataset $D$, and I want to
1) Train a density estimator on $D$
2) Compute the estimated density at each point in $D$
These two operations should have an aggregate time complexity $< \mathcal O(n^2)$, and the PDF estimate should be differentiable.
An $\mathcal O(n)$ time complexity of the aggregate process is possible with the histogram estimator. However, the PDF estimate is not differentiable.
The Gaussian kernel density estimator gives a differentiable PDF estimate. However, the time complexity of the aggregate process is $\mathcal O(n^2)$. With Gaussian KDE, density estimation of a single point is $\mathcal O(n)$, so density estimation of all points in the dataset would be $\mathcal O(n^2)$. Thus this method does not have an aggregate time complexity $< \mathcal O(n^2)$.
Does there exist a density estimator that would satisfy both conditions?
EDIT:
I found a way to have an aggregate time complexity of $\mathcal O(n)$ with Gaussian KDE. See the following link...
http://www-stat.wharton.upenn.edu/~lzhao/papers/MyPublication/Fast_jcgs.2010.pdf