  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.
