Is there a fast way to compute histograms for high-dimensional large datasets?

Question

Currently the way I compute histograms for data is by generating grid in $N$ dimensions (where $N$ is the dimension of the data) and searching through the $M$ data points in each dimension to see in which bin each one of them fits.

This is the same as an exhaustive search and takes very long if $N$ and $M$ are large (in my case $N=6$, $M=125,000$).

My question is: is there a faster way to accurately compute (or possibly estimate) the number of samples in each bin given a grid and data?

Alternatively, if there is no way to estimate/compute a histogram, is there an alternative method for construct distributions that is fast for high-dimensional large datasets? I've used kernel density estimators, but they are sensitive to which type of kernel you use and depend on prior knowledge of the nature of the data to get good results. (I have no prior knowledge of the nature of the data.)

Answer 1

Histograms are not useful for high dimensional data. The curse of dimensionality affects one quite fast. As in your case if the grid is of size 7**6, you have on average one point in one bin. Kernel density estimator are better suited as long as you keep the kernel bandwidth large enough. In my experience the top hat kernel as k-nearest neighbor yields reasonable results up to D=10, if sampling is sufficient. There is also a quite efficient algorithm for calculating k-nearest neighbors in higher dimensions, which I can recommend.

Also, the kernel shape doesn't really matter so much, because you need to keep the bandwidth large enough due to lack of data. If you see a dependency on the kernel shape your bandwidth is likely too small. There are a couple of rule of thumbs how to select the bandwidth.

If you calculate some other property from the probability density, in nearly all cases you are better off not computing the density at all.

Edit to properly comment on the comment

I am afraid you cannot capture nuanced differences in high dimensional data with histograms if you check the statistical error for each bin. Go ahead and do some simple random number experiment and check the fluctuation in each bin with your sample size. Unless you use a really small grid size like 2**6, which is pointless to begin with, you will only see noise as nuanced differences.

For calculating entropies == Jensen Shannon divergences I recommend following papers which I used in my phd thesis.

Article (Hnizdo2007) Hnizdo, V.; Darian, E.; Fedorowicz, A.; Demchuk, E.; Li, S. & Singh, H. Nearest-neighbor nonparametric method for estimating the configurational entropy of complex molecules. Journal of computational chemistry, J Comput Chem, 2007, 28, 655

Article (Hnizdo2008) Hnizdo, V.; Tan, J.; Killian, B. & Gilson, M. Efficient calculation of configurational entropy from molecular simulations by combining the mutual-information expansion and nearest-neighbor methods Journal of computational chemistry, NIH Public Access, 2008, 29, 1605

I have no idea for the earth mover distance and have never used that before though. It kinda looks like that you need the work for a phase space transformation bringing two distributions together. It seems to me that is similar to a free energy difference between the two systems given by the distributions.

Answer 2

I don't have a rigorous proof for this, but we have solved this problem with a random sampling based approach. Or data is something like $4\,096 \times 12\,000 \times 1\,000 \times 6 \times 3 \times 2 \times 4 $. Hint: (X, Y, Z, stack#, RGB, state, samples)

Basically, we figure out what two categories we want to do differential histograms for, then pick random points using uniform sampling over the remaining axes. An exact answer obviously requires consideration of all the points, but for our data-set consideration of 1-3% gets an answer who's PDF is >0.95 correct (1 - RMSE) of the full data-set.

NB: This answer is also clearly contingent on the underlying distribution. If, for example, each sample were uniformly spaced over all of IEEE 754 float 64 space, then this approach will fall on its face. So, the accuracy of this approach actually depends on the underlying PDF.

As mentioned in the above answer by @bort, the Entropy of you data-set will directly be a measure of the accuracy of a histogram which selectively samples, as it is after all direct measure of both the total informational content or capacity of a given sample to represent the whole.