## 1. The Fourier Transform

The Fourier transform of an integrable function with is given by

(1)

Under suitable conditions, the inverse transform from to with is then given by

(2)

The Fourier transform has some nice properties. Assume and are integrable functions:

*Linearity*: For , if , then .*Translation:*For , if , then .*Modulation:*For , if , then .*Scaling:*For , if , then .

Here we use the notation is used .

An important feature of the Fourier Transform is convolution. Suppose two given functions and and let the convolution be defined as , then and .

## 2. Discrete Fourier Transform

The discrete Fourier Transform (DFT) is based on points and given by

(3)

(4)

The DFT can be interpet as a discrete version of 1. To see this, let be some grid. Then a discrete, approximate version of (1) is given by

(5)

If are g-dimensional equidistantly spaced then (5) will be the Riemann sum while for g-dimensional i.i.d. random observations one may interpret (5) as an monte carlo intergral.

Looking at (1) with integration by substitution with . Assume now observations at an equidistant univariate grid on , , and define and , then (5) corresponds to (4).

Pingback: Fast Kernel Density Estimation using the Fast Fourier Transform – The Big Data Blog

Pingback: Kernel Regression using the Fast Fourier Transform – The Big Data Blog