1ME 233 Advanced Control II
Lecture 21
Parameter Convergence inLeast Squares Estimation
andPersistence of Excitation

2

Estimation of ARMA model

Where•

known bounded input•

measured output

3

Estimation of ARMA model

Where(anti-Schur)• Orders n and m are known• Relative degree d is known• a’s and b’s are unknown but constant coefficients

4

ARMA ModelUnknown
parameter vector:

Known regressor vector:

nn+m+1m+ 1

5

ARMA series-parallel estimation• A-priori output• A-priori error

6

ARMA series-parallel estimation• A-priori error• Parameter error

7

RLS Estimation Algorithm

8Overview• In Lecture 20 we learned how to analyze thestability of adaptive systems and proved:– Convergence of the output error• Today we will provide conditions on the input
sequencethat guarantee that

also converges to zero.

9Parameter error convergence• Remember that

It can be shown that the n+m+1 parameter error
also converges:

nm+ 1

10Parameter error convergence
The steady-state parameter error satisfies

Regressornm+ 1

11Parameter error convergenceThe steady-state parameter error satisfies

Where the regressor correlation
is:

12

Parameter error convergence
Since the steady-state parameter error satisfies

The regressor vector

is persistently exciting if

13Persistence of Excitation
u(k)

y(k)

-d

