## Fast Fourier Transform

As shown in the last subsection, kernel density estimates can be
expressed as a submatrix of a certain convolution. The fast
Fourier transform (FFT) is a computationally effective method for
computing such convolutions. For a reference on this material,
refer to Press et al. (1988).

The *discrete Fourier transform* of a complex
vector **z** = (*z*_{0}, ... ,*z*_{N-1}) is the
vector **Z** = (*Z*_{0}, ... ,*Z*_{N-1}) where

and *i* is the square root of -1. The vector
**z** can be recovered from **Z** by
applying the *inverse discrete Fourier
transform* formula

Discrete Fourier transforms and their inverses can be computed quickly
using the FFT algorithm, especially when *N* is *highly
composite*; that is, it can be decomposed into many factors, such as a
power of 2. By the *Discrete Convolution Theorem*, the
convolution of two vectors is the inverse Fourier transform of the
element-by-element product of their Fourier transforms. This, however,
requires certain periodicity assumptions, which explains why the
vectors *K* and *C* require zero-padding. This is to avoid
"wrap-around" effects (refer to Press et al. 1988, pp. 410 -
411). The vector *K* is actually mirror-imaged so that the convolution
of *C* and *K* will be the vector of binned estimates. Thus, if *S*
denotes the inverse Fourier transform of the element-by-element
product of the Fourier transforms of *K* and *C*, then the first *g*
elements of *S* are the estimates.

The bivariate Fourier transform of an
*N*_{1}×*N*_{2} complex matrix
having (*l*_{1}+1,*l*_{2}+1) entry equal to
is the
*N*_{1}×*N*_{2} matrix with (*j*_{1}+1 ,*j*_{2}+1) entry given by

and the formula of the inverse is

The same Discrete Convolution Theorem applies, and zero-padding is
needed for matrices *C* and *K*. In the case of *K*, the matrix is
mirror-imaged twice. Thus, if *S* denotes the inverse Fourier
transform of the element-by-element product of the Fourier transforms
of *K* and *C*, then the upper-left *g*_{X}×*g*_{Y} corner of *S*
contains the estimates.

Copyright © 1999 by SAS Institute Inc., Cary, NC, USA. All rights reserved.