信息处理 - 频谱估计算法的计算复杂度是多少？它们依赖什么？ - 吾爱随笔录

信息处理 fft 频谱功率谱密度估计频谱估计

2022-02-06 19:56:20

有很多频谱估计技术，每一种都有一些优点和缺点。算法如：

和许多其他的。但是我不知道哪个更适合嵌入式系统实现，因为我不知道它们的计算复杂性，所以我对这种方法的计算复杂性的数学估计更感兴趣，特别是它们的复杂性如何受输入噪声等因素的影响，频谱占用等？

我找到了Spectrum Estimaton Methods，它极大地解释了这些方法，但没有从计算复杂性的角度比较它们。

1个回答

[*] 中讨论了各种非参数 PSD 估计方法的计算要求。复杂度取决于长度 $N$ 您的数据记录。粗略地讲：

计算 DFT 幅度平方的最直接的周期图方法 $N$ 样本的复杂度为 $N \log N$ .
Bartlett 和 Welch 方法使用 $M$ 重叠的长度窗口 $M$ 每个并计算〜 $N/M$ DFT，所以复杂度是 $\frac{N}{M} \cdot M \log M = N \log M$ .
Yule-Walker 方法 $AR(p)$ 反转一个 $p\times p$ Toeplitz 矩阵的复杂度为 $O(p^2)$ . Toeplitz 矩阵本身是由计算自相关值的估计形成的 $p$ 不同的滞后 $N$ - 给出复杂度的长数据向量 $O(Np)$ . 所以总复杂度是 $O(p^2 + Np)$ .
音乐估计 $M \times M$ 来自数据的自协方差矩阵，通过平均外部产品，例如， $N/M$ $M$ - 原版的长块 $N$ -long 信号，然后计算特征分解 $M\times M$ 自协方差矩阵是 $O(M^3)$ . ( $M$ 由用户选择。对于一个信号 $p$ 频率成分，选择 $M>p$ .)

我认为复杂性不受输入噪声水平的影响，因为算法本身不会改变。

参考

其它你可能感兴趣的问题