I have the generic problem of analysing a discretly sampled signal, lets say at 100Hz, and would like to compute features (ML application) of this signal at different scales:

An instantiation of this problem is computing the FFT on real-signal with N samples:

Original signal: X[1],...,X[N]

Suppose I have already computed the FFT of the following subarrays:





which is each of size k. Then I would like to compute the FFT of the subarray


(which is of size 4*k), WITHOUT reconstructing the original array X[.] and running an ordinary FFT on the array of size 4k. Roughly I would like to do O(N) primitive operations in the best case if that is at all possible.

Is there some recursive property I could use?

PS: Note that if the goal of computing the FFT is substituted with e.g. finding the mean or the variance there exist easy recursive properties that allow merging of the results in constant time.

  • $\begingroup$ Possible duplicate of: How to calculate a large size FFT using smaller sized FFTs? $\endgroup$ – ThP Oct 31 '14 at 14:28
  • $\begingroup$ Not at all a duplicate. Let me rephrase the problem. I am giving my signal array to a group of children. They cut the signal into parts so that each child gets a piece. Then each child separatedly computes a full-size FFT on its piece. The children deliver the FFT pieces to me. I want to construct the FFT of the original signal in time faster than O(N log N)! $\endgroup$ – muellerclaudio Oct 31 '14 at 16:57

You can compute the DFT of the total signal from the DFTs of its parts but this is not efficient. What you would need to do is interpolate each DFT to the length of the total array (which is equivalent to zero-padding the sub-blocks to length $N$ before computing the individual FFTs), and then combine the interpolated DFTs with appropriate complex factors. This is computationally less efficient than going back to the time domain and computing the FFT of the whole sequence.

There is no recursion involved (unlike your examples of recursive mean and variance computation), simply because the data blocks are not related to each other. If you were to have a sliding window with a fixed length and you wanted to recompute the DFT after shifting the window by one sample, then you would indeed get a recursive formula for the DFT. This is known as the sliding DFT.

  • $\begingroup$ Thanks for your answer. Thanks for pointing out the sliding FFT, it is another way I could organize the computation. // It would still be recursive right? Because you would still DIVIDE by splitting the arrays, RECURSE by applying FFTs (although of same size as original array) to the sub-arrays and then COMBINE with the complex factors as you proposed. $\endgroup$ – muellerclaudio Nov 2 '14 at 7:01
  • $\begingroup$ @muellerclaudio: You mean zero-padding the smaller sequences and then combine them? I wouldn't call that procedure recursive, because a recursion normally computes something new by updating something older, whereas here the sequences are all from the same (longer) time frame. It's rather combining things to get the total result. $\endgroup$ – Matt L. Nov 2 '14 at 10:44

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.