Currently, I'm a 3rd year university student. I don't have a strong background in real analysis or differential equations so please bear with me. I'm trying to learn about the Discrete Fourier transform (DFT) and I came across this video.
I know that a Discrete Fourier transform is essentially decomposing a function $f(x)$ into $N$ sinusoidals where each one has a frequency of $k\omega$ where $\omega$ is some fundamental frequency and $k$ is an integer multiple.
When we're looking at the discrete Fourrier transform with $N$ data points, the $kth$ Fourrier coefficent is computed using the formula
$$\hat{f_k} = \sum_{n=0}^{N-1}f_ne^{-2\pi i k n/N}$$
where $0 \leq k \leq N-1$.
From my understanding $\hat{f_k}$ is a complex value where the magnitude of the complex number gives me the amplitude of the sinusoidal having frequency $k\omega$ and the angle of the complex number is the phase shift of the sinusoidal used in the decomposition of $f(x)$.
The things that confuses me about the formula $\hat{f_k} = \sum_{n=0}^{N-1}f_ne^{-2\pi i k n/N}$ is the fact that $n$ is involved in the exponential. By Euler's formula we know that $$e^{-2\pi i k n/N} = \cos(-2\pi k n/N) + i\sin(-2\pi k n/N)\\ = \cos(2\pi k n/N) – i\sin(2\pi k n/N).$$ Then from this we see that that when we are computing the $nth$ term of $\hat{f_k}$, the frequency inside the sinusoidal is also changing. I wouldv'e expected that the frequency remains at $2\pi k/N$ over all summations instead of $2\pi kn/N$. If the frequency is changing at each term of the summation, how does this formula give the total contribution for frequency $k\omega$.
Best Answer
There's always going to be an $n$ in the exponent of the summation. Conceptually, the Fourier transform evaluates the inner product of $\{f_n\}_{n=0}^{N-1}$ with the complex exponential $\{e^{-i \omega n}\}_{n=0}^{N-1}$, where $\omega$ is the frequency of interest: $$\tilde{f}(\omega) = \sum_{n=0}^{N-1} f_n e^{-i\omega n}$$ where $\tilde{f}$ denotes the continuous-frequency version of the Fourier transform. This is a $2\pi$-periodic function of the real-valued frequency $\omega$.
If there were no $n$ in the exponent, then you would have $e^{-i\omega}$, which is just a constant that can be pulled out of the summation, and you would end up with $$e^{-i\omega}\sum_{n=0}^{N-1}f_n$$ which isn't very interesting!
The discrete Fourier transform evaluates $\tilde{f}$ at specific values of $\omega$, namely $\omega = 2\pi k/N$ for $k=0,1,\ldots N-1$. This is just a uniform sampling of the interval $[0,2\pi)$. $$\hat{f}_k = \tilde{f}(2\pi k / N) = \sum_{n=0}^{N-1} f_n e^{-i(2\pi k/N) n} = \sum_{n=0}^{N-1} f_n e^{-i2\pi k n / N}$$