A Modified Prony Algorithm for Fitting Functions Defined by Difference Equations
Michael Robert Osborne, Gordon K. Smyth · SIAM Journal on Scientific and Statistical Computing · 1991
This paper reformulates, generalizes, and investigates the stability of the modified Prony algorithm introduced by Osborne [SIAM J. Numer. Anal. 12 (1975), pp. 571–592], with special reference to rational and exponential fitting. The algorithm, originally for exponential functions, is generalized to the least squares fitting of any function which satisfies a linear homogeneous difference equation. Using the difference equation formulation, the problem is expressed as a separable regression, and hence as a nonlinear eigenproblem in terms of the coefficients of the difference equation. The eigenproblem involves finding the null space of a matrix of data differences B, and is solved using a variant of inverse iteration. Stability of the algorithm is shown to depend on the fact that B closely approximates the Hessian of the sum of squares. The expectations of B and the Hessian are evaluated. In the case of rational fitting, the relative difference between B and the Hessian is shown to converge to zero almost surely. Some details of the implementation of the algorithm are given. A simulation study compares the modified Prony algorithm with the Levenberg algorithm on a rational fitting problem, and supports the theoretical results.