Skip to content Skip to navigation

Connexions

You are here: Home » Content » Linear Models

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Linear Models

Module by: Clayton Scott, Robert Nowak. E-mail the authors

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

Finding an MVUB estimator is a very difficult task, in general. However, a large number of signal processing problems can be respresented by a linear model of the data.

Importance of Class of Linear Models

  1. MVUB estimator within this class is immediately evident
  2. Statistical performance analysis of linear models is very straightforward

General Form of Linear Model (LM)

x=Hθ+w x H θ w where xx is the observation vector, HH is the known matrix (observation or system matrix), θθ is the unknown parameter vector, and ww is the vector of White Guassian noise w∼0σ2I w 0 σ 2 I .

Example 1

∀n,n∈1…N: x n =A+ B n + w n n n 1 … N x n A B n w n x= x 1 ⋮ x N x x 1 ⋮ x N w= w 1 ⋮ w N w w 1 ⋮ w N θ=AB θ A B H=1112⋮⋮1N H 1 1 1 2 ⋮ ⋮ 1 N

Probability Model for LM

x=Hθ+w x H θ w x∼px|θ=Hθσ2I x p θ x H θ σ 2 I

CRLB and NVUB Estimator

θ ̂=gx θ g x the MVUB estimator iff ∂∂θlogpx|θ=Iθgx−θ θ p θ x I θ g x θ In the case of the LM, ∂∂θlogpx|θ=-12σ2∂∂θxTx−2xTHθ+θTHTHθ θ p θ x 1 2 σ 2 θ x x 2 x H θ θ H H θ Now using identities ∂∂θbTθ=b θ b θ b ∂∂θθTAθ=2Aθ θ θ A θ 2 A θ for AA symmetric.

We have ∂∂θlogpx|θ=1σ2HTx−HTHθ θ p θ x 1 σ 2 H x H H θ Assuming HTH H H is invertible ∂∂θlogpx|θ=HTHσ2HTH-1HTx−θ θ p θ x H H σ 2 H H H x θ which leads to

MVUB Estimator

θ ̂=HTH-1HTx θ H H H x (1)

Fisher Information Matrix

Iθ=HTHσ2 I θ H H σ 2 (2)
〈 θ ̂2〉= C θ =Iθ-1=σ2HTH-1 2 θ C θ I θ σ 2 H H

Theorem 1: MVUB Estimator for the LM

If the observed data can be modeled as x=Hθ+w x H θ w where w∼0σ2I w 0 σ 2 I and HH is invertible. Then, the MVUB estimator is θ ̂=HTH-1HTx θ H H H x and the covariance of θ ̂ θ is C θ =σ2HTH-1 C θ σ 2 H H and θ ̂ θ attains the CRLB.

note:

θ ̂∼θσ2HTH-1 θ θ σ 2 H H

Linear Model Examples

Example 2: Curve Fitting

Figure 1
Figure 1 ()

Model: ∀n,n∈1…N:x t n = θ 1 + θ 2 t n +…+ θ p t n p−1+w t n n n 1 … N x t n θ 1 θ 2 t n … θ p t n p 1 w t n where θ 1 + θ 2 t n +…+ θ p t n p−1 θ 1 θ 2 t n … θ p t n p 1 is a p - 1 st p - 1 st -order polynomial and w t n ∼0σ2 w t n 0 σ 2 idd. Therefore, x=Hθ+w x H θ w x=xt⋮x t n x x t ⋮ x t n θ= θ 1 θ 2 ⋮ θ p θ θ 1 θ 2 ⋮ θ p H=1 t 1 … t 1 p−11 t 2 … t 2 p−1⋮⋮⋱⋮1 t N … t N p−1 H 1 t 1 … t 1 p 1 1 t 2 … t 2 p 1 ⋮ ⋮ ⋱ ⋮ 1 t N … t N p 1 where HH is the Vandermonde matrix. The MVUB estimator for θθ is θ ̂=HTH-1HTx θ H H H x

Example 3: System Identification

Figure 2
Figure 2 ()

Hz=∑k=0m−1hkz-k H z k 0 m 1 h k z k ∀n,n∈0…N−1:xn=∑k=0m−1hkun−k+wn n n 0 … N 1 x n k 0 m 1 h k u n k w n Where wn∼0σ2 w n 0 σ 2 idd. Given xx and uu, estimate hh.

In matrix form x=u00…0u1u0…0⋮⋮⋱⋮uN−1uN−2…uN−mh0⋮⋮hN−m+w x u 0 0 … 0 u 1 u 0 … 0 ⋮ ⋮ ⋱ ⋮ u N 1 u N 2 … u N m h 0 ⋮ ⋮ h N m w where u00…0u1u0…0⋮⋮⋱⋮uN−1uN−2…uN−m=H u 0 0 … 0 u 1 u 0 … 0 ⋮ ⋮ ⋱ ⋮ u N 1 u N 2 … u N m H and h0⋮⋮hN−m=θ h 0 ⋮ ⋮ h N m θ

MVUB estimator

θ ̂=HTH-1HTx θ H H H x (3)
〈 θ ̂2〉=σ2HTH-1= C θ ^ 2 θ σ 2 H H C θ ^ An important question in system identification is how to choose the input un u n to "probe" the system most efficiently.

