Prony's method

Summary

Prony's method recovers a sum of exponentials $f(k) = \sum_{j=1}^{n} c_j z_j^k$ from equally spaced samples. It uses the fact that such samples satisfy a linear recurrence whose characteristic polynomial has the roots $z_j$. One solves a Hankel linear system for the recurrence, finds the roots, and then solves a linear system for the amplitudes $c_j$. The method underlies many techniques of signal processing and spectral estimation. It is close to rational approximation, since the generating function $\sum_k f(k) w^k$ of such samples is rational.