Fourier Analysis

Discrete Fourier Transform

In the space ${\mathbb{C}}^n$, fourier provide an orthogonal basis

$$\{v_k=({\omega }^0,{\omega }^k,{\omega }^{2k},\dots ,{\omega }^{(n-1)k}){\}}_{0\le k\le n-1}$$

with $\omega =e^{2\pi i/n},$ the $n$-th root of $1$.

This proposition is valable thanks to

$$⟨v_k,v_l⟩=n\cdot {\delta }_{k,l}.$$

and $\forall k\in \mathbb{Z},||v_k|{|}^2=n$.

As a consequence,

$$I_n=\frac{1}{n}\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& \omega & {\omega }^2& \cdots & {\omega }^{(n-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }^{n-1}& {\omega }^{2(n-1)}& \cdots & {\omega }^{(n-1)(n-1)}\end{array}\right]\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& \bar{\omega }& {\bar{\omega }}^2& \cdots & {\bar{\omega }}^{(n-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\bar{\omega }}^{n-1}& {\bar{\omega }}^{2(n-1)}& \cdots & {\bar{\omega }}^{(n-1)(n-1)}\end{array}\right]$$

The discrete fourier transform can be represented as follows,

$$\left[\begin{array}{c}{\hat{f}}_0\\ {\hat{f}}_1\\ ⋮\\ {\hat{f}}_{n-1}\end{array}\right]=\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& \bar{\omega }& {\bar{\omega }}^2& \cdots & {\bar{\omega }}^{(n-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\bar{\omega }}^{n-1}& {\bar{\omega }}^{2(n-1)}& \cdots & {\bar{\omega }}^{(n-1)(n-1)}\end{array}\right]\left[\begin{array}{c}{f}_0\\ f_1\\ ⋮\\ f_{n-1}\end{array}\right]$$

then the inverse fourier transform would be

$$\left[\begin{array}{c}{f}_0\\ f_1\\ ⋮\\ f_{n-1}\end{array}\right]=\frac{1}{n}\left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& \omega & {\omega }^2& \cdots & {\omega }^{(n-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }^{n-1}& {\omega }^{2(n-1)}& \cdots & {\omega }^{(n-1)(n-1)}\end{array}\right]\left[\begin{array}{c}{\hat{f}}_0\\ {\hat{f}}_1\\ ⋮\\ {\hat{f}}_{n-1}\end{array}\right]$$

Equivalently, the fourier transform element

$${\hat{f}}_k=\sum _{j=0}^{n-1}{\bar{\omega }}^{jk}{f}_j,0\le k\le n-1,$$

and the inverse fourier transform element recovered by

$$f_l=\sum _{k=0}^{n-1}{\omega }^{kl}{\hat{f}}_k,0\le l\le n-1.$$

Fast Fourier Transform (FFT)

Note that $\forall k\in \mathbb{Z},e^{2\pi k}=1$, the elements in matrix above are massively in common, $n$ elements disinct, precisely.

With the orthogonality, rewrite the formula as follows,

$$\begin{array}{rl}{\hat{f}}_k=& \sum _{j=0}^{n-1}{\omega }^{jk}{f}_j\\ =& \sum _{j=0}^{n-1}{\omega }^{2jk}{f}_{2j}+\sum _{j=0}^{n-1}{\omega }^{2jk+k}{f}_{2j+1}\\ =& \sum _{j=0}^{n-1}{\omega }^{2jk}{f}_{2j}+{\omega }^k\sum _{j=0}^{n-1}{\omega }^{2jk}{f}_{2j+1}\end{array}$$

The above result shows that the coefficients of fourier transform can be calculated recursively using the method of divide and conquer which reduce the calculation complexity from $O(n^2)$ to $O(n\log n)$.

Denote the transform matrix as $\Omega$, then

$${\Omega }_{2n}=\left[\begin{array}{cc}{I}_n& D_n\\ I_n& -D_n\end{array}\right]\left[\begin{array}{cc}{\Omega }_n& 0\\ 0& {\Omega }_n\end{array}\right]P$$

with $P$ is a permutation matrix and

$$D_n=\left[\begin{array}{ccccc}{\omega }^0& & & & \\ & {\omega }^1& & & \\ & & {\omega }^2& & \\ & & & \ddots & \end{array}\right].$$

Fourier series

Consider the space $L^1(-\frac{T}{2},\frac{T}{2})$, the functions $\{{\psi }_k=e^{ikt\cdot 2\pi /T},t\in \mathbb{R}{\}}_{k\in \mathbb{Z}}$, form a orthogonal basis since

$$⟨{\psi }_k,{\psi }_l⟩={\int }_{-T/2}^{T/2}{e}^{ikt\cdot 2\pi /T}{e}^{-ilt\cdot 2\pi /T}dt=T\cdot {\delta }_{k,l}$$

