What is the computational complexity of Spectrum Estimation Algorthms and What they depend upon?

Question

There are lots of spectrum estimation techniques, each with some pros and cons. Algorithms like:

• Music
• Welch's method
• Yule-Walker AR method
• Periodogram
• modified covariance method
• multitaper method (MTM)
• Spectrogram using short-time
• Fourier transform
• Burg method covariance method

and many many other. However I do not know which is more proper for embedded system implementation, because I don't know their computational complixy so I am more interested in mathematical estimation of computational complexity of this methods and especially how their complexity is affected with factors like input noise, spectrum occupation, etc?

I'v found Spectrum Estimaton Methods, which greatly explains these methods, but does not compare them from computational complexity point of view.

Answer 1

The computational requirements for various non-parametric PSD estimation methods is discussed in [*]. The complexity depends on the length $N$ of your data record. Roughly speaking:

1. The most straightforward periodogram method which calculates the magnitude squared of the DFT of $N$ samples has a complexity of $N \log N$.
2. Bartlett and Welch methods use $M$ overlapping windows of length $M$ each and calculate ~$N/M$ DFTs, so the complexity is $\frac{N}{M} \cdot M \log M = N \log M$.
3. Yule-Walker method for an $AR(p)$ inverts a $p\times p$ Toeplitz matrix which has a complexity of $O(p^2)$. The Toeplitz matrix itself is formed from estimates of the autocorrelation values calculated at $p$ different lags from the $N$-long data vector giving a complexity $O(Np)$. So the total complexity is $O(p^2 + Np)$.
4. MUSIC estimates an $M \times M$ autocovariance matrix from data by averaging the outer products of, say, $N/M$ $M$-long blocks of the original $N$-long signal and then calculates the eigendecomposition of the $M\times M$ autocovariance matrix which is $O(M^3)$. ($M$ is chosen by the user. For a signal with $p$ frequency components, choose $M>p$.)

I don't think the complexity is affected by input noise level because the algorithms themselves do not change.

Reference

[*] J. Proakis Digital Signal Processing, 4th Edition Ch. 14 https://www.pearsonhighered.com/program/Proakis-Digital-Signal-Processing-4th-Edition/PGM258227.html