论文标题
具有结构化支持的信号的快速DFT计算
Fast DFT Computation for Signals with Structured Support
论文作者
论文摘要
假设$ n- $长度信号具有$ k $的已知频率支持。给定样品访问此信号，我们可以计算DFT的速度？这个问题的答案取决于频率支持的结构。 我们首先确定一些频率支持，该支持（理想）$ o（k \ log k）$复杂性是可以实现的，称为均匀集。我们给出了radix-2的概括，该概括可以启用$ o（k \ log k）$具有均匀频率支持的信号计算。使用均匀的集合作为构建块，我们构建了更复杂的支持结构，可以实现$ O（k \ log k）$的复杂性。我们还调查了DFT计算与支持结构的关系，并提供部分对话。
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.