¡ -11)q¡ q1 BB((qq)
A(q¡q1-1)
A( )nregressor
Parameter
Adaptation
Algorithme(k) +-^y(k)We need to find the conditions that the input
sequence u(k) must satisfy to guarantee
thatis persistently exciting.

m+ 114

Excitation matrix
Given an input sequence

Define the u-regressor of order n:

only present and pastvalues of u(k) are used

15

Excitation matrix
Given an input sequence

Define the n x n excitation matrix:

Time average of16

Persistence of Excitation (PE)The input sequence u(k)is persistently exciting of order n if
the n x n excitation matrix is positive definite

17

PE inputs in FIR models
Theorem:is persistently exciting (PE) of order n iff

the following holds for all nonzero polynomialsof order at most n-1

wherew(k) is PE of order 1

18

PE inputs in FIR models
Alternate statement of Theorem:
The following are equivalent:• u(k) is PE of order n• A(q -1)u(k) is PE of order 1 for all nonzero
polynomials A(q -1) of degree at most n-1

19

PE inputs in FIR models
Proof: LetThen

20

PE inputs in FIR models
Proof (cont’d):21

PE inputs in FIR models
Proof (cont’d):Since U = aTCna, we see that U > 0,
if and only if.

Therefore, U > 0 for all nonzero
polynomials A(q -1) of order at most n-1
if and only if

22

PE inputs in FIR models
To determine the PE order of a sequence
1. Find a nonzero polynomialof order nsuch that A(q -1)u(k) is not PE of order 1
this means thatis PE of order at most n

2. Compute the excitation matrix
that it is positive definite.

and verify

23

Conditions for PE
Examples: Constant input
u(k) is not PE oforder 2u(k) is PE oforder 1

24

Conditions for PE in FIR Models
Examples: Sinusoid input

u(k) is not PE oforder 3

25

Conditions for PE in FIR Models
Examples: Sinusoid input

26

Conditions for PE in FIR ModelsExamples: Sinusoid inputu(k) is not PEof order 3u(k) is PE oforder 2

27

Conditions for PE in FIR Models
Examples: Sum of Sinusoids

28

Conditions for PE in FIR Models
Examples: Random process

29

PE in Filtered Signals
Filtered signals:Let•• v(k) be the output of the model• A(q -1) is a nonzero polynomial of degree m < n30

PE in Filtered Signals
Filtered signals:
••

•

Let

31

PE in Filtered Signals
Theorem

Let v(k) be the output of the model

where A(q -1) is a nonzero polynomial
1. If u(k) is not PE of order n, then v(k) is not PE oforder n

2. If u(k) is PE of order n and A(q -1) has degree m < n,then v(k) is PE of order n-m
3. If A(q -1) is anti-Schur, then u(k) is PE of order n ifand only if v(k) is PE of order n32Interpretation of Theorem
1.
Not PE oforder n

Not PE oforder n

PE oforder n

PE oforder n-m

2.

order m<n33Interpretation of Theorem
3. When A(q -1) anti-Schur(this is redundantwith part 1 of thetheorem)

Not PE oforder nNot PE oforder n

Not PE oforder n

Not PE oforder n34

PE in Filtered Signals
Preliminary result 1:
If u(k) is not PE of order 1, then v(k) is not PE of order 1

Proof:
Let

35

PE in Filtered Signals
Proof of preliminary result 1 (continued):

Since u(k) is not PE of order 1, C1 = 0
The diagonal elements of Cn are zeroSince

, this implies that Cn = 0

U = 0, which implies that v(k) is not PE of order 1

36

PE in Filtered Signals
Preliminary result 2:
If A(q -1) is anti-Schur and v(k) is not PE of order 1,
thenis not PE of order 1

The proof is based on frequency domain techniques fordeterministic signals that are analogous to power spectral
density techniques for wide sense stationary random signals(see the additional material at the end of this lecture)

37

PE in Filtered Signals
Proof of (1):Let u(k) not be PE of order nChoose nonzero B(q -1) of degree at most n-1 suchthat w(k) = B(q -1) u(k) is not PE of order 1

By the preliminary result, A(q -1) w(k) is not PEof order 1, which implies that B(q -1) v(k) is not
PE of order 1v(k) is not PE of order n38

PE in Filtered Signals
Proof of (2):Let u(k) be PE of order n and A(q -1) have degree m < nSuppose B(q -1)v(k) is not PE of order 1 whereB(q -1) has order at most n-m-1
B(q -1)A(q -1)u(k) is not PE of order 1
Since B(q -1)A(q -1) has order at most n-1 and u(k) is
PE of order n, B(q -1)A(q -1) is the zero polynomial
Since A(q -1) is a nonzero polynomial,B(q -1) is the zero polynomialv(k) is PE of order n-m

39

PE in Filtered Signals
Proof of (3):By statement (1) of the theorem, if u(k) is not PE oforder n, then v(k) is not PE of order n
It only remains to show that if v(k) is not PE of order n,then u(k) is not PE of order n
Let v(k) not be PE of order n and choose nonzeroB(q -1) of order at most n-1 such that w(k)= B(q -1)v(k) isnot PE of order 1This implies that A(q -1)B(q -1)u(k) is not PE of order 1

40PE in Filtered Signals
Proof of (3), continued:A(q -1)B(q -1)u(k) is not PE of order 1
Since A(q -1) is anti-Schur, we use preliminary result 2
to see that B(q -1)u(k) is not PE of order 1
Since B(q -1) is a nonzero polynomialof order at most n-1u(k) is not PE of order n41

ARMA Model (review)

Where(anti-Schur)• Orders n and m are known• Relative degree d is known• a’s and b’s are unknown but constant coefficients

42

ARMA Model (review)

Unknownparameter vector:

Known regressor vector:

nn+m+1m+ 1

43

PE in ARMA models
Theorem:•••Parameter estimates convergence to the true values

44

PE in ARMA models - Proof
Simplifying assumption: the parameter error converges

Define: the LS output estimation error byWe know that45

PE in ARMA models - Proof
Notice that,Therefore, if we can show that Cn+m+1
conclude that0, we will be able to46

PE in ARMA models - Proof
Notice that

where

47

PE in ARMA models - Proof
FromWe obtain

48

PE in ARMA models - Proof

Polynomial of order n+mNotice that sinceand49

PE in ARMA models - Proof

Polynomial of order n+m••Since e(k) = 0, it cannot be PE of order 1
Therefore,

50

PE in ARMA models - Proof
So far, we know that ifthenwhere51

PE in ARMA models - Proof

This equation can be written as follows:

whereand:52

PE in ARMA models - Proof

53

PE in ARMA models - Proof

Therefore, when
Parameter estimates convergence to the true values

54

Example• Plant:• We need u(k) to be a PE sequence of order 4
to guarantee parameter convergence

55

Example: Input Random Noiseu(k) : zero mean uniform white noise between [-1,1]

parameter convergence2110.500-10500

1000-0.50500

1000

500

1000

apriori error, series parallel predictor
0.1

0.2

0.2

0.1

00.05

0-0.05-0.1-0.15
0a-priori error
200

400
600
input:random

800

1000

00500

1000

-0.2056

Example: Step Input
u(k) = 2*1(t)NO parameter convergence
21
0.5

1
000

apriori error, series parallel predictor
0.3

500

1000

-0.50500

1000

500

1000

0.2

0.1

0.2

0.05

00.1
0-0.1
-0.2

a-priori error-0.3-0.4
0200

400
600
input:random

800

1000

00500

1000

-0.2
057

Example: Sinusoidal input – 1 frequency
u(k) = 2*sin(t)NO parameter convergence
2

1
0.5

1
0
00

apriori error, series parallel predictor

500

1000

-0.5
0500

1000

500

1000

0.25

0.2

0.1

0.2

0.05

00.15

0.1

0.05

0-0.05a-priori error

-0.1

-0.15

-0.2

-0.25
0100

200

300

400

500

600

input:random

700

800

900

1000

00500

1000

-0.2058

Example: Sinusoidal input – 2 frequencies
u(k) = 2*sin(t)+2cos(2*t)

parameter convergence
210.5

1
000

apriori error, series parallel predictor
0.3
0.2

500

1000

-0.5
00.2

0.2

0.1

0500

1000

500

1000

0.1
0-0.1
-0.2

a-priori error

-0.3
-0.4
0200

400
600
input:random

800

1000

00500

1000

-0.2
0

Additional Material(you are not responsible for this)• Proof of preliminary result 259

60

PE in Filtered Signals
Preliminary result 2:If A(q -1) is anti-Schur and v(k) is not PE of order 1,thenis not PE of order 1

The proof is based on frequency domain techniques fordeterministic signals that are analogous to power spectral
density techniques for wide sense stationary random signals

61

Stochastic and Deterministic Signals
WSS zero-mean random
signals, X(k) and Y(k)Deterministic signals, x(k) and y(k)Average value of x(k+j)yT(k) over k

62

Stochastic and Deterministic Signals
where G(z) is stable
WSS zero-mean random
signals, U(k) and Y(k)Scalar U(k)and Y(k)Deterministic signals,u(k) and y(k)Scalar u(k)and y(k)63

Proof of Preliminary Result 2Let• A(q -1) be anti-Schur• v(k) not be PE of order 1• u(k) be generated bystable

Choose M such that

64

Proof of Preliminary Result 2

Therefore, we have

65

Proof of Preliminary Result 2v(k) not PE of order 1u(k) not PE of order 1

66

PE inputs
To determine the PE order of a sequence
1. Find an annihilating polynomial
order n such

this means thatofis at most PE of order n

2. Compute the excitation matrix

and verify that it is positive definite.

67

Persistence of excitation forARMA model identification
u(k)

y(k)

q-d B(q-1)-1A( q )nregressor
Parameter
Adaptation
Algorithme(k) +-^y(k)We need to find what conditions must the input
sequence u(k) satisfy so thatispersistently exciting.

m+ 1

68

PE in ARMA models
Given:

nm+ 1• u(k) is bounded•is Schur•andare co-prime

69

Derivation of Results
1. Determine conditions on the input sequence•For the parameter convergence of a Moving
Average (MA) model•

For the parameter convergence of an ARMAmodel

70

Statistical Interpretation of LS Estimation
Stochastic ModelWhere•

observed output•

zero-mean noise•

regressor•

unknown parameter vector

71

Statistical Interpretation of LS Estimation
Assumptions:•zero-mean•

Independence or orthogonality:•Ergodicity

72

Statistical Interpretation of LS Estimation
Collect data for k observations:

73

LS Statistical Interpretation
Collect data for k observations:

Where••••

74

LS Statistical Interpretation

75

Deterministic Least Squares Estimation
Parameter estimate after k observations:

Which minimizes the following cost functional:

Notice thatis kept constant in the summation

76

Deterministic Least Squares Estimation: Parameter estimate which minimizes

Is given by the Normal Equation:

77

LS Statistical Interpretation
Normal equation:

Stochastic model:

Parameter error vector:

78

LS Statistical Interpretation
Substitute the stochastic model

Into the normal equation:

To obtain:

79

LS Statistical Interpretation

Notice that

Therefore,

80

LS Statistical Interpretation
Assume now that the parameter error converges :Multiply by 1/k and take limits as

81

LS Statistical Interpretation

By Ergodicity,

82

LS Statistical InterpretationIfandSince,

are independent or orthogonal,

83

LS Statistical Interpretation
The parameter error vector satisfies:

Thus, a sufficient condition foris that(positive definite)

84

LS Statistical Interpretation
We now define the Excitation matrix

85

LS Statistical Interpretation
Theorem:
Under the conditions:••
If the excitation matrix

is positive definite,

the parameter error vector of the least square algorithm
converges to zero.

86

Persistence of Excitation (PE)Persistently exciting regressor:
There exist finite constants:••
For all k

87Persistence of Excitation (PE)Persistently exciting regressor:

for all kand a fixed m

88

PE in Moving Average (MA) models
Finite Impulse Response (FIR) model:

where

89

Conditions for PE in FIR Models
Persistently exciting input sequence:

Is persistently exciting (PE) of order nif the regressor vector

is persistently exciting

90

Conditions for PE in FIR Models
For a persistently exciting input sequencewith regressor

The excitation matrix Cn is a Positive Definite Toeplitz
matrix