A highly optimized nonlinear least squares technique for sinusoidal analysis: From O(K~2N) to O(N log(N))

摘要

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 G(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.