I'm using a discrete Fourier transform to translate a finite set of samples to the frequency domain. I'm trying to start with a very simple set, but am still getting confused.
I'm starting with this set of samples:
$$\{ 1,0,1,0,1,0,1,0\}$$
I expected to get output indicating that the frequency domain representation of this set was expressed by
1*cos(t)
But instead I get:
Raw output:
$$\{ 4.0, 0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 0.0\}$$
My (possibly flawed) interpretation of the output:
Frequency representation=
$$ 4.0\cos(2\pi/1)+$$
$$ 0.0\cos(2\pi/2)+$$
$$ 0.0\cos(2\pi/3)+$$
$$ 0.0\cos(2\pi/4)+$$
$$ 4.0\cos(2\pi/5)+$$
$$ 0.0\cos(2\pi/6)+$$
$$ 0.0\cos(2\pi/7)+$$
$$ 0.0\cos(2\pi/8)$$
Why are the coefficients $4$?
Why, when my source data has a very simple repeating pattern, do I have more than one entry in the frequency domain representation?
If my output interpretation of correct, how should I interpret the resulting function? Here's a graph.
I'm using an Apache math library's implementation of the DFT (Commons math 3-3.3).
Best Answer
Your input is not just cosine. Cosine function has zero mean. Your function has mean $1/2$. It is accurately represented by $$ \frac12 + \frac12 \cos 4 t,\quad t=0,\pi/4,\pi/2,3\pi/4,\dots,7\pi/4 $$ This means: coefficient $1/2$ of frequency $0$, coefficient $1/2$ of frequency $4$.
The output lists frequencies beginning with $0$. Also, the normalization of the transform in this routine happens to be such that instead of the Fourier coefficients themselves you get $N$ times them, where $N$ is the length of your vector. Dividing by $8$ gives the vector of coefficients.
Generally, the Fourier transform involves complex exponential functions $e^{ikt}=\cos kt+i\sin kt$. You don't see the sines here because the input data is "even".
The implementation you are using gives the same result as Matlab's fft command, so I refer there for the complete list of formulas for the direct and inverse transform implemented by this function.
Let's take a more generic example (I rounded Matlab output below) :
The easiest way to see how the output $X$ represents the input $x$ is to look up the inverse command (
ifftin Matlab), because this is the thing that recovers original vector. Its formula is$$x(j) = \frac1N \sum_{k=1}^8 X(k) e^{-2\pi i(j-1)(k-1)/N} \tag{1}$$
(which is unfortunately mistyped on the Matlab page). Although both $X$ and the complex exponentials involve complex numbers, the result of summation will be real if your input $x$ is real. Therefore, we can simplify the matter by keeping only the real part of (1):
$$x(j) = \frac1N \sum_{k=1}^8 (\operatorname{Re}X(k))\cos( 2\pi i(j-1)(k-1)/N) \\+ \frac1N \sum_{k=1}^8 (\operatorname{Im}X(k))\sin( 2\pi i(j-1)(k-1)/N) \tag{2}$$
With specific numbers: $$x(j) = \frac18 (9-4\cos (2\pi (j-1)/8)+6\cos (2\pi (j-1)(4-1)/8) - 5\cos (2\pi (j-1)(5-1)/8) + \dots) + \frac18 ( -2 \sin(2\pi (j-1)/8)-\sin(2\pi (j-1)(3-1)/8) +4\sin(2\pi (j-1)(4-1)/8) \dots) $$ This should recover the input
[1 0 2 3 0 4 -1 0]for $j=1,\dots,8$, but I was too lazy to type in all the terms. The formulas are easier to write if the arrays use $0$-based indexed, but Matlab has $1$-based indices.