Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Prony's Method

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Prony's Method

Module by: Douglas L. Jones. E-mail the author

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

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

Hz= b 0 1+ k =1M a k zk H z b 0 1 k 1 M a k z k
(1)
and hn= k =1M a k hnk+ b 0 δn h n k 1 M a k h n k b 0 δ n where hn=0 h n 0 , n<0 n 0 for a causal system.

Note:

For h=0 h 0 , h0= b 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 h d n .

A true least-squares solution would attempt to minimize ε2= n =0| h d nhn|2 ε 2 n 0 h d n h n 2 where Hz 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 |desiredactual|2 desired actual 2 response error.

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

hn= k =1M a k hnk hn k 1 M a k h n k
(2)
the right hand side of this equation is a linear predictor of hn h n in terms of the M M previous samples of hn 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 nk|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 N1 h d N2... h d NM ) 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 Hz H z is an M th M th -order IIR (ARMA) system, Hz= k =0M b k zk1+ k =1M a k zk H z k 0 M b k z k 1 k 1 M a k z k or

hn= k =1M a k hnk+ k =0M b k δnk={ k =1M a k hnk+ b n   if  0nM k =1M a k hnk  if  n>M 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
(3)
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 M1... h d 1 h d M+1 h d M... h d 2 h d N1 h d N2... h d NM ) 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^dah^d H d a h d and a opt =H^dH H d -1 H d Hh^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 nk b n k 1 M a k h d n k where h d nk=0 h d n k 0 for nk<0 n k 0 .

For N=2M 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 hn h n . Thus for N=2M N 2 M , the first 2M+1 2 M 1 points of hn 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>2M N 2 M , h d n=hn h d n h n for 0nM 0 n M , the prediction error is minimized for M+1<nN M 1 n N , and whatever for nN+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 .

Shank's Method

  1. Assume an all-pole model and fit h d n h d n by minimizing the prediction error 1nN 1 n N .
  2. Compute vn v n , the impulse response of this all-pole filter.
  3. Design an all-zero (MA, FIR) filter which fits vn* h z n h d n v n h z n h d n optimally in a least-squares sense (Figure 1).
Figure 1: Here, hn h d n h n h d n .
Figure 1 (fig1.png)

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

This is is solved by min b k b k n =0N| h d n k =0M b k vnk|2 b k n 0 N h d n k 0 M b k v n k 2 or in matrix form ( v000...0 v1v00...0 v2v1v0...0 vNvN1vN2...vNM ) b 0 b 1 b 2 b M h d 0 h d 1 h d 2 h d N 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 =VHV-1VHh b opt V V -1 V h

Notice that none of these methods solve the true least-squares problem: min a , b a , b n =0| h d nhn|2 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: min α , β α , β n =0| h d n i =1M α i e β i n|2 α β 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 α i and β i β i .

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks