# Fourier series coefficients

Suppose I have a function

$S_n(t) = \sum_{k=1}^n a_k \sin((k-1/2)\pi t)$,

with unknown coefficients $a_k$. $S_n$ is perodic with period 4. If I can observe $S_n$ over the interval $[0,4]$, I can take a fast fourier transform to deduce the coefficients. I've implemented this in matlab, and everything works nicely.

Suppose I can only observe $S_n$ on the interval $[0,1]$. Is it still possible to deduce the $a_k$s?

• well it's odd so you only need half the period. – yoyo Mar 30 '11 at 19:06
• All the sines in the sum are linearly independent, so you can just pick $n$ points in $[0,1]$ in general position to get a non-singular system of $n$ linear equations for the $n$ coefficients. Or did you mean to ask whether it's possible to deduce the $a_k$ efficiently, e.g. using FFT rather than solving a system of linear equations? – joriki Mar 30 '11 at 19:37
• I was looking for an efficient way to deduce the coefficients - say $n \log n$ or better. – Simon Mar 30 '11 at 21:00

As yoyo noticed, the function is odd, so $S_n(t)=-S_n(4-t)$ for $t\in[2,4]$. Moreover, $S_n(t)=S_n(2-t)$ for $t\in[1,2]$.
There seem to be two possibilities of reducing the computational overhead, which can be combined to achieve an 8-fold improvement. The easy part is that all Fourier coefficients $X_j$ with even $j$ are zero, as $a_k$ corresponds to (the negative imaginary part of) $X_{2k-1}$. If you look at the butterfly scheme of the FFT, you can trace the even outputs all the way back to the first butterfly column, and see that you can drop half of the computations.
The other part is that you can essentially omit the lower 3/4 of the rows because of the symmetries that exist, and replace the last two butterflies by closed terms for all coefficients. However, this only works if the values of $t$ where you measure the function are chosen such that the omitted rows have exact mirrors, for example 1/8, 3/8, 5/8, 7/8 instead of 0, 1/4, 1/2, 3/4. I haven't worked out the details yet because I don't know how far you actually want to go.
• Ok, I see it now. If I have $f$ on [0,1], oddness gives me the value on [0,1] and [3,4]. Then the symmetry in your first paragraph gives me the value on [1,2] and applying oddness again, I have the value on [2,3]. Thus I can reconstruct the signal and compute the FFT. Nice, I owe you one. – Simon Mar 30 '11 at 22:51
• Exactly. Or apply the symmetry at $t=1$ first to extend it to $[0,2]$, then oddness on $[0,2]$ to extend it to $[0,4]$. – Sebastian Reichelt Mar 30 '11 at 23:54