Fourier Transform - The Big Data Blog

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:

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)$ .
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)$ .
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)$ .
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).