search

JuliaStats / KernelDensity.jl

Kernel density estimators for Julia
Other
177 stars 40 forks source link

Use 1D FFTs in bivariate KDE #4

Closed simonster closed 10 years ago

simonster commented 10 years ago

Since we are convolving with a product distribution, the 2D convolution is separable. This approach has complexity O(m*log(m)+n*log(n)) whereas the 2D FFT has complexity O(m*n*(log(m)+log(n))).

simonbyrne commented 10 years ago

That's not quite right: you have to apply the column-wise FFT n times, and the row-wise one m times, so the total complexity ends up being 

O(n*m*log(m) + m*n*log(n)) = O(m*n*(log(m) + log(n)))

which is exactly the same as the 2D form. As I understand it, the 2D FFT is actually obtained by just applying the 1D FFTs each way.

I think that any improved performance possible here is likely to be from using in-place FFTs.

simonster commented 10 years ago

Yes, you are correct; I'm not sure what I was thinking.

simonster commented 10 years ago

There may still be some performance to be gained by computing the characteristic functions once for the rows and once for the columns, instead of for each data point.

simonbyrne commented 10 years ago

That's true. I was more focusing on functionality rather than optimising performance at the moment (especially since the FFT interface is still under debate), but if you want to look at it I'm more than happy to incorporate any improvements.