Fourier Transform

Description:

• Most real life signals are periodic, the sum is another signal
• It can be used to approximate the resulting signal as a sum of periodic ones
• Most simple and common periodic function as signal are cos and cosine
  • ex: $t\to \cos (\frac{2\pi k}{n}t)$ where $k\in \{0,1,...,n-1\}$

Fourier basis

• Let $w$ be the $n$-th root of unity: $w=e^{-2\pi \mathbf{i}/n}$
• Define the vectors in ${\mathbb{R}}^n$ as $u^{(j)}(t)=\frac{1}{\sqrt{n}}{w}^{tj},t=1,...,n$
• ex: $W=\frac{1}{\sqrt{4}}\left[\begin{array}{cccc}{w}^0& w^0& w^0& w^0\\ w^0& w^1& w^2& w^3\\ w^0& w^2& w^4& w^6\\ w^0& w^3& w^6& w^9\end{array}\right]=\frac{1}{\sqrt{4}}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& -i& -1& i\\ 1& -1& 1& -1\\ 1& i& -1& -i\end{array}\right]$