TransWikia.com

Sparse Inverse Fourier Transforms

Signal Processing Asked by Tobi Akinyemi on October 24, 2021

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?

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

Answered by Marcus Müller on October 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP