Pruned FFT runtime

Question

Pruned fast Fourier transforms compute only a specified subset of the result indices in faster time, although sometimes with a slower implementation constant (because FFT is generally so optimized). They can also exploit sparsity in the input vector to further accelerate computation.

On http://www.fftw.org/pruned.html, the runtime is reported to be $\in O(n\log k)$, where $n$ is the length of the input vector and $k$ is the number of desired indices to compute in the result (of course, the standard FFT could always be used to compute the full result in $O(n\log n)$ steps); however, I cannot figure out where the benefit of sparsity in the input vector is measured in this bound.

Does anyone know the runtime / how to get the runtime of a pruned FFT on $n$ inputs, $m$ of which are nonzero, and where $k$ outputs are computed? I have an algorithm that depends on a step very similar to a pruned FFT calculation, and I have a lot of sparsity.

Thanks a lot for any advice you can lend.

Answer 1

If you want to do a normal FFT, and just try to exploit the fact that many of the input coefficient are zero because of padding, or that you are only interested in part of the output coefficients because you intentionally oversampled the input, then this isn't really worth the trouble, especially in 1D.

If you are thinking about 2D or 3D, want to avoid the coupling between pitch and resolution (i.e. that the pitch has to be a multiple of the resolution), and implement the data reduction for pruned FFT explained in the linked FFTW documentation, then an implementation based on Bluestein FFT/Chirp Z-transform can provide real practical benefits. It is still an exact transform without any resolution based error. This is the variant I most often ended up with in the past, but sometimes variants with resolution dependent error were more appropriate, see below for more details.

The Bluestein FFT can be implemented once (with appropriate case districtions for optimal speed) using FFTW (or your prefered FFT library) as a backend, and then forgotten and used as a black box. Don't know whether there exists a good free implementation, but it wouldn't be difficult to provide one.

The runtime of such an implementation is best measured in term of the needed intermediate memory. A single 1D Bluestein FFT needs $O((n+m)\log(n+m))$ time and $O((n+m))$ space. For a 2D implementation, the intermediate storage after the FFT has been performed in one direction will be $n_x m_y$ or $m_x n_y$, depending on whether the x- or y-direction was chosen. The corresponding runtime will be $O(n_x(n_y+m_y)\log(n_y+m_y)+(n_x+m_x)\log(n_x+m_x)m_y)$ or $O((n_x+m_x)\log(n_x+m_x)n_y+m_x(n_y+m_y)\log(n_y+m_y))$.

---

The story doesn't end here. In the past, I sometimes also had to use a non-uniform FFT. This transform has a well controllable resolution based error, but it can transform much more than just sums of delta distributions, it can also compute transforms of polygonal domains and more.

But the story doesn't end here either. I hope I will never have to use those, but in a recent breakthrough development, researchers at MIT came up with ingenious randomized algorithms, and presented several new results for sparse Fourier transform:

• An $O(k \log n)$-time algorithm for the exactly k-sparse case.

• An $O(k \log n \log(n/k))$-time algorithm for the general case.

• An $\Omega(k \log(n/k) /\log\log n)$ lower bound for sample complexity.