2
$\begingroup$

I was looking at the Discrete Fourier Tranform section in these notes and I'm very confused about how the transform is being indexed.

There, a list of the form $f(x_n)$ is given where $x_n$ takes on the values $x_n\in \{0,1,\ldots,N\}$, that is $x_n=n$. It is then claimed that $f(x_n)$ is the Discrete Fourier Transform of a list $f(k_j)$ if the two are related by

\begin{align} f(x_n)=\sum_{j=0}^N f(k_j)\exp (-ix_n k_j) \end{align}

where $k_j$ takes on the values $k_{j}\in \frac{2\pi}{N}\{0,1,\ldots, \frac{N}{2},1-\frac{N}{2}, 2-\frac{N}{2}, \ldots , -1\}$, that is

\begin{align} k_{j}&=\begin{cases} \frac{2\pi}{N}j & 0\le j\le N/2\\ \frac{2\pi}{N}\left (j-N\right ) & N/2 \le j\le N-1\ . \end{cases} \end{align}

What is going on with this indexing? Why don't we just have $k_j=\frac{2\pi}{N}j$?

This kind of indexing isn't what the Wikipedia page on Fourier transforming has, but it seems commonly used in code involving Fast Fourier Transforms, see the code on this page, for example.

$\endgroup$
2
$\begingroup$

Adding or subtracting a multiple of $2\pi$ from $k_j$ does not affect the values of the sum $\sum_{j=0}^N f(k_j)\exp (-ix_n k_j)$ at the points $x_n$. Thus, either form could be used if all we ever going to plug for $x_n$ are integers. (Or we could randomly add $10\pi$ to all the $k_j$.)

Aliasing is the term used for this agreement of different trigonometric waves on a discrete grid.

But if at any point someone will want to recover the sampled signal from the Fourier coefficients, then non-integer values of $x$ may come into play, and then the $2\pi$ frequency shift matters. Lower frequencies are preferred*, which means that, among all $k_j+2\pi \mathbb{Z}$ possibilities we should use the one with the smallest absolute value. This leads to the indexing you noticed.

Why should we prefer lower frequencies? Because out of the infinitely many trigonometric polynomials passing through given points, the one with the lowest frequencies possible minimizes the energy $\int |f'|^2$. Indeed, by virtue of orthogonality (Parseval's theorem) each term $c\exp (i\omega t)$ contributes some multiple of $|c|^2|\omega|^2$ to the energy, hence we minimize the energy by associating the Fourier coefficient $c$ with the lowest possible value of $|\omega|$. Minimizing energy eliminates extraneous oscillation in the recovered signal (see the graph below), and is a standard approach in signal/image restoration. Incidentally, if we were not restricted to using trigonometric polynomials, minimization of $\int |f'|^2$ among all functions passing through given points would produce a natural cubic spline (my blog post Connecting dots naturally).

I have a small illustration handy (for the discrete cosine transform, but the principle is the same): blue dots are the sampled values, red curve is constructed by using Fourier coefficients in the manner of $k_j = 2\pi j/N$, while in the green curve the high-frequency terms are replaced by their lower-frequency aliases. Clearly, the green curve is the one we want here.

aliasing

Source: my blog post Poor man’s discrete cosine transform.

If the above is not convincing, here is another reason: trigonometric sums $$ \sum_{k=0}^n (A_k \cos kx + B_k\sin kx) $$ naturally correspond to exponential sums $$ \sum_{k=-n}^n C_k \exp(i kx) $$ not to $$ \sum_{k=0}^{2n} C_k \exp(i kx) $$

$\endgroup$
  • $\begingroup$ Ok, cool, this is basically what I thought was going on. However I'd still like a more rigorous way to demonstrate your statement that "lower frequencies are preferred" and that they give a somehow better result than the $k_j=\frac{2\pi}{N}j$ indexing. $\endgroup$ – user26866 Jun 21 '18 at 8:53
  • $\begingroup$ It seems like anything but the smallest magnutde k_j's is an over-fitting, in some sense? At least heuristically $\endgroup$ – user26866 Jun 21 '18 at 9:25
  • 1
    $\begingroup$ The picture is similar to overfitting, but the phenomenon is different: it is more like Runge's phenomenon in interpolation. It's not that we use too many parameters, it's that we attach them to functions that are suboptimal for interpolating the curve. Also, I added a mathematical reason to prefer low frequencies, based on energy minimization. $\endgroup$ – user357151 Jun 21 '18 at 9:36

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.