Line 31: | Line 31: | ||
=== Fourier Matrix === | === Fourier Matrix === | ||
Let $F_n$ be a Fourier matrix: | Let $F_n$ be a Fourier matrix: | ||
− | * | + | * <math>F_n = \begin{bmatrix} |
1 & 1 & 1 & \cdots & 1 \\ | 1 & 1 & 1 & \cdots & 1 \\ | ||
1 & w^2 & w^2 & \cdots & w^{n - 1} \\ | 1 & w^2 & w^2 & \cdots & w^{n - 1} \\ | ||
Line 37: | Line 37: | ||
\vdots & \vdots & \vdots & \ddots & \vdots \\ | \vdots & \vdots & \vdots & \ddots & \vdots \\ | ||
1 & w^{n-1} & w^{2(n-1)} & \cdots & w^{(n-1)^2} \\ | 1 & w^{n-1} & w^{2(n-1)} & \cdots & w^{(n-1)^2} \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* each element is $(F_n)_{ij} = w^{ij}$ for all $i,j$ (indexes of $F_n$) | * each element is $(F_n)_{ij} = w^{ij}$ for all $i,j$ (indexes of $F_n$) | ||
− | * matrix $F_n$ is a [[Symmetric | + | * matrix $F_n$ is a [[Symmetric Matrices|symmetric]] |
where $w \in \mathbb C$: | where $w \in \mathbb C$: | ||
Line 55: | Line 55: | ||
* $w = \exp \left( i \ \cfrac{2\pi}{4} \right) = i$ | * $w = \exp \left( i \ \cfrac{2\pi}{4} \right) = i$ | ||
* so we have $1, i, i^2 = -1, i^3 = 1$ | * so we have $1, i, i^2 = -1, i^3 = 1$ | ||
− | * thus, | + | * thus, <math>F_4 = \begin{bmatrix} |
1 & 1 & 1 & 1 \\ | 1 & 1 & 1 & 1 \\ | ||
1 & w^2 & w^3 & w^4 \\ | 1 & w^2 & w^3 & w^4 \\ | ||
Line 70: | Line 70: | ||
1 & -1 & 1 & -1 \\ | 1 & -1 & 1 & -1 \\ | ||
1 & -i & -1 & i \\ | 1 & -i & -1 & i \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* for 4-point Fourier transform: for a vector with 4 components | * for 4-point Fourier transform: for a vector with 4 components | ||
Line 77: | Line 77: | ||
Columns of $F_n$ are orthogonal | Columns of $F_n$ are orthogonal | ||
* Let's check it for $n=4$: | * Let's check it for $n=4$: | ||
− | * | + | * <math>\overline{\Big[ 1 \ i \ -1 \ -i \Big]} \begin{bmatrix} 1 \\ -i \\ -1 \\ i \end{bmatrix} = 1 + 1 - 1 - 1 = 0</math> |
* but they are not orthonormal | * but they are not orthonormal | ||
* e.g. for $F_4$ all columns have length 2 | * e.g. for $F_4$ all columns have length 2 | ||
Line 105: | Line 105: | ||
How can we use this fact? | How can we use this fact? | ||
− | * we want to go from $W_64$ to a matrix | + | * we want to go from $W_64$ to a matrix <math>\left[ \begin{array}{c|c} |
W_{32} & 0 \\ | W_{32} & 0 \\ | ||
\hline | \hline | ||
0 & W_{32} \\ | 0 & W_{32} \\ | ||
− | \end{array} \right] | + | \end{array} \right]</math> |
* i.e. factorize $W_{64}$ in terms of $W_{32}$ | * i.e. factorize $W_{64}$ in terms of $W_{32}$ | ||
− | * can factorize it as | + | * can factorize it as <math>W_{64} = \begin{bmatrix} |
I_{32} & D_{32} \\ | I_{32} & D_{32} \\ | ||
I_{32} & -D_{32} | I_{32} & -D_{32} | ||
Line 119: | Line 119: | ||
0 & W_{32} | 0 & W_{32} | ||
\end{bmatrix} | \end{bmatrix} | ||
− | P_{64} | + | P_{64}</math> |
− | ** where $P_n$ is a $n \times n$ [[Permutation Matrices|permutation matrix]] | + | ** where $P_n$ is a $n \times n$ [[Permutation Matrices|permutation matrix]] <math>P_n = \begin{bmatrix} |
− | 1 & & & & | + | 1 & & & & & & \\ |
− | & & 1 & & | + | & & 1 & & & & \\ |
− | + | & & & & \ddots & & \\ | |
− | & & & & | + | & & & & & 1 & \\ |
\hline | \hline | ||
− | & 1 & & & | + | & 1 & & & & & \\ |
− | & & & 1 & | + | & & & 1 & & & \\ |
− | + | & & & & \ddots & & \\ | |
− | & & & & | + | & & & & & & 1 \\ |
− | \end{bmatrix} | + | \end{bmatrix}</math> |
** first, in $P$ we have rows with even columns containing $1$, and then, in the second half, rows that contain $1$ in odd columns (here we start indexing columns from 0) | ** first, in $P$ we have rows with even columns containing $1$, and then, in the second half, rows that contain $1$ in odd columns (here we start indexing columns from 0) | ||
** $P_n$ takes even-numbered components first, and then odd-numbered | ** $P_n$ takes even-numbered components first, and then odd-numbered | ||
** $D_n$ is a diagonal matrix, | ** $D_n$ is a diagonal matrix, | ||
− | ** | + | ** <math>D_n = \begin{bmatrix} |
1 & & & & \\ | 1 & & & & \\ | ||
& w & & & \\ | & w & & & \\ | ||
Line 140: | Line 140: | ||
& & & \ddots & \\ | & & & \ddots & \\ | ||
& & & & w^{n/2 - 1} | & & & & w^{n/2 - 1} | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* now we can break $W_{32}$ down in the same way! | * now we can break $W_{32}$ down in the same way! | ||
− | ** | + | ** <math>W_{32} = \begin{bmatrix} |
I_{16} & D_{16} \\ | I_{16} & D_{16} \\ | ||
I_{16} & -D_{16} | I_{16} & -D_{16} | ||
Line 150: | Line 150: | ||
0 & W_{16} | 0 & W_{16} | ||
\end{bmatrix} | \end{bmatrix} | ||
− | P_{32} | + | P_{32}</math> |
* use recursion | * use recursion | ||
Goal: to expand a function $f(x)$
These functions $\cos nx$ and $\sin nx$ are orthogonal
Let's start with $a_0$
We can do it for all the coefficients
Let $F_n$ be a Fourier matrix:
where $w \in \mathbb C$:
Example
$n = 4$
Columns of $F_n$ are orthogonal
So, given a matrix $W_n$ and a vector $\mathbf u \in \mathbb C^{n}$ (or in $\mathbb R^{n}$)
The idea of FFT
Example:
How can we use this fact?
This way we reduce computation from $O(n^2)$ to $\cfrac{n}{2} \, \log_2 n$