1
$\begingroup$

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?

  • 0
    I was looking for an efficient way to deduce the coefficients - say $n \log n$ or better.2011-03-30

1 Answers 1

2

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.

  • 0
    Th$a$nks 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.2011-03-31