Prony's Method 1.1 2005/02/21 02:09:38 US/Central 2005/04/24 16:13:37 GMT-5 Douglas L. Jones dl-jones@uiuc.edu Douglas L. Jones dl-jones@uiuc.edu Jeffrey Silverman jsilv@rice.edu Kyle Clarkson kclarks@rice.edu Prony's Method is a quasi-least-squares time-domain IIR filter design method. First, assume H z is an "all-pole" system: H z b 0 1 k 1 M a k z k and h n k 1 M a k h n k b 0 δ n where h n 0 , n 0 for a causal system. For h 0 , h 0 b 0 . 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 . A true least-squares solution would attempt to minimize ε 2 n 0 h d n h n 2 where H z takes the form in . 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 response error. Notice that for n 0 , with the all-pole filter hn k 1 M a k h n k the right hand side of this equation is a linear predictor of h n in terms of the M previous samples of h n . For the desired reponse h d n , one can choose the recursive filter coefficients a k to minimize the squared prediction error ε 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 . In matrix form, that's 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 The optimal solution is a lp H d H d -1 H d h d Now suppose H z is an M th -order IIR (ARMA) system, H z k 0 M b k z k 1 k 1 M a k z k or h n k 1 M a k h n k k 0 M b k δ n k k 1 M a k h n k b n 0 n M k 1 M a k h n k n M For 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 or H d a h d and a opt H d H d -1 H d h d Having determined the a 's, we can use them in to obtain the b n 's: b n k 1 M a k h d n k where h d n k 0 for n k 0 . For N 2 M , 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 2 M , the first 2 M 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 2 M , h d n h n for 0 n M , the prediction error is minimized for M 1 n N , and whatever for 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 to h d M .

Shank's Method Assume an all-pole model and fit h d n by minimizing the prediction error 1 n 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 h d n optimally in a least-squares sense ().

Here, h n h d n .

The final IIR filter is the cascade of the all-pole and all-zero filter. This is is solved by b k n 0 N h d n k 0 M b k v n k 2 or in matrix form v 0 0 0 ... 0 v 1 v 0 0 ... 0 v 2 v 1 v 0 ... 0 ⋮ ⋮ ⋮ ⋱ ⋮ v N v N 1 v N 2 ... v N M b 0 b 1 b 2 ⋮ b M h d 0 h d 1 h d 2 ⋮ h d N Which has solution: b opt V V -1 V h Notice that none of these methods solve the true least-squares problem: a b 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: α β 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 to solve for the α i and β i .