Convolutions

The KDE Procedure

Convolutions

The formulas for the binned estimator $\hat f$ in the previous subsection are in the form of a convolution product between two matrices, one of which contains the bin counts, the other of which contains the rescaled kernels evaluated at multiples of grid increments. This section defines these two matrices explicitly, and shows that $\hat f$ is their convolution.

Beginning with the weighted univariate case, define the following matrices:

$K & = & \frac{1}n(\varphi_{h}(0),\varphi_{h}(\delta), ... ,\varphi_{h}((g-1)\delta))' \ C & = & (c_{1},c_{2}, ... ,c_{g})'$

The first thing to note is that many terms in K can practically be ignored. The term $\varphi_{h}(i\delta)$ is taken to be 0 when $|\frac{i\delta}h|\geq 5$ ,so you can define

$l = \min(g-1,floor(5h/\delta))$

as the maximum integer multiple of the grid increment to get nonzero evaluations of the rescaled kernel. Here floor(x) denotes the largest integer less than or equal to x. .

Next, let p be the smallest power of 2 that is greater than g+l+1,

p = 2^{ceil(log₂ (g+l+1))}

where ceil(x) denotes the smallest integer greater than or equal to x.

Modify K as follows:

$K = \frac{1}n(\varphi_{h}(0), \varphi_{h}(\delta), ... ,\varphi_{h}(l\delta),... ...brace{0, ... ,0}_{p-2l-1}, \varphi_{h}(l\delta), ... ,\varphi_{h}(\delta))'$

Essentially, the negligible terms of K are omitted, and the rest are "symmetrized" (except for one term). The whole matrix is then padded to size p×1 with zeros in the middle. The dimension p is a highly composite number, that is, one that decomposes into many factors, leading to the fastest Fast Fourier Transform operation (refer to Wand 1993).

The third operation is to pad the bin count matrix C with zeros to the same size as K:

$C = (c_{1},c_{2}, ... ,c_{g}, \underbrace{0, ... ,0}_{p-g})'$

The convolution K*C is then a p×1 matrix, and the preceding formulas show that its first g entries are exactly the estimates $\hat{f}(x_{i}),i=1,2, ... ,g$ .

For bivariate smoothing, the matrix K is defined similarly as

$K = [ \kappa_{0,0} & \kappa_{0,1} & ... & \kappa_{0,l_{Y}} & 0 & \kappa_{0... ..._{1,l_{Y}} & 0 & \kappa_{1,l_{Y}} & ... & \kappa_{1,1} ]_{p_{X} x p_{Y}}$

where $l_{X} = \min(g_{X}-1,floor(5h_{X}/\delta_{X}))$ ,p_X = 2^{ceil(log₂ (g_X+l_X+1))}, and so forth, and $\kappa_{i,j} = \frac{1}n\varphi_{h} (i\delta_{X},j\delta_{Y}), i = 0,1, ... ,l_{X}, j = 0,1, ... ,l_{Y}$ .

The bin count matrix C is defined as

$C = [ c_{1,1} & c_{1,2} & ... & c_{1,g_{Y}} & 0 & ... & 0\ c_{2,1} & c_{2,2... ... 0 & ... & 0 \ \vdots \ 0 & 0 & ... & 0 & 0 & ... & 0 ]_{p_{X} x p_{Y}}$

As with the univariate case, the g_X ×g_Y upper-left corner of the convolution K*C is the matrix of the estimates $\hat{f}(grid)$ .

Most of the results in this subsection are found in Wand (1993).

Chapter Contents
Previous
Next
Top