First note that σθ̂i2=eiT C θ ^ ei θ i e i C θ ^ e i where ei=0…010…0T e i 0 … 0 1 0 … 0 . Also, since C θ ^ -1 C θ ^ is symmetric positive definite, we can factor it by C θ ^ -1=DTD C θ ^ D D where DD is invertible.1 Note that

eiTDTDT-1ei2=1 e i D D e i 2 1 (4)
The Schwarz inequality shows that Equation 4 can become
1≤eiTDTDeieiTD-1DT-1ei 1 e i D D e i e i D D e i (5)
1=eiT C θ ^ -1eieiT C θ ^ ei 1 e i C θ ^ e i e i C θ ^ e i which leads to σθ̂i2≥1eiT C θ ^ -1ei=σ2HTHii θ i 1 e i C θ ^ e i σ 2 H H i i The minimum variance is achieved when equality is attained in Equation 5. This happens only if η1=Dei η 1 D e i is proportional to η2=DTei η 2 D e i . That is, η1=Cη2 η 1 C η 2 for some constant CC. Equivalently, ∀i,i∈12…m:DTDei= c i eu i i 1 2 … m D D e i c i e u DTD= C θ ^ -1=HTHσ2 D D C θ ^ H H σ 2 which leads to HTHσ2ei= c i ei H H σ 2 e i c i e i Combining these equations in matrix form HTH=σ2 c 1 0…00 c 2 …000… c m H H σ 2 c 1 0 … 0 0 c 2 … 0 0 0 … c m Therefore, in order to minimize the variance of the MVUB estimator, un u n should be chosen to make HTH H H diagonal.

∀i∧j,i∧j∈1…m:HTHij=∑n=1Nun−iun−j i j i j 1 … m H H i j n 1 N u n i u n j For large NN, this can be approximated to HTHij≈∑n=0N−1−|i−j|unun+|i−j| H H i j n 0 N 1 i j u n u n i j using the autocorrelation of seq. un u n .

note:

un=0 u n 0 for n<0 n 0 and n>N−1 n N 1 , letting limit of sum -∞ , ∞ gives approx.
These steps lead to HTH≈N r uu 0 r uu 1… r uu m−1 r uu 1 r uu 0…⋮⋮⋮⋱⋮ r uu m−1 r uu m−2… r uu 0 H H N r uu 0 r uu 1 … r uu m 1 r uu 1 r uu 0 … ⋮ ⋮ ⋮ ⋱ ⋮ r uu m 1 r uu m 2 … r uu 0 where r uu 0 r uu 1… r uu m−1 r uu 1 r uu 0…⋮⋮⋮⋱⋮ r uu m−1 r uu m−2… r uu 0 r uu 0 r uu 1 … r uu m 1 r uu 1 r uu 0 … ⋮ ⋮ ⋮ ⋱ ⋮ r uu m 1 r uu m 2 … r uu 0 is the Toeplitz autocorrelation matrix and r uu n=1N∑n=0N−1−kunun+k r uu n 1 N n 0 N 1 k u n u n k For HTH H H to be diagonal, we require rk=0 r k 0 , k≠0 k 0 . This condition is approximately realized if we take un u n to be a pseudorandom noise sequence (PRN)2. Furthermore, the PRN sequence simplifies the estimator computation: θ ̂=HTH-1HTx θ H H H x θ ̂≈IN r uu 0HTx θ I N r uu 0 H x which leads to hi ̂≈1N r uu 0∑n=0N−1−iun−ixn h i 1 N r uu 0 n 0 N 1 i u n i x n where ∑n=0N−1−iun−ixn=N r ux i n 0 N 1 i u n i x n N r ux i . r ux i r ux i is the cross-correlation between input and output sequences.

Hence, the approximate MVUB estimator for large N with a PRN input is ∀i,i∈01…m−1: hi ̂= r ux i r uu 0 i i 0 1 … m 1 h i r ux i r uu 0 r ux i=1N∑n=0N−1−iunxn+i r ux i 1 N n 0 N 1 i u n x n i r uu 0=1N∑n=0N−1u2n r uu 0 1 N n 0 N 1 u n 2

CRLB for Signal in White Gaussian Noise

∀n,n∈1…N: x n = s n θ+ w n n n 1 … N x n s n θ w n px|θ=12πσ2N2ⅇ-12σ2∑n=1N x n − s n θ2 p θ x 1 2 σ 2 N 2 1 2 σ 2 n 1 N x n s n θ 2 ∂∂θlogpx|θ=1σ2∑n=1N x n − s n θ∂∂θ s n θ θ p θ x 1 σ 2 n 1 N x n s n θ θ s n θ ∂2∂θ2logpx|θ=1σ2∑n=1N x n − s n θ∂2∂θ2 s n θ−∂∂θ s n θ2 θ 2 p θ x 1 σ 2 n 1 N x n s n θ θ 2 s n θ θ s n θ 2 E∂2∂θ2logpx|θ=-1σ2∑n=1N∂∂θ s n θ2 θ 2 p θ x 1 σ 2 n 1 N θ s n θ 2 σ θ ̂2≥σ2∑n=1N∂∂θ s n θ2 θ σ 2 n 1 N θ s n θ 2

Footnotes

  1. Cholesky factorization
  2. maximal length sequences

Content actions

Give Feedback:

E-mail the module authors | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

My Favorites (?)

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

| A lens (?)

Definition of 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.

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