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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ How can i see that $ X_ {k + N} = X_k $? $\endgroup$– MassimoCommented 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$ Commented 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$– MassimoCommented 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$ Commented Mar 18, 2022 at 18:56