Complex form

For function $f\in L^1(-\frac{T}{2},\frac{T}{2})$,

$$f(t)=\sum _{k=-\infty }^{\infty }{c}_k{e}^{ikt\cdot 2\pi /T}$$

where

$$c_k=\frac{1}{T}⟨f(t),e^{ikt\cdot 2\pi /T}⟩=\frac{1}{T}{\int }_{-T/2}^{T/2}f(t)e^{-ikt\cdot 2\pi /T}dt$$

From complex to real

Since $e^{i\theta }=\cos \theta +i\sin \theta$, suppose $c_k=a_k+i{b}_k,a_k,b_k\in \mathbb{R}$, then

$$\begin{array}{rl}f(t)=& \sum _{k=-\infty }^{\infty }(a_k+i{b}_k)(\cos (kt\cdot 2\pi /T)+i\sin (kt\cdot 2\pi /T))\\ =& (a_0+i{b}_0)+\sum _{k=1}^{\infty }(a_k+i{b}_k)(\cos (kt\cdot 2\pi /T)+i\sin (kt\cdot 2\pi /T))\\ & +\sum _{k=1}^{\infty }(a_{-k}+i{b}_{-k})(\cos (-kt\cdot 2\pi /T)+i\sin (-kt\cdot 2\pi /T))\end{array}$$

if $f(t)\in \mathbb{R}$, $a_k=a_{-k}$ and $b_k=-b_{-k}$ which means $c_k=\overline{c_k}$, then

$$f(t)=a_0+\sum _{k=1}^{\infty }(2a_k)\cos (kt\cdot 2\pi /T)+(-2b_k)\sin (kt\cdot 2\pi /T))$$

Real value, conventional form

For $2\pi$-periodic function $f$,

$$f(t)=\frac{a_0}{2}+\sum _{k=1}^{\infty }(a_k\cos (kt)+b_k\sin (kt))$$

where

$$a_k=\frac{1}{||\cos (kt)|{|}^2}⟨f(t),\cos (kt)⟩=\frac{1}{\pi }{\int }_{-\pi }^{\pi }f(t)\cos (kt)dt$$

$$b_k=\frac{1}{||\sin (kt)|{|}^2}⟨f(t),\sin (kt)⟩=\frac{1}{\pi }{\int }_{-\pi }^{\pi }f(t)\sin (kt)dt$$

Fourier Transform

From fourier series to fourier transform

$$f(t)=\sum _{k=-\infty }^{\infty }\left(\frac{1}{T}{\int }_{-T/2}^{T/2}f(x)e^{-ikx\cdot 2\pi /T}dx\right)\cdot e^{ikt\cdot 2\pi /T}$$

Since

$${\int }_{-\infty }^{\infty }f(t)dt=\underset{T\to \infty }{\lim }\sum _{k=-\infty }^{\infty }\frac{2\pi }{T}f(k\cdot \frac{2\pi }{T})$$

which leads,

$$\begin{array}{rl}f(t)& =\underset{T\to \infty }{\lim }\sum _{k=-\infty }^{\infty }\left(\frac{1}{T}{\int }_{-T/2}^{T/2}f(x)e^{-ikx\cdot 2\pi /T}\cdot e^{ikt\cdot 2\pi /T}dx\right)\\ & =\frac{1}{2\pi }\underset{T\to \infty }{\lim }\sum _{k=-\infty }^{\infty }\frac{2\pi }{T}\left({\int }_{-T/2}^{T/2}f(x)e^{-ikx\cdot 2\pi /T}\cdot e^{ikt\cdot 2\pi /T}dx\right)\\ & =\frac{1}{2\pi }{\int }_{-\infty }^{\infty }\left({\int }_{-\infty }^{\infty }f(x)e^{-ix\cdot \xi }\cdot e^{it\cdot \xi }dx\right)d\xi \\ & =\frac{1}{2\pi }{\int }_{-\infty }^{\infty }\left({\int }_{-\infty }^{\infty }f(x)e^{-ix\cdot \xi }dx\right)e^{it\cdot \xi }d\xi \end{array}$$

Denote the Fourier transform as follows,

$$\hat{f}(\xi )={\int }_{-\infty }^{\infty }f(x)e^{-ix\cdot \xi }dx$$

then the Inverse Fourier transform

$$f(t)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }\hat{f}(\xi )e^{it\cdot \xi }d\xi$$

this is non-unitary, angular frequency form.

Fourier transform (unitary, oridnay frequency form)

For function $f\in L^1(\mathbb{R})$, i.e. ${\int }_{-\infty }^{\infty }|f(t)|dt<\infty$,

$$\hat{f}(\xi )={\int }_{-\infty }^{\infty }f(t)e^{-2\pi i\xi t}dt$$

with $\hat{f}\in L^1(\mathbb{R})$, i.e. ${\int }_{-\infty }^{\infty }|f(\xi )|d\xi <\infty$.

