Asymptotic analysis of a fast algorithm for efficient multiple frequency estimation

Abstract

Based on an asymptotic analysis of the contraction mapping (CM) method of Li and Kedem (IEEE Trans. Inform. Theory, vol. 39, pp. 989-998, May 1993), a bandwidth shrinkage rule is proposed for fast and accurate estimation of the frequencies of multiple sinusoids from noisy measurements. The CM frequency estimates are defined as the fixed points of a contractive mapping formed by the lag-one autocorrelation coefficient calculated from the output of a parametric filter applied to the observed time series. With bandwidth parameters judiciously chosen according to the asymptotic analysis, the algorithm is shown to be able to accommodate possibly poor initial values of precision O(n -1/3) and converge to a final estimate whose accuracy is arbitrarily close to O(n -3/2), the optimal error rate for frequency estimation under the Gaussian assumption. The total computational complexity of the algorithm is shown to be O(n log n), which is comparable to that of n-point fast Fourier transform (FFT). A novelty in the asymptotic analysis is that it accommodates closely spaced frequencies by allowing not only the filter bandwidth but also the frequency separation to be functions of the sample size n. This enables an assessment of the accuracy of the frequency estimates for given bandwidths and initial values in situations where some or all of the frequencies are close to each other.