2.5 Prony's method

Prony's Method is a quasi-least-squares time-domain IIR filter design method.

First, assume $H(z)$ is an "all-pole" system:

A true least-squares solution would attempt to minimize $$\epsilon ^2=\sum_{n=0}$$∞ h d n h n 2 where $H(z)$ takes the form in . This is a difficult non-linearoptimization problem which is known to be plagued by local minima in the error surface. So instead of solving thisdifficult non-linear problem, we solve the deterministic linear prediction problem, which is related to, but not the same as , the true least-squares optimization.

The deterministic linear prediction problem is a linear least-squares optimization, which is easy to solve, but it minimizes the prediction error, not the $\left|\mathrm{desired}-\mathrm{actual}\right|^2$ response error.

Notice that for $n> 0$ , with the all-pole filter

For the desired reponse $h_d(n)$ , one can choose the recursive filter coefficients $a_k$ to minimize the squared prediction error $${\epsilon }_p^2=\sum_{n=1}$$∞ h d n k 1 M a k h d n k 2 where, in practice, the $$∞ is replaced by an $N$ .

In matrix form, that's $$\begin{pmatrix}{h}_d(0) & 0 & \mathrm{...} & 0\\ h_d(1) & h_d(0) & \mathrm{...} & 0\\ & & & \\ h_d(N-1) & h_d(N-2) & \mathrm{...} & h_d(N-M)\\ \end{pmatrix}\left(\begin{array}{c}{a}_1\\ a_2\\ \\ a_M\end{array}\right)\approx -\left(\begin{array}{c}{h}_d(1)\\ h_d(2)\\ \\ h_d(N)\end{array}\right)$$ or $$H_{d}a\approx -h_d$$ The optimal solution is $$a_{\mathrm{lp}}=-(((H_d)H_d)^{-1}(H_d)h_d)$$ Now suppose $H(z)$ is an $M^{\mathrm{th}}$ -order IIR (ARMA) system, $$H(z)=\frac{\sum_{k=0}^M b_{k}z^{-k}}{1+\sum_{k=1}^M a_{k}z^{-k}}$$ or

For $N=2M$ , $(H_d)$ is square, and we can solve exactly for the $a_k$ 's with no error. The $b_k$ 's are also chosen such that there is no error in the first $M+1$ samples of $h(n)$ . Thus for $N=2M$ , the first $2M+1$ points of $h(n)$ exactly equal $h_d(n)$ . This is called Prony's Method . Baron de Prony invented this in 1795.

For $N> 2M$ , $h_d(n)=h(n)$ for $0\le n\le M$ , the prediction error is minimized for $M+1< n\le N$ , and whatever for $n\ge N+1$ . This is called the Extended Prony Method .

One might prefer a method which tries to minimize an overall error with the numerator coefficients, rather than justusing them to exactly fit $h_d(0)$ to $h_d(M)$ .

Shank's method

• Assume an all-pole model and fit $h_d(n)$ by minimizing the prediction error $1\le n\le N$ .
• Compute $v(n)$ , the impulse response of this all-pole filter.
• Design an all-zero (MA, FIR) filter which fits $(v(n), h_z(n))\approx h_d(n)$ optimally in a least-squares sense ( ).

The final IIR filter is the cascade of the all-pole and all-zero filter.

This is is solved by $$\min\{b_k , \sum_{n=0}^N \left|h_d(n)-\sum_{k=0}^M b_{k}v(n-k)\right|^2\}$$ or in matrix form $$\begin{pmatrix}v(0) & 0 & 0 & \mathrm{...} & 0\\ v(1) & v(0) & 0 & \mathrm{...} & 0\\ v(2) & v(1) & v(0) & \mathrm{...} & 0\\ & & & & \\ v(N) & v(N-1) & v(N-2) & \mathrm{...} & v(N-M)\\ \end{pmatrix}\left(\begin{array}{c}{b}_0\\ b_1\\ b_2\\ \\ b_M\end{array}\right)\approx \left(\begin{array}{c}{h}_d(0)\\ h_d(1)\\ h_d(2)\\ \\ h_d(N)\end{array}\right)$$ Which has solution: $$b_{\mathrm{opt}}=((V)V)^{-1}(V)h$$

Notice that none of these methods solve the true least-squares problem: $$\min\{a, , b , \sum_{n=0} \}$$∞ h d n h n 2 which is a difficult non-linear optimization problem. The true least-squares problem can be written as: $$\min\{\alpha , , \beta , \sum_{n=0} \}$$∞ h d n i 1 M α i β i n 2 since the impulse response of an IIR filter is a sum of exponentials, and non-linear optimization is then used tosolve for the ${\alpha }_i$ and ${\beta }_i$ .