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,...,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.