1
$\begingroup$

This might be a silly question, but I'm really confused by the way Fourier Transform was taught in my algorithms class, and everything else I found on the internet.

The way we defined FT is first talking about polynomial multiplication, and using FFT (DFT) as a means to transform the vector of $(x_0, x_1, \cdots)$ into $(P(x_0), P(x_1), \cdots)$. This lead to a definition that DFT is a linear mapping defined as

\begin{align} y_j = \sum_{k=0}^{n-1}{x_k \cdot \omega^{jk}} \end{align}

where $y_j = P(\omega^j)$, that is the polynomial value at $\omega^j$. Then we proceeded to prove that DFT can be represented by a matrix, and that it has an inverse and can be used to convert the polynomial values (called graph) back into the coefficients. This all makes perfect sense to me, but is in no way related to signal processing (at least in my mind).

Then we went on to define spectral analysis, ending up with a theorem saying something like _For every real vector there are coefficients $\alpha_0, \cdots, \alpha_{n/2}$ and $\beta_0, \cdots, \beta_{n/2}$, such that

\begin{align} x = \sum_{k=0}^{n/2}{(\alpha_k c^k + \beta_k s^k)} \end{align}

where $s^k$ and $c^k$ are defined as a Fourier tranform of a vector sampled from $\sin 2 k \pi x$ and $\cos 2 k \pi x$ respectively (sampling at $n$ points).

The problem I have here is that the spectral analysis seems to go the other way around, taking function values of the analysed function (sampled at $n$ points), and returning some form of coefficients for the linear combination of sine/cosine functions. On the other hand, the first definition takes coefficients and produces function values, meaning it goes the other way around.

My confusion here is that I'm not sure if these two are at all related, or if it's just a coincidence that I can use FFT (DFT) to do both of these seemingly related things, only the other way around.

To add one last bit of confusion, I've also seen DFT defined as follows, with the exponent sign flipped (other than that it seems identical, having $\omega = e^{2 \pi i / N}$):

\begin{align} DFT[k] = \sum_{n=0}^{N-1}{x[n] \cdot e^{-2 \pi i k \frac{n}{N}}} \end{align}

What I'm looking for is an explanation of how these definitions and use cases are related, and why are they working in the seemingly opposite directions.

$\endgroup$
  • $\begingroup$ your teacher is crazy. work only on the last formula and understand that it is an orthogonal matrix, thus that it is easy to invert (just take the conjugate transpose of the matrix), and realize that the product of two polynomials $A(x),B(x)$ is the polynomial whose coefficients are the convolution of the coefficients of $A(x)$ and $B(x)$, and that the main property of the DFT is that it transforms convolution products into normal products (read a real DFT course !) $\endgroup$ – reuns Jan 20 '16 at 21:39
  • $\begingroup$ @user1952009 I understand the part about convolution, but that's not the issue. I'm trying to understand how DFT on polynomial relates to signal processing. $\endgroup$ – Jakub Arnold Jan 20 '16 at 22:08
0
$\begingroup$

First: This two equations $$ \begin{align} y_j &= \sum_{k=0}^{n-1}{x_k \cdot \omega^{jk}}\\ DFT[k] &= \sum_{n=0}^{N-1}{x[n] \cdot e^{-2 \pi i k \frac{n}{N}}} \end{align} $$ are the same, if you choose $\omega = e^{-\frac{2\pi i}{N}}$. Of course you have to rename some varibles the $k$ in the first equation is $n$ in the second and so on.

Second: The fast fourier transform gives you the coefficients. In the case that you have a time series for example it gives you frequencies. At the same time there exists an inverse fourier transformed. This gives you back the original vector if you have the coefficients. Say you know the frequencies of a signal then you can calculate the timeseries. The inverse fourier transformed looks nearly like the fourier transformed but with a sign flipped. Actually they are pretty similar and it is up to you (or your professor) what to call the fourier and what the inverse.

Third: The sine/cosine transformation is another transformation although it is named fourier transformed as well. That is because it is closely related to the fourier transformed. The advantage is that your coefficients are all real numbers (you like that more in most programming languages). Sometimes it is called real fourier transformed. In a way it is the same because $$e^{-2\pi \frac{k n}{N} i} = \cos(-2\pi \frac{k n}{N}) + i \sin(-2\pi \frac{k n}{N})$$ So you can recombine the coefficients of one to the ones of the other.

PS: DFT (discrete fourier transformed) is the mathematical concept. While FFT (fast fourier transformed) is an algorithm for the DFT. (Which is very fast btw.) Wasn't sure if that was obvious to you.

$\endgroup$
  • $\begingroup$ Thanks for explaining, though I'd appreciate if you could show how is the sign changed between the "normal" and the "inverse". If the "normal" gives coefficients, then I'd apply both the normal to get polynomial coefficients and signal frequencies? Because from what I understand, the "normal" is for coefficients and timeseries, and the "inverse" is for the original vector and the frequencies. At least that's how I understand it from my definition of the cosine transform. $\endgroup$ – Jakub Arnold Jan 20 '16 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.