1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.