Inverse Fourier transform

$$f(t)={\int }_{-\infty }^{\infty }\hat{f}(\xi )e^{2\pi it\xi }d\xi$$

More

If function $f$ is frequency band-limited, i.e. $\exists \Omega \le 0,\forall |\xi |\ge \Omega ,\hat{f}(\xi )=0.$ Then

$$\hat{f}(\xi )=\sum _{k=-\infty }^{\infty }{c}_k{e}^{ik\xi \cdot \pi /\Omega }$$

where

$$c_k=\frac{1}{2\Omega }⟨\hat{f}(\xi ),e^{ik\xi \cdot \pi /\Omega }⟩=\frac{1}{2\Omega }{\int }_{-\Omega }^{\Omega }\hat{f}(\xi )e^{-ik\xi \cdot \pi /\Omega }d\xi$$

Further

$$c_k=\frac{2\pi }{2\Omega }\frac{1}{2\pi }{\int }_{-\infty }^{\infty }\hat{f}(\xi )e^{i(-k\pi /\Omega )\xi }d\xi =\frac{2\pi }{2\Omega }f(-k\pi /\Omega )$$

and

$$\hat{f}(\xi )=\sum _{k=-\infty }^{\infty }\frac{2\pi }{2\Omega }f(-k\pi /\Omega )e^{ik\xi \cdot \pi /\Omega }=\sum _{k=-\infty }^{\infty }\frac{2\pi }{2\Omega }f(k\pi /\Omega )e^{-ik\xi \cdot \pi /\Omega }$$

Therefore,

$$\begin{array}{rl}f(t)& =\frac{1}{2\pi }{\int }_{-\Omega }^{\Omega }\hat{f}(\xi )e^{it\cdot \xi }d\xi \\ & =\frac{1}{2\pi }{\int }_{-\Omega }^{\Omega }\left(\sum _{k=-\infty }^{\infty }\frac{2\pi }{2\Omega }f(k\pi /\Omega )e^{-ik\xi \cdot \pi /\Omega }\right)e^{it\cdot \xi }d\xi \\ & =\frac{1}{2\Omega }\sum _{k=-\infty }^{\infty }f(k\pi /\Omega ){\int }_{-\Omega }^{\Omega }{e}^{-i\xi (k\cdot \pi /\Omega -t)}d\xi \\ & =\frac{1}{2\Omega }\sum _{k=-\infty }^{\infty }f(k\pi /\Omega ){\left[\frac{1}{-i(k\cdot \pi /\Omega -t)}{e}^{-i\xi (k\cdot \pi /\Omega -t)}\right]}_{-\Omega }^{\Omega }\\ & =\sum _{k=-\infty }^{\infty }f(k\pi /\Omega )\frac{\sin (k\pi -\Omega t)}{k\pi -\Omega t}\end{array}$$

Derivatives.

$${\int }_{-\infty }^{\infty }{f}^{\prime }(t)e^{-it\cdot \xi }dt={\left[f(t)e^{-it\cdot \xi }\right]}_{-\infty }^{\infty }-{\int }_{-\infty }^{\infty }f(t)(-i\xi )e^{-it\cdot \xi }dt=(i\xi ){\int }_{-\infty }^{\infty }f(t)e^{-it\cdot \xi }dt$$

$$\mathcal{F}(\frac{df(t)}{dt})=(i\xi )\mathcal{F}(f(t))$$

Convolution

Definition

$$(f\ast g)(x)={\int }_{-\infty }^{\infty }f(\xi )g(x-\xi )d\xi$$

$$\mathcal{F}(f\ast g)=\mathcal{F}(f)\cdot \mathcal{F}(g)$$

$$f\ast g=g\ast f$$

$$\begin{array}{rl}\mathcal{F}(f\ast g)=& {\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f(\xi )g(x-\xi )d\xi e^{-ix\cdot t}dx\\ =& {\int }_{-\infty }^{\infty }f(\xi )\left({\int }_{-\infty }^{\infty }g(x-\xi )e^{-ix\cdot t}dx\right)d\xi \\ =& {\int }_{-\infty }^{\infty }f(\xi )\left({\int }_{-\infty }^{\infty }g(x-\xi )e^{-i(x-\xi )\cdot t}d(x-\xi )\right)e^{-i\xi \cdot t}d\xi \\ =& \hat{g}(t){\int }_{-\infty }^{\infty }f(\xi )e^{-i\xi \cdot t}d\xi \\ =& \mathcal{F}(f)\cdot \mathcal{F}(g)\end{array}$$

Parseval's theorem

$${\int }_{-\infty }^{\infty }|\hat{f}(\xi ){|}^{2}d\xi =2\pi {\int }_{-\infty }^{\infty }|f(t){|}^{2}dt$$