Connexions

You are here: Home » Content » Linear Prediction
Content Actions
Lenses

What is a lens?

Lenses

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

What is in a lens?

Lens makers point to Connexions 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 Connexions member, a community, or a respected organization.

This content is ...
Affiliated with (?)
This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.

  • This module is included inLens: Rice University OpenCourseWare
    By: OpenCourseWare ConsortiumAs a part of collection:"Digital Filter Design"

    Click the "Rice University OCW" link to see all content affiliated with them.

    Rice University OCW
Tags

(?)

These tags come from the endorsement, affiliation, and other lenses that include this content.

Linear Prediction

Module by: Douglas L. Jones

Recall that for the all-pole design problem, we had the overdetermined set of linear equations: 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 with solution a= H d H H d -1 H d Hhd a H d H d -1 H d h d
Let's look more closely at H d H H d =R H d H d R . r i ​ j r i ​ j is related to the correlation of h d h d with itself: r i ​ j =∑k=0N-max{ij} h d k h d k+|i-j| r i ​ j k 0 N i j h d k h d k i j Note also that: H d Hhd= r d 1 r d 2 r d 3⋮ r d M H d h d r d 1 r d 2 r d 3 ⋮ r d M where r d i=∑n=0N-i h d n h d n+i r d i n 0 N i h d n h d n i so this takes the form aopt=-RHrd a opt R r d , or Ra=-r R a r , where R R is M×M M M , a a is M×1 M 1 , and r r is also M×1 M 1 .
Except for the changing endpoints of the sum, r i ​ j ≈ri-j=rj-i r i ​ j r i j r j i . If we tweak the problem slightly to make r i ​ j =ri-j r i ​ j r i j , we get: r0r1r2...rM-1r1r0r1...⋮r2r1r0...⋮⋮⋮⋮⋱⋮rM-1.........r0 a 1 a 2 a 3 ⋮ a M =-r1r2r3⋮rM r 0 r 1 r 2 ... r M 1 r 1 r 0 r 1 ... ⋮ r 2 r 1 r 0 ... ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ r M 1 ... ... ... r 0 a 1 a 2 a 3 ⋮ a M r 1 r 2 r 3 ⋮ r M The matrix R R is Toeplitz (diagonal elements equal), and a a can be solved for with OM2 O M 2 computations using Levinson's recursion.

Statistical Linear Prediction

Used very often for forecasting (e.g. stock market).
Given a time-series yn y n , assumed to be produced by an auto-regressive (AR) (all-pole) system: yn=-∑k=1M a k yn-k+un y n k 1 M a k y n k u n where un u n is a white Gaussian noise sequence which is stationary and has zero mean.
To determine the model parameters a k a k minimizing the variance of the prediction error, we seek
min a k {Eyn+∑k=1M a k yn-k2}=min a k {Ey2n+2∑k=1M a k ynyn-k+∑k=1M a k yn-k∑l=1M a l yn-l}=min a k {Ey2n+2∑k=1M a k Eynyn-k+∑k=1M∑l=1M a k a l Eyn-kyn-l} a k y n k 1 M a k y n k 2 a k y n 2 2 k 1 M a k y n y n k k 1 M a k y n k l 1 M a l y n l a k y n 2 2 k 1 M a k y n y n k k 1 M l 1 M a k a l y n k y n l (1)
Note: The mean of yn y n is zero.
ε2=r0+2r1r2r3...rM a 1 a 2 a 3 ⋮ a M + a 1 a 2 a 3 ... a M r0r1r2...rM-1r1r0r1...⋮r2r1r0...⋮⋮⋮⋮⋱⋮rM-1.........r0 ε 2 r 0 2 r 1 r 2 r 3 ... r M a 1 a 2 a 3 ⋮ a M a 1 a 2 a 3 ... a M r 0 r 1 r 2 ... r M 1 r 1 r 0 r 1 ... ⋮ r 2 r 1 r 0 ... ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ r M 1 ... ... ... r 0 (2)
∂∂aε2=2r+2Ra a ε 2 2 r 2 R a (3)
Setting Equation 3 equal to zero yields: Ra=-r R a r These are called the Yule-Walker equations. In practice, given samples of a sequence yn y n , we estimate rn r n as rn ̂=1N∑k=0N-nynyn+k≈Eykyn+k r n 1 N k 0 N n y n y n k y k y n k which is extremely similar to the deterministic least-squares technique.

Comments, questions, feedback, criticisms?

Send feedback