有没有一种方法可以以最小的计算成本（少于 FFT 的计算）来识别信号的非零傅立叶系数的位置（只是位置，而不是值）？

因此，首先，计算 FFT：

请记住，$10N$-point FFT，您需要的分辨率：

假设我的信号是一个长度向量$N$与一些白噪声相关。假设要求的频率精度为

$$\frac{f_\text{sample}}{10N}$$

复杂度为$\mathcal O\left(10N\log(10N)\right)$.

你有一个稀疏的ca。$\frac1{20}$：

评论澄清我举一个例子，想象我们有长度为 1000 或 2000 的信号。我们取它的 DFT，并且有不到 50 个非零系数。

这意味着它不是那么稀疏，并且所有通过向问题抛出线性代数来利用稀疏性的算法都不能真正从这种情况中受益；一种$K$/$L$秩矩阵/矩阵运算通常具有最佳情况复杂度$K\cdot L$，所以考虑$K=N$ 这只能解决¹有利于稀疏操作，如果$L<10\log(10N)$. 现在你给了$N\approx 1000$，让我们在这里选择一个非常适中的对数基数——$\log_{10}$– 所以，你最终会遇到这种情况$L < 10\log_{10} 10000 = 40$，如你所见，与$L\approx 50$，通常情况并非如此——这只有在你的稀疏利用“音调查找器”非常、非常、非常有效的情况下才能奏效。

但是，你会说，有超高效的参数估计器，例如 ESPRIT，可以用更少的样本获得更高的分辨率！

是的，这也是我在你的情况下所建议的，一般来说，但你必须意识到这些基于子空间/特征值的方法适用于自相关信号模型——即它们需要估计自相关——矩阵，通常通过计算$N$-样本向量 - 一个复杂的操作$\frac 12 N^2$，即远远超过 FFT 的复杂性。

所以，回答你的问题：不，据我所知，没有计算成本更低的估计器，但有比 DFT 更有效的数学估计器；但是，您实际上可能会得到一个$\frac1{10}$分辨率小于$N$样本，但实际上，您的矩阵估计等级需要比您正在寻找的音调数量高得多，所以恐怕这不会有太大变化。