Basic question about the Discerete Fourier Transfrom

Question

I have trouble understanding the transition from the infinite integral of the Fourier transform $$ \mathcal{F}f(v) = \int^\infty_{-\infty}e^{ivk}f(k)dk $$ to the discrete version $$ \mathbf{F}f_n = \sum^{N-1}_{k=0} f_k e^{ink/N}. $$ I first thought that one picks a finite subinterval of $\mathbb{R}$ and paritions it into $N$ pieces, and then somehow use periodicity of the integrand to extend this to infinity, but $e^{ivk}f(k)$ isn't necessarily periodic. This also doesn't make any sense if I want to calculate the transform for a single value $v$. So what does this finite sum actually represent?

Answer 1

I think what might be confusing for you is the fact that there are two different discrete transforms:

1. the Discrete Fourier Transform (DFT), which is only applicable to series with finite lengths (the length is usually denoted by $N$, as in the formula you gave)
2. the Discrete-time Fourier transform (DTFT), which is defined for series with infinite lengths:

$$X(\omega)=\sum_{n=-\infty}^{\infty}x[n]e^{-in\omega}$$

The importance of the DFT lies in the fact that there are very efficient algorithms (the Fast Fourier Transform (FFT) algorithm) for its computation.

Answer 2

Try approximating the integral using a Riemann sum, using $N$ intervals of length $1/\sqrt N$, going from $x=-\sqrt N/2$ to $x=\sqrt N/2$.