我正在寻找计算 IDFT，但我的输入非常稀疏：
例子：
- IDFT 长度：7,408,800（复杂浮点数）
- 稀疏性：96.61% 至 99.99%
我找到了这个Sparse FFT网站，但它看起来像库处理标准DFT 的稀疏输入 - 而不是 IDFT - 而且它看起来也不适合消费者使用。
在更改我的 DFT 库之前，我是否可以采用任何技术来提高稀疏 IDFT 的性能？现在，是否有任何可用的库可以提高备用 IDFT 的性能？
稀疏傅里叶逆变换
信息处理
fft
自由度
IFFT
2022-02-03 01:13:29
1个回答
FFT 通过矩阵向量乘积比朴素 DFT 更快，因为它可以重用许多中间结果。
但是，对于这种稀疏的输入，即使在最好的情况下，实际上也没有多少可以重复使用。
因此，这里最有效的方法可能是直接工作：
- 分配空间 (值）为您的输出（用零初始化）.
- 浏览您的输入. 嵌套循环：
- 对于每个非零输入索引：
- 对于每个输出索引： 添加到.
- 对于每个非零输入索引：
笔记：
- 因为使用稀疏输入，您的输出是非稀疏的，通常只遍历输入一次，但输出多次，而不是相反（这是因为内存在线性寻址时要快得多）
- 要计算复指数，您可以使用 SIMD 加速计算，因为这些值位于连续地址中并且具有比例相位。LibVOLK 有许多可能有助于快速计算的实现。