LIBRARY
Michigan State
University

 

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or boforo duo due.

  

DATE DUE DATE DUE DATE DUE

I L
C_J

 
 

 

 

 

 

 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MSU Is An Affirmative Action/Equal Opportunity institution
cWMI

__ ____.._____--

NUMERICAL STABILITY AND CONVERGENCE
ISSUES IN THE SM-WRLS ALGORITHM

By
' M arwan Mahdi K mm

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements

for the degree of
MASTER OF SCIENCE

Department of Electrical Engineering

1992

_., ’. '.'.

I 5 J JR:

70/

ABSTRACT

NUMERICAL STABILITY AND CONVERGENCE
ISSUES IN THE SM-WRLS ALGORITHM

By

M arwan Mahdi K mm

This research is concerned with a particular class of optimal bounding ellipsoid
(08E) algorithms which implements an optimization criterion based on the volume
of the optimal ellipsoid. The OBE algorithms are set membership identification tech-
niques that use a priori information about the pointwise “energy bounds” on the
error sequence to identify the parameters of linear system or signal models.

In this work, the convergence behavior of the ellipsoid for the class of OBE al-
gorithms that utilizes the volume ratio measure is studied under different types of
disturbances.

The conventional OBE algorithms minimize the volume of the ellipsoid by finding
an optimal error minimization weight associated with the present datum. In this work,
a new OBE algorithm, the set membership past weight optimization (SM-PWO), is
developed. The data selection technique in this algorithm is based on minimizing the
volume with respect to an error minimization weight associated with the whole past
data. Duality between SM-PWO and known SM-WRLS in terms of the estimates
produced and minimal ellipsoid is established. The important advantage of SM-
PWO is that the variables involved in the algorithm are much more numerically
stable. In effect, SM-PWO is more effecient than SM-WRLS when implemented on

small wordlength processors.

To my family

Acknowledgments

I am gratefully indebted to both of my thesis co—advisors, Professor John R.
Deller, Jr., and Professor Majid Nayeri for their continuous support and guidance
throughout the course of this research, and the for invaluable time and effort they
spent in discussing and reviewing my thesis.

I also like to thank Professor Alan G. Haddow, the member of my graduate com-
mittee, for his time and effort to review and discuss my thesis.

I would like to thank my parents for their contiuous love and support.

This work was supported in part by the Office of Naval Research (ONR) under
grant no. N00014-91-J-l329, and in part by the National Science Foundation (NSF)
under grant no. MIP-9016734.

Contents

List of Tables vii
List of Figures viii
1 Introduction and Background 1
1.1 Objectives and significance of this research ............... l
1.2 The OBE Algorithms: Theoretical Background ............. 4
1.2.1 The Least Square Error (LSE) Method . . . . - ......... 4
1.2.2 The OBE Algorithms ....................... 7
1.2.2.1 The SM-WRLS Algorithm .............. 8
2.4.1.2 Suboptimal Test for Innovation in SM-WRLS Algorithm 10
2 Convergence Study of the Ellipsoid 12
2.1 Introduction ................................ 12
2.2 Persistency of Excitation ......................... 13
2.3 Non-Persistently Exciting Colored Noise Case ............. 15
2.3.1 AR(2) Model with DC Input ................... 15
2.3.2 AR(2) Model with Cosine Input ................. 20
2.3.3 AR(3) Model with Cosine Input ................. 21
2.4 The Colored Noise Paradox ....................... 24

3 The Set-Membership Past-Weight Optimization (SM-PWO) Algo-
rithm 30
3.1 Introduction ................................ 30
3.2 Problems Encountered in Conventional OBE Algorithms ....... 31
3.3 WRLS Method with Weighted-Past Measurements ........... 33
3.3.1 Development of the Modified WRLS Recursions ........ 33
3.3.2 Describing a, in Terms of the Modified WRLS Equations . . 37
3.3.3 Establishing the Volume Measure pdfln) ............ 39
3.3.4 Minimization of mumfln) .................... 41
3.3.4.1 Minimization With Respect to An ........... 41
3.3.4.2 Minimization With Respect to 6,, ........... 42
3.4 The SM~PWO Algorithm ......................... 43

3.4.1 Development of the Basic Recursions and the Optimization of 13., 43

3.4.2 Updating Criterion ........................ 45

3.4.3 Imposing an Upper Bound on the Optimal Weight 5,, ..... 47

3.5 Simulation Results ............................ 48
3.5.1 AR(2) Model with White Noise Disturbances ......... 49

3.5.2 AR(2) Model with Colored Noise Disturbances ......... 49

4 Conclusions and Further Work 65
4.1 Conclusions ................................ 65
4.1.1 Convergence Study of the Ellipsoid ............... 65

4.1.2 Development of the SM-PWO Algorithm ............ 66

4.2 Further Work ............................... 67
Appendix A 68
Appendix B 70
Bibliography 74

vi

List of Tables

2.1

2.2

2.3

The estimates, the last data used, and the volume of the ellipse at
n = 7000 for different true parameter values under first order p.e.
disturbances. ............................... 16
The estimates, the last data used, and the volume of the ellipse at
n = 7000 for different true parameter values under second order p.e.

disturbances. ............................... 20
The estimates and eigenvalues of P(n) at n = 7000 for AR(3) model
with cosine input noise. ......................... 24

vii

List of Figures

1.1
2.1
2.2

2.3

2.4

2.5

3.1

3.2

3.3

3.4

3.5

3.6

3.7

SM-WRLS algorithm based on the matrix inversion lemma .......
The SM-WRLS algorithm with AR(2) model disturbed by first order
exciting noise. (a) The optimal weights A; (b) K(Tl) ...........
The set flu after 12 = 7000 for different true parameters for an AR(2)
model with first order p.e. disturbance. In each case, ‘*’ denotes the
true parameters and ‘ x’ denotes the estimate (ellipsoid center). . .

The SM-WRLS algorithm with AR(2) model disturbed by second order
exciting noise. (a) The optimal weights A; (b) K.(n) ...........
The set (2,, after 12 = 7000 for different true parameters for an AR(2)
model with second order p.e. disturbance. In each case, ‘*’ denotes
the true parameters and ‘x’ denotes the estimate (ellipsoid center). .
Illustration of the conservative behavior of the OBE algorithms. . . .
SM-PWO algorithm based on the matrix inversion lemma. ......

The estimates produced by the SM-PWO or the SM-WRLS algorithm

for an AR(2) model with white noise disturbance (i) a,(n) (ii) (“12(n).

The values of some parameters that are used in the SM-PWO algorithm
in the identification of an AR(2) model with white noise disturbances
(i) 6; (ii) 76(12) (iii) C(n). .......................
The values of some parameters that are used in the SM-WRLS algo-
rithm in the identification of an AR(2) model with white noise distur-
bances (i) A; (ii) x.(,n) (iii) C(n) ....................
The estimates of an AR(2) model with white noise disturbances using
the SM-PWO that uses an upper bound [3,, = 5 on the optimal weights
,3; (i) &1(n) (ii) &2(n) ...........................
The values of some parameters that are used by the SM-PWO al-
gorithm that uses an upper bound [3,, = 5 on the optimal weights
in the identification of an AR(2) model with white noise disturbance
(i) 6; (ii) 76(n) (iii) C(n). .......................
The estimates produced by the SM-PWO or the SM-WRLS algorithm
in the identification of an AR(2) model with colored noise disturbance

(i) &1(n) (ii) 52(n). ...........................

viii

10

17

19

53

54

56

57

59

3.8 The values of some parameters that are used by the SM-WRLS al-
gorithm in the identification of an AR(2) model with colored noise
disturbance (i) A; (ii) 5(n) (iii) C(n). ................

3.9 The values of some parameters that are used by the SM-PWO al-
gorithm in the identification of an AR(2) model with colored noise

~

disturbance (i) )6; (ii) E(n) (iii) C(n) ................
3.10 The estimates of an AR(2) model with colored noise disturbances using
the SM-PWO that uses an upper bound 3,, = 5 on the optimal weights
,6; (2) 61(n) (22) 62(n) ...........................
3.11 The values of some parameters that are used by the SM-PWO algo-
rithm that uses an upper bound Bu = 5 on the optimal weights in

the identification of an AR(2) model with colored noise disturbance

(2') 3;; (a) 76(n) (iii) C(n). .......................

ix

6O

61

63

64

Chapter 1

Introduction and Background

 

1.1 Objectives and significance of this research

Set membership (SM) identification refers to a class of algorithms which is used to
estimate the parameters of linear system or signal models in which the error sequence
is bounded. The area of SM identification was first developed in the domains of control
and systems science [2, 3, 22, 24, 31, 33, 34, 38, 42, 43, 44]. Because of their potential
for application and theoretical development in many signal processing problems that
involve estimation of linear parametric models, SM techniques have recently received
considerable attention from researchers and engineers in many fields such as speech
processing [12, 13, 18, 19], image processing [39], neural networks [11, 25], robust
adaptive control [1, 21, 27, 28, 29], and time series analysis [41].

Contrary to the conventional identification techniques, SM identification assumes
no probabilistic knowledge about the error in the data with respect to the assumed
model form. Instead of modeling the error sequence as a random variable with some
probability density function, a priori information about the bounds on the error
sequence is used to constrain the solutions to certain sets in the parameter space. This

approach is particularly suitable for applications where the number of data points is

very limited. In such cases, an attempt to model the data error as a stochastic process
would result in an extremely crude estimate of the parameter uncertainty. Moreover,
many applications involve data errors which are not random (see for example [43]).
In such cases, the use of SM identification techniques can be very useful.

A commonly studied case is when the disturbance to the parametric model is
point-wise “energy bounded”

5201) S 7n Vn (1.1)

*

where e...(n) is the unknown disturbance process, and 7,, is known or can be estimated
from the data prior to the identification at time n. (Other types of constraints include
stability constraints [5], and other types of noise bounds [6, 7]). Based on (1.1), each
measured datum defines a set of solutions to which the true parameter vector must
belong. For each n, this set forms a “hyperstrip” in the parameter space. Since the
true parameter vector 0... must belong to each of the “hyperstrips” (to be consistent
with the data), then 0.. belongs to the polytopic region defined by the intersection
of all the “hyperstrips” for n E [1,N] . Generally, it is very difficult to describe
the polytopic region to which 0... belongs. Instead, simpler but more conservative
sets that include the polytope are used to form supersets which can be described
mathematically with fewer parameters. These sets include ellipsoidal outer bounding
[4, 9, 22, 23, 26], orthotopic outer bounding [31, 37], inner bounding [35, 40] and other
types of symmetric boundings (see [43] for a survey).

This research focuses on one particular class of SM algorithms commonly referred
to as optimal bounding ellipsoid (OBE) algorithms. This name was originally used to
indicate the first OBE algorithm which was developed by Fogel and Huang (denoted
here by F-H/OBE) [23]. Following the F -H / OBE, Deller developed the set member-

ship weighted recursive least square (SM- WRLS) algorithm [9, 12] which is somewhat

more familiar to DSP engineers in terms of the approach used in its development.
Both F-H/OBE and SM-WRLS lack a clear understanding of the convergence behav-
ior of the ellipsoid. However, they involve simple optimization criteria. Another OBE
algorithm was developed by Dasgupta and Huang [8] which is denoted by D-H/OBE.
This algorithm sacrifices the simplicity of the optimization criterion for the sake of
acquiring a proof of convergence under normal conditions of excitation.

All OBE algorithms are based on the constraint (1.1). They mainly differ by the
optimization criterion used and / or the selective technique employed to accept data.
Recently, Deller, Nayeri, and Odeh developed a general OBE algorithm called the
unified OBE (UOBE') that includes all the existing OBE algorithms [14].

This research has two goals. First to investigate the convergence behavior of the
ellipsoid for the class of OBE algorithms with volume optimization criterion (to be
defined later) when the system is subjected to non persistently exciting (non p.e.)
disturbances. The analysis will be extended to the general colored noise case. No
previous attempt has been made to analyze the convergence behavior of any OBE
algorithm with an interpretable optimization criterion. In Chapter 2 we study the
convergence behavior of the ellipsoid in the OBE algorithms with the volume opti-
mization criterion under different types of excitation. It will be shown that a non p.e.
input will cause the ellipsoid to collapse (degenerate) at least in one of its dimensions.
The use of the volume ratio measure as an optimization criterion will cause the algo-
rithm to stop taking data even though the ellipsoid has not shrunk to a point. The
behavior of the SM-WRLS algorithm under colored noise is further explored in the
same chapter.

The second target of this research is to develop a new method of optimization
that takes into account the effect of the history of the data in the optimization

procedure. This method will be referred to as WRLS method with weighted past

 

measurements. This procedure will then be specialized to the case in which only the
past measurements are weighted. This will be the basis of a new algorithm called
the set membership past-weight optimization (SM-PWO) algorithm. When compared
to the SM-WRLS algorithm, the SM-PWO algorithm has much better numerical
stability. However, it still maintains the advantages of the SM-WRLS algorithm.
This analysis and further characterization of the SM-PWO algorithm is the subject
of Chapter 3. Finally, Chapter 4 concludes the thesis and draws some guidelines for

open research problems.

1.2 The OBE Algorithms: Theoretical Background

Before introducing the underlying concepts of the OBE identification, it is useful to
comment on its relation with the well-known least square error (LSE) method. While
the OBE algorithms produce a feasible set of solutions to which the true parameter
vector 9.. belongs, the LSE produces a point estimate that eventually converges to 0...
(with the assumption of white noise input) [30]. In the OBE algorithms, the center
of the ellipsoidal region at each time n is the same as the WRLS estimate. This
is particularily obvious in the SM-WRLS algorithm. Let us first introduce the LSE

method.

1.2.1 The Least Square Error (LSE) Method

Consider the general autoregressive with exogenous input ARX (p, q) model

y(n) = i ak.y(n — k) + 29: bk...u(n — lc) + e...(n) (1.2)
k=1

k=0

 

where y(n) is a measurable scalar output, u(n) is a measurable input, and e..(n)
is some unknown error process that is uncorrelated‘ and independent of u(n). We
assume the existence of a “true” model of the form (1.2) underlying the observed
sequences {y(l::)}]:’=1 and {u(lc)}kN=1, though the parameters ah, bk. are unknown. We

can write (1.2) in a vector form

3101) = 93301) + 5:01) (1 3)
where
23T(n) = [y(n — l) . . . y(n — p)u(n) . . . u(n -— q)] (1.4)
and
9? = [al.az. . . .ap.bo. . . . bq.] . (1.5)

For convenience define the integer

m=p+q+1. (1.6)

Given the data {y(n),u(n)} for n E [1, N], and some set of error minimization weights

{An}£’=1, the identification problem is to estimate the parameter vector 0....

The LSE estimate of 0.. of (1.3) is found by minimizing the loss function VN(0)

with respect to 0 [30]
N
:1

1 .
VN(9) = 7V 2 A1:010") “ y(k))2 (1-7)
I:
where 32(k) denotes the predicted output, so that

1

N
V~(9) = N 1; Adz/(k) - 9T2(k))2 - (1-8)

 

1The case when e.(n) is correlated, and hence the estimate is biased, will be discussed later.

5

Taking the gradient of VN(0) and setting it to zero, yields the LSE estimate at time N

N -1 N
0(N) = [2: Akz(k)xT(k)] [2 menu] . (1.9)
k=l k=l
The term with the inverse is called the weighted covariance matrix C(n)
C(n) = E Aka:(k):cT(k) . (1.10)
k=1

Based on the matrix inversion lemma (MIL), 6(n) and C“1(n) can be written in a

recursive fashion

AnP(n -— 1)z(n)xT(n)P(n — 1)

 

P(n)=P(n—1)— (1.11)

l + AnG’(n)
19(71): 0(12 — 1) + AnP(n):c(n)e(n, é(n — 1)) (1.12)
where
P(n) d2 c-1(n)
C(n) déf :cT(n)P(n — l):c(n) (1.13)

and where 5(n, 0) denotes the residual sequence when the parameter vector 0 is used
in the model

502,0) = y(n) - 0Tz(n) . (1.14)

The two recursions in (1.11) and (1.12) are known as the WRLS equations. As
described in [30], a necessary and sufficient condition for the convergence of 6(n) to
0.. is that; {13...(n)},’:'=1 be a sequence of uncorrelated random variables with zero mean

(white noise) and independent of u(n).

1.2.2 The OBE Algorithms

Given the sequence of data {y(n),u(n)} for n E [1,N] and an assumed model of
the form (1.3) and based on the constraint (1.1), the OBE algorithms integrate the
WRLS recursions and define a region of solutions in the parameteric space that is
centered around some LSE estimate. In light of (1.1), it is natural to consider only

solutions in the set

can 2 {9 : 52(n,0) s 7,, , 9 E ’Rm} (1.15)

at time n. 02,, forms a “hyperstrip” in the m-dimensional parameteric space. To
be consistent, 0,. must belong to each to", and thus to the intersection of all the

“hyperstrips” for any set of times included in the estimate, say, n E [1, N],

N
0... E 0N E n can . (1.16)

11:]

Hence 52,, forms a polytope in the parameter space. Note that (In is the most restric-
tive set under the conditions of the problem. Finding Rn, however, is an intractable
task since the complexity of describing the set S1,, grows linearly in n. Also, solving
for 0 which is consistent with (1.1) involves the solution of 2n m‘h order inequalities
which is undesirable even for small it and m [23].

The OBE algorithms employs a bigger set that contains (In. This superset, de-

~

noted by 0..., takes the form of an ellipsoid in the m-dimensional parameter space
a, = {o : (o _ 9(n))To-1(9 — 9(n)) g 1, o 6 km} (1.17)

where Q” is a symmetric positive definite matrix, 6(n) is the estimate (center of the

ellipsoid) at time n and

n, g 0,, vn e [1,N]. (1.18)

7

 

The strategy of the OBE algorithms is to find an optimal weight A; that will
shrink the size of the set flu at time n. Optimality here is defined in terms of quanti-
ties that reflect the size of (In. Common measures for the size of fl” are the volume
(or some quantity proportional to it), and the sum of the semi-axes of the ellipsoid.
If no such weight can be found, which indicates that the data do not carry useful
information that can help to refine the set of estimates at time 11 (based on the par-
ticular measure used to describe the size of flu), then the weight An is set to zero, and
the computational complexity needed to update the estimate is avoided. In practice,
only small percentage of the data is useful. Thus, OBE algorithms have the advan-
tage over the LSE method that they utilize a data selection technique that updates
only when data can refine the estimates. Also, in the case of colored disturbances,
the OBE algorithms provide a worst case bias.

Among the various OBE algorithms, the SM-WRLS is the most familiar to DSP
engineers in terms of the approach taken in its development. Because of its similarity
to the new algorithm to be developed in Chapter 3 (the SM-PWO), we introduce the
SM-WRLS algorithm and its main features in the next section. The argument will
deal with the case when the volume optimization criterion is used, mainly because of

its relative simplicity (for more details of the SM-WRLS see [9, 10, 16]).

1.2.2.1 The SM-WRLS Algorithm

The SM-WRLS algorithm developed by Deller et al. implements the WRLS solution
taking set membership considerations into account. Starting from the constraint
(1.1), Deller develops a computable hyperellipsoidal domain in the parameter space

which is centered on the WRLS estimate. This set (IN is given by

 

[a — 0(n)] g 1, a 6 km} (1.19)

where

4n) = (‘2 (momma) + 2": Am. — yea» (1.20)

k=1
6(n) is the weighted LS estimate at time n, and C (n) is the covariance matrix defined
above. The size of (2,, is a function of the weight A,,. The algorithm implements
a strategy for data selection based on minimization of the volume of the set flu.
A quantity proportional to the square of the volume is used in the optimization

procedure, namely, the determinant of B (n) where,

B(n) “Li! n(n)P(n) . (1.21)

Defining the ratio of the square of the volume of the ellipsoids at time n and n — 1 as

”u(fin) : dejeggt(i)l) a (122)

 

then, the minimization procedure is carried out by minimizing pv(f~l,,) with respect to
An and finding the optimal weight A;. Optimality in this context means a nonnegative
A; that will produce the minimum #061"). Differentiating p061“) with respect to A,,

and setting the result to zero, a quadratic equation results [12],

F(A,,) = alA; + 02A,, + 03 = 0 (1.23)

where,

01 = (m — ”7110201)
oz; = {(2m -1)7,, + 52(n,6(n —1))— K.(n —1)G(n)}G(n)

a3 = m(7,, — 82(n,9(n —1)))— rc(n —1)G(n) . (1.24)

The solution of (1.23) can be either one positive root and one negative root, or

two negative roots [14]. If both roots are negative, this means that there is no

optimal positive weight A,, that can shrink the volume of On at time 11 (data are not

informative). Hence, the data are rejected, A,, is set to zero, and the updating effort is

avoided. On the other hand, a positive root of (1.23) will guarantee that the volume

of flu is decreasing. Thus the data are informative and are accepted. One version of

the SM-WRLS algorithm which is based on the MIL is shown in Fig. 1.1.

 

 

 

 

 

Initialization C'1(0) déf P(O) = 6—11
9(0) = 0
A] = I
rs:(0 = [6T:c(1)]2 + 312(1) (compute after step 3 for n = 1)
Recursion For n = 1,2, ,N

Step 1. Update G(n), 5(n,é(n — 1))
C(n) = zT(n)P(n — 1)::(n) where P(n) déf C‘l(n)
e(n.é(n —1))= y<n> - 0% —1)z(n)

Step 2. (Skip if n = 1) compute optimal A; by finding a positive root of the
quadratic equation (1.23).

Step 3. (Skip if n = 1) If A; _<_ 0, set P(n) = P(n — 1), 6(1).) = 6(n — 1),
n(n) = Ic(n — 1) and go to step 5. Otherwise, continue.

Step 4. Update P(n), 6(n), and u(n)
0-11..) = pt.) = p1,. _ 1) — 1.P<n-vergfajg>1’<n-v
3(n) = 9(n — 1) + A..P(n)e(n,é(n — 1)):c(n)
4n) = an — 1) + m. — “33%;?

Step 5. If n < N, increment n and return to step 1.

Figure 1.1: SM-WRLS algorithm based on the matrix inversion lemma.

10

 

1.2.2.2 Suboptimal Test for Innovation in SM-WRLS Algorithm

As described above, the test for useful data in the SM-WRLS algorithm is based on
finding an optimal weight A,, which will minimize 11,,(fln). A positive root of (1.23) will
result if the constant term in (1.23), namely 03, is negative. Minimization of 11,,(fln)
over An 6 [0,00) involves maximizing det[C(n)] and at the same time minimizing
ri(n). As illustrated in [36], the quantity det[C(n)] is monotonically increasing with
respect to An 6 [0,oo). However, the increase in det[C(n)] will not be significant
over reasonably small values of An. On the other hand, minimization of u(n) with
respect to An 6 [0, 00) tends to decrease the value of A,,, unless a minimum of u(n)
occurs at a large value of An. Based on the previous reasoning, a suboptimal test is
constructed [17] which will further reduce the computational complexity in the SM-
WRLS algorithm. The key point here is to find a value of An 6 [0,00) at which a

minimum of n(n) will occur. This will be true iff,

52(n,0(n —1))> 7,, . (1.25)

Thus if (1.25) is satisfied, the algorithm accepts the data. This heuristic argument
happens to be true since (1.25) is a sufficient condition for (13 to be negative.
Next, we proceed to study the convergence of the ellipsoid in the OBE algorithms

with volume optimization criterion under different types of disturbances.

 

11

Chapter 2

Convergence Study of
the Ellipsoid

 

2.1 Introduction

In this chapter, we investigate the convergence behavior of the ellipsoid under different
types of excitation for the class of OBE algorithms that implements the volume ratio
measure. The particular importance of this class is its simple updating criterion in
addition to its clear interpretability (see [15] for comparison among different OBE’s).

Because of the similarity in the optimization criterion, different excitations will
affect the convergence behavior of the ellipsoid in all the algorithms of this class
in a similar manner. Therefore, simulation experiments are carried on for only one
algorithm, namely the SM-WRLS algorithm (with the volume optimization criterion)
and the results are general for all algorithms in the class considered.

It will be shown that under the condition of a non-persistently exciting (non-p.e.)
input, the estimates will not converge to the true parameter values. Instead, the
algorithm will stop accepting data after only few iterations. These expriments will
provide a good understanding of the behavior of the algorithm under general colored

noise disturbances.

12

For the sake of simplicity of illustration, an autoregressive model of order two
AR(2) will be considered in most of the experiments. The location of the poles of the
system have a drastic effect on the behavior of the algorithm. This will be illustrated
by some examples. The types of “noisy inputs” chosen are of a DC input, cosine input
and colored noise produced by passing a white noise sequence through a IOWpass filter.

The remainder of the chapter will be devoted to the investigation of the behavior
of the OBE algorithms (with volume measure u,(fl,,)) in the case of colored noise

disturbances. This problem is not fully understood and is still being researched.

However, we shall be able to draw some conclusions and show some empirical results.

2.2 Persistency of Excitation

In order to understand how OBE algorithms behave in the case of non-persistently
exciting coloured noise, we begin by defining what we mean by a persistently exciting

input [30].

 

Definition 1 Let {u(n)} be a stationary, ergodic input sequence. Then {u(n)} is
said to be persistently exciting of order k, if the k x k autocorrelation matrix Ru
is nonsingular, where the i,j element of Ru is r(i - j), r(j) is the autocorrelation
sequence given by :

N
r(j)déf1\iEI;o-11VZ u(m)uT(m —j) V 0 Sj S k —1. (2.1)
m=l

 

In the frequency domain, {u(n)} is persistently exciting to order k, if it has a spectral
density that is nonzero at at least k points.
In the case in which the system is subjected to non-p.e. disturbances, the volume

measure [1,,(fln) used in the OBE algorithms fails to define a proper “metric” in

13

 

the parameter space [32]. This means that if d is a distance measure such that
d(0(n),0.) = pv(f~l,,), then d(0(n),9.) = 0 does not imply that 6(n) = 9,... This
situation arises because the ellipsoid It" may potentially degenarate and reside in a
subspace of 11’”, thus achieving zero volume without being reduced to a point. In
the colored noise case, this problem may cause the algorithm to stop accepting points
at a very early stage. The use of other optimization criteria that define a proper
“metric” could potentially solve this problem. However, this is at the expense of
more complexity and slower speed of operation. One such common measure is the

~

trace measure [1&in which minimizes the ratio

11 ) _ ammo-«n» (2.2)

(~71
fi;_1) _ tr{n(n — 1)C‘1(n — 1)}

 

t
#t(

where tr{.} denotes the trace of the matrix. The minimization of (2.2) to find the
optimal weight An results in trying to solve for the roots of a polynomial of order
three [23]. The increase of order of the polynomial (relative to u,(fl,,)) results in
additional complexity in the analysis.

Refering to (1.19), the eigenvalues of C(n)/n(n) at time n, say e,- for i = 1,... , m,
are inversely proportional to the square of the lengths of the ellipsoid axes. Accord-
ingly, convergence of the ellipsoid to a single point requires that either e,- tends to
infinity for all i, or n(n) tends to zero. Experimental evidence shows that rc(n) is
increasing most of the time and thus it is very unlikely that it will tend to zero. In
other words, limnxoo (2,, is a nontrivial set iff one or more e,- remains finite [32]. Thus,
in the presence of colored disturbances, lirnnxoo u¢(fl,,) must be positive as a result
of at least one finite e,-. On the other hand, a single infinite eigenvalue of C (n) / K.(n)
will cause lim,,_.oo pv(fl,,) = 0. Thus, the ellipsoid need only to collapse from one

dimension to assure zero volume. This argument leads to the following conjecture:

14

 

Conjecture 1 When the volume measure is used, the limiting ellipsoid will degener-
ate (collapse into a subspace) ifl the input is non-persistently exciting and the algo-
rithm does not cease to accept data.

 

The following examples illustrate these ideas.

2.3 Non-Persistently Exciting Colored Noise Case

2.3.1 AR(2) Model with DC Input

Given an AR(2) model,
y(n) = a1...y(n — l) + a2.y(n — 2) + 6...(n) (2.3)
Suppose that 5.,(n) is a realization of the following random process
e...(n) = x/2cos(27r§) (2.4)

where 6 is a random phase uniformly distributed between 1 and —1. Then, a particular

outcome of 5 is chosen in this experiment such that
e.(n) = x/2cos(27r x 0.213421) = 0.322178 v n

Let N be the total number of data, 7000, and 7,, = max{53(n)} = 0.1038 for all n.
In this experiment, the SM-WRLS algorithm is used to estimate the parameters of

a model whose true parameters a1... and a2... are constant. Different values of a1... and

15

 

 

a1. a2... poles (“u(n) (“u(n) Time of last det B (n)
at n = 7000 at n = 7000 datum accepted at n = 7000
1.8 -0.82 0.9 :1: J01 1.923 -0.924 36 5.033 x10"4
1.6 -0.65 0.8 ij0.1 1.893 -0.895 30 9.713 x 10'3
1.4 -0.5 0.7 :l:j0.1 1.858 -0.862 25 6.540 x 10‘2
1.2 -0.37 0.6 :1:j0.1 1.813 -0.820 22 2.587 x 10‘1

 

 

 

 

 

 

 

 

 

Table 2.1: The estimates, the last data used, and the volume of the ellipse at n = 7000
for different true parameter values under first order p.e. disturbances.

a2... (corresponding to different locations for the poles of the system) are used. The
DC input is persistently exciting to order one.

Because of non-p.e., the ellipse fl" tends to collapse (degenerate) from one dimen-
sion while the other dimension remains finite. Since the u,(fl,,) optimization criterion
is used, the algorithm will stop accepting data after a short time even though the
ellipse has not been reduced to a point. Table 2.1 contains the results obtained from

the SM-WRLS algorithm after 7000 for different values of the true parameters. The

estimate at n (the center of the ellipse) is given by

The optimal weight A; and the parameter Kn are shown in Fig. 2.1 for the case in
which a1... = 1.8 and a2. = —0.82. The graphs are shown for the first 100 iterations
only. Since the algorithm stops accepting data after n = 36, An will be set to zero and
u(n) remains constant for n 6 [36,7000]. The ellipsoids corresponding to Table 2.1
are shown in Fig. 2.2. Note that the further the poles of the system are from the
unit circle (in the z-plane), the fewer data the algorithm uses and thus the volume is

bigger (the volume of the set is proportional to the product of the semi-axes of flu).

16

1300

 

1600 l.
1400 l- \ '1
1200 l- l

1000 1 « “

 

 

o 1 4 L l A L L 1 A
0 10 20 30 40 50 60 7O 80 N 100

 

Iteration, n (samples)

(a)

 

2500)-

 

(C(71)

ISM]-

ION)-

5W)-

 

 

L

10 20 30 40 SO 60 70 U N 100

 

Iteration, n (samples)

(1’)

Figure 2.1: The SM- WRLS algorithm with AR(2) model disturbed by first order
exciting noise. (a) The optimal weights A; (b) u(n).

17

02

02

 

.1p

.3.

-4r—

 

 

-3

01

—0.82
_ 1.8, 021- =
(Z) 01.

 

 

 

G1

-0.65
= 1.6, 02. =

.. 1-
(ii) a

18

 

 

 

 

 

 

 

 

 

 

4 f 4 ,—
3r .
2, .
1.

02
0r 4 ~
.1.- -
.2,
-3~ ,
‘* 1
’3 2 .T o I i i 4 5 6

a1
(iii) a1. = 1.4, a2. = —0.5

4 r .
3. .
2.. «l
1» 1

02
o» 1
.1. ..
2» .1
.3. -(
.‘1- .1
-3 2 1 o 1 i 3 T s s

01

(iv) a1. = 1.2, a2. = -0.37

Figure 2.2: The set flu after n = 7000 for different true parameters for an AR(2)
model with first order p.e. disturbance. In each case, ‘*’ denotes the true parameters
and ‘ x’ denotes the estimate (ellipsoid center).

19

2.3.2 AR(2) Model with Cosine Input

Consider the AR(2) model defined in (2.3) with an input noise 5,.(n) realized by the
random process:

e.(n) = «2 cos(27r(312 + 0) (2.5)

where 5 is the same random phase defined above. This input is persistently exciting
to the order two (see appendix). Three experiments were performed for different true
parameters a“, a2... using the SM-WRLS algorithm with 11,,(fln) used. The results
are shown in Table 2.2 with N = 7000 and 7,, = 2.0 for all n. Note that in this case
the ellipsoid does not collapse as in the case of first order excitation. Basically, this

is because the order of the system is not greater that the order of the exciting input

(both are of order two).

 

 

a1... a2... 61(n = 7000) (“12(n = 7000) Number of data used det B(n = 7000)
1.8 -0.82 1.957 -0.9933 45 1.782 X 10‘”
1.6 -0.65 1.961 -0.9995 72 2.606 X 10'3
1.4 -0.5 1.962 -l.0000 120 2.234 X 10"2

 

 

 

 

 

 

 

 

Table 2.2: The estimates, the last data used, and the volume of the ellipse at n = 7000
for different true parameter values under second order p.e. disturbances.

Note that regardless of the values of a1. and a2..., the estimates are almost the
same. This suggests that the algorithm has converged to some bias which is not the
true parameter vector (more about this in the next section). The optimal weights
A; and the parameter K.(n) in the case when a1... = 1.6 and a2... = —0.65 are shown
in Fig. 2.3 for the first 100 iterations only. Note that the algorithm stops accepting
points after iteration 72. Thus, A; is set to zero and an is kept unchanged for all
n E [72, 7000]. The ellipsoids for two cases are shown in Fig. 2.4. It is obvious that

the values of A; and rc(n) are growing very large. The same behavior is noted in

20

all simulation experiments. If the algorithm keeps accepting data, then A; and r:(n)
will continue increasing causing serious numerical problems when the algorithm is

implememnted on a finite wordlength machine.

2.3.3 AR(3) Model with Cosine Input

Consider an AR(3) model given by

y(n) = 01*?!(71— 1l+ Gag/(n — 2) + 03:3!(71 —' 3) + 5:01) (2-6)

where 5..(n) is a realization of the cosine random process defined in (2.5). The cosine
input is p.e. to the order two, while the given system is of order three. Let a1... =
1.9, a2. = —1.2, and a3... = 0.25. 7,, = 2.0 for all n. The simulation results of
running the SM-WRLS algorithm (with )u,,(fl,,) measure) for this system are shown
in Table 2.3. Similar to the situation in the previous sections, the algorithm stops
accepting points at a very early stage. From a total number of points N = 7000, the
algorithm uses only 32 points and the last point incorporated is at n = 62. The reason
why the algorithm stops accepting points is mainly due to the lack of innovation in
the data. Table 2.3 shows the estimates of the true parameter, and the eigenvalues of
the matrix P(n) for i = 1, 2, 3. Note that the square of the length of each of the axis
of the ellipsoid is proportional to one of the eigenvalues of P(n). It is obvious that 62
is almost zero which means that the ellipsoid is degenerating in the dimension that
corresponds to eg. Also, e3 is five orders of magnitude less than e1 which strongly

suggests that the ellipsoid is also degenerating in the dimension that corresponds to

63.

21

 

~
_- ..-_'...——-.—__‘__—

 

0 I 1 1 1 L 1 1 A
0 10 20 30 40 50 60 70 80 M 1m

 

Iteration, 71 (samples)

 

 

0.8 i
0.6 >-
0.4 >-

0.2 '-

 

 

 

o A L l A A A A L A

0 10 20 30 40 50 60 70 n N 100

 

Iteration, 11 (samples)

(5)

Figure 2. 3: The SM- WRLS algorithm with AR(2) model disturbed by second order
exciting noise. (a) The optimal weights A; (b) u(n).

22

 

1:: .
-0.2 '- ‘
-0.4 i- '1
0.2 -0.6 - "
~03 1- «1
1_ j 7
-1.2 1- .
-LAP «
-I.6 )- -
~1.8 )- s

 

 

 

(2') a1. = 1.8, a2. = —0.82

 

0 r v r
-0.2 1- .
0.4 L ~
02 -0.61- ‘
arr <
,. l
.13 . q
.14 r «
.LsL ~
4.8 1- -1

 

 

 

(I) 01. = 1.6, 02. = -0.65

Figure 2.4: The set flu after 71 = 7000 for different true parameters for an AR(2) model
with second order p.e. disturbance. In each case, ‘*’ denotes the true parameters and
‘ x ’ denotes the estimate (ellipsoid center).

23

 

 

 

 

 

211(n) (“u(n) {13(n) e1 62 63
at n = 7000 at n = 7000 at n = 7000
2.826 -2.697 0.865 0.5313 2.133 x10”? 7.709 ><10"5

 

 

 

 

 

Table 2.3: The estimates and eigenvalues of P(n) at n = 7000 for AR(3) model with

cosine input noise.

2.4 The Colored Noise Paradox

In this section, we study the asymptotic convergence, if any, of the hyperellipsoidal
region (1,, in the general colored noise case. In Chapter 1, it was mentioned that the
OBE algorithms have an advantage over the LSE method in the colored noise case
since the OBE algorithms provide a worst case bias for the true parameter vector 9...
The study of the convergence behavior of fin in the colored noise case is related to
the white noise case since white noise is a very special case of colored noise in which
all the frequences in the spectrum of the noise signal are equally excited. Although
experimental evidence confirms that the size of (2,, (the volume or the trace measure)
tends to a very small value in the case of white noise, still no proof has been established
for the convergence of $2,, to a point (the true parameter vector 0...). The lack of such a
proof makes it more difficult to study the colored noise case. However, some hueristic

results can still be obtained. Let us start by stating the following lemma:

 

Lemma 1 If the error sequence {5.(n)} can be realized by a wide sense stationary,
second order ergodic almost surely (as) white noise, then the WRLS estimate B(n)
( with a proper choice of the optimal weights) will converge asymptotically to 9,. (as)

[30].

 

If the noise is colored then 0(n), in general, will not converge to 0... It can be shown

24

that for properly chosen sequences of optimal weights, and under p.e. colored noise,
the WRLS estimate 0(n) will converge to a biased point 0), 75 0... in as. sense.
For a general OBE algorithm, the optimal weights are chosen in a manner that will

certainly diminish the set measure used. This is stated in the following proposition:

 

Proposition 1 Consider a general OBE algorithm. If an optimal weight exists at
time n, then its use will certainly diminish the set measure used.

u(n) < #(n - 1)

where u is either If.” or ,u,. Therefore, in general u(n) S u(n — 1). Further, for the
trace measure, ,ut{fl,,} = 0 iflfln = {9...}.

 

Proof: see [32]. El

Proposition 1 suggests that the set measure used will continuously diminish and
the ellipsoid has to converge to some limiting set. Thus if the system is excited by
a p.e. colored disturbances, then the WRLS estimate which is also the center of the
ellipsoid will asymptotically converge to a biased value 0), which is, in general, not
equal to 9....

If the noise is colored, then the convergence of flu to a point will cause a con-
tradiction since fin should contain both points 0), and 0.. which are not equal, in
general. This contradiction is what we refer to as the colored noise paradox. To avoid
this contradiction, it should be true that in the case of colored noise the set 52,, is
continuously shrinking and its asymptotic limit contains at least two points (0... and

0),). The above argument justifies the following proposition:

25

 

Proposition 2 In the case of colored noise disturbances, the feasible set fin will
converge asymptotically to a nontrivial set.

 

For a non-p.e. colored noise (see examples in the previous section), the above assertion
is true since the algorithm will cease to accept data in finite time due to lack of
innovation. If the colored noise is p.e., then the assertion should be true as a result
of Proposition 1 and the fact that the center of the ellipsoid (i.e the WRLS estimate
0(n)) will converge to the biased value 0),. It is important to note that 0... does
not necessarily lie on the boundaries of the nontrivial set in Proposition 2. In fact,
experimental evidence shows that under p.e. colored noise, 0... tends to be close
to the boundary of the limiting set of Proposition 2 but still does not lie on this
boundary. This behavior encouraged us to investigate the conservatism of the OBE
algorithms. It turned out that the optimization criterion used in the OBE algorithms
results in a relatively pessimistic set fin compared to the original “polytopic” set
(In. Moreover, as the number of data increases the set 9,, tends to shrink in a rate
much faster that the rate of shrinking of flu. We have investigated some approaches
to overcome this problem. However, those solutions are still too complicated to be
implemented practically and thus can not be accepted at the time being. For now,
we only show the above situation pictorially for an experiment conducted using the
SM-WRLS algorithm with white noise input (uniformly distributed between -0.5 and
0.5) with an AR(2) system model. The true parameters are: a1... = 1.0, a2... = —0.5.
The hyperstrips w,- and the sets f2,- and ii,- are shown in Fig. 2.5 for the initial five
iterations of the algorithm.

During simulation experiments that was conducted on the SM-WRLS algorithm,

it was noted that the values of some of the parameters used by the algorithm grow

26

02

02

 

 

 

y-

P

 

(11

(1)9" and 92,, at n = 3.

 

 

 

 

01

(ii) (2,, and $2,, at n = 4.

27

 

 

 

02

-2_

-3)—

 

 

 

 

01

(iii) 0,; and S2,, at n = 5.

 

02

-2_

-3r-

 

 

 

 

01
(iv) (1,, and 11,, at n = 6.

Figure 2.5: Illustration of the conservative behavior of the OBE algorithms.

28

so large to the extent of causing a serious precision problem when implemented on
a finite precision processor. This problem motivated the search for other algorithms
that provide better numerical stability and at the same time maintaining the bene-
fits of the conventional OBE algorithms. In the next chapter we develop a general
method for optimization that can be applied to many OBE algorithms. Later, this
approach will be specialized to develop a new OBE algorithm (referred to as the
set-membership past weight optimization SM—PWO algorithm. This algorithm is ac-
tually a modified version of the SM-WRLS. For each n, the SM-PWO produces the
same ellipsoid generated in the SM-WRLS. However, the SM-PWO maintains better

numerical stability for the quatities A;, u(n) and C(n) used in both algorithms.

 

29

Chapter 3

The Set-Membership Past-Weight

Optimization (SM-PWO)
Algorithm

 

3.1 Introduction

In this chapter, a new OBE algorithm will be introduced. We call it the set-membership
past-weight optimization (SM-PWO) algorithm. This algorithm will possess the fa-
vorable features of the SM-WRLS algorithm such as (empirically) fast convergence,
a simple checking criterion for useful data and a suboptimal innovation test. On
the other hand, it maintains much better numerical stability than the SM-WRLS
algorithm.

The original motivation behind the development of the SM-PWO algorithm was
the search for a new optimization criterion for the OBE algorithms that accelerates
the convergence of the ellipsoid to its asymptotic theoretical set (whether this limit
is 0,. or some neighbourhood around it). While this goal has not yet been reached,
the pursuit of such an investigation led to a technique for optimization of the weights

which can be utilized to satisfy another desired requirement (such as an upper bound

30

on the weighted covariance matrix C (n)) in addition to the requirement of minimizing
the size of the hyper-ellipsoid. The technique is based on assigning two independent
weights to be optimized. One of these weights is the error minimization weight which
is associated with the present incoming data. The new weight is associated with the
covariance matrix at time n - 1 and is used to minimize the volume of the ellipsoid at
time n by optimizing, in a certain sense, all the past weights that have accumulated in
C(n - 1). By specializing this general procedure for the case in which only the past-
weight factor (to be defined later) is optimized, we obtain the SM-PWO algorithm.
The SM-PWO produces identical estimates to the ones produced by the SM-WRLS
algorithm with the advantage of maintaining better numerical stability.

In the next section, we briefly investigate two major problems encountered with
conventional OBE algorithms and explore the reasons for these problems. Then we
start a general development to obtain an optimization criterion which is based on
optimization of two factors, namely the present weight and a past-weighting factor.
Following that, we specialize this development to include optimization with respect
to only the past-weighting factor. This leads to the SM-PWO algorithm. The main
features of the SM-PWO algorithm will be studied and compared to its counterpart,
the SM-WRLS algorithm. Finally, simulation results that confirm the development

and analysis of the SM-PWO algorithm are presented.

3.2 Problems Encountered in Conventional OBE
Algorithms
At the end of Chapter 2, it was shown that the ellipsoid flu in the OBE algorithms

with volume optimization criterion can shrink much more slowly than the the polytope

31

0,, which is contained inside the ellipsoid (see Fig. 2.5). Eventually, 52,, will not tightly
bound the boundaries of flu. Unfortunately, it is still not obvious whether (2,, or even
51,, converges to 0. (under the assumption of white noise disturbances). However,
it is evident that 92,, will at least tend to some neighborhood of 9.... Regardless of
our lack of knowledge about the asymptotic convergence behavior of the ellipsoid, it
is clear that fin is not generally the smallest (in the sense of the chosen criterion)

ellipsoidal set to bound (In. This brings us to the issue of optimality of weights in
the OBE algorithms.

A closer look at an OBE algorithm with 11,152”) reveals that the optimization
criterion implemented in the algorithm is not sufficient to provide a minimum set flu
that optimally bounds (In. To illustrate this idea in more detail we specialize the
argument to the SM-WRLS algorithm with [1,,(f1n). It is, however, general for all
OBE algorithms which implements the same optimization criterion.

In the SM-WRLS algorithm with 11,,(fln) used, the algorithm compares det B(n)
(a quantity proportional to the volume of fin) to det B(n — 1) (B(n) was defined
in (1.21)) and based on their ratio, it is decided whether to accept the datum. If the
datum is useful, a quadratic equation is solved (see (1.23)) to get the best positive
weight A; that will produce the “minimum possible” volume ratio. However, all the
weights {A; 2;] are kept fixed. For each h E [1,n — 1], A; was the optimal weight
at time I: but generally it is not optimal at time 71. Therefore, the set (2,, will be
the minimal ellipsoidal set to bound 0,, only if the volume ratio is optimized with
respect to all the previous weights up to time 71. If this is achieved, then fin will
touch as many as possible of the vertices of (In. However, this kind of optimization
is practically impossible to implement since it requires the optimization of n weights

at each time, and thus solving a set of n nonlinear equations simultaneously.

The other problem which is encountered specifically in the SM-WRLS algorithm

32

is related to the numerical stability of the optimal weights A; and the parameters
u(n) and C(n). It was noted that A; and u(n) grow very large as 72 increases. Also
C(n) tends to decrease to very small values. If the algorithm keeps accepting data
(as is the case under p.e. disturbances), the numerical values of A; and u(n) will
keep growing indefinitely. This will cause a serious numerical problem in any finite
wordlength processor that implements the algorithm. The SM-PWO algorithm to
be developed in later sections provides an equivalent algorithm to the SM-WRLS
algorithm with the advantage of improved numerical stability.

Next we develop a general procedure for optimization. This method is based on
using two weights to be optimized. The first weight is the weight associated with the
data at time n, namely An, which is the optimization factor conventionally used in
OBE algorithms. The second weight, denoted by fin, is a sort of past-measurement

weighting factor.

3.3 WRLS Method with Weighted-Past Measure-

ments

3.3.1 Development of the Modified WRLS Recursions

Recall the computation of the weighted covariance matrix C (n),
C(n) = C(n — 1) + Ana:(n):cT(n) . (3.1)

In section (1.2), it was illustrated that the quantity det C (n) is inversely proportional
to the volume of fin. As 71 increases, more terms are added to C(n) which will

consequently tend to infinity. At time n, the conventional optimization strategy seeks

33

an optimal value for A,, which produces the minimum volume (and consequently a
larger C(n)). However, this strategy leaves the history of the data (accumulated in
C (n — 1)) fixed. The proposed strategy starts with the assignment of a varying factor
6,, to the matrix C(n — 1) to take into account the optimization of the past data as a
whole in one quantity, C(n — 1), in addition to the trivial weighting factor An. Thus

(3.1) becomes:

~

C(n) = 73,5171 — 1) + Ana:(n)a:T(n) (3.2)
writing C(n) in a nonrecursive fashion,

71 n

5(n) = 2(1—1 fljllkfiklqul

k=1 j=k+l

2:: \Il(n, k)x(k)a:T(k) (3.3)

where \ll(n, k) is defined by

Akl—Iyzk-i-lflj ifn>k

\Il(n, k) = (3.4)
n ifn=k.
Note that for n > k,
71 11-1
\Il(n, k) = A]; H 51' = flnAk II ,Bj 2' ,BnWU‘t — 1, k) . (3.5)
j=k+l j=l¢+l

The form (3.3) suggests a definition for the loss function 1710(0) of the following form :

N
me) = 2 WM k)[y(k) — We)? (3.6)
k=l

34

1.2:.

A" I I

I7N(9) is quadratic in 9. Minimizing 1710(9) with respect to 9 is done by setting the

gradient V9 1710(9) to zero,

N
vgmo) = 2 Z \I'(N. 100(k) — é (N)m(k>)<—2:T(k>) = 0.
k=1

 

 

Thus
N ‘1 N
= Z 0(N, k)x(k)xT(lc)] [Z 117(N, k)y(lc)x(k) . (3.8)
k=1 k=1
Lemma 2 The off line estimate in {3.8) can be computed recursively as
9(n) = 9(n _ 1) + 1,502,002 _ 1))P(n)a:(n) (3.9)
where
P(n) “'é’ c“< )
€(n,9(n _1)) dé’ y(n) —o (n —1):c(n) (3.10)
Proof:

From (3.8) and (3.3)

9(n) = c (n) 21:01, k)y( k)x( k)

:1

= c (n) [gums/002(k)+w1n.n)y(n)z(n)]

71-]

= c (n) [3.211101— 11),(1),(k)+1,,(n),(n)]

= 5402) [an (n_1)o(n-1)+Any<n>e(”)l

 

35

Replacing C(n -— 1) by its equivalence from (3.2),

. ~_1 ’ ~n—nxnxTn.
002) = C (71171.0() Am“ ()o(n-1)+A.y(n)x(n)]

= 5%) 30000: — 1) — 1,,(n),7(n)3(n — 1) + 1.1/(mam)

 

 

__. c (n)anne—1)+A.z(n)[y<n)—mT(n>9(n-1>ll

= 9(n — 1) + 1,501,160; —1))’13(n)x(n) . - a

Note that equation (3.9) has the exact form of the well-known WRLS estimate. Since

this recursion requires the evaluation of the matrix P(n) at each n, it would be more

 

efficient to develop a recursion for P(n) instead of inverting the matrix C(n) at each

n. To calculate P(n) recursively we make use of the matrix inversion lemma [30]
[A + BCD]‘l = A‘1 — A’IB[DA’IB + C’1]‘1DA'1 (3.11)

where A, B, C, and D are matrices of compatible dimensions. Now consider (3.2).

Taking A = 3,502 — 1), B = 23(n), C = 1,, and D = zT(n), then

P(n) = [COIN—1: Winn-11+)»: ”(n)$T(n)l’1
___ C (n—1)_ C (n— 1) mm)” T(n)C (n—l)x(n)+3‘1:]‘le(n)C (n—l)

         

 

 

 

0.. fl 5,. fl,
= F<n—1)_P:(__n— C(n) i 1-1;T(n)F(n—1)
3,. a. "LA, fl.
= P(n—1)__1_P(n—1)x(n):cT(n)P(n—1)
,Bn flz _AJ—Ancin'gjfi"
~ ~ T ..

36

where,

C(n) d2 :cT(n)P(n —1):c(n) . (3.13)

Equations (3.9) and (3.12) are modified versions of the WRLS recursions.

3.3.2 Describing 5,, in Terms of the Modified WRLS Equa-

tions

The next step is to relate the set S2,, to the above recursions. This will be done using
a geometrical approach. Starting with the ARX(p,q) model described by (1.2) and
assuming a noise sequence which is bounded as in (1.1), let (~10 be a sufficiently large
hyper-ellipsoid in Rm such that {10 definitely contains 9.... As explained in Chapter 1,
at each instant of time n, the measured data (y(n), u(n)) which is consistent with (1.1)
defines a “hyperstrip” 0.1,, in 12'". This set was described in (1.15). Then, at n = 1,
9... should belong to both I10 and w], and thus to their intersection. To construct an
OBE identification problem, the intersection of Flo and (.121 should be contained in the
next ellipsoid I21, whose volume should be optimal in some sense. In this fashion, we

construct the sequence of ellipsoidal sets {(1),}le which are recursively related by,
[5H flan] g 11,, (3.14)
Suppose that (71,,4 is described by

$1,.-. = {a 6 nm : (a _ 9(n _1))T’13“(n —1)(0 — 9(n _1)) s E(n _1)} (3.15)

37

where 76(n — 1) is some positive quantity. Then, using (1.15) and (3.14), the set (1,,

is given by
0.. =10 e 72'" : 0.10 — an —1))TF“(n —1)(0 — 002 —1)>+ 4.002) — Nun»?

S {31.7301 - 1) + Ann} (3-16)

where 9,, and A,, can be viewed here as nonnegative error minimization weights. To

evaluate fin in terms of the quantities at time n, we introduce the following theorem.

 

Theorem 1 Consider the inequality,

5,,(0—0(n_1))7"13“(n_1)73.,(()_1§1(n_1))+1,,(y(n)_07‘:.:(n))2 g flnE(n—l)+A,,7,,

~ (3.17)
where P(nA— 1) is an m x m positive definite symmetric matrix given recursively
by (3.12), 9(n) is a vector given recursively by (3.9), and the other quantities are as
defined before. If B(n) can be evaluated recursively by

An/Bfl52(ni 9(7). - 1))

 

 

E(n) = 5,720; _ 1) + 1.7,. — 5.. + 1,, 5: (n) (3.18)
where C(n) is as given by
C(n) = xT(n)P(n _ 1)::(n) , (3.19)
then {3.16) is equivalent to the form
(a — 0(n))TF“(n)(a — 9(n)) s 76(n) . (3.20)
Proof: See appendix. C]

By mathematical induction, if the ellipsoid at time n—l is given by (3.15), then the

ellipsoid at time n which bounds the intersection of 1.0,, and fin—l is given by (3.20),

38

where 9(n), P(n), and E(n) are computed recursively by (3.8), (3.12), and (3.18)
respectively.

After describing the ellipsoid S2,, recursively, it is required to construct an opti-
mization criterion that will determine the data selection strategy to be implemented.

One such criterion is based on the volume measure pv(f~1,,) characterized by the ratio

det B(n)/det B(n — 1).

3.3.3 Establishing the Volume Measure [1,,(fln)

To eliminate redundancy of information in measured data, and thus increase the
efficiency of the OBE algorithm, it is required that the Size of {(1,}le constitute a
nonincreasing sequence. One way to describe the size of (2,, given in (3.20) is given
by the quantity det B(n) which is proportional to the square of the volume of f1”.
Let 11,,(I1n) be defined by

 

mm.) = (3.21)

with

‘B'(n) 4;! E(n)P(n) . (3.22)

Note that the volume measure u,,(f1,,) is not the only way for establishing a strategy
for data selection. It is however the easiest to implement.
In the following analysis, we manipulate (3.21) to get an expression for pv(f~l,,) in

terms of A,, and 9". From (3.12) and (3.21),

B(n) _ B(n — 1) _ A,,B(n — 1)x(n xT(n)B(n — 1)

 

 

~

75(7).) 5M4” _ 1) 37,3202 — 1)(AnG(n) + 7611)
E(n) Em — 1) __ 1,2301 — 1)x(n)xT(n)B(n — 1)
7602 — 1) In 0.801 — 1)(A,,C(n) + A)

 

 

39

z it) ~ _ 1,1301 —1):c(n):cT(n)B(n — 1)

 

 

 

0.301 — 1) B(n — 1) E(n —1)(A,,C(n)+ flu)
Defining
71,, d2 1,6:(11) + 0., (3.23)
and
def E(n
dn 0,7601 _ 1) , (3.24)
then
~ ~ A,,B(n —1)x(n)xT(n)B(n — 1)
B(n) — d,, [B(n—1)— E(n—1)h,, ]
_ ~ dnAnx(n)xT(n)B(n — 1)
— B(n — 1) [d,,l — RI” _1)hn ] (3.25)

where I is the identity matrix. Taking the determinant of both sides of (3.25),

 

~ _ ~ d,,A,,:c(n)a:T(n)B(n -— 1)
det B(n) — det B(n — 1) X det [d,,I — an -1)hn . (3.26)
Using the identity [20]
det(cI + sz) = cm‘1(c + yTz) (3.27)

where c is a scalar, y and z are m-dimensional vectors, it follows that

 

 

det B(n) _ elm-1 Pd d,,AnzT(n)B(n - 1)z(n)]
detB(n—1) — " _" E(n—1)h,,
= (fr—1 Ida ._ W] .

 

40

Thus

_ det B(n) _ d,’{‘6,,
#0011431.) — det B(n — 1) _ hn ' (3.28)

 

 

where we have explicitly expressed u, as a function of both A,, and 6,, to emphasize

the dependence of p, on both weights.

3.3.4 Minimization of uv(A,,, 6,,)

3.3.4.1 Minimization With Respect to A,,

Taking the partial derivative of (3.28) with respect to A,, and setting it to zero,

 

3.1.0-3.) z a [manna—drew)

 

 

 

 

 

 

6A,, hi J
__ 0,7124 6d,, '
_ hi [mh'lB—A: — G(Tt)dn
= 0 .
Since d,, 75 0 and 6,, ¢ 0 (for nontrivial solution), then
6d,, ~
mhnCA—n- — G(R)dn — 0 . (3.29)
To evaluate %, d,, should be expressed in terms of A,,. Consider (3.24) and (3.18),
76(n) 1,7,, 1,5201, 9(n — 1))
d,, = —— = 1 — . .
nan — 1) + sun —--I) an ~1)h. (3 3‘”
Then,
6d,, _ 7., _ 52(n,9(n -1)) h,, — 1,6702)
8A,, _ 0,302 — 1) E(n - 1) h},

41

 

 

 

 

6d,, _ 1 7.. 5202.902 —1))B.
=> 31.. — 7.7.7:?) [a ‘ h; ] ' (3°31)
Substituting (3.31) in (3.29),
mh,, 1 5201.902 — 1))fln ~ _
7c(n _ 1) [7M — hi. ] — G(n)d,, _ 0 . (3.32)

Substituting the value of d,, from (3.30) and with some algebraic manipulations (3.32)

becomes,

where,

51 = (m - 117125201)

512 = (2m —1)7,,C(n)— C2(n)ii(n — 1) + C(n)e2(n,9(n — 1))

83 = my” _ m€2(n,9(n _ 1)) — C(n)ii(n — 1) (3.34)
(compare 51,, 62, and 63 to (11, 012, and 03 in (1.24)).
3.3.4.2 Minimization With Respect to 6,,

Consider (3.28) again. Differentiating p, with respect to 6,

atoms.) _ mdm-x%&+dma(fl")

 

 

 

an. ‘ " Bah. 7;
_ -1 1718166111 61611 _
— d: (h. afln+dnahn _0. (3.35)

Substituting for d,, using (3.24), and for h,, using (3.23), after some algebraic manip-
ulations, an identical equation to (3.33) results.

The optimal pair of weights (A;, 6;) is the solution of (3.33) which is a polynomial

42

of order two in two variables and therefore there is not a unique solution for (3.33).

We have thus shown the following :

 

Theorem 2 When the past measurements of the covariance matrix in the WRLS are
weighted, there will exist infinitely many optimal pairs of weights (A;,6;) that will
produce the same minimum volume ratio [1,,(Qn).

 

The natural question that arises is which pair of weights to choose. Apparently,
one could impose another restriction in the problem that will help to choose one
particular optimal pair of weights. One such condition is to require the matrix C(n)
to be bounded above. This will guarantee the convergence of the ellipsoid to some
small region around the true parameter vector 9,...

The interesting result stated in Theorem 2 implies that the effect of optimizing
the error minimization weight A,, associated with the data at time n is theoretically
equivalent to optimizing the weighting factor 6,, associated with the history of the
data. In the next section, a special case will be considered for the optimization of 6,,

while leaving the present datum unweighted.

3.4 The SM-PWO Algorithm

3.4.1 Development of the Basic Recursions and the Opti-

mization of 6,,

Suppose that the covariance matrix C(n) is given by

C(n) = 6,,C(n — 1) + a:(n)a:T(n) . (3.36)

43

In this case, the OBE identification problem is reduced to finding an optimal past-
measurement weight 6,, that minimizes pv(f~2,,). This is a special case of the general
case developed in the previous section. Thus, setting A,, in (3.9), (3.12), and (3.18)

to unity for all n, we obtain the following recursions:

 

 

9(n) = 9(n— l)+€(n,9(n—1))P(n)x(n) (3.37)
~ n _ 15(n - 1) _ P(n -1)z(n)zT(n)”P’(n _ 1)

P( l — fl. mm. + C(72)) (3'38)
,n _ M_ _fin62(n,‘(n-1))

~( ) — fin ( 1)+7n 0.. +610. (339)

Setting A,, in (3.33) to unity for all n, then the optimal 6,, is given by the following

theorem.

 

Theorem 3 The optimal past measurements weight 6,, that corresponds to the min-
imum volume ratio )1, is the solution of the following quadratic equation:

{13.2. + £251; + {3 = 0 (3.40)
where,
51 = m(7n - 6201.901 -1)))- (701)3(7‘ - 1)
C2 C(n) [7..(2m — 1) - C(n)E(n — 1) + 82(n, 9(n — 1))]
63 (m —1)7n(3”(n) . (3.41)

 

It is important to notice the similarity between the coefficients in (1.23) and the

coefficients in (3.40). This result is expected since both equations share the general

form (3.33).

44

.1

1

The previous observations can be used to explore some of the features of the

SM-PWO algorithm that are shared as well by the SM-WRLS algorithm.

3.4.2 Updating Criterion

Consider (3.40) and (3.41). The optimal 6,, is one of the roots of (3.40). If the
solution of (3.40) results in two negative roots, then 6,, is simply set to zero and
the updating effort is avoided (the data are not informative). Similar to the test
used in the SM-WRLS algorithm [14], a checking procedure can be developed for the
SM-PWO algorithm which is based on the sign of (1 in (3.40).

 

Lemma 3 The solutions of (3.40) are two negative roots if {1 is positive, and one
positive root and one negative root if {1 is negative.

 

Proof:
From (3.40) and (3.41),
{3 > 0 . (3.42)

Let 6"

n

’1, 6;,2 denote the two roots of (3.40). Then

5,2,1 .2. =E—3 (3.43)
1

0;. + 5.2,. = fl . (3.44)
1

Suppose that {1 < 0. Then
62,1532 < 0 - (3-45)

45

Thus, one root is positive and the other is negative.

Now suppose that {1 > 0. Then

 

 

 

62 261 > 0 . (3.46)
So 6;’16;',2 > 0 and 93,1 + 6;, < 0. Thus both roots are negative. [I]
Initialization E"(0) ”‘2 75(0) = e" I (e is very small)
0(0) = 0
91 = 1 r
E(0) = [9 :c(1)]2 + y2(1) (compute after step 3 for n = 1)
Recursion For n = 1,2, . . .,N
Step 1. Update C(n), e(n,9(n — 1))
(”:01 )= ”(11) (n —1)x(n) where 15(11) 4;! E“(n)
9T
501 9(n -1))= y(n)- 9(n -1)3(n)
Step 2. (Skip if n = l) compute optimal 6; by finding a positive root of the
quadratic equation (3.40).
Step 3. (Skip if n = 1) If 6; S 0, set P(n): P(n — 1), 9(n): 9(n — 1),
76(n) = E(n — 1) and go to step 5. Otherwise, continue.
Step 4. Update P(n ), 9(n), and 112(n)
~-1 P(n-n_ P(n-11214123eiP1n-1)
f: (n )= P(n): an(an+o(n))
9(n) = 9(n -1) + 19001541219“n -1))5(n)
~, _ ~ _ _ 6,,e2(n,0(n—1))
“(7’) "' flunIn 1) + 7n 6n+5(n)
Step 5. If n < N, increment n and return to step 1.

 

 

Figure 3.1: SM-PWO algorithm based on the matrix inversion lemma.

To check whether the datum is useful or not, the algorithm needs to check the sign

46

 

of {1. If {1 is positive, then the datum is discarded and the updating effort is avoided.
If {1 is negative, then (3.40) is solved for the positive root. The algorithm is shown in
Fig. 3.1. The optimal test in the SM-PWO is very similar to the optimal test used in
the SM-WRLS algorithm. However, one should note that in the SM-WRLS algorithm
the magnitude of A,, is an indication of the usefulness of the datum at time it. So the
more informative is the datum, the larger the value of A,,. Then we would expect A,,
to grow without limit as long as the algorithm is accepting points. This situation will
cause numerical problems on finite wordlength processors. This problem is overcome
in the SM-PWO algorithm. In fact, the larger the value of 6,,, the less important
is the current datum. In addition to providing numerical stability to the algorithm,
the SM-PWO algorithm can be slightly modified by imposing an upper bound on 6,,
without considerably affecting the reduction of the size of On. This has the advantage

of simplifying the analysis of the identification problem.

3.4.3 Imposing an Upper Bound on the Optimal Weight 6,,

As mentioned above, the magnitude of A; in the SM-WRLS reflects the amount
of information in the incoming datum. That is, a large positive A; indicates more

relative decrease in the volume of the ellipsoid at time 71, measured in terms of the

magnitude of det B(n)/ det B(n — 1). The situation in the SM-PWO is quite the

I

n, the more informative is the datum at time

opposite. The smaller the value of
n, and thus the more relative decrease in the volume of the ellipsoid. This opposite
behavior of the two algorithms is a result of their “inverse duality”. The mechanism
of the SM-WRLS is based on fixing the effect of the whole past of the data and seeks
an optimal weight A; associated with the present datum. The SM-PWO works in the

reverse direction by fixing the effect of the present information and optimizing the

47

weight associated with the entire history of the data (accumulated in C(n—1)). From
the previous analysis in Section 3.3, it was noted that in the general case described
by (3.2), the same (3.33) equation resulted when optimization was carried out with
respect to A,, and with respect to 6,, taken to be independent. If the coefficients in
(1.24) are equal to their equivalent in (3.41) at time n — 1, then A; of the SM-WRLS
will be exactly the inverse of 6; of the SM-PWO. However, the exact equality does
not occur since the corresponding coefficients in the quadratics (1.24) and (3.41) need
not in general be equal at any instant of time.

The insignificance of the current datum when a large value of 6; occurs suggests
that one can impose some upper bound on 6;, say 6,, such that if 6; Z 6,,, then
the information in the datum is very little (in terms of reducing the size of the ellip-
soid) and the datum can be disregarded without significantly affecting the estimation
process, and the updating effort is avoided. A simulation experiment that shows the
effect of imposing an upper bound on 6; is given in the next section.

Finally, the same suboptimal test for data selection which is used in the SM-WRLS
algorithm (see Section 1.2.2.2) can be used for the SM-PWO algorithm. This is true

because the same coefficients exist in both quadratic equations.

3.5 Simulation Results

In this section, several simulation studies for the SM-PWO algorithm are conducted.
These studies will show that both the SM-WRLS and the SM-PWO algorithms pro-
duce the same estimates and the same set (2,, at time n for all n E [1, N]. However,
the values of 6;, E(n), and C(n) used in the SM-PWO will be numerically stable in
contrast to their counterparts A;, u(n) and C(n) in the SM-WRLS. An AR(2) model

(see (2.3)) will be used in all experiments.

48

*3

3.5.1 AR(2) Model with White Noise Disturbances

Consider an AR(2) model with true parameters a1... = 1.8, and a2... = —0.82 and
suppose that the disturbance sequence is the output of a pseudo-random number
generator where the random variable of this process at each instant of time is uni-
formly distributed between —0.5 and 0.5. This random process represents stationary
white noise. Let N = 30000, 7,, = max{e§(n)} = 0.25 for all n E [1,N]. Simulation
studies for this model using the SM-PWO and the SM-WRLS algorithms show the
exact similarity of the estimates of parameters, produced in both algorithms. The
estimates 5,, and £12 from both algorithms are shown in Fig. 3.2. The first 100 esti-
mates are shown in one graph while the rest are shown in a second graph. The true
parameter is shown in the same graphs by a dotted line. Both algorithms used 465
data which represents 1.55% of the total number of data. The graphs of 6;, 76(n),
and C(n) are shown in Fig. 3.3. The corresponding A;, u(n), and C(n) of the SM-
WRLS algorithm are shown in Fig. 3.4. If an upper bound 6,, is imposed on 6; in
the SM-PWO with 6u = 5.0 (if 6; is negative or 6; is greater than 5, then the data
at time n is neglected), then the algorithm uses only 395 points. The corresponding

estimates and parameters for this case are shown in Fig. 3.5, and Fig. 3.6.

3.5.2 AR(2) Model with Colored Noise Disturbances

Consider the same AR(2) model with true parameters a1... = —1.6, and a2. = —0.68
which correspond to system poles at —0.8 :I: 30.2. Suppose that the white noise
sequence generated in the first experiment above is passed through a Butterworth-
type, bandpass filter of order 14 with passband frequences at w = 1.75 rad and
w = 2.75 rad, attentuation at bandpass is —1dB, and attenuation at stopband is

—60dB. The output of the filter is, therefore, colored and p.e. In this case, 7,, =

49

max{53(n)} = 0.364, and N = 10000. Using the SM-WRLS algorithm, the estimates
£11 and (12 are shown in Fig. 3.7. The corresponding values of A;, u(n), and C(n)
are shown in Fig. 3.8. Using an optimal testing criterion, the algorithm accepts 112
sample points which constitutes 1.12% of the total number of samples. For the same
experiment, the SM-PWO produces exactly the same estimates shown in Fig. 3.7. It
also uses the same number of data. Note that in this experiment the estimates are
biased. The values of 6;, Fr(n), and C(n) used by the SM-PWO algorithm are shown
in Fig. 3.9. A comparison between Fig. 3.8 and Fig. 3.9 shows that the parameters
used by the SM-PWO algorithm have much better numerical stability compared to
their counterparts in the SM-WRLS algorithm. For the SM-PWO algorithm which
employs an upper bound 6,, = 5.0 on the optimal weights (that is, the datum with
an associated optimal weight 6; > 5.0 is rejected), the algorithm uses 105 samples

out of (useful data). The estimates are shown in Fig. 3.10. The corresponding values

of 6;, E(n),and C(n) are shown in Fig. 3.11.

 

50

 

 

 

 

 

 

 

 

5 r -
. 0]] ‘
01 '5 " . . “
true 13 dotted
estimate is solid
~10 1- -1
-15 r- .1
cm I- c]
-25 M A L 1 A A 1 A A
o 10 20 30 40 so so 70 so 90 100
Iteration, 11 (samples)
1.88 A . . m r
1.86l .
1.84 E 1

I
1

  

    

01 1.82
E

1.8 -

I

.ll[ ; l

I _.

[11.41“ 0| _..I l l_.I-‘ ’
"Illf‘ rim!" 11.1.1. I 1' v 'I

    

1.78

 

 

1.76 -

1.74 .

1.720 0:: 1 1:5 5 2:: s
Iteration, 71 (samples) “0‘

(i) The estimate &,(n). (a) shows the first 100 samples and (b) shows the
samples for n 6 [101, 30000].

51

 

 

true is dotted
estimate is solid

 

 

 

 

 

 

-10 I- u
-15 L. .
-m a n a 1_ 1 a A 1 M
0 10 20 30 40 50 60 7O 80 90 100
Iteration, 11 (samples)
£074 7 T
-O.‘76 ’ s
-0.78 l .,

   

02

Illillllld.k.luhl.Is-J Ids—1 _111‘. I‘I .-
11(11'101'07'1”: ‘-

| l
.1

 

'0.“ "
-0.88 -
.0. A 1 j. a a
90 0.5 l 1.5 2 2.5 3

 

Iteration, 11 (samples) 11104

(ii) The estimate 62(n). (a) shows the first 100 samples and (b) shows the
samples for n E [101, 30000].

Figure 3.2: The estimates produced by the SM-PWO or the SM-WRLS algorithm for
an AR(2) model with white noise disturbance (i) 61(11) (ii) 6:01).

52

 

 

 

 

 

 

lo. I _
10 I ‘
3,1 10° I ‘ II .
.1... ‘1 i‘ ' ‘ I 1 I
l I 1 : ] ] I . I) I z 1 ‘1 .
11:11» ,1 1; .1
1 i 1 1 l I ; l ( . z !
O 0.5 l 1.5 2 2.5 1'
Iteration. 11 (samples) no-
0)
IO.

K(n) 10- g
10‘ i
10° i I !
10-‘0 0.: , 1.: 2 3.: J

Iteration, n (samples) no.
(ii)
10‘
IO.

 

 

O 0.5 1 1.8 2 3.8 I

Iteration, 71 (samples)

(1'17)

Figure 3.3: The values of some parameters that are used in the SM-PWO al-
gorithm in the identification of an AR(2) model with white noise disturbances

(a) 4.: (0)7201) (iii) 6(a).
53

 

  

g 111"“ um“ Illll' num IIIII'

I
u

Iteration, n (samples)

(2')

 

 

K0?) :0-

i

 

 

 

0.5 l l.’ 2 2.,

I

H

9. “ll- ln_11u- llfl- Ill]- All
-

Iteration, n (samples)

(ii)

 

C(n) ,0-

 

:o-no 0.: 1 1.: a 3.3 a
310‘

Iteration, 7: (samples)

(1'11)

Figure 3.4: The values of some parameters that are used in the SM-WRLS al-
gorithm in the identification of an AR(2) model with white noise disturbances

(i) A; (ii) x(n) (iii) C(n).
54

01.

(i)

 

a1

-10 -

 

-Se

 

 

 

 

 

10

20 30

50

6O 7O 8O

Iteration, 71 (samples)

90

100

 

1 .76

1.72 I
O

0.5

l

_1

1.5

1 l , . . . _. _
”'lll ('rl'il inml .-.' ll).

Iteration, 71 (samples)

55

 

3
1:104

The estimate &I(n). (a) shows the first 100 samples and (b) shows the
samples for n E [101, 30000].

 

 

 

02 '5 L . ‘
true 18 dotted «
estimate is solid

 

 

 

 

 

-10 . a
-15 n -1
-20 1 A A A A 1 L A L

O 10 20 30 4O 50 60 7O 8O 90 100

Iteration, n (samples)

 

'0-74 V v 1 r
-O.76 l ..
'0078 l I -'
02 ‘
-O.8 .

l

l I ‘II

m 4 ll ‘ k. It I 8- Id —I L I‘. ‘l .—
.03211H ‘i'l ’ '1 h 1: .1, .l_ '11- l . .

 

 

-o.s4 ~
-0.86 ~
70.88 .
'0‘90 0.5 1 1.5 2 2.5 3
310‘

Iteration, n (samples)

(ii) The estimate 62(n). (a) shows the first 100 samples and (b) shows the
samples for n 6 [101, 30000].

Figure 3.5: The estimates of an AR(2) model with white noise disturbances us-
ing the SM-PWO that uses an upper bound 3.. = 5 on the optimal weights ,3;

(i) C“u(n) (ii) 62(71)-

56

A"

 

l
|

 

l 1.5

 

Iteration, n (samples)

 

 

 

 

(I)
101 a
7c(n) ‘°‘ 5 E
l , I
too ‘ i l 5:1
xo-Io 0., 1 1.: a 2.5 II
Iteration, n (samples) “0‘
(ii)
10‘
10°
C(n)

 

 

0 0.3 I 1.3 2 2.5 3

:10.

Iteration, 1: (samples)

(iii)

Figure 3.6: The values of some parameters that are used by the SM-PWO algorithm
that uses an upper bound fl. = 5 on the optimal weights in the identification of an

AR(2) model with white noise disturbance (1') 3; (ii) 76(n) (iii) 6(11).

57

 

true is dotted
estimate is solid

 

 

 

0.0.0 .D-D-C-O-I-0.0.0-0-0.t.0.0-..

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.2.5 1 r L r L . . L
o 10 20 30 4o 50 60 7o 80 90 100
Iteration, n (samples)
-1.4 . . . , . .
4.45 + l
01 -1.5 J- 4
-l.55H I] ——-\___-
-L6~ ..... 4 -----------------------
r‘
-1.65 r- l «-
-l.7 - -]
-1.75

 

 

 

o robozobosobombosooosooovooosooosoooroooo
Iteration, n (samples)

(2') The estimate 61(n). (a) shows the first 100 samples and (b) shows the
samples for n 6 [101, 10000].

58

 

 

 

 

 

 

 

 

 

 

 

0‘“ d
02 '0’5 h - - _ _ ”l
1 .. \J - q
-15 - true is dotted -
estimate 18 SOlld

-2 n -4
2.5 ~ _

-3 1 n a 1 1 n n A P

o 10 20 3o 40 so so 70 so 90 100
Iteration, n (samples)
-o.4 ~ .
-O.5 r- -
02
0.6% .
-0.7 h— ................................................................................................... :1
-0_8 r- u
-09 I I J i -1
Q
-1 r- . . _
'0

 

 

 

orooozoooaooo4ooosoooeooo7ooosooomooroooo
Iteration, 12 (samples)

(ii) The estimate &2(n). (a) shows the first 100 samples and (b) shows the
samples for n 6 [101, 10000].

Figure 3.7: The'estimates produced by the SM-PWO or the SM-WRLS algo-
rithm in the identification of an AR(2) model with colored noise disturbance

(i) at1(71) (ii) (320%)-

59

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

:00. , - fl
:0"
A;
10'
30¢
tot
‘°‘0 1:000 2000 3000 0000 5000 0000 1000 0000 9000 10000
Iteration, 71 (samples)
(0
10‘ f f r
10“ i
rc(n) to. I
103
:0-
1‘"‘0 1000 2.000 3030 4000 3030% 7000 0000 0000 10000
Iteration, 12 (samples)
(ii)
109 . . - - - - - fi
10. '- a:
10- - -
10. I- .1
C(71) ‘0‘ .
10" d
10-0
:0»- l l r '
1"'“0 xémfiosfioaoiosokoohwmfiaum

 

Iteration, 12 (samples)

(iii)

Figure 3.8: The values of some parameters that are used by the SM-WRLS al-
gorithm in the identification of an AR(2) model with colored noise disturbance

(i) A; (it) 5(a) (iii) C(n).
60

 

IO. - v r - - v T

6. ‘0.
u

30.

10"

 

 

 

 

 

 

 

 

’
L111

 

 

 

 

 

 

.- A - .* + _
‘0 O 1000 2000 30“! 4000 5000 0000 1-000 0000 9000 10000

Iteration, n (8311113133)
0’)

30’ f

 

B(n) ‘°'

10'

 

 

10.

 

.1
d

 

, - r - - - , .,___,I
“"0 10002000300040003000000010000000000010000

Iteration, 11 (samples)
(55)

10. - v v - - v f

 

10‘
100
IO"

(7(n) u...

10“

 

10"

10"

 

10'.

 

- . - - - A - 1
10" -

Iteration, n (samples)

(as)

Figure 3.9: The values of some parameters that are used by the SM-PWO al- I
gorithm in the identification of an AR(2) model with colored noise disturbance

(1') fl: (ii) E(n) (“051")
61

 

-O.5 r-

true is dotted

0, estimate is solid

d

 

 

-l.5 -

 

 

-2-

 

 

 

 

-2.5 1 1 . . r r . .
o 10 20 30 40 50 so 70 so 90 100
Iteration, n (samples)

 

'1.45 r r r r ' t r

-. ‘_____-I
01 ISSIJ‘fl

-l.6 .,.....

 

 

 

 

 

 

 

 

 

 

-l.65

I

 

'1.7"' q

 

 

 

 

 

'1‘750 1000 zooo 3000 4000 5000 6000 7000 0000 900010000

Iteration, 7: (samples)

(2') The estimate 61(n). (a) shows the first 100 samples and (b) shows the
samples for n 6 [101, 10000].

62

 

 

 

 

 

 

 

 

 

 

 

 

 

0.5 a e
0 true is dotted
estimate is solid
05 - ..
02 -- ....... ..........................
-1 I- I \J " a
4,5 . .
.2 I d
-2.5 r-
'30 To 20 30 4b 50 60 70 so 90 100 3.
Iteration, n (samples)
'0‘ "' u]
-0.5 ~ 4
.06 +
02
-o.7 - """""""""""""""""""""""""""""""""""""""""""""""""""""""""" 1
-0.s - -
0.9 1 d
-1 u- .1

 

 

 

010002000300040005000600070000000900010000
Iteration, 12 (samples)

(ii) The estimate 6:03). (a) shows the first 100 samples and (b) shows the
samples for n e [101, 10000].

Figure 3.10: The estimates of an AR(2) model with colored noise disturbances us-
ing the SM- PWO that uses an upper bound 0. = 5 on the optimal weights ,6;

(0010') (ii) “2(a).

63

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.8 ' - w - - - - ~
‘ d
3., ..
5: . .
3.3 .1
2 -4
1.5 ..
1 -
°"' Ill 1 l l * . ‘
0° 1000 2000 3000 4070 3000 0000 1000 0000 0000 101100
Iteration, n (samples)
(1')
30 f
2, I- .1
2(a) 3°. 4
IS F- ‘ u:
10 I- d
s [ I l l J
J __I
oo 1000 2000 1000 4000 5500 0000 W100
Iteration, 1: (samples)
(ii)
10‘ f f - - v r v f
100
~ 10d
C(n) 104 '
10".
10-
30"
10" b -I
10‘ ‘—_

 

 

n - - - g I . .
O 1000 3000 3000 4000 3000 0000 1000 0000 0000 10000

Iteration, n (samples)
(iii)
Figure 3.11: The values of some parameters that are used by the SM-PWO algorithm
that uses an upper bound 0,, = 5 on the optimal weights in the identification of an
AR(2) model with colored noise disturbance (i) ,8; (ii) 2(a) (iii) 6(a).

64

 

Chapter 4

Conclusions
and Further Work

 

4.1 Conclusions

This research has focused on a certain class of OBE algorithms that is used to identify
the parameters of linear systems or signal models based on a priori information about
the pointwise “energy bound” of the error sequence. This class of algorithms employs
a data selection technique which is based on finding an optimal error minimization
weight that results in reducing the volume of the ellipsoid which contains the true

parameter vector.

4.1.1 Convergence Study of the Ellipsoid

The first achievment of this research was the study of the convergence behavior of the
ellipsoid under various types of disturbances, for the class of OBE algorithms which
implements the volume optimization criterion. One algorithm in this class, namely
the SM-WRLS, has been tested for the convergence of the ellipsoid under persistently

exciting white and colored noise and non-persistently exciting colored noise. It has

65

been shown that a non-p.e. noise will cause the ellipsoid to degenerate at least from
one of its dimensions. Moreover, the algorithm stops accepting data after a very
short time due to the lack of innovation in the data. For a p.e. colored noise, it has
been shown that the ellipsoid can not shrink to a point and it actually converges to

a non-trivial limiting set.

4.1.2 Development of the SM-PWO Algorithm

The second achievment in this research was the development of a new OBE algo-
rithm named the set membership past weight optimization algorithm (SM-PWO).
The SM-PWO is based on the volume Optimization criterion and it provides identical
estimates of the parameters to the estimates produced by the SM-WRLS. However,
the variables employed by the SM—PWO are much more numerically stable com-
pared to their counterparts in the SM-WRLS. This has a great advantage when the
algorithm is to be implemented on a finite-word processor (in particular a 16-bit pro-
cessor). The development of the SM-PWO was based on a new strategy for assigning
the minimization weights. This startegy assigns one weight to the present incoming
datum and another weight to the whole history of the data. When the two sequences
of weights are considered and taken to be independent, then it has been found that
there exists an infinite number of optimal weights that can achieve the same reduction
in the volume of the ellipsoid. The SM—WRLS and the SM-PWO are the result of two
special cases of the above procedure. In the SM-WRLS, only the weight associated
with the new incoming datum is considered while in the SM-PWO, it is the weight

associated with the whole history of the data that is considered.

66

 

4.2 Further Work

The convergence behavior of the ellipsoid in the OBE algorithms still needs to be
further investigated. Theoretical proof of the convergence of the ellipsoid has not yet
been established. It is of a great interest to find the non-trivial limiting set to which
the ellipsoid converges in the case of colored noise.

The optimization criterion employed by the OBE algorithms results in an “ellip-
soidal” region which is too conservative compared to the polytope. The development
of an optimization criterion that is based on a weighting strategy that can provide

an ellipsoid which tightly bounds the polytope is very useful.

Marwan M. Krunz
East Lansing, Michigan
June,1992

 

67

Appendix

Appendix A

Persistency of Excitation

 

Definition 2 A scalar input signal {u(k)} is said to be weakly persistently exciting

of order m if

N Pu(k+m)-
. 1 .
pI>AleNI§ : '[u(k+m) U(k+l)]>0 (A1)
u(lc+1)

 

 

where p > 0.

Lemma 4 A stationary input {u(k)} is weakly persistently exciting of order m if its

two-sided spectrum is nonzero at m points (or more).

Example: Cosine Input

Let the u(k) be the following random process:

u(k) = ficos(wok + ('9), (.00 75 (2n +1)7r (A2)

where ('3 is a random variable uniformly distributed on [0,21r). Then

Ru('r) = 0030207 (A.3)

68

 

Therefore, u(k) is persistently exciting of order '2. This can be further seen by

 

b

1 cos (.00 cos 2am

cos we 1 cos wo

 

cos nwo cos (n — 1)wo

exp (jwo) exp ("jwol

exp (2ij) exp (-2J'wo)

exp (J'(n +1)wo) exp (-J'(n +1)Wo)

Thus rank(R) = 2.

cos nwo

cos(n — 1)wo

cos we 1
exp I "jwol
eXPUwol

 

 

exp(—j(n+1)wo)

6Xp(j(n +1)wo)

 

69

, Appendix B

Proof of Theorem 1

 

Multiplying (3.12) by the quantity [flnF-IUL — 1)0(n — 1) + A,,:u(n)y(n)], then
fin) [fln‘fi"(n —1)é(n — 1) + A.z(n>y(n)]

 

_1_ A,,fin —1)z(n)mT(n)F(n — 1)] _
Bu Ané(n) ‘l” (in

[new -1)é(n — 1) + malt/(12)]

[T’m- l)—

 

 

 

 

 

. AnFn—lx(nc7n0n—l) A,,~

= 0(n — 1) — ( A3602) + (5n) ( + EPM —1):c(n)y(n)
A3. F<n - 1)z(n)mT(n)~(n — 1)m(n)y(n)

’ T. A. ~(n) + a.

= 9( _1) + ainfin —1)z(n)m"(n)é(v: - 1) + 50.1502 —1)x(n)y<n)
fln(AnG(n) + B.)
+ A3750! - 1)=v(n)y(n) -A%G(n)fi(n - 1.)z(n-)y(n)
3.0.602) + 5..)

. A,,P(n — l):c(n)e(n,9(n — 1))

— 9(n—1)+ AnC(n)+fln (B.l)

consider (3.9) and substitute for F(n) by (3.12),

Now

i.

. ~ A,, ~ A,,]?(n — l):c(n)a:T(n)T’(n — l)
9 = — — — — .. -
(n) B(n 1) + 5n P(n 1) AnGIH) + [3n

 

70

a:(n)€(n,0(

 

 

n — 1))
= 9(n __ 1) +113? [3.1302 —/31):(:):(n)0(n — 1))
= 9(n _1)+ “P(n —;n):(::22;f(n "1)) (8.2)
comparing (13.1) and (3.2), then
em) = 13(1)) 13.?sz — 1)é(n - 1) + mum/(n) (8.3)

Now consider the left hand side of (3.17),

we — é<n —1))T'I3“(n — 1);).(9 — (“9(n —1))+ Ana/(n) — 07mm)?

snoTfi“(n — 1)9 - 23,9779“(n —1)é(n — 1)

+HJWn—HF”m—IMM—I)
+ Any21n)— 21.y(n)0"z(n) + A.(0Tz(n))2
= snoTfi'Rn — 1)0 + 1407202))?
— 20’ [M402 -1)é(n — 1) + A.m(n)y(n)]
+ fin9T(n —1)‘fi“(n -1)é(n — 1) + 1.1/2(1))
= 3,97?er — 1)!) + An0T2:(n)a:T(n)0 — 20TF"(n)é(n)
+ 5.6T(n —1)F"(n -1)é(n - 1) + 1.1/”(22)
= 0T(fl.F"(n — 1) + A,z(n)zT(n))o — 207‘?"(n)é(n)
+ 97(n)fi“(n)é(n) — éT(n)fi"(n)é(n)
+ 3.9% -1)‘13"(n -1)é(n — 1) + 1.y’(n)
.—_ oTF"(n)o — 207T:"(n)é(n) + éT()z)'15"(n)é(n)

— 97(n)fi“(n)é(n) + 5.197(1) —1)F"(n —1)é(n — 1) + A,,y2(n)

71

= (0 — é(n))"'f>“(n)(0 - 002)) — 6‘1 (n)P (n)é<n)

~—1

+ 73.9%: — 1)P (n —1)é(n — 1) + 1.4/2(7),) (8.4)
Then (3.17) becomes,

(0 — é(n))"i5"(n)(0 - 9(n)) s an): - 1) + m. — [1.312110

— 61%)]: (n)é(n) + 8.9% _ 1)P (n _ l)9(n — 1)
So for the theorem to be true, we must prove that,

an) = fink(n—1)+An7n- [1.y2(n)—6T(n)‘fi"<n)é<n)

~—

+ snéTm— 1)P l(n—1)é(n— 1)] (8.5)
Consider the last term in (8.5)

1.2/fin) = A.(e(n.é(n —1))+ xT(n)é(n — 1))”
= A,,52(n,6(n —1))+ 2A,,e(n,é(n — 1))mT(n)6(n — 1)
+ 1.(zT(n)é(n —1))2 (8.6)
e (n)P (n)i)(n) = [9702— 1) +An5(n,0(n— 1))zT(n)‘13(n)] ‘13"(n) [6(n —' 1)

+ 1,502,002 — 1))?(n)z(n)]

6T(n -1)fi"(n)é(n — 1) + 2A,,e(n,6(n —1))zT(n)é(n — 1)
+ 13,302,902 — 1))zT(n)fi(n)z(n)

= 9702 — 1) [af‘m -1)+ 1.x(n)m7(n)] 9(n — 1)

+ 2A,,e(n,6(n — 1))zT(n)é(n — 1)

+ 13,5202, (9(n — 1))zT(n)fi(n)z(n)

72

fl

= éT(n -1)8,,T9“(n —. l)0(n — 1)
+ A,,0T(n — l)z(n)a:T(n)6(n — l)
+ A3,52(n,0(n - 1))zT(n)?(n)m(n)

+ 2An€(n,0(n —1)):cT(n)6(n — 1) (8.7)

From (B6) and (8.7),
1.3/20) — éT(n)fi"(n)é(n) + 3.6% —1)F"(n — 1)éT(n - 1)

= An52(n,6(n — 1)) — A§52(n,0(n — 1))mT(n)?(n)m(n)

= A,,52(n,0(n — 1))(1 — AnxT(n)fi(n)z(n))
T’(n — l)
13..

a.)

 

= An€2(n,0(n - 1)) [I - Aan(n)(

 

_fifim -1)z(n)zT(n)fi(n — 1)
It. 8,. + 1,602)

_ 2n‘n— _A_,, flné(n)
_ A,,e( .9( 1))]1 flnlfin+AnC(n)]l

 

Anfln€2(naé(n _ 1))
- fl. + A5902)

 

From (3.8), (8.5), and (3.18) the theorem is proven. Cl

 

73

 

Bibliography

[1] L.V.R. Arruda and G. Favier, “A review and a comparison of robust estima-
tion methods,” Proc. 9‘h IFAC / IF ORS symp. on Identification and System

Parameter Estimation, vol. 2, pp. 1027-1032, Budapest, July 1991.

[2] B.R. Barmish and J. Sankaran, “The propagation of parametric uncertainty via
polytopes,” IEEE Trans. Automatic Control, vol. AC-24, pp. 346-349, 1979.

[3] DP. Bertsekas and LB. Rhodes, “Recursive state estimation for a set-
membership description of uncertainty,” IEEE Trans. Automatic Control, vol.
AC-16, pp. 117-128, 1971.

[4] F .L. Chernousko, “Ellipsoidal bounds for sets of attainability and uncertainty in
control problems,” Optimal Control Appl. Methods 3, pp. 187-202, 1982.

[5] P.L. Combettes and H.J. Trussell, “Stability of the linear prediction filter: A set
theoretic approach,” Proc. IEEE Int. Conf. Acoust., Speech, and Signal Process.
’88, New York, vol. 4, pp. 2288-2291, 1988.

[6] P.L. Combettes and H.J. Trussell, “General order moments in set-theoretic esti-
mation,” Proc. IEEE Int. Conf. Acoust., Speech, and Signal Process. ’89, Glas-
gow, vol. 4, pp. 2101-2104, May 1989.

[7] P.L. Combettes, Set Theoretic Estimation in Digital Signal Processing (Ph.D.
Dissertation), North Carolina State University, Raleigh, 1989.

[8] S. Dasgupta and Y.F. Huang, “Asymptotically convergent modified recursive
least squares with data-dependent updating and forgetting factor for systems
with bounded noise,” IEEE Trans. Information Theory, vol. IT-33, pp. 383-392,
1987.

[9] J.R. Deller, Jr., “Set membership identification in digital signal processing,”
IEEE ASSP Magazine, vol. 6, no. 4, pp. 4-20, Oct. 1989.

74

[10] J .R. Deller, Jr., “A ‘systolic array’ formulation of the optimal bounding ellipsoid
algorithm,” IEEE Trans. Acoust., Speech, and Signal Process., vol. 37, pp. 1432-
1436, Sept. 1989.

[11] J.R. Deller, Jr., “Toward the use of set-membership identification inefficient
training of feedforward neural nets,” Proc. 1990 IEEE Int. Symp. Circuits and
Systems, New Orleans, vol. 3, pp. 2041-2044, 1990.

[12] J .R. Deller, Jr. and T.C. Luk, “Linear prediction analysis of speech based on set-
membership theory,” Computer Speech and Language, vol. 3, no. 4, pp. 301-327,
Oct. 1989.

[13] J.R. Deller, Jr. and T.C. Luk, “Set-membership theory applied to linear pre-
diction analysis of speech,” Proc. IEEE Int. Conf. Acoust., Speech, and Signal
Process. ’87, Dallas, vol. 2, pp. 653-656, 1987.

[14] J.R. Deller, Jr., M. Nayeri, and S.F. Odeh, “System identification using set-
membership-based signal processing,” IEEE Proc. (in review).

[15] J .R. Deller, Jr., M. N ayeri, and M.S. Liu, “Unifying the landmark developments
in optimal bounding ellipsoid identification,” (in review).

[16] J .R. Deller, Jr. and S.F. Odeh, “Implementing the optimal bounding ellipsoid
algorithm on a fast processor,” Proc. IEEE Int. Conf. Acoust., Speech, and Signal
Process. ’89, Glasgow, vol. 2, pp. 1067-1070, May 1989.

[17] J .R. Deller, Jr. and S.F. Odeh, “SM-WRLS algorithms with an efficient test for
innovation,” Proceedings of the 9‘“ IFAC / IF ORS Symp. on identification and
System Parameter Estimation, vol. 2, pp. 1044-1049, Budapest, July 1991.

[18] J .R. Deller, Jr. and GP. Picaché, “Advantages of a Givens rotation approach to
temporally recursive linear prediction analysis of speech,” IEEE Trans. Acoust.,
Speech, and Signal Process., vol. 37, pp. 429-431, March 1989.

[19] J .R. Deller, Jr. and D. Hsu, “An alternative adaptive sequential regression al-
gorithm and its application to the recognition of cerebral palsy speech,” IEEE
Trans. Circ. and Syst., vol. OAS-34, pp. 782-787, July 1987.

[20] Feron, M.L, “Membership set system identification with pulse train input,” M.S.
Dissertation, Illinois Institute of Technology, Chicago, 1982.

[21] G. Fiorio, S. Malan, M.Milanese, and A. Vicino, “Guaranteed specification con-
trol design of inerial platforms for a high accuracy calibration device,” Proc. 29‘“

IEEE Conf. on Decision and Control, Honolulu, 1990.

[22] E. Fogel, “System identification via membership set constraints with energy con-

strained noise,” IEEE Trans. Automatic Control, vol. AC-24, pp. 752-758, 1979.

75

[23] E. Fogel and Y.F. Huang, “On the value of information in system identification
— Bounded noise case,” Automatica, vol. 18, pp. 229-238, 1982.

[24] Y.F. Huang, “System identification using membership set description of system
uncertainties,” MS Thesis, University of Notre Dame, 1979.

[25] SC. Huang and Y.F. Huang, “Learning algorithms for perceptrons using back-
propagation with selective updates,” IEEE Control Systems Magazine, pp. 56-61,
Apr. 1990.

[26] W. Kahan, “Circumscribing an ellipsoid about the intersection of two ellipsoids,”

Canad. Math. Bull. 11 pp. 437-441, 1968.

[27] K. Keesman, “Robust identification and prediction for output-error models,”
Proc. of the 9’” IFAC / IF OBS Symp. on Identification and System Parameter
Estimation, vol. 2, pp. 878-882, Budapest, July 1991.

[28] R.L. Kosut, “Adaptive robust control via parameter set estimation,” Int. J.
Adaptive Control and Signal Processing, vol. 2, pp. 371-399, 1988.

[29] J.M. Krause, G. Stein, and RP. Khargonekar, “Robust performance of adap-
tive controllers with generally uncertain structure,” Proc. 29‘“ IEEE Conf. on
Decision and Control, Honolulu, 1990.

[30] L. Ljung and T. S6derstr6m, Theory and Practice of Recursive Identification,
Cambridge, MA: MIT Press, pp. 14-15 & Sect. 2.2.1., 1983.

[31] M. Milanese and G. Belforte, “Estimation theory of unknown but bounded errors:
Linear families of models and estimators,” IEEE Trans. Automatic Control, vol.

AC-27, pp. 408-414, 1982.

[32] M. N ayeri, J .R. Deller, Jr., and M.M. Krunz, “Convergence and colored noise is-
sues in bounding ellipsoid identification,” Proc. IEEE Int. Conf. Acoust., Speech,
and Signal Process. ’92, San Francisco, vol. 5, pp. 337-340, Mar. 1992.

[33] J .P. Norton, “Identification of parameter bounds of ARMAX models from records
with bounded noise,” Int. J. Control, vol. 45, pp. 375-390, 1987.

[34] J .P. Norton, “Identification and application of bounded-parameter models,” Au-
tomatica, vol. 23, pp. 497-507, 1987.

[35] J .P. Norton, “Recursive computation of inner bounds for the parameters of linear
models,” Intern. J. Control, vol. 50, pp. 2423-2430, 1989.

[36] S.F. Odeh, Algorithms and Architectures for Adaptive Set Membership-based Sig-
nal Processing (Ph.D. Dissertation), Michigan State University, East Lansing,
1990.

76

[37] EN. Pshenichnyy and V.G. Pokotilo. “A minimax approach to estimation of
linear regression parameters”, Engrg. Cybernetics, pp. 77-85, 1983.

[38] F .C. Schweppe, “Recursive state estimation: Unknown but bounded errors and
system inputs,” IEEE Trans. Automatic Control, vol. AC-13, pp. 22-28, 1968.

[39] A. Venot, L. Pronzato, E. Walter, and J.F. Lebruchec, “A distribuation-free
criterion for robust identification with applications in sysytem modelling and
image processing,” Automatica, vol. 22, pp. 105-109, 1986.

[40] A. Vicino and M. Milanese, “Optimal inner bounds of feasible parameter sets
in linear estimation with bounded noise”, Proc. IEEE Int. Conf. Decision and
Control ’89, Tampa, pp. 2576-2580, 1989.

[41] A. Vicino, R. Tempo, R. Genesio, and M. Milanese, “Optimal error and GMDH
predictors: A comparison with some statistical techniques,” Int. J. Forcasting,
vol. 2, pp. 313-328, 1987.

[42] HS. Witsenhausen, “Sets of possible states of linear systems given perturbed
observations,” IEEE Trans. Automatic Control, vol. AC-13, pp. 556-568, 1968.

[43] E. Walter and H. Piet-Lahanier, “Estimation of parameter bounds from bounded-
error data: A survey,” Proc. 12‘” IMA CS World Congress on Scientific Compu-
tation, Paris, pp. 467-472, July 1988.

[44] E. Walter and H. Piet-Lahanier, “Exact and recursive description of the feasible
parameter set for bounded error models,” Proc. 26"“ IEEE Conf. Decision and
Control, Los Angeles, pp. 1921-1922, 1987.

 

77