A faster version of the [[Discrete Cosine Transform|Discrete Fourier Transform]] / [[Fourier Decomposition]] of a [[Discrete]] [[Set|set]] / [[Vector]] of either [[Real Numbers]] or [[Complex Numbers]]. This method is also called the [[Fast Fourier Transform|Cooley-Tukey Algorithm]]. This method takes advantage of [[Complex Exponential|complex exponentials]] and the symmetry of [[Sine]] and [[Cosine]] to cut down the computation required. With some array $\vec x$ of size $N$ (where $N=2^{k},k\in \mathbb{Z}^{+}$. Our two sets class of vectors are $\set{\vec c_{k},\vec s_{k}}$ that we use as a [[Basis]] $\set{\vec c_{k},\vec s_{k}}$. $\huge \begin{align} \vec c_{k} &= \mat{ \cos 0 , \cos \pa{ \frac{2\pi k}{N}}, \dots, \cos \left( \frac{2\pi(N-1)k}{N} \right) }\\ \vec s_{k} &= \mat{ \sin 0 , \sin \pa{ \frac{2\pi k}{N}}, \dots, \sin \left( \frac{2\pi(N-1)k}{N} \right) } \end{align} $ $ \huge \begin{align} \vec c_{0} &= \mat{1,1,\dots,1} \\ \vec c_{N} &= \mat{1,-1,1,-1,\dots,-1} \\ \braket{\vec c_{0},\vec c_{0} } &= \braket{\vec c_N ,\vec c_{N} } = N \\ \braket{\vec c_{k},\vec c_{k} } &= \braket{\vec s_{k},\vec s_{k} } = \frac{N}{2} \\ \vec x &\in \R^{N} \\ a_{k} &= \braket{\vec c_{k},\vec x } \\ b_{k} &= \braket{\vec s_{k}, \vec x } \\ \end{align} $ $ \huge \begin{align} \vec x &= \frac{1}{N} a_{0} \vec c_{0} + \frac{2}{N}\sum_{k=1}^{\frac{N}{2}-1}\pa{ a_{k}\vec c_{k} + b_{k}\vec s_{k} } + \frac{1}{N}a_{\frac{N}{2}} \vec c_{\frac{N}{2}} \end{align} $ With [[Complex Numbers]], $ \huge \begin{align} \let \vec F_{k} &= \vec c_{k} + i \vec s_{k} \\ &= \mat{ \cos\pa{\frac{2\pi kn}{N}} + i\sin \left( \frac{2\pi kn}{N} \right) }_{n=0,\dots,N-1} \\ &= \mat{ e^{\frac{2\pi ikn}{N}} }_{n=0,\dots,N-1} \\ \let \omega &= e^{\frac{2\pi i}{N}} \\ \vec F_{0} &= \mat{1,1,\dots,1} \\ \vec F_{1} &= \mat{ \omega^{0}, \omega^{1}, \omega^{2}, \dots, \omega^{N-1}} \end{align} $ Where $\omega$ is a [[Roots of Unity|Root of Unity]]. $\huge \begin{align} \vec F_{2} &= \mat { \omega^{0}, \omega^{2}, \omega^{4} ,\dots, \omega^{2(N-1)}} \end{align} $ Being able to express this in terms of a root of unity is that we only need to compute cosine and sine for $\omega$, and we can get the rest of the terms by simply multiplying by $\omega$, eg. a [[Geometric Series]]. $ \huge \begin{align} \inprod{\vec F_{k}, \vec x} &= \inprod{\vec c_{k},\vec x } + i\inprod{\vec s_{k}, \vec x } \\ &= \sum_{n=0}^{N-1} \omega^{kn} x_{n} \\ &= \sum_{n=0}^{\frac{N}{2}-1} \omega^{2kn}x_{2n} + \sum_{n=0}^{\frac{N}{2}-1} \omega^{k(2n+1)}x_{2n+1} \\ &= \op{DFT}\pa{\mat{x_{0},x_{2},\dots,x_{{N}-2}}}_{k} + \omega^{k}\op{DFT}\pa{ \mat{x_{1},x_{2},\dots,x_{{N}-1}} } \end{align} $ >[!example] $N=8$ >$ >\large \begin{align} >\inprod{\vec F_{3} ,\vec x } &= x_{0}+ \omega^{3}x_{1} + \omega^{6}x_{2} + \omega x_{3} + \omega^{4}x_{4} + \omega^{7}x_{5}+\omega^{2}x_{6}+\omega^{5}x_{7} \\ >&= \pa{x_{0}+\omega^{6}x_{2} + \omega^{4}x_{2} + \omega^{4}x_{4}+\omega^{2}x_{6}} + \pa{\omega^{3}x_{1} + \omega x_{3} + \omega^{7} x{5} + \omega^{5}x_{7}} \\ >&= \pa{x_{0}+ \omega^{3}x_{2}+ \omega^{6}x_{4}+\omega^{4}x_{6} } + \omega^{3}\pa{x_{1}+\omega^{3}x_{3}+\omega^{6}x_{5}+\omega^{4}x_{7}} >\end{align} >$