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

m4 macro which realize indexer in C

I introduce m4 macro which realize indexer like C# in C.
There is still room for improvement on this program,however I think I want to introduce as a temporary program.

define(`defObject',`
        setIndexer($2)
        $1 $2=NULL;
        $2=$1Init(shift($@));
');
define(`setIndexer',`define(`$1',
                `if'`else('
                        `$'`#'`,2,'
                        ``$1''`->a['`$'`1'`*'`$'`2'`],
                        ``$1'''
                `)'
        )
');

#include <stdlib.h>

typedef struct{
        int *a;
} testObj;
testObj *testObjInit(void *a,int n){
        struct testObj *result=malloc(sizeof(struct testObj));
        result->a=malloc(sizeof(int)*n);
 return result;
}
int main(void){
        defObject(testObj,objs,1024);    //(1)
        objs(1,3)+=1;//realize access like indexer here.
 objs->a[2]=2;//can do normal access.
}

Position (1),First argument is type name and second argument is variable name defined.
Arguments after third  are data that is given to testObjInit.
[type name]Init can is called in defObject.(Use testObjInit in this case )
setIndexer macro which is called in defObject is a function realizing indexer.