Discrepancy in Discrete Fourier Transform Algorithm Formula?

185 Views Asked by At

I'm having a bit of trouble with a small part of the following formula (taken from this page):

$$F_k=\sum_{n=0}^{N-1}f(x_n)e^{-(2\pi i)k\frac{n}{N}}\tag{1}$$

This formula is supposed to represent the discrete Fourier transform (DFT) of the set of points $x_n\in \mathbb{C}$, sampled at "frequency" values $k=0,1,\cdots,(N-1)$.

What I don't understand is the derivation of this expressions. From my understanding, the DFT is an approximation to the true/continuous Fourier transform for when one only has access to values of the original function at certain discrete points. If the original function is $f(x)$, the discrete "sampling" points are $x_n$, and the distance between $x_n$ and $x_{n+1}$ is $\Delta x_n$, then one way to approximate this integral on the assumption that $f(x)$ dies off sufficiently quickly outside the sampling interval is by

$$\mathcal{F}[f(x)](k)=\int_{-\infty}^{\infty}f(x)e^{-(2\pi i)kx}\,dx\longrightarrow \sum_{n=0}^{N-1}f(x_n)e^{-(2\pi i)kx_n}\Delta x_n$$

If we now assume that $x_n=x_0+n\Delta x$ and only take values of the Fourier transform for $N$ discrete values of $k$, we arrive at the following formula for the DFT

$$F_k=\color{red}{\text(\Delta x)e^{-(2\pi i)kx_0}}\sum_{n=0}^{N-1}f(x_n)e^{-(2\pi i)k(n\color{red}{\Delta x})}$$

As you can see, the expression I have arrived at above doesn't agree with the first equation (1). I have colored red the terms that don't agree. How do I mend my equation into the correct equation, (1)? What have I missed?

Every source I've found online gives almost no explanation for why they make the assumptions/exceptions they do in order to arrive at an equivalent expression to (1). For example, this article seems to make the assumption that $x_0=0$ and $\Delta x = 1$, which I can't see the motivation for other than notational simplicity.

1

There are 1 best solutions below

0
On BEST ANSWER

From my understanding, the DFT is an approximation to the true/continuous Fourier transform for when one only has access to values of the original function at certain discrete points.

In my opinion, the way to derive $(1)$ is not through approximating the continuous Fourier transform evaluated at integers, but through approximating the coefficients of the Fourier series expansion.

In particular, if $f(x) = \sum_k a_k e^{i 2 \pi kx}$ where

$$ a_k = \int_0^1 f(x) e^{-i 2 \pi k x} dx $$

then you find $a_k \approx (1)$ via the "left endpoint rule".

Note that implicit in this, is the assumption that the discrete array that you are performing DFT on, is a sample from the function $f(x)$ at $ f(\frac{n}{N})$, $n=0,\ldots,N-1$. This is fair so long as you keep this in mind.