0
$\begingroup$

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.

enter image description here

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

$\endgroup$
1
  • $\begingroup$ If you are familiar with the basics of matrices, it's much easier in matrix form, IMHO. $\endgroup$ Commented Mar 11, 2021 at 3:38

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I see. Thank you for your response. From your answer, I'm assuming that $\{e^{-i\omega n}\}_{n=0}^{N-1}$ forms an orthonormal basis which people commonly refer to as the Hilbert Vector space. Then it follows the reason we take the inner product is because we want want to represent $f_n$ in terms of those basis. Is this the case? $\endgroup$
    – coderhk
    Commented Mar 11, 2021 at 0:59
  • 1
    $\begingroup$ Yes, that's essentially correct. There are some technicalities when dealing with the continuous-frequency version (need to extend the linear algebra notion of basis to deal with infinitely many basis functions, and define exactly which functions are in the Hilbert space), but those technicalities do not occur with the discrete-frequency version $\hat{f}_k$. $\endgroup$
    – user169852
    Commented Mar 11, 2021 at 1:05
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .