Given a positive integer $N$, the [[Discrete]] [[Fourier Transform|Fourier Transform]] with $0\leq k < N$, and a input [[Complex Vector Space|complex vector]] $\vec x\in \mathbb{C}^{N}$ is defined as: $\huge \begin{align} \op{DFT}\left( N,k,\vec x\right) &= \left< \vec x, \vec u_{k} \right> \\ &= \sum^{N-1}_{j=0} x_{j} e^{-i \frac{2\pi}{N}kj} \end{align} $ Where $\vec u_{k}$ is the $k^{\text{th}}$ [[Fourier Basis|Fourier Basis Vector]] of $\mathbb{C}^{N}$, and we are using the standard [[Complex Inner Product]] $\left< \cdot,\cdot \right>$. >[!warning] >Note there is some disagreement on the definition of the DFT, where some people choose to normalize in different places (eg. multiplying the output by $\frac{1}{N}$ on one side or the other ) ## Specializations ### Cosine Transform ($\mathbb{R}$) Given our array $\vec x=\braket{1,0,4,5,3,7,4,5, \dots}$ with $n$-points, we wish to make a fourier [[Function|Transformation]] using [[Cosine]] functions. $\huge \begin{align} \vec c_{k} &= \mat{\cos \left( \frac{\pi}{N}\left( n+ \frac{1}{2} \right)k \right) }_{n} \end{align} $ All of these functions are in a [[Vector Space]] are are [[Orthogonal]] (up to the [[Functional Inner Product]]). $\huge \begin{align} \forall i \neq j&: \braket{\vec c_{i}, \vec c_{j} } =0 \\ \braket{\vec c_{0},\vec c_{0}} &= n \\ \forall k \neq 0 &: \braket{\vec c_{k} ,\vec c_{k}} = \frac{n}{2} \end{align} $ This constitutes a basis $\set{\vec c_{0},\vec c_{1},\vec c_{2},\dots,\vec c_{n-1}}$. $\huge \begin{align} a_{0} &= \frac{1}{n} \braket{\vec c_{0}, \vec x} \\ a_{k} &= \frac{2}{h}\braket{\vec c_{k}, \vec x }\, \forall 1 \leq k < n \\ \vec a &= \mat{a_{0}\\ a_{1} \\\vdots} \end{align} $ $ \huge \begin{align} \\ \vec x &= a_{0} \vec c_{0} + a_{1} \vec c_{1} + \dots \\ \vec c_{0} &= \braket{1,1,\cdots} \\ \vec c_{k} &= \left< 1, \\ \cos\pa{ \frac{k\pi}{n}2}, \cos\pa{ \frac{k\pi}{n}2}, \dots, \cos\pa{ \frac{k\pi}{n}(n-1)} \right> \end{align} $ --- Given, $\huge \begin{align} \vec x &= \left[ x_{0},x_{1},x_{2},\dots , x_{N-1}\right] \\ \huge \vec x &= X_{0} \vec c_{0} + X_{1}\vec c_{1} + \cdots + X_{N-1}\vec c_{N-1} \end{align} $ $ \huge \begin{align} \forall \vec c_{k} : \left< \vec c_{k}, \vec x \right> &= \left< \vec c_{k}, X_{0}\vec c_{0}+X_{1}\vec c_{1} + \cdots \right> \\ &= X_{0} \braket{\vec c_{k}, \vec c_{0} } + \cdots + X_{N-1}\braket{\vec c_{k},\vec c_{N-1} } \\ &= X_{k}\braket{{\vec c_{k},\vec c_{k}}} \\ X_{k} &= \frac{\braket{\vec c_{k},\vec x }}{\braket{\vec c_{k},\vec c_{k}}} \end{align} $ $\huge \begin{align} \braket{\vec c_{0},\vec c_{0} } &= N \\ \braket{\vec c_{k},\vec c_{k} } &= \frac{N}{2} \\ \end{align} $ $ \huge \begin{align} X_{0} &= \frac{1}{N}\braket{\vec c_{0},\vec x } \\ X_{k} &= \frac{2}{N}\braket{\vec c_{k}, \vec x } \end{align} $ We can use the sequence $X_{k}$ to reconstruct the original vector $\vec x$. $\huge \begin{align} x_{n} &= \sum_{k=0}^{N-1} X_{k} \cos \left( \frac{\pi}{N}\left( n+\frac{1}{2} \right) k \right) \\ X_{k} &= \frac{2}{N} \sum_{n=0}^{N-1} x_{n}\cos \left( \frac{\pi}{N}\left( n+\frac{1}{2} \right) k \right) \end{align} $