Can't extract odd function with FFT

Question

I can't correctly extract spectrum from data points of odd function (e.g. $\cos\left(\frac23\pi x\right)$, $16$-points vector $[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1]$), instead of one function I get a bunch of sines and cosines (which are correct for a given window and points, but still not ok for further analysis):

$(0.375000)\cos( (2.00)\pi x) + (0.000000)\sin( (2.00)\pi x)+ (0.042224)\cos( (1.88)\pi x) + (0.008399)\sin( (1.88)\pi x)+ (0.044194)\cos( (1.75)\pi x) + (0.018306)\sin( (1.75)\pi x)+ (0.048952)\cos( (1.62)\pi x) + (0.032708)\sin( (1.62)\pi x)+ (0.062500)\cos( (1.50)\pi x) + (0.062500)\sin( (1.50)\pi x)+ (0.164437)\cos( (1.38)\pi x) + (0.246097)\sin( (1.38)\pi x)+ (-0.044194)\cos( (1.25)\pi x) + (-0.106694)\sin( (1.25)\pi x)+ (-0.005612)\cos( (1.12)\pi x) + (-0.028213)\sin( (1.12)\pi x)+ (0.000000)\cos( (1.00)\pi x) + (0.000000)\sin( (1.00)\pi x)+ (-0.005612)\cos( (0.88)\pi x) + (0.028213)\sin( (0.88)\pi x)+ (-0.044194)\cos( (0.75)\pi x) + (0.106694)\sin( (0.75)\pi x)+ (0.164437)\cos( (0.62)\pi x) + (-0.246097)\sin( (0.62)\pi x)+ (0.062500)\cos( (0.50)\pi x) + (-0.062500)\sin( (0.50)\pi x)+ (0.048952)\cos( (0.38)\pi x) + (-0.032708)\sin( (0.38)\pi x)+ (0.044194)\cos( (0.25)\pi x) + (-0.018306)\sin( (0.25)\pi x)+ > (0.042224)\cos( (0.12)\pi x) + (-0.008399)\sin( (0.12)\pi x)$

Is it a fundamental restriction of the FFT or am I doing something wrong? Thank you.

Answer 1

Input sanity check: repeat your sequence to see if it describes the function you want. Your input:

1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1

when repeated, becomes

1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,...

This obviously is not a simple periodic function: sometimes two 1s appear together. This is what your FFT output describes.

How to fix this? Don't include the redundant right endpoint of the period. Concretely:

1. Find the period of your function, $T=3$
2. Decide on the number of samples per period; you want $n=16$.
3. Determine the sample interval: $h = T/n = 3/16$.
4. Sample the function at $0,h,2h,3h,\dots, (n-1)h$. This is the data for FFT. Note it does not include the value at $T = nh$, which would be redundant.

---

Additional points:

1. What does the vector 1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1 have to do with $\cos(2\pi/3)$? Sampling this function at integers, I get 1,-.5,-.5 repeated.
2. What do you mean by an odd function? $\cos(2\pi x/3)$ is not odd in my book.
3. It is not necessary for the length to be a power of 2. Discrete Fourier transform amounts to multiplying a given vector by the Fourier matrix of same size, which makes perfect sense for every length of vector. The powers of 2 are convenient to the FFT algorithm, but no more than that. In particular, fft([1,0,0,1,0,0,1,0,0,1,0,0,1,0,0])/15 in Matlab works just fine, resulting in $$\frac13 + \frac13 \exp(5\cdot 2\pi ix/15)+\frac13 \exp(-5\cdot 2\pi ix/15) = \frac13+\frac23 \cos(2\pi x/3)$$
4. If you don't know the period of your function, you should sample it at a much higher rate than at this example. To resolve an unknown periodic function from three samples per period is unrealistic.