Computing a pruned FFT in O(n*log(k))

Specific Domains Numerics
1

Let’s say that I consider a DFT with n coefficients. I am only interested in k<<n of these coefficients. In theory, it is possible to compute these k coefficients in O(n* log(k)) instead of O(n* log(n)), see https://www.fftw.org/pruned.html. This is called the pruned FFT. Does someone know how to compute a pruned FFT in Julia that runs in O(n*log(k))?

1 Like
2
1 Like
3

This is the link I posted myself. If this is a solution, it’s only for the case where one wants the k first coefficients, and not arbitrary components of the transform. But let’s say I try to expand on it, then what is the equivalent of fftw_plan_many_dft in FFTW.jl? I don’t see it among the functions available in the package. I’ll think about it more and post my solution if I get something running.

4

The procedure for the pruned FFT described by FFTW is O(n log(k)) to compute k coefficients out of n. Interestingly, I found a C++ library called sparse fast Fourier transform (SFFT) that does the same thing in O(k log(n)).

1 Like
5

See the references at the end of that page, for example. My understanding is that the constant factors are going to be significantly worse if you want a completely arbitrary set of coefficients (as least for exact algorithms).

(If you just want a different block of k consecutive coefficients, you can easily modify the code on the FFTW page: multiply the inputs by a linear phase, which has O(n) cost, and the window of computed coefficients is shifted via the shift theorem.)

No, it’s not doing the same thing — it’s solving a different problem.

A pruned FFT computes k specified DFT outputs from n inputs, regardless of the values of the inputs or the other outputs. (The pruned FFT on the FFTW page, for k consecutive outputs, is exact up to roundoff errors, but there are also other algorithms that are approximate.)

The SFFT algorithm works only if you have inputs such that there are only k nonzero (or at least non-negligible) outputs of the DFT (i.e. the outputs are “sparse”), but you don’t have to know which outputs are nonzero. Moreover, it’s a randomized, approximate algorithm (via sampling the inputs) — and there are additional errors if the other DFT outputs are not exactly zero.

(The original SFFT authors are at MIT too and I’ve chatted with them on occasion. Note that the SFFT method actually uses an ordinary FFT as a subroutine, and in fact their code uses FFTW itself.)

4 Likes
6

Thanks for these clarifications!