Spectral line analysis via a fast Prony algorithm

This paper reports a fast new algorithm for a previously developed spectral estimation technique. A modification of the two-step Prony method permits least-squares estimation of the parameters of a set of pure sinusoids: amplitude, frequency, phase. An algorithm is presented that permits a very efficient computation for the first step least-squares estimate of the frequencies and number of sinusoids, M. The normal least squares algorithm requires O(M³) operations if done with conventional methods of solution; the fast algorithm solves the same least squares equations with a total of O(M²) operations, providing all lower order solutions from m=1 to M as a side benefit (useful for recursively fitting an increasing number of sinusoids to a data set).