Prony's method

Remarks

The coefficients of $P(z) = \prod_j (z - z_j)$ satisfy step 1, since $f$ obeys the linear recurrence with characteristic polynomial $P$. The matrix $H = (f(k + m))_{k, m = 0}^{n-1}$ of step 1 is a Hankel matrix. It factors as $H = V^T C V$ with the Vandermonde matrix $V = (z_j^m)$ and $C = \operatorname{diag}(c_j)$. So $H$ is invertible under the hypotheses, and step 1 has a unique solution. Example: samples $2, 3, 5, 9$ with $n = 2$ give $2 a_0 + 3 a_1 = -5$ and $3 a_0 + 5 a_1 = -9$, so $a_0 = 2$, $a_1 = -3$, $P(z) = (z - 1)(z - 2)$, and then $c_1 = c_2 = 1$: $f(k) = 1 + 2^k$. Non-example: $f(k) = k$ is not such a sum with $n = 1$; the step 1 equation $a_0 f(0) = -f(1)$ reads $0 = -1$ and has no solution. With noisy data or more samples, one solves steps 1 and 3 in the least squares sense. The method is then sensitive to noise, and variants such as the matrix pencil method improve it.