Fourier Transform

1. The Fourier Transform

The Fourier transform \tilde{f} of an integrable function f: \mathbb{R}^g \rightarrow \mathbb{C} with s \in \mathbb{R}^g is given by

(1)   \begin{equation*} \tilde{f}(s) = \int_{\mathbb{R}^g} f(x) exp(-2\pi i <x,s>) dx. \end{equation*}

Under suitable conditions, the inverse transform from \tilde{f} to f with t \in \mathbb{R}^g is then given by

(2)   \begin{equation*} f(t) = \int_{\mathbb{R}^g} \tilde{f}(x) exp(-2\pi i <s,x>) ds. \end{equation*}

The Fourier transform has some nice properties. Assume f (x), g(x) and h(x) are integrable functions:

  1. Linearity: For a,b \in \mathbb{C}, if f(x)= a h(x) + b g (x), then \tilde{f}(s)= a \tilde{h}(s) + b \tilde{g}(s).
  2. Translation: For x_0 \in \mathbb{R}^n, if f(x)=h(x-x_0), then \tilde{f}(s) = exp(-2\pi i <x_0,s>) \tilde{h}(s).
  3. Modulation: For s_0 \in \mathbb{R}^n, if f(x)=exp(-2\pi i <x,s>)  h(x), then \tilde{f}(s) = \tilde{h}(s-s_0).
  4. Scaling: For a\neq 0, if f(x)=h(a x), then \tilde{f}(s)=\frac{1}{|\prod_{i=1}^g a_i|} \tilde{h}(a^{-1} s).

Here we use the notation is used a \in \mathbb{R}^g, a^{-1} := (a_1^{-1},\dots a_g^{-1}).

An important feature of the Fourier Transform is convolution. Suppose two given functions f and g and let the convolution be defined as (f *g)(z) = \int_{\mathbb{R}^g} f(x) g(z-x)dx, then \widetilde{f*g} = \tilde{f} \cdot \tilde{g} and \widetilde{f \cdot g} = \tilde{f} * \tilde{g}.

2. Discrete Fourier Transform

The discrete Fourier Transform (DFT) is based on points f_1, \dots, f_n, \; f_i \in \mathbb{C} and given by

(3)   \begin{equation*} \tilde{f}_k = \sum_{l=1}^n f_l exp(-2 \pi i k l) \end{equation*}

and the inverse by

(4)   \begin{equation*} f_i = \sum_{k=1}^n \tilde{f}_k exp(-2 \pi i n k). \end{equation*}

The DFT can be interpet as a discrete version of 1. To see this, let x_1, \dots, x_T, \; x_i \in \mathbb{R}^g be some grid. Then a discrete, approximate version of (1) is given by

(5)   \begin{equation*} \tilde{f}(x_k) =\frac{1}{T} \sum_{l=1}^T f(x_l) exp(-2 \pi i x_l x_k). \end{equation*}

If x_1, \dots, x_T 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 x=\frac{1}{T} u. Assume now observations at an equidistant univariate grid on [0,1], x_i=\frac{i}{T}, and define T f_i \equiv T f(i)=T f(u_i) and i=u_i=T x_i, then (5) corresponds to (4).

2 thoughts on “Fourier Transform

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.