0
$\begingroup$

While I was studying Positional Encoding, I came across an article that links coding resolution to Fourier transforms: "For anyone who has studied finite Fourier transforms, this problem should be familiar. Only half of the frequencies are unique. " However, even if I have explored this topic, I do not find the connection with the Fourier transform, in particular the reference to the fact that only half of the frequencies must be unique. Can anyone help me?

Reference: https://towardsdatascience.com/master-positional-encoding-part-i-63c05d90a0c3#:~:text=Fourier%20transforms%2C%20this%20problem%20should%20be%20familiar.%20Only%20half%20of%20the%20frequencies%20are%20unique.

$\endgroup$

1 Answer 1

2
$\begingroup$

I think the statement "Only half of the frequencies are unique" refers to the aliasing and the time series being real for a discrete Fourier transform. The discrete Fourier transform (DFT) is defined as $$ X_k = \sum_{n=0}^{N-1}x_n\exp\left(-i\frac{2\pi}{N}kn\right). $$ You can see that $X_{k + N} = X_k$. As $$ \begin{aligned} X_{k+N} &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi\frac{(k+N)n}{N}\right)\\ &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi \frac{kn}{N} - i2\pi \frac{N}{N}\right)\\ &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi \frac{kn}{N} - i2\pi\right)\\ &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi \frac{kn}{N}\right)\exp\left(- i2\pi\right)\\ &= \sum_{n=0}^{N-1}x_n\exp\left(-i2\pi \frac{kn}{N}\right)\\ &= X_k \end{aligned} $$ This "feature" is called aliasing. Because of that only for $k \in [-N / 2, N/2 - 1]$ (assuming $N$ is even), $X_k$ are unique. And if the series to be transformed $x_n$ is real ($x_n^* = x_n$), then $$ \begin{aligned} X_{-k} &=\sum_{n=0}^{N-1}x_n\exp\left(-i\frac{2\pi}{N}(-k)n\right)\\ &=\sum_{n=0}^{N-1}x_n\exp\left(i\frac{2\pi}{N}kn\right)\\ &=\sum_{n=0}^{N-1}\left[x^*_n\exp\left(-i\frac{2\pi}{N}kn\right)\right]^*\\ &=\sum_{n=0}^{N-1}\left[x_n\exp\left(-i\frac{2\pi}{N}kn\right)\right]^*\\ &=X^*_k, \end{aligned} $$ where $^*$ refers to complex conjugate. Resulting in only half of the frequencies' $X_k$ being unique.

$\endgroup$
4
  • $\begingroup$ How can i see that $ X_ {k + N} = X_k $? $\endgroup$
    – Massimo
    Mar 18, 2022 at 18:30
  • 1
    $\begingroup$ As adding $N$ is the same as shifting the phase by $2\pi$, the value does not change ($\exp(i2\pi) = 1$), in details: $X_{k+N} = \sum_{n=0}^{N-1}x_n\exp(-i2\pi(k+N)n/N) = \sum_{n=0}^{N-1}x_n\exp(-i2\pi kn/N - i2\pi N/N) = \sum_{n=0}^{N-1}x_n\exp(-i2\pi kn/N - i2\pi) = \sum_{n=0}^{N-1}x_n\exp(-i2\pi kn/N) = X_k$. Let me also add this to the answer. $\endgroup$
    – Peter Pang
    Mar 18, 2022 at 18:36
  • $\begingroup$ your answer is really perfect, $$ exp \ left (- i2 \ pi \ right) \\ $$ is it 1 for Euler's identity (practically it is the square)? $\endgroup$
    – Massimo
    Mar 18, 2022 at 18:52
  • $\begingroup$ There are a few different ways to look at it, the easiest way would be $\exp(i2\pi) = \cos(2\pi) - i\sin(2\pi) = 1$. Or if you understood $\exp(i\theta)$ as a rotational on the complex plane, rotate by $2\pi$ obviously give you $1$. Glad that my answer helps; please consider accepting my answer. $\endgroup$
    – Peter Pang
    Mar 18, 2022 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.