Sparse Inverse Fourier Transforms

Question

I'm looking to compute an IDFT but my input is very sparse:
Example:

IDFT length: 7,408,800 (complex floats)
Sparsity: 96.61% to 99.99%

I found this Sparse FFT website but it looks like the library deals with sparse inputs to standard DFT - not IDFT - also it doesn't look like it is not for consumer use.
Are there any techniques I can employ to improve performance for sparse IDFT - before even changing my DFT library? And now, are there any available libraries that give performance improvements for spare IDFT?

Marcus Müller · Answer

The FFT is faster than the naive DFT through matrix-vector products because it can reuse many intermediate results.
However, for inputs this sparse, there's really not much that can be re-used, even in the best case.
So, the most efficient way here is probably to work straight forward:

Allocate the space ($N=7408800$ values) for your output (initialize with zeros) $o$.
Go through your input $i$. Nested loops:

For every nonzero input index $n$:

For every output index $k$: add $i_ne^{j2pi frac{nk}N}$ to $o_k$.

Notes:

since with sparse input, your output is non-sparse, it's usually faster to traverse the input only once, but the output many times, instead of the other way around (that is because memory is much faster when addressed linearly)
to calculate the complex exponential, you can use SIMD-accelerated calculations, because the values are in consecutive addresses and have proportional phase. LibVOLK has a number of implementations that might be helpful for fast calculation here.

Sparse Inverse Fourier Transforms

One Answer

Add your own answers!

Ask a Question