Nonparameteric multivariate density approximation -- where do I start? I am currently working on a research project that requires a reliable method for non-parametric kernel density estimation. Some specifics about my problem:


*

*I have $N$ sample points $X_1,X_2...X_N$, each of which corresponds to an outcome of an $M$ dimensional random variable $W = (w_1..w_M)$. I would like to assign a density to each of these points in an accurate and consistent way. 

*I am looking for a method that does not assume that the random variables be independent. As in my situation, I know that $f(W) \neq \prod_{i=1}^M {f_m(w_i)}$.

*In my case, $N \leq 25000$ and $M \leq 5$ but I can generate as much data as needed. 
Open to any and all suggestions!
 A: For those who are looking for a batch method for bandwidth estimation, I would suggest the multivariate bandwith estimator from [1] -- the approximate calculation in C interfaced to Matlab can be obtained from the following link:
http://www.vicos.si/images/2/2e/KDE_bw_Matlab.zip
If you have large amounts of data (e.g., order of 1000), it might not make sense to apply the standard batch method. Instead you can use the online Kernel Density Estimator from [1], of which Matlab implementation can be obtained from this site:
http://www.vicos.si/Research/Multivariate_Online_Kernel_Density_Estimation
(Also some video examples of the estimation process are included)
[1] Multivariate Online Kernel Density Estimation with Gaussian Kernels
Matej Kristan, Aleš Leonardis, and Danijel Skočaj, Pattern Recognition, 2011
A: How about putting the points into a
Kd tree ?
This is fast and easy in 5d (in fact up to 20d, even 128d).
Then you can find nearest neighbours of single query points, or a grid;
or do data reduction by keeping midpoints of leaves,
of 10 or 100 points. (Which of these do you want to do ?)
If you're using
scipy.spatial.cKDTree,
see also the code snippet
forleaves() in a Kd tree.
A: The ks package in R can do multivariate kernel density estimation. I guess it depend on how many dimensions you have and whether you want to visualize the multivariate pdf or compute certain expectations. ks can handle up to 6 dimensional data.
A: I am looking at a similar problem, and although I can't point you to concrete implementations, I found a couple of papers that give multivariate density estimates that are not assumed to be independent a priori, and that also avoid "the curse of dimensionality" at least to some extent. These are:


*

*Forest Density Estimation by Han Liu, Min Xu, Haijie Gu, Anupam
Gupta, John Lafferty, Larry Wasserman (CMU)

*Density Estimation Trees by Parikshit Ram, Alexander G. Gray (Georgia Tech)
If you do run into a general implementation, please submit an update!
