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?

  • 1
    $\begingroup$ well it's odd so you only need half the period. $\endgroup$ – yoyo Mar 30 '11 at 19:06
  • 1
    $\begingroup$ 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? $\endgroup$ – joriki Mar 30 '11 at 19:37
  • $\begingroup$ I was looking for an efficient way to deduce the coefficients - say $n \log n$ or better. $\endgroup$ – 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.

  • $\begingroup$ Great, thanks for your help. I have very little intuition for fourier series or fourier analysis. I'm watching Brad Osgood's video lectures at the moment, but that'll take about 30 hours. $\endgroup$ – Simon Mar 30 '11 at 22:10
  • $\begingroup$ 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. $\endgroup$ – Simon Mar 30 '11 at 22:51
  • $\begingroup$ 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]$. $\endgroup$ – Sebastian Reichelt Mar 30 '11 at 23:54
  • $\begingroup$ Thanks for the comments about improving efficiency. You don't need to go to any trouble. For now, I'm just using this technique as part of a proof-of-concept for something else. I'll dig out a reference on FFTs if I ever need to start optimising. $\endgroup$ – Simon Mar 31 '11 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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