# Can someone clearly explain the discrete Fourier transform (DFT)?

Consider a signal $f \in L_2$. Make $N$ samples

$f[n]:= f(\frac{2\pi n}{N}), n=0, \dots , N-1$

If we perform the discrete Fourier transform, we get coefficients

$$F[k] = \sum_{n=0}^{N-1} f[n]\omega^{kn}$$

where $\omega = e^{2\pi i /N}$.

I really don't see what these coefficients $F[k]$ represent, and why we would be interested in finding these.

Can someone explain this both intuitively and mathematically?

• It is a aliased / low-resolution copy of $f$ – user251257 Jun 5 '18 at 21:53
• I gave a quick linear algebra explanation of the DFT here and a slightly longer but still short explanation here. – littleO Jun 6 '18 at 0:51
• There is a link to the Princeton lectures here, see if it may help you. – Giuseppe Negro Jun 8 '18 at 13:48
• The Fourier Transform article on Better Expalined is full of intuition, images and highly recommended. – Somos Jun 8 '18 at 22:21

The Fourier transform is a change of basis ("coordinate system") for the vector space of integrable functions. Specifically, it is a pure rotation onto the basis of complex exponentials (sinusoids). This description is both intuitively geometric, and mathematically precise. Let me explain:

If you have studied linear algebra you have likely run into the concept of a change of basis. Imagine you have a vector on $\mathbb{R}^2$. You construct a basis $\{\hat{a}_x, \hat{a}_y\}$ to represent your vector $v$ as, $$v = a_1\hat{a}_x+a_2\hat{a}_y$$

To express $v$ on an alternative basis, $\{\hat{b}_x, \hat{b}_y\}$, we make use of the inner product (or "dot" product) that geometrically does the job of computing projections. Basically, we are asking:

Given $\begin{bmatrix}a_1\\a_2\end{bmatrix}$, $\{\hat{a}_x, \hat{a}_y\}$, and $\{\hat{b}_x, \hat{b}_y\}$, compute $\begin{bmatrix}b_1\\b_2\end{bmatrix}$ so that, $$v = a_1\hat{a}_x+a_2\hat{a}_y = b_1\hat{b}_x+b_2\hat{b}_y$$

If we take the inner product of both sides of this equation with $\hat{b}_x$, we get, $$\hat{b}_x\cdot(a_1\hat{a}_x+a_2\hat{a}_y) = \hat{b}_x\cdot(b_1\hat{b}_x+b_2\hat{b}_y)$$ $$a_1(\hat{b}_x\cdot\hat{a}_x)+a_2(\hat{b}_x\cdot\hat{a}_y) = b_1$$

To make the right-hand-side simplification, I assumed that basis $\{\hat{b}_x, \hat{b}_y\}$ is mutually orthonormal, as is common: $$\hat{b}_x\cdot\hat{b}_x=1,\ \ \ \ \hat{b}_x\cdot\hat{b}_y=0$$

Now we have $b_1$ in terms of $a_1$ and $a_2$ with some weights $\hat{b}_x\cdot\hat{a}_x$ and $\hat{b}_x\cdot\hat{a}_y$ that are really equal to the cosines of the angles between these vectors, which we know since we were the ones who chose these coordinate systems. We do the same thing again but dotting with $\hat{b}_y$ to compute $b_2$.

We can construct a matrix representation of this process, $$R \begin{bmatrix} a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \end{bmatrix}$$ where $R$ is an orthogonal matrix, $$R = \begin{bmatrix} \hat{b}_x\cdot\hat{a}_x & \hat{b}_x\cdot\hat{a}_y \\ \hat{b}_y\cdot\hat{a}_x & \hat{b}_y\cdot\hat{a}_y \end{bmatrix}$$

What does this have to do with the Fourier transform? We need to generalize our understanding of vectors now. 3Blue1Brown does a great job of explaining this. Put concisely: a function can be thought of as an infinite-dimensional vector. It has one element for every value it can take on, in an ordered array.

$$f(x) = \begin{bmatrix} \vdots \\ f(0.05) \\ f(0.051) \\ f(0.052) \\ \vdots \end{bmatrix}$$

where of course, it has elements for values in between 0.0500000... and 0.051, etc. The indexing is uncountable for continuous functions. For discrete domain functions, the indexing is countably infinite, $$f[n] = \begin{bmatrix} \vdots \\ f \\ f \\ f \\ \vdots \end{bmatrix}$$

and for finite domain functions, they are literally just large but finite (ordinary) $N$-dimensional vectors, $$f[n] = \begin{bmatrix} f \\ f \\ \vdots \\ f[N-1]\end{bmatrix}$$

Regardless, they are vectors because they satisfy the properties of vectors. Just consider that everything we do with functions is identical to what we do with ordinary (finite-dimensional) vectors: when you add two functions you add them "element-wise", scalar multiplication does what it should, and furthermore, we even have an inner product! (So these functions are not just members of a vector space, but actually a Hilbert space).

$$f(x)\cdot g(x) = \int_{-\infty}^\infty f(x)g(x) \, dx$$

or on a discrete domain like, say, discrete time (starts at $n=0$),

$$f[n]\cdot g[n] = \sum_{n=0}^\infty f[n]g[n]$$

Read what that integral means: for each $x$ (index), multiply $f(x)$ and $g(x)$ and sum that result down all the $x$. Look familiar?

$$\begin{bmatrix} a_1 \\ a_2 \\ \vdots \end{bmatrix} \cdot \begin{bmatrix} b_1 \\ b_2 \\ \vdots\end{bmatrix} = a_1b_1 + a_2b_2 + \cdots$$

If functions are vectors, then don't they need to be expressed on bases of other functions? Yes. How many basis functions do you need to span an infinite dimensional space? Infinitely many. Is it hard to describe an infinite number of unique functions? No. One example: $$g_1(x)= 1,\ \ g_2(x)=x,\ \ g_3(x)=x^2,\ \ \ldots,\ \ g_n(x)=x^n$$ Notice that we don't have both $x^n$ and $cx^n$, because they are linearly dependent; they span the same direction. We sometimes call linearly dependent functions "like-terms" in the sense that we can combine $x^n + cx^n = (1+c)x^n$ as opposed to linearly independent functions we cannot combine $x^n + x^{n+1}$.

If we took the inner product of one of these $g_i(x)$ with $g_j(x)$ we would certainly not get 0, so they don't have that nice orthogonal property where $\hat{b}_x\cdot\hat{b}_y=0$. The polynomials don't form an orthogonal basis. However, the complex exponentials do. There are plenty of other good demonstrations for many different function bases.

Now lets look at that mysterious Fourier transform (in finite discrete time, since that seems to be your interest). Let $c := 2\pi i / N$. $$\mathscr{F}(f[n]) = \sum_{n=0}^{N-1} e^{ckn}f[n]$$

Imagine all possible values of $e^{ckn}$ in a big (orthogonal) matrix, where each row corresponds to plugging in a specific $k$ and each column corresponds to plugging in a specific $n$. If you select some $k$, you are plucking out a specific value of the function that resulted from the multiplication of this matrix with the vector $f[n]$, a function we call $F[k]:=\mathscr{F}(f[n])$. Specifically, $$F[k=3] = f[n] \cdot e^{(c)(3)(n)}$$

(where that dot is an inner product, not ordinary multiplication). We say that $F[k]$ is just $f[n]$ expressed on a basis of exponential functions. Choosing a specific value of $k=k_1$ is picking out the value of $f[n]$ in the $e^{ck_1 n}$ direction. The entire $e^{ckn}$ can be viewed as the change of basis matrix.

Why would we be interested in something like this? Here are some practical reasons. I like to think about it like this: choice of basis (coordinates) is arbitrary, yes, but depending on the problem / application, a clever choice of basis makes all the difference in solving it. For example, exponentials are the eigenfunctions of the derivative operator, so switching to the basis of exponentials might help with solving differential equations, and it does!

Each coefficient F(k) represents how 'strong' the frequencies in the kth bin are. That is, if you have N samples, then the number of bins goes as 1/N, and F(k) is how much total frequency component is from k-1 to k. This is useful because as long as your N is large enough such that the size of each bin is smaller then the frequency resolution you care about, then you can use F(k) as the frequency spectrum.

For the intuition on this, lets look at this term $$\omega^{kn} = e^{2\pi i \cdot kn/N}$$ This is a wave that has kn cycles over the range N. When you sum over n, you are summing over the discrete frequencies 0,k,2k,...,(N-1)k. Just like when you evaluate an integral by summing over small intervals $\Delta x$, you approximate each interval or 'bin' by the value at one point, and just take that value across the entire interval.

In physics, harmonic signals of various origins are studied. A common feature of these signals is that the corresponding measuring instrument fixes the sinusoid. The measuring instrument may have a pair of quadrature channels spaced apart in phase. In this case we speak of a complex input signal.

The meaning of spectral processing of the signal consists in determining the parameters of harmonics - frequency, amplitude and phase. In this case, the quality of spectral processing is characterized by the accuracy of measuring these parameters, as well as by the resolution of the separation of nearby harmonics.

Analog devices of spectral analysis assume the presence of "strings", according to the resonant excitation of which one can judge the presence of signals of a known frequency. A feature of such devices is the continuous nature of the input signal. At the same time, the measured spectrum of the signal is discrete, since the number of "strings" is limited.

The sampling of the input signal with a fixed interval $\Delta t$ generates a "repetition frequency" $F = 1 / \Delta t$ for complex signal at the input. The effect of this frequency is manifested in the fact that harmonics whose frequency difference is a multiple of this frequency become indistinguishable (stroboscopic effect).

Discrete Fourier transform (DFT) is a mathematical apparatus for spectral processing of discrete signals. In the case of $n$ input samples, the parameters of $n$ equidistant harmonics $$f_i = \dfrac in F,\ i=0, 1\dots n-1$$ are usually calculated.

The signal extraction for each harmonic of the DFT is carried out by multiplying the samples of the input signal by a signal with a unit amplitude and a zero phase, complex conjugate to the expected one. In this case, the average value of the modulus of the accumulated productions is considered as the amplitude of the signal, and the ratio of the real and imaginary parts determines the phase.

A remarkable feature of the DFT is the presence of fast ($O (n \log n)$) algorithms (FFT) for its realization. This allows to use it, in particular, for quick calculation of convolutions.

If the autocorrelation function of the signal is in the input of the DFT, then, according to the Wiener-Khinchin theorem, the output will be a function of the power spectrum density. A more economical analogue is the spectral analysis of the sequence of initial (complex or real) amplitudes. With a significant length of the input sample, the difference between these two methods is reduced.

In addition, the DFT can be part of more sophisticated signal processing algorithms (as cepstral analysis).

An unpleasant effect in the processing of amplitude data is the gap between the final and initial samples of the signal which is manifested as a broadband interference. This effect can be reduced using special "weight windows", smoothly falling from the middle of the sample to its edges.