Why does the Discrete Fourier transform involve the $nth$ data in the transform?

Question

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$.

Answer 1

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}$$

Answer 2

Your intuition about the discrete Fourier transform seems to be confusing you. I suggest the following intuition about DFT. Fix the positive integer $N$. Define the roots of unity $$ \zeta_k = \zeta_{k,N} := e^{2\pi i k/N} = \zeta_1^k.\tag{1} $$ Define the sequence of functions $$ z_k(n) := \zeta_k^n \quad\text{ where }\quad 0\le k<N. \tag{2} $$ Check that each $\,z_k(n)\,$ function for $k>0$ is sinusoidal with period $N$ and frequency $\,k\,\omega=k/N.\,$

Check that the average value of $\,z_k(n)\,$ is $0$ if $\,k>0\,$ while $\,z_0(n)\,$ is the constant value $1$. Expressed as an equation this is $$ \delta_{0,k} = \frac1N\sum_{n=0}^{N-1} z_k(n)\quad \forall k. \tag{3}$$ Check that the $\,z(.)\,$ functions satisfy $$ z_{j+k}(n) = z_j(n)z_k(n)\quad \forall j,k. \tag{4}$$ Assume that we have a sequence that is a sum of sinusoids $$ f_n := \sum_{k=0}^{N-1} c_k\,z_k(n). \tag{5} $$ Define the DFT of $\,f\,$ with $$ \hat{f_k} := \frac1N \sum_{n=0}^{N-1}f_nz_{-k}(n) \\ = \frac1N \sum_{n=0}^{N-1}\left( \sum_{j=0}^{N-1} c_j\,z_j(n)\right)z_{-k}(n)\\ = \sum_{j=0}^{N-1}c_j \left(\frac1N \sum_{n=0}^{N-1}\,z_{j-k}(n) \right) = c_k. \tag{6}$$ Thus the coefficients $\,c_k\,$ in equation $(5)$ are exactly the values of the DFT $\,\hat{f_k}\,$ defined in equation $(6)$.