Why the difference between definitions of the discrete/continuous Fourier transforms?

512 Views Asked by At

I should preface this question with the fact that I'm not familiar with the meaning/utility of the Fourier transform. Perhaps more accurately: I may have learned them, but have since forgotten; in any case, I'm just looking into some info about it to help a student out with its calculation, as I figured that would be easy enough. The Wikipedia page on the Discrete Fourier transform defines the transform as $$X_k=\sum_{n=0}^{N-1}x_n\exp\left(-\frac{2\pi i nk}{N}\right)$$ for a sequence $\{x_0,x_1,\ldots,x_{N-1}\}$, with $k\in\mathbb{Z}$.

Given the sequence $\{1,0,1,-1\}$, I have $$\begin{align*} X_k&=\sum_{n=0}^3x_n\exp\left(-\frac{2\pi ink}{4}\right)\\[1ex] &=\underbrace{1}_{n=0}+\underbrace{\exp\left(-\pi ik\right)}_{n=2}-\underbrace{\exp\left(-\frac{3\pi ik}{2}\right)}_{n=3}\\[1ex] &=1+\left(e^{-i\pi}\right)^k-\left(e^{-3i\pi/2}\right)^k\\[1ex] &=1+(-1)^k-i^k \end{align*}$$ I then have $X_k=\{1,-i,3,i\}$, where $k\in\{0,1,2,3\}$. However, checking with Mathematica, I should be getting $\dfrac{1}{2}\left\{1,i,3,-i\right\}$. As it turns out, there's a slight modification in the definition that accounts for the difference in our results. (Fourier is defined with $\frac{1}{\sqrt n}$ multiplied by a sum containing a positive exponent.)

Now, the factor of $\dfrac{1}{\sqrt n}$, I can wrap my mind around (sort of): in the article about the continuous transform, MathWorld mentions that the use of $\dfrac{1}{\sqrt{2\pi}}$ as opposed to $\dfrac{1}{2\pi}$ is a way of "restoring symmetry". But why the sign change in the exponent? The same disparity can be seen in the Mathematica documentation and Wikipedia article. Does using one sign over the other confer any special advantage?

1

There are 1 best solutions below

2
On BEST ANSWER

Let's back up a tad and talk about Fourier series.

Call $\phi_k(t) = \exp(ikt)$. Let's work on $L^2[0,2\pi]$. We can take the Fourier expansion of some function:

$$ x = \sum_{k\in\mathbb{Z}} a_k \phi_k $$

where

$$ a_k = \frac{\langle f, \phi_k \rangle}{\langle \phi_k, \phi_k \rangle} = \frac{1}{2\pi} \int_0^{2\pi} x(t) \phi_k(t)^*dt = \frac{1}{2\pi}\int_0^{2\pi} x(t)\exp(-ikt)dx $$

Notice that we could've just as easily called $\phi_k(t) = \exp(-ikt)$ and expanded. The $a_k$ in this case would be the conjugate of the above. So this choice is somewhat arbitrary. Keep that in mind.


How does this fit in with the DFT? Let's suppose you wanted to approximate the $a_k$ of the Fourier expansion of $x$. This is just the approximation of an integral. Let's do that in the simplest way imaginable — the left rectangle rule.

We'll take a uniform grid on $[0,2\pi]$ using $t_n = \Delta t \cdot n = \frac{2\pi}{N} \cdot n$, so that:

$$ a_k \approx \frac{1}{2\pi} \sum_{n=0}^{N-1}x(t_n)\exp(-ikt_n) \Delta t = \frac{1}{N} \sum_{k=0}^{N-1}x\left(2 \pi n / N\right)\exp\left(-i 2 \pi k n / N\right) $$

Now just define $x_n := x(2\pi n /N)$, and you see that $X_k \approx a_k$. If you approximate $N$ of the $a_k$ with $X_k$, you now have an $N \times N$ linear system which can be represented by a matrix (try writing it out!). This is non-normalized DFT matrix. If you want this matrix to be orthonormal, you need to change the factor of $\frac{1}{N}$ to $\frac{1}{\sqrt{N}}$.

Also if you look back to where I mentioned expanding in the conjugate of the $\phi_k$, you hopefully you realize that doing this derivation under this basis would result in the sign flip in the exponent.

So in a nutshell, mostly these things you ask about are just design choices.