Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » Statistical Signal Processing » Linear Models

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Linear Models

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

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σ2⁢I w 0 σ 2 I .

Example 1

x n =A+ B n + w n   ,   n∈1…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=( 11 12 ⋮⋮ 1N ) H 1 1 1 2 ⋮ ⋮ 1 N

Probability Model for LM

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

CRLB and NVUB Estimator

θ ^=g⁢x θ g x the MVUB estimator iff ∂logpx| θ ∂ θ =I⁢θ⁢(g⁢x−θ) θ p θ x I θ g x θ In the case of the LM, ∂logpx| θ ∂ θ =(−12⁢σ2)⁢∂(xT⁢x−2⁢xT⁢H⁢θ+θT⁢HT⁢H⁢θ)∂ θ θ p θ x 1 2 σ 2 θ x x 2 x H θ θ H H θ Now using identities ∂(bT⁢θ)∂ θ =b θ b θ b ∂(θT⁢A⁢θ)∂ θ =2⁢A⁢θ θ θ A θ 2 A θ for AA symmetric.

We have ∂logpx| θ ∂ θ =1σ2⁢(HT⁢x−HT⁢H⁢θ) θ p θ x 1 σ 2 H x H H θ Assuming HT⁢H H H is invertible ∂logpx| θ ∂ θ =HT⁢Hσ2⁢(HT⁢H-1⁢HT⁢x−θ) θ p θ x H H σ 2 H H H x θ which leads to

MVUB Estimator

θ ^=HT⁢H-1⁢HT⁢x θ H H H x
(1)

Fisher Information Matrix

I⁢θ=HT⁢Hσ2 I θ H H σ 2
(2)
〈 θ ^ 2 〉= C θ =I⁢θ-1=σ2⁢HT⁢H-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σ2⁢I w 0 σ 2 I and HH is invertible. Then, the MVUB estimator is θ ^=HT⁢H-1⁢HT⁢x θ H H H x and the covariance of θ ^ θ is C θ =σ2⁢HT⁢H-1 C θ σ 2 H H and θ ^ θ attains the CRLB.

note:

θ ^∼𝒩θσ2⁢HT⁢H-1 θ θ σ 2 H H

Linear Model Examples

Example 2: Curve Fitting

Figure 1
Figure 1 ()

Model: x⁢ t n = θ 1 + θ 2 ⁢ t n +…+ θ p ⁢ t n p−1+w⁢ t n   ,   n∈1…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=x⁢t⋮x⁢ t n x x t ⋮ x t n θ= θ 1 θ 2 ⋮ θ p θ θ 1 θ 2 ⋮ θ p H=( 1 t 1 … t 1 p−1 1 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 θ ^=HT⁢H-1⁢HT⁢x θ H H H x

Example 3: System Identification

Figure 2
Figure 2 ()

H⁢z=∑ k =0m−1h⁢k⁢z−k H z k 0 m 1 h k z k x⁢n=∑ k =0m−1h⁢k⁢u⁢n−k+w⁢n  ,   n∈0…N−1    n n 0 … N 1 x n k 0 m 1 h k u n k w n Where w⁢n∼𝒩0σ2 w n 0 σ 2 idd. Given xx and uu, estimate hh.

In matrix form x=( u⁢00…0 u⁢1u⁢0…0 ⋮⋮⋱⋮ u⁢N−1u⁢N−2…u⁢N−m )⁢h⁢0⋮⋮h⁢N−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 ( u⁢00…0 u⁢1u⁢0…0 ⋮⋮⋱⋮ u⁢N−1u⁢N−2…u⁢N−m )=H u 0 0 … 0 u 1 u 0 … 0 ⋮ ⋮ ⋱ ⋮ u N 1 u N 2 … u N m H and h⁢0⋮⋮h⁢N−m=θ h 0 ⋮ ⋮ h N m θ

MVUB estimator

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

First note that σ(θ^i)2= e i T⁢ C θ ^ ⁢ e i θ i e i C θ ^ e i where e i =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=DT⁢D C θ ^ D D where DD is invertible.1 Note that

e i T⁢DT⁢DT-1⁢ e i 2=1 e i D D e i 2 1
(4)
The Schwarz inequality shows that Equation 4 can become
1≤( e i T⁢DT⁢D⁢ e i )⁢( e i T⁢D-1⁢DT-1⁢ e i ) 1 e i D D e i e i D D e i
(5)
1=( e i T⁢ C θ ^ -1⁢ e i )⁢( e i T⁢ C θ ^ ⁢ e i ) 1 e i C θ ^ e i e i C θ ^ e i which leads to σ(θ^i)2≥1 e i T⁢ C θ ^ -1⁢ e i =σ2(HT⁢H)i,i θ 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 =D⁢ e i η 1 D e i is proportional to η 2 =DT⁢ e i η 2 D e i . That is, η 1 =C⁢ η 2 η 1 C η 2 for some constant CC. Equivalently, DT⁢D⁢ e i = c i ⁢ e u   ,   i∈12…m    i i 1 2 … m D D e i c i e u DT⁢D= C θ ^ -1=HT⁢Hσ2 D D C θ ^ H H σ 2 which leads to HT⁢Hσ2⁢ e i = c i ⁢ e i H H σ 2 e i c i e i Combining these equations in matrix form HT⁢H=σ2⁢( c 1 0…0 0 c 2 …0 00… 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, u⁢n u n should be chosen to make HT⁢H H H diagonal.

(HT⁢H)i,j=∑ n =1Nu⁢n−i⁢u⁢n−j  ,   i∧j∈1…m    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 (HT⁢H)i,j≃∑ n =0N−1−|i−j|u⁢n⁢u⁢n+|i−j| H H i j n 0 N 1 i j u n u n i j using the autocorrelation of seq. u⁢n u n .

note:

u⁢n=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 HT⁢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 ) 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−ku⁢n⁢u⁢n+k r uu n 1 N n 0 N 1 k u n u n k For HT⁢H H H to be diagonal, we require r⁢k=0 r k 0 , k≠0 k 0 . This condition is approximately realized if we take u⁢n u n to be a pseudorandom noise sequence (PRN)2. Furthermore, the PRN sequence simplifies the estimator computation: θ ^=HT⁢H-1⁢HT⁢x θ H H H x θ ^≃IN⁢ r uu ⁢0⁢HT⁢x θ I N r uu 0 H x which leads to h⁢i ^≃1N⁢ r uu ⁢0⁢∑ n =0N−1−iu⁢n−i⁢x⁢n h i 1 N r uu 0 n 0 N 1 i u n i x n where ∑ n =0N−1−iu⁢n−i⁢x⁢n=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 h⁢i ^= r ux ⁢i r uu ⁢0  ,   i∈01…m−1    i i 0 1 … m 1 h i r ux i r uu 0 r ux ⁢i=1N⁢∑ n =0N−1−iu⁢n⁢x⁢n+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

x n = s n ⁢θ+ w n   ,   n∈1…N    n n 1 … N x n s n θ w n px| θ =12⁢π⁢σ2N2⁢e−(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 θ ∂2logpx| θ ∂ θ 2 2 =1σ2⁢∑ n =1N(( x n − s n ⁢θ)⁢∂2 s n ⁢θ∂ θ 2 2 −∂ s n ⁢θ∂ θ 2) θ 2 p θ x 1 σ 2 n 1 N x n s n θ θ 2 s n θ θ s n θ 2 E∂2logpx| θ ∂ θ 2 2 =−(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

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection 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

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