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

First, assume H⁢z H z is an "all-pole" system:

and h⁢n=−∑ k =1M a k ⁢h⁢n−k+ b 0 ⁢δ⁢n h n k 1 M a k h n k b 0 δ n where h⁢n=0 h n 0 , n<0 n 0 for a causal system. Let's attempt to fit a desired impulse response (let it be causal, although one can extend this technique when it isn't) h d ⁢n h d n .

A true least-squares solution would attempt to minimize ε2=∑ n =0∞| h d ⁢n−h⁢n|2 ε 2 n 0 h d n h n 2 where H⁢z H z takes the form in Equation 1. This is a difficult non-linear optimization problem which is known to be plagued by local minima in the error surface. So instead of solving this difficult 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 |desired−actual|2 desired actual 2 response error.

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

the right hand side of this equation is a linear predictor of h⁢n h n in terms of the M M previous samples of h⁢n h n .

For the desired reponse h d ⁢n h d n , one can choose the recursive filter coefficients a k a k to minimize the squared prediction error ε p 2=∑ n =1∞| h d ⁢n+∑ k =1M a k ⁢ h d ⁢n−k|2 ε p 2 n 1 h d n k 1 M a k h d n k 2 where, in practice, the ∞ is replaced by an N N.

In matrix form, that's ( h d ⁢00...0 h d ⁢1 h d ⁢0...0 ⋮⋮⋱⋮ h d ⁢N−1 h d ⁢N−2... h d ⁢N−M )⁢ a 1 a 2 ⋮ a M ≃− h d ⁢1 h d ⁢2⋮ h d ⁢N h d 0 0 ... 0 h d 1 h d 0 ... 0 ⋮ ⋮ ⋱ ⋮ h d N 1 h d N 2 ... h d N M a 1 a 2 ⋮ a M h d 1 h d 2 ⋮ h d N or H d ⁢a≃− h d H d a h d The optimal solution is a lp =−( H d H⁢ H d -1⁢ H d H⁢ h d ) a lp H d H d -1 H d h d Now suppose H⁢z H z is an M th M th -order IIR (ARMA) system, H⁢z=∑ k =0M b k ⁢z−k1+∑ k =1M a k ⁢z−k H z k 0 M b k z k 1 k 1 M a k z k or

For n>M n M , this is just like the all-pole case, so we can solve for the best predictor coefficients as before: ( h d ⁢M h d ⁢M−1... h d ⁢1 h d ⁢M+1 h d ⁢M... h d ⁢2 ⋮⋮⋱⋮ h d ⁢N−1 h d ⁢N−2... h d ⁢N−M )⁢ a 1 a 2 ⋮ a M ≃ h d ⁢M+1 h d ⁢M+2⋮ h d ⁢N h d M h d M 1 ... h d 1 h d M 1 h d M ... h d 2 ⋮ ⋮ ⋱ ⋮ h d N 1 h d N 2 ... h d N M a 1 a 2 ⋮ a M h d M 1 h d M 2 ⋮ h d N or H^d⁢a≃h^d H d a h d and a opt =H^dH⁢ H d -1⁢ H d H⁢h^d a opt H d H d -1 H d h d Having determined the a a's, we can use them in Equation 3 to obtain the b n b n 's: b n =∑ k =1M a k ⁢ h d ⁢n−k b n k 1 M a k h d n k where h d ⁢n−k=0 h d n k 0 for n−k<0 n k 0 .

For N=2⁢M N 2 M , H^d H d is square, and we can solve exactly for the a k a k 's with no error. The b k b k 's are also chosen such that there is no error in the first M+1 M 1 samples of h⁢n h n . Thus for N=2⁢M N 2 M , the first 2⁢M+1 2 M 1 points of h⁢n h n exactly equal h d ⁢n h d n . This is called Prony's Method. Baron de Prony invented this in 1795.

For N>2⁢M N 2 M , h d ⁢n=h⁢n h d n h n for 0≤n≤M 0 n M , the prediction error is minimized for M+1<n≤N M 1 n N , and whatever for n≥N+1 n 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 just using them to exactly fit h d ⁢0 h d 0 to h d ⁢M h d M .

Content actions

Footer

This work is licensed by Douglas L. Jones under a Creative Commons Attribution License (CC-BY 2.0), and is an Open Educational Resource.

Last edited by Jeffrey Silverman on Jun 14, 2005 3:22 pm GMT-5.