Kernel density estimation which was optimized by the fast Gauss transform

I introduce the fast Gauss transform and optimize kernel density estimation(KDE) using it.
Prediction model when x₁, x₂, ..., x_N is i.i.d samples.

Kernel density estimation and Kernel regression and Mean shift  that  used Gaussian kernel  are similar model of this. They frequently  appears in statistic.

Degree of a polynomial of this model is the same as number of sample. So when M is count of prediction, Its very expensive computational complexity  is O(MN) .

The fast Guss transform that derives from the fast multipole method rewrite N with small positive integer K by making approximation of Gaussian function in Hermite expansion.

Its computational complexity  is O(MK) .

 

There is IFGT which imploved this fast Gauss transform. But I developed KDE C library in the orijinal fast Gauss transform. And upload github. http://github.com/y-mitsui/fastKDE If you execute with intel CPU and 32bit Linux, Code which was optimized by SSE2 is available. I think you should read README.md. [Execution result] Number of normal random as samples: 1000000 Prediction count: 5000 K: 10 direct time:444.13400sec optimized time:0.60800sec directValue[00000]:0.221897     optimizedValue[00000]:0.242221 directValue[00250]:0.233130     optimizedValue[00250]:0.252617 directValue[00500]:0.243662     optimizedValue[00500]:0.262466 directValue[00750]:0.253349     optimizedValue[00750]:0.271657 directValue[01000]:0.262056     optimizedValue[01000]:0.280076 directValue[01250]:0.269658     optimizedValue[01250]:0.287611 directValue[01500]:0.276041     optimizedValue[01500]:0.294152 directValue[01750]:0.281110     optimizedValue[01750]:0.299593 directValue[02000]:0.284789     optimizedValue[02000]:0.303839 directValue[02250]:0.287019     optimizedValue[02250]:0.306803 directValue[02500]:0.287767     optimizedValue[02500]:0.308415 directValue[02750]:0.287020     optimizedValue[02750]:0.308619 directValue[03000]:0.284790     optimizedValue[03000]:0.307384 directValue[03250]:0.281112     optimizedValue[03250]:0.304698 directValue[03500]:0.276040     optimizedValue[03500]:0.300573 directValue[03750]:0.269653     optimizedValue[03750]:0.295048 directValue[04000]:0.262046     optimizedValue[04000]:0.288185 directValue[04250]:0.253331     optimizedValue[04250]:0.280067 directValue[04500]:0.243634     optimizedValue[04500]:0.270803 directValue[04750]:0.233090     optimizedValue[04750]:0.260516 CPU: Core i5(Nehalem)  MEM:4GB OS:Windows 7 COMPILER:mingw 4.62