# Which way does the Fourier Transform go?

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.

• 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 !) – reuns Jan 20 '16 at 21:39
• @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. – Jakub Arnold Jan 20 '16 at 22:08

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