Fast DFT Computation for Signals with Structured Support

Abstract

Suppose an $N-$length signal has known frequency support of size $k$. Given sample access to this signal, how fast can we compute the DFT? The answer to this question depends on the structure of the frequency support. We first identify some frequency supports for which (an ideal) $O(k\log k)$ complexity is achievable, referred to as homogeneous sets. We give a generalization of radix-2 that enables $O(k\log k)$ computation of signals with homogeneous frequency support. Using homogeneous sets as building blocks, we construct more complicated support structures for which the complexity of $O(k\log k)$ is achievable. We also investigate the relationship of DFT computation with additive structure in the support and provide partial converses.

45 pages, 16figures

References in corpus (5)

• The structure theory of set addition revisited
• Discrete Sampling and Interpolation: Universal Sampling Sets for Discrete Bandlimited Spaces
• Convolution Idempotents with a given Zero-set
• Computing the Discrete Fourier Transform of signals with spectral frequency support
• An $O(k\log n)$ Time Fourier Set Query Algorithm