A Highly Optimized Nonlinear Least Squares Technique for Sinusoidal Analysis: From (Omega)(K2N) to (Omega)(N log (N))

D'haes W. A Highly Optimized Nonlinear Least Squares Technique for Sinusoidal Analysis: From (Omega)(K2N) to (Omega)(N log (N)). In: AES Convention 116. Audio Engineering Society; 2004. Paper 6045. Available from: https://aes.org/publications/elibrary-page/?id=12767

@inproceedings{Dhaes2004_12767,
  author = {D'haes, Wim},
  title = {{A Highly Optimized Nonlinear Least Squares Technique for Sinusoidal Analysis: From (Omega)(K2N) to (Omega)(N log (N))}},
  booktitle = {AES Convention 116},
  note = {Paper 6045},
  year = {2004},
  month = may,
  publisher = {Audio Engineering Society},
  url = {https://aes.org/publications/elibrary-page/?id=12767}
}

TY  - CPAPER
TI  - A Highly Optimized Nonlinear Least Squares Technique for Sinusoidal Analysis: From (Omega)(K2N) to (Omega)(N log (N))
AU  - D'haes, Wim
T2  - AES Convention 116
M1  - Paper 6045
PY  - 2004
DA  - 2004/05/06
UR  - https://aes.org/publications/elibrary-page/?id=12767
PB  - Audio Engineering Society
LA  - en
AB  - In the field of sinusoidal modelling, two types of least squares amplitude estimation methods are distinguished. A first group of methods estimate the complex amplitude of each sinusoid in an iterative manner. Although their main disadvantage is that they are unable to resolve overlapping frequency responses, they are used frequently because of their computational complexity being O(N log (N)). By contrast, methods that compute all amplitudes simultaneously can resolve overlapping frequency responses but their computational complexity scales with a power of three in function of the number of sinusoidal components. In this work a method is proposed which allows to compute all amplitudes simultaneously and still has an O(N log (N)) complexity. This is realized by explicitly including a window with a bandlimited frequency response in the least squares derivation resulting in a band diagonal system of equations which can be solved in linear time. Since overlapping frequency responses are allowed, an iterative method must be used to optimize the frequencies resulting in a nonlinear least squares technique. A commonly used technique is Newton optimization which requires the computation of the gradient and the Hessian matrix. Also here, the same computational gain is realized by applying the same methodology.
ER  -