u .
km”,

 

; ..
3 . .4
. ,. 171,...
£21.; .v. .
I .»
if":

. I

.5

1.3.. a
:5? r

'I‘V.

}1’\.n.n .Eflr
3: . ‘f\

 

 

  

Ema-1,. . if... m3.§...f.._..\._é

 
 

 

 

 

LlB-‘SARY
Michigan State
UniversitL J

 

 

This is to certify that the
dissertation entitled

THE QOBE ALGORITHM: STOCHASTIC CONVERGENCE
ANALYSIS AND APPLICATION TO CLASSIFICATION

presented by
GIHAN MANDOUR

has been accepted towards fulfillment
of the requirements for the

Ph.D. degree in Electrical and Computer
Engineering

‘1 R ADM/[Lu— g4

 

 

Major Professor’s Signature

.l—5- Quj9m{ 02003

Date

MSU is an Affinnative Action/Equal Opportunity Institution

PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/01 c:/C|RCJDateDue.p65-p15

 

THE QOBE ALGORITHM: STOCHASTIC CONVERGENCE
ANALYSIS AND APPLICATION TO CLASSIFICATION

By
Gihan M andour

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Electrical and Computer Engineering

August 2003

ABSTRACT
THE QOBE ALGORITHM: STOCHASTIC CONVERGENCE
ANALYSIS AND APPLICATION TO CLASSIFICATION
By
Gihan Mandour

The quasi-optimal bounding ellipsoid (QOBE) algorithm has potential for applica-
tion and theoretical development in many applications involving estimation of linear
parametric models. QOBE offers superior adaptation, improved accuracy, efficient
use of innovation in the data, improved computational efficiency, robustness to mea-
surement noise and to deviation from the assumed noise model, and a set of feasible
solutions supplementing the single point estimate.

Deterministic convergence analysis of the QOBE algorithm has been investigated
in the literature. However, in many real-time DSP applications the signals to be mod-
eled are approximated as the output from a linear shift-invariant filter whose inputs
are stochastic signals. Therefore, there is a need for stochastic convergence analysis
of an algorithm used in any system parameter identification or estimation to ensure
its proper performance.

This research analyzes the convergence properties of the QOBE algorithm in a
stochastic framework and provides insights into its operation in practical applica-
tions. For stochastic analysis, the innovations and the bounded noise sequences are
modeled as random variables defined on a probability space. Mathematical formula-
tions of theorems proving the almost sure convergence of the central estimator and
that the hyperellipsoidal membership set associated with QOBE cannot converge to
a point set, are constructed.

Simulation studies are performed to show the performance of the QOBE algorithm,

its tracking capabilities, and demonstrate potential uses in classification problems.

Copyright by
Gihan Mandour
2003

To my late father: fulfilling his wish.

iv

ACKNOWLEDGEMENTS

My gratitude goes first and foremost to God. I feel that He has been watching
over me and has blessed me with all the strength to finish up my dissertation.

I would like to deeply thank my dissertation advisor Dr. John R. Deller, Jr. for
all his support, help, and guidance throughout this work. The numerous discussions
we had together broadened my knowledge of many aspects of this field of research
and he had always pointed me towards the correct directions in my research.

I am very indebted to Dr. Hassan Khalil for he has provided me with all kinds of
help, valuable advice and moral support.

I would like to extend my gratitude and thanks to Dr. Michael Frazier and Dr.
Percy Pierre for all their help and guidance.

I owe a profound sense of gratitude and appreciation to my dear husband Tarek
for he has supported me with love, patience, encouragement and strength. To him
and to my lovely daughters, Dina and Noora, I am deeply indebted.

Finally, I am very grateful and obliged for all my family and friends who stood by

my side and provided me with great comfort and compassion.

Table of Contents

List of Tables viii
List of Figures ix

1 Introduction and Background 1
1.1 Introduction ................................ 1
1.2 QOBE Algorithm ............................. 3

6
8

1.3 Review of QOBE Algorithms ......................
1.4 Motivation for the Current Research ..................

2 Stochastic Convergence Analysis of QOBE Algorithm 10
2. 1 Introduction ................................ 10

2.2 Definitions ................................. 1 1

2.3 Persistency of Excitation Condition ................... 14
2.4 Lemmas .................................. 16
2.5 Almost Sure Stochastic Convergence of QOBE ............. 17
2.6 Convergence of the Central Estimator (Independent Noise Case) . . . 17
2.7 Convergence of the Central Estimator (Mixing Case) ......... 25
2.8 Convergence Analysis of the Membership Set .............. 29
2.9 Convergence Analysis of the Membership Set (Mixing Case) ..... 29

3 Simulation Results 43
3.1 Introduction ................................ 43

3.2 Types of Noise Sequences ........................ 44
3.2.1 IID Noise Sequence ........................ 44

3.2.2 Colored Noise Sequence ..................... 52

3.3 Effect of Unsatisfied Conditions ..................... 62
3.4 Tracking Performance of QOBE ..................... 64

4 Application of QOBE in Classification 70
4.1 Introduction ................................ 70
4.2 Classification Using QOBE Algorithms ................. 7O

5 Conclusion and Future Work 81
5.1 Conclusions ................................ 81
5.2 Contributions and Future Work ..................... 82

vi

Appendix

Bibliography

vii

85

87

4.1

4.2

4.3

4.4

List of Tables

The minimum distance between class C and estimates of System 1 and
System 2 along the minor axis .....................
The minimum distance between class C and estimates of System 1 and
System 2 along the major axis ......................
The minimum distance between class C and estimates of System 1 and
System 2 after rotating the major axis of System 2 by 90 degrees . . .
The minimum distance between class C and estimates of System 1 and
System 2 after rotating the major axis of System 1 by 90 degrees . . .

viii

78

78

79

3.1

3.2

3.3

3.4

3.5

3.6

3.7

3.8

3.9

3.10

3.11

3.12

List of Figures

Case 1: Estimators of a1, = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1) with 7,, = 0.96, where 146

points and 223 points were used, respectively, from a total of 3000 points.

Case 1: Estimators of a2, = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1) with 7,, = 0.96, where 146

points and 223 points were used, respectively, from a total of 3000 points.

Case 1: Estimators of a3. = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1) with 7,, = 0.96, where 146

points and 223 points were used, respectively, from a total of 3000 points.

Case 1: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 0.96, where 146 points and 223
points were used, respectively, from a total of 3000 points. ......
Case 2: Estimators of a1... = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7n = 1.04, where 24 points
and 916 points were used, respectively, from a total of 3000 points. . .
Case 2: Estimators of a2. = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7n = 1.04, where 24 points
and 916 points were used, respectively, from a total of 3000 points. . .
Case 2: Estimators of a3, = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 24 points
and 916 points were used, respectively, from a total of 3000 points. . .
Case 2: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 1.04, where 24 points and 916
points were used, respectively, from a total of 3000 points. ......
Case 3: Estimators of a1... = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 27 points
and 374 points were used, respectively, from a total of 3000 points.

Case 3: Estimators of a2, = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 27 points
and 374 points were used, respectively, from a total of 3000 points. . .
Case 3: Estimators of a3... = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 27 points
and 374 points were used, respectively, from a total of 3000 points. . .
Case 3: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 1.04, where 27 points and 374
points were used, respectively, from a total of 3000 points. ......

ix

46

48

48

49

50

50

51

3.13

3.14

3.15

3.16

3.17

3.18

3.19

3.20

3.21

3.22

3.23

3.24

3.25

3.26

3.27

Case 4: Estimators of a1... = -0.1 and a2... = 0.56 convergence using
QOBE for identification of model (3.4) with 7,, = 0.96, where 125
points were used from a total of 3000 points ...............
Case 4: Volume of the ellipsoid in QOBE algorithm for identification
of model (3.4) with 7,, = 0.96, where 125 points were used from a total
of 3000 points ................................
Case 4: The trajectory of the estimators inmodel (3.4) with 7,, = 0.96,
where 125 points were used from a total of 3000 points .........
Case 5: Estimators of a1... = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7n = 1.04, where 26 points
and 845 points were used, respectively, from a total of 3000 points. . .
Case 5: Estimators of a2... = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1), ’Yn = 1.04, where 26 points
and 845 points were used, respectively, from a total of 3000 points. . .
Case 5: Estimators of a3. = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points
and 845 points were used, respectively, from a total of 3000 points. . .
Case 5: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 1.04, where 26 points and 845
points were used, respectively, from a total of 3000 points. ......
Case 6: Estimators of a1. = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points
and 207 points were used, respectively, from a total of 3000 points. . .
Case 6: Estimators of a2... = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points
and 207 points were used, respectively, from a total of 3000 points.

Case 6: Estimators of a3... -—- 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points
and 207 points were used, respectively, from a total of 3000 points. . .
Case 6: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 1.04, where 26 points and 207
points were used, respectively, from a total of 3000 points. ......
Case 7: Estimators of a1. = -0.1 and a2... = 0.9175 and a5. = 0.2601
convergence using QOBE for identification of model (3.7) with 7,, =
1.04, where 115 points were used from a total of 3000 points ......
Case 7: Volume of the ellipsoid in QOBE algorithm for identification
of model (3.7) with 7,, = 1.04, where 115 points were used from a total
of 3000 points ................................
Case 8: Estimators of a1... = -0.1 and a2... = 0.56 convergence using
QOBE for identification of model (3.4) with 7,, = 0.96, where 974
points were used from a total of 3000 points ...............
Case 8: Volume of the ellipsoid in QOBE algorithm for identification
of model (3.4) with 7,, = 0.96, where 974 points were used from a total
of 3000 points ................................

53

53

53

55

55

56

56

57

57

58

58

60

60

61

61

3.28

3.29

3.30

3.31

3.32

3.33

3.34

3.35

3.36

3.37

3.38

3.39

4.1

4.2

4.3

4.4

Case 8: The trajectory of the estimators inmodel (3.4) with 7,, = 0.96,
where 974 points were used from a total of 3000 points .........
Estimators of a1... = 2.0, a2, = -1.48 and a3. = 0.34 using QOBE for
identification of model (3.1) when the PE condition is not satisfied.

Estimators of a1. = 2.0, (12, = -1.48 and a3... = 0.34 using QOBE for
identification of model (3.1) when the UCT condition is not satisfied.
Estimators of a1, = 2.0, a2... = -1.48 and a3... = 0.34 using QOBE for
identification of model (3.1) when both the PE and the UCT conditions
are not satisfied ...............................
Case 9: Estimators of a1, (time-varying parameter with slow abrupt
change) convergence using QOBE and OBE algorithms for identifica-
tion of model (3.8), 7,, = 1.1. ......................
Case 9: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.8), ’Yn = 1.1, and a1, is time-varying param-
eter with slow abrupt change. ......................
Case 10: Estimators of a1, (time-varying parameter with fast abrupt
change) convergence using QOBE and OBE algorithms for identifica-
tion of model (3.8), 7,, = 1.1. ......................
Case 10: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.8), 7,, = 1.1, and a1... is time-varying param-
eter with fast abrupt change ........................
Case 11: Estimators of a1... (time-varying parameter with slow gradual
change) convergence using QOBE and OBE algorithms for identifica-
tion of model (3. 8), 7,,- — 1.1. ......................
Case 11: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.8), 7,, = 1.1, and a1, is time-varying param-
eter with slow gradual change .......................
Case 12: Estimators of a1... (time-varying parameter with fast gradual
change) convergence using QOBE and OBE algorithms for identifica-
tion of model (3.8), 7,, = 1.1. ......................
Case 12: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.8), 7,, = 1.1, and a1... is time-varying param-
eter with fast gradual change. ......................

QOBE central estimator 0, of 01... and 62... of two AR(2) systems repre-
sented by ’+’ and ’0’, respectively .....................
BLLSE estimator of 01... and 02., of two AR(2) systems represented by
’+’ and ’0’, respectively. .........................
QOBE other estimators Q, of I91. and 62... of two AR(2) systems repre-
sented by ’+’ and ’0’, respectively .....................
The direct 256 points FFT spectrum of the impulse response for AR(2).
The upper graph for Systeml. The lower graph for System2. In each
graph: the true parameters (-); estimators along the minor axis Otherl
(o) and Other2 (+); and estimators along the major axis Other3 (D)
and Other4 (..) ..............................

xi

61

62

63

63

66

66

68

68

69

69

73

73

74

4.5

4.6

4.7

4.8

QOBE central estimator 6, of 91,. and 62... of two AR(14) systems rep-
resented by ’+’ and ’0’, respectively ....................
6,,Lsg estimator of 61... and 62... of two AR(14) systems represented by
’+’ and ’0’, respectively. .........................
QOBE other estimators Q, of 61... and 92,. of two AR(14) systems rep-
resented by ’+’ and ’0’, respectively ....................
Final ellipsoids of System 1 and System 2 used for associating class C
to its membership set ...........................

xii

76

77

78

Chapter 1

Introduction and Background

1 .1 Introduction

Many digital signal processing (DSP) applications require parametric signal mod-
els. Linear-in-parameters systems form a broad class of models that has been exten-
sively investigated. Many system identification or parameter estimation techniques
have been developed to estimate the unknown parameters in a linear model.

Set membership (SM) algorithms are used to identify linear-in-parameters signal
or system models of the form

y,, = 63rn+ez (1.1)

in which 0., E Rm is the unknown “true” parameter vector to be identified; {11.3,} is a
sequence of measurable vectors of dimension m; and {5;} is a noise sequence or an
error sequence. SM algorithms have recently begun to find their way into the DSP field
because of their tremendous potential for application and theoretical development in
virtually any application involving estimation of linear parametric models. The basic
idea of the estimation procedure is to provide a set of solutions that are compatible
with the observations 23,, and the disturbance constraint 5;. Thus the estimate is a set

in parameter space rather than a single vector as in the least square (LS) estimation

techniques [1]. In some applications, the center of the parameter set can be used as
a point estimate for the model parameters, while in other applications the entire set
of parameters might be of interest [2]. A widely researched class of SM algorithms
is that involving bounded error (BE) constraints where a pointwise bound on the
disturbance sequence is assumed. The optimal bounding ellipsoid (OBE) algorithms
belong to the class of BE methods. The bounding ellipsoid associated with an OBE
algorithm can be calculated recursively in real time using an algorithm of relatively
low computational complexity. Like all SM methods, the OBE algorithms seek a
membership set in the parameter space which is guaranteed to contain all solutions
that are compatible with the model of the underlying process, the assumptions on
the noise and the observation data.

OBE identification algorithms are of practical use in many real-time signal-
processing applications and have received considerable attention [3]-[16]. With respect
to the conventional recursive methods like recursive least squares (RLS) [1],[2],[17]-
[22], OBE identifiers offer superior adaptation, improved accuracy, efficient use of in-
novation in the data, improved computational efficiency, robustness to measurement
noise and to deviation from the assumed noise model, and a set of feasible solutions
supplementing the single point estimate. The references in [3],[4],[7]-[16],[23]-[38] pro-
vide a broad and current overview of such work.

This research is concerned with a specific SM algorithm known as the quasi
optimal bounding ellipsoid (QOBE) algorithm [39]-[41]. The QOBE algorithm is a
member of the class of general OBE algorithms [10] but its particular structure gives it
properties that yield special application performance and makes it worthy of separate
investigation . QOBE algorithm’s convergence properties have been studied in a de-
terministic framework. The purpose of the present work is to analyze the convergence
properties of QOBE in a stochastic framework, and to furnish an understanding of

its operation in practice through application studies, such as classification problems.

1.2 QOBE Algorithm

QOBE shares most of the motivating principles and algorithmic structure with
the other OBE algorithms; however, it has other geometric and classic least-squares
interpretations that promote its use in potential applications. The name QOBE has
been used in the literature to indicate both the similarities and differences between
QOBE and previous instances of OBE.

The OBE algorithms in general are used to identify a linear-in—parameters discrete-
time model of the form (1.1). One special case that is used extensively in many signal
processing applications and on which we will base our study is the auto-regressive
with exogenous input (ARX) model [2, 18] , in which :1:,, = [y,,_1, ,y,,_,,,u,,,
,u,,_,,]T is the observed data sequence consisting of samples of an observable input
sequence {an} and output sequence {y,,} [13]. In this case m = p + q + 1 in (1.1) and
6. = [a,., ,a,.,b..,b1., ,b,.]7‘.

The OBE algorithm, in general, is based on the assumption that {5;} has a

pointwise energy bound that is known a priori
8:2 s 7,2, for all n (1.2)
At each n, these bounds imply two hyperplanes in parameter space
HI: {9 lyn=6Tx+7n} and H; = {0 |y,,=0T:r-7,,} (1.3)

between which 0. must lie. The intersection of these pairs of hyperplanes over time
forms a polytope in W", which can be shown [10] to be a subset of a hyperellipsoidal

set at time it given by

a, ‘1—3‘ {a |(6—6,,)TC,,(6-6,,) < M} (1.4)

where 1%,, is expressed as
52,, =6ICn6n-l-ZA, (73—3/3) +rso, n=1,2,.. (1.5)
3:1

1

The ellipsoid center, 6’", It", and matrix P,, dr—e-f C; are computed recursively using

 

[9, 10, 42]

G" = Igpn—NL‘n (1.6)
5,, = 3],, — 0,1123" (1.7)

1 finPn—lxnxTPn—l
P" = — P,,_ — n 1.8
an 1 an + :BnGn ( )
6n = gn—I + [BnannEn (19)

art/811572;

1%,, = annn_1+ fin7n - (1.10)

an + flnGn
It is also useful for theoretical purposes to note that Cm the so-called covariance

C11 — anCn-l I finxnxn

Recursions (1.6) - (1.10) comprise the basis for a general OBE algorithm. OBE
algorithms are distinguished from one another by the choices of the positive weighting
sequences {an} and {fin} according to the optimization criterion that minimizes the
size of the set (2,, at each iteration.

In the QOBE algorithm, the scalar K." is minimized at each iteration by letting
fin = An and 01,, = 1, then seeking the optimal An, a strategy first used by Dasgupta
and Huang [4]. Since {an} and {3"} are functions of An, then the optimization

criterion is performed with respect to A" only. The optimal weight for QOBE is

found by solving F,,(/\) = 0 where

 

F,,()\) =a,,)\2+b,,)\+c,, (1.11)

in which

a,, = 73,03,

bn = 2712,01:

c,, = (73—53,) (1.12)
Thus yielding

1 Isnl 6..

A, = — —— — 1 = 1.1
Ga (7.. ) Gn7n ( 3)

where (5, dg [8,] — 7, and the reduced value of 5,, is computed as

Kn = lin_1— 67:16,? (1.14)

Note that a necessary and sufficient test for the existence of the positive root is c,, < 0.
Therefore, the algorithm updates the estimators only when 0,, < 0.

QOBE algorithms are distinguishable by their ability to selectively use the in-
coming data to update the ellipsoid and the central estimator. When the observations
at time n contain no innovation in the sense that they cannot be used to reduce the
size of the set 9,,_1, then they are discarded. This implies that no valid weights can
be found at this instant and thus the effort of updating at this time can be avoided.
Therefore, depending on the properties of the sequence {8?}, QOBE algorithms often

update only 10 percent of the time or less.

1.3 Review of QOBE Algorithms

This section is based largely on the review in the papers by [7]-[12],[14],[23]-
[25],]39],[40],[43]-[46]. In 1968, Schweppe published the first bounding ellipsoid algo-
rithm [23] for estimating the state parameters of a linear dynamic system using noisy
observations. He derived the algorithm under the assumption that both the input
and the observation errors are unknown but bounded. His choice of bounding the
optimum estimate set by an ellipsoid was due to fact that an ellipsoidal approxima-
tion algorithm has certain computational advantages. However, as Scheweppe notes,
this new algorithm was presented with no convergence proof and required impractical
computational loads.

Following the footsteps of Scheweppe, Witsenhausen[43] , and Bertsekas and
Rhodes [24] introduced the SM algorithm using similar assumptions of bounded-
input and bounded-noise. However, Bertsekas and Rhodes showed that SM is similar
in structure and comparable in simplicity to the Kalman-Bucy filter [48] known to be
the best linear estimator for the Gaussian white noise case.

In 1979, Fogel [25], studied for the first time the problem of estimating a mem-
bership set of unknown parameters of a dynamic system. The analysis yielded an
OBE identification algorithm for the ARX model with bounded-energy constraints
on the noise sequence. In a deterministic sense, Fogel has shown that the sequence
of bounding hyperellipsoids asymptotically reduces to a point set (the true model
parameter vector). Fogel’s assertion that the convergence of his algorithm implies
the convergence of the OBE algorithm has remained controversial [7, 9].

In 1982, Fogel and Huang [44] formulated system parameter identification as a
membership-set estimation problem and proposed the first OBE algorithm (FH/OBE)
that employs selective updating to ignore redundant data. Selective updating in
FH/OBE is achieved by using a weighting strategy that assigns a sequence of weights

{q,-} to incoming data points. In the FH/OBE algorithm, a set measure defined on Rm

that reflects the geometric size of the set is defined such that only data points which
can reduce such size of the set are used. If g,- is zero then the new data point contains
no useful information to reduce the set size and thus it can be discarded. The results
of FH/OBE algorithm are comparable to the LS estimation method while achieving
0(m2) computations . However, Fogel and Huang expressed the convergence of their
algorithm only when the observation error is white noise and with known pointwise
upper bounds. This assumption was employed to make use of Fogel’s previous asser-
tion [25] and therefore has rendered some argument about the validity of their proof
[10]-[12],[14].

A new minimization strategy was introduced by Dasgupta and Huang in 1987 [4].
They considered minimization of Kn, a scalar, to facilitate convergence. However, later
Deller et al. [9, 10] questioned the interpretability of the algorithm’s optimization
criterion since minimization of 5,, had no apparent relation to the hyperellipsoid
volume. Dasgupta and Huang proved that their algorithm (DH/OBE) is simple, of
0(m) complexity, and its parameter estimates converge asymptotically to a region
around the true parameter.

Several attempts have been made to implement the minimization strategy of
Dasgupta and Huang within an OBE algorithm that has geometric and least square
interpretations [8],[39]-[40],[45]-[46],[48]. In 1996, Gollamudi et al. [39] presented a
SM state estimation scheme based on the DH / OBE algorithm to recursively estimate
the state of a system with bounded inputs and noise. The algorithm showed significant
performance and computational savings in terms of the mean-square error in the state
estimate. In 1997, the same group of authors [46] introduced a novel formulation of the
linear-in—parameters SM filtering problem and presented an adaptive algorithm named
“SMART”. SMART, the set-membership adaptive recursive technique, was derived
using the SM filtering framework of DH / OBE while implementing the same recursions

as the normalized least mean square (NLMS) algorithm. The technique offered non-

increasing size of the set estimates in the parameter space. In 1997, Nagaraj et al.
introduced the “official” QOBE [40] with its asymptotic convergence properties and
selective-updating capabilities. The algorithm used the same minimization criterion
as the one developed by Dasgupta and Huang and was shown to reduce the percentage
of updates and have excellent tracking performance. The convergence analysis of the
QOBE algorithm for identification and filtering was presented by Deller et al., in 1997
[41]. They showed that QOBE represents a “hybrid” between the set-membership
weighted recursive least square SM-WRLS algorithm and the DH/OBE algorithm
where QOBE implements the same weighting technique as the one used in SM-WRLS
but uses the minimization technique used by Dasgupta and Huang. However, their
convergence analysis was restricted to a deterministic setting. Since then, many
papers have been published by this group of authors and others interested in the
development of the QOBE algorithm and its implementation in many of the DSP
applications [38] , [40]- [4 1] , [45]- [47] , [49]- [50] .

1.4 Motivation for the Current Research

The development of algorithms for recursively identifying the parameters of a
time-invariant dynamic system is widely studied in the literature using two ap-
proaches, the deterministic and the stochastic approach. In deterministic settings,
signals may be defined as those that can be described by a mathematical expression
or that can be reproduced repeatedly [1]. On the other hand, stochastic signals are
defined as representation of random processes that are not repeatable in a predictable
manner and which are identified by the statistical properties of such random processes.
In many real-time DSP applications the signals to be modelled are approximated as
the output from a linear shift-invariant filter whose inputs are stochastic signals such

as stationary white noise. Therefore, there is a need for deriving the stochastic con-

vergence analysis of an algorithm used in any system parameter identification or
estimation to ensure its proper performance.

In this research we analyze the convergence properties of the QOBE algorithm
in a stochastic framework and provide some insights into its operation in practical
applications. For stochastic analysis, y", u,,, and c,, are modelled as random vari-
ables defined on a probability space. Complete analysis and details of the stochastic

convergence for the QOBE algorithm are introduced in the following chapter.

Chapter 2

Stochastic Convergence Analysis of

QOBE Algorithm

2. 1 Introduction

Many researchers, especially the group of Nagaraj, Gallamudi, Huang, Kapoor
and Deller [39]-[41],[45]-[46],[48]-[49], have focused on the development of the QOBE
algorithm, an algorithm that uses a weighting strategy similar to the SM-WRLS [9]-
[12] but optimizes over the scalar A2,, as in the DH / OBE algorithm [4]. These groups
have proved in a deterministic setting that the parameter estimator asymptotically
converges to the “true” parameter vector under certain persistency of excitation (PE)
conditions of the observation sequence {xn}:‘;1 and under infinite visitation (IV) con-
ditions of the true disturbance sequence {5;}:1 of any arbitrary small neighborhood
of its true bounds [51]. The purpose of the present work is to analyze the conver-
gence properties of the QOBE algorithm in a stochastic framework and to provide
some insights into its operation in practical applications.

QOBE features include highly-selective updating, linear complexity in the num-

ber of parameters, and its excellent tracking ability in time-varying environments.

10

Further, since QOBE does not explicitly depend upon the bounding ellipsoid, the
need to assure that 6. remains inside the ellipsoid, which is critical in OBE pro—
cessing, is not important in QOBE. This is another important feature of QOBE for
tracking performance. Finally, the ellipsoidal set associated with QOBE has inter-
esting convergence behavior in practice, which, while seemingly undesirable from a
theoretical point of view, may also benefit tracking behavior.

Deterministic approaches to convergence analysis assume signals to be predictable.
However, for stochastic analysis, yn, u,,, and 5,, are modelled as random variables
defined on a probability space (S, 8‘, P) where S is a sample space, 8‘ is a Borel
o—algebra of subsets of S, and P is a probability measure on 8‘. In an ARX model,
the observation sequence is of the form {:z:,,} (1;: {yn_1, ,y,,_,,,u,,, ,u,,_q}.
For analytical purposes, we will assume that the model is stable, and, if we let
3,, = o (em,u,,,+1, m S n), then (c,, is 8,,_1 measurable.

Recent results for more conventional OBE algorithms in stochastic settings [13,
14] provide us with guiding principles for our present work on analyzing the stochastic

convergence of the QOBE algorithm. They also suggest that the analysis of the QOBE

algorithm in a stochastic framework is feasible following similar lines.

2.2 Definitions

In this section we will introduce definitions that will facilitate the statement and

analysis of new theorems. Most of these definitions are cited from the literature.

Definition 2.1 [2] An estimator 0”, of 0..., is called p. convergent ( convergent in

probability) if for all e > 0
lim P (||6,, — 6.“ > 6) = 0 (2.1)

where H.” denotes any norm.

11

It is be noted that convergence in probability implies weak convergence (convergence

in distribution).

Definition 2.2 [2] An estimator 6,,, of 6,, is called as. convergent (almost surely

convergent) if

P( lim 6,, = 6...) = 1 (2.2)
Equation (2.2) is equivalent to
P(||6,,—6,,|| >6 i.o.)=0 Vc>0 (2.3)

where i.o. denotes infinitely often with respect to n.

From Definition 2.2 it can be seen that as convergence implies p. convergence.
Although s. convergence (sure convergence), defined as lim,,_.co 6,, = 6... [52], is theo-
retically stronger than as convergence, the latter is regarded as the strongest type

of convergence employed in practice and in most of the literature [13].

Definition 2.3 A random sequence {5;} is said to be asymptotically independent if

lim |P ((5: e:- A) n (53,, e B)) — P (a: e A) P (52;, e 8)] = 0

n—ooo

Vi and VA,B 68‘ (2.4)

Recall from (1.2) that in SM algorithms, in general, it is assumed that the noise
sequence{e;} has a pointwise energy bound that is known a priori. Therefore, for

convenience, we will denote c—neighborhoods of the noise bounds as

D? = [in-6m]

D: : {—7na _7n+€]

Definition 2.4 [29] A random sequence {5;} is said to be almost surely uniformly

12

conditionally heavy tailed (a.s. UCHT) if there exits 01 > 02 > 0 and an infinite

subsequence {n,-} C {n} C N such that, with any sufi‘iciently small 6 > 0
(3'1ch(5:6(03UD:)|8‘,,_1)£C'26 Vn€{n,-} (2.5)

Definition 2.5 A random sequence {5;} is said to be almost surely uniformly condi-
tionally tailed (a.s. UCT) if given 6 > 0 there exits a (5 > 0 and an infinite subsequence

{n,-} C {n} C N , such that
P (a; e (D: U D;) 13H) > 5 v n e {71,-} (2.6)

Definition 2.6 A random sequence {5;} is said to be almost surely uniformly tailed
(a.s. UT) if given 6 > 0 , there exits a 6 > 0 and an infinite subsequence {n,-} C
{n} C N such that

P(e; E (DJUD:)) >6 Vne {71,-} (2.7)

It is be noted that UT and UCT conditions are less restrictive than the UCHT

condition.

Definition 2.7 A random sequence {5;} is asymmetrically bounded with as. UCT

condition if given 6 > 0 , there exits a 6 > 0 such that
P (8:6D2|8n_1)26 andP (5:, ED;|3,,_1) =0 Vn

07'

P(8;ED:|S‘,,_1)=O andP(€;ED; |8n_1)26 Vn

Definition 2.8 A random sequence {5;} is symmetrically bounded with as. UCT

condition if given 6 > 0 , there exits a 6 > 0 such that

P (€f,€Dj|S‘,,_1) 251 andP (e;€0:|3n_1)262 Vn

13

Definition 2.9 The term infinite visitation (IV) refers to the condition in which
the true disturbance sequence {5;} visits arbitrarily small neighborhoods of its bounds

infinitely often (i.o.). That is, IV occurs iffor any 6 > 0 [8;] > 7,, — e i.o.

Definition 2.10 The term infinite updating (1U) refers to the condition in which the

QOBE algorithm does not cease updating in finite time.

Definition 2.11 The term infinite nulling (IN) refers to the condition in which any
infinite subsequence say {5:2,}211 of the true disturbance sequence {5;},311 satisfies

< e i.o.

 

 

the condition that for any e > 0 ,

n:
5n),

2.3 Persistency of Excitation Condition

A key requirement for the convergence of any recursive estimator is that the
inputs be sufficiently uncorrelated or persistently exciting (PE) so as to make the
parameters in (1.1) uniquely identifiable. The following definitions of PE appear in

the literature:

Definition 2.12 [29/ A sequence of random vectors, {x,,}, is called persistently ex-

citing (PE’), or omni-directional, almost surely (as) if for any nonsingular cone
K: {xzxzale1+ +amem , det(el, , em)7é0 , a,- >0Vi}
there exits p1 and p2 such that
"lingo ian (23,, E K I 3,,_2) _>_ p1 > 0 (2.8)

and

E (Han | 371—2) _>_ {)2 > 0 V 71 (2-9)

14

Condition (2.8) means that the orientation of x,, is sufficiently varied in a con-
ditional probability sense, while (2.9) means that the magnitude of 23,, cannot be too

small on the average.

Definition 2.13 [2.9] A sequence of random vectors, {xn}, is called PE as. if there

exits p1 and p2 such that

lim infE ($an | SW) 2 p11 > 0 (2.10)
and
EUI$nll I 371—2) 2 P2 > 0 V 71 (2-11)

The fact that E (E (:1:an I 3,,_2)) = E (xan) leads to an equivalent definition

of PE:

Definition 2.14 [29] A sequence of random vectors, {xn}, is called PE as if there

exits p1 and p2 such that

lim infE (xan) 2 p11 > 0 (2.12)
and
E(Il$nll Kin—2) 2 P2 > 0 V n (213)

Definition 2.15 [26] A WSS sequence of random vectors, {xn}, is called PE as. if

there exists p1 and p2 such that

E (xan) 2 p11 > 0 V n (2.14)

and

EUIIUnll I 871—2) 2 P2 > 0 V Tl (2-15)

15

It is to be noted that similar definitions exist in the literature for deterministic

analysis [2, 18, 26].

2.4 Lemmas

The following lemmas are useful in a convergence proof to follow.

Lemma 2.1 [15] Let x,y be random variables. If x is continuously distributed, then
x + y is continuously distributed. If in addition y at 0, then xy is continuously

distributed.

Lemma 2.2 [13] Assume the model (1.1) is a stable ARX model and {u,,} and {5;}
are bounded. If both {u,,} and {5;} are asymptotically independent sequences, and
{u,,} is independent of {5;} , then y,, converges to a continuous random variable as

Tl'—*OO.

It is to be noted that if {u,,} or {5;} or both are continuously distributed, then
the assumptions that {u,,} and {5;} are asymptotically independent sequences and

the independence between {u,,} and {5;} are not required in Lemma 2.2.

Lemma 2.3 [13] Assume that model (1.1) is a stable ARX model, and {u,,} and
{8;} are bounded. If PE holds, both {u,,} and {5;} are asymptotically independent
sequences, {u,,} is independent of {5;}, and the noise bounds are overestimated for
QOBE algorithms, i.e., if there exists an 61 > 0 and an N E N such that V n > N,
7,2, — 5:2 > 61 , then the expected updating interval of the estimator 6,, approaches

infinity as n approaches infinity.

It is to be noted that if {u,,} or {5;} or both are continuously distributed, then
the assumptions that {u,,} and {5;} are asymptotically independent sequences and

the independence between {u,,} and {5;} are not required in Lemma 2.3.

16

 

2.5 Almost Sure Stochastic Convergence of QOBE

White noise has been commonly studied in the analysis of many system iden-
tification and parameter estimation algorithms as well as model structures. In the
following work, we consider cases in which {5;} is white noise, i.e., E (5;) = 0 and
E (5:5?) = 026 (s —— t) where 6 is the Kronecker sequence.

The theorems of as. convergence of QOBE algorithm are introduced and proven
when both the input sequence {u,,} and the noise sequence {5;} are assumed station-

ary and {u,,} is assumed independent of {5;}. For p. convergence, {u,,} and {5;} are

 

not required to be stationary. Furthermore, if {u,,}, {5;}, or both are continuously
distributed, then the conditions for as. and p. convergence can be relaxed.

In [53], it is shown through an illustrative example, how different cross-sequence
dependencies can affect the convergence behavior of QOBE. Fortunately, the depen-
dencies needed for “good behavior” can be easily described in a stochastic framework.

This will be illustrated in the next theorems of as. convergence.

2.6 Convergence of the Central Estimator (Inde-
pendent Noise Case)

Theorem 2.1 Assume that the stationary sequences {u,,} and {5;} are independent.
If PE (2.8) holds, U CT holds, and {u,,} and {5;} are asymptotically independent and

ergodic, then the central estimator of the QOBE algorithm is as. convergent.

Proof: Since PE (2.8) and UCT (2.6) hold, then there exits aninfinite subsequence
{n,} E Z such that for all n E {n,}, (2.6) and

P (an K|8n_2) 2p] >0 a.s.

hold, where K is defined in Definition 2.12 and p] = p1 - c, for some 6 > 0. For

17

convenience we let n replace n, throughout the proof.
Let {5; : n E Z} denote the noise sequence and {u,, : n E Z} denote the input

sequence of model (1.1). Thus we can rewrite (1.1) as

p q
y,, - Z a,y,,_,- = Z b,u,,_,- + 5; (216)
j=l '=o
Let
I r q
w,, (é Z bjun_j (2.17)
:0

and v,, = w,, + 5;. Then (2.16) becomes

yn = Zhn—jvj (2.18)

where h,, is the infinite impulse response, y,,, if v,, is set to a Kronecker delta function.
By Lemma A.1 {w,,} is stationary and ergodic. Also, by Lemma A.2 {u,,} is stationary
and ergodic.

Let {1),} be a sequence of time intervals of length 1V1 over which the algorithm does
not update its estimator. This willbe helpful in asserting a contradiction later on.

Therefore, for each k = 1,2, - - - ,K
0 “=e‘ [6(1) 6(2) Bonn

is a constant vector for all n in each 1),. From (1.7) we have

5,, = y,, — 6,1113,
: yn — 20(ilyn-i
i=1
5,, = — Z6(i)y,,_,- , where 6(0) déf —1 (2.19)
i=0

18

From (2.18) and (2.19) we have

m n—i

5,, = — Z Z 6(i)h,,-,-_,~v,-

i=0 j=—oo

Changing the order of summation, we get V n > m

“—2 ’Uj "256W n— ,‘_J'— E ’Uj :0(2)hn_i_j
j: —n—— -m+1 i=0 j=—oo i=0
Let p = n —j, then
p 00 m
5,, = — n: v,,_.,, :0( 6(i ,—2 v,,_,, 2 6(i)hp_,
p=CIl i: p=m i=0
5n = —Z—:lvn— 1291" gvn-pg2

p20

where g1 and 92 are mapping functions independent of n, hence,

5.71 = .9 (via a vn—l a ”rt—2 a ' ' ) (220)

where g : Rk —> IR is measurable and independent of n. Thus, by Lemma A.1 {5,,} is

stationary and ergodic as M —) 00.

For each I: = 1,2, - -- ,K, it follows from (1.12)

c,,=7,2,—5,2, >0VnEI;c

and from (1.7)

T
= y" _- 671—13371

Since

T
€2=yn—6$n

*

19

then we get by letting and—3} 6., — 6,,

NT
5,, - 621—an xn
and thus
~71"
5,, = 52+ 19,,_1 x,, (2.21)

Let A; be the event that 5:, E D; and 5:, x,, 2 0.

Let A; be the event that 5;“, E D: and 5:, x,, < 0.

Let A,, = A; U A; . Note that 5:, x,, is 83-1 measurable.

Also, let 3;, denote the event that A,, occurs at least once in 1),. Then for all n 6 [HI

we have 8;, 6 83-2. Thus since
P (513,, 5 K | 8,,_2) 2 p’, > o as.

then

NT ,
P (971—1 x,, Z 0 I Bk) 2 p1 > p > 0 (2.22)

and

~T ,
P (911—1 113,, < 0 | Bk) 2 p2 > p > 0 (2.23)

I ~T
where p2 2 p2 — 5 for some 5 > 0. Since B), E 8,,_2 C 3%, and 0,,_1 x,, is 3,,_1

measurable, it follows from (2.6) that
~T 6
P (51,5 (DjUD;)I0,,_,a:,,20,Bk) 261>P>0 (2.24)

and

~T
P (5:15 (DjUDg) |6,,_1 x,,<O,B;,) 262>g>0 (2.25)

Since A; and A; are mutually exclusive for sufficiently small 5 , it follows from (2.22)

20

. Isa.”

 

- (2.25) and the definition of symmetrically bounded sequence with UCT in Defintion

2.7, we have that

P(An|Bk) = P (A;|B;.)+P (AllBk)

NT NT
= P (5:,ED;|6,,_1x,,20,Bk)P (6,,_1x,,20|Bk)

~T ~T
+P (5:, E D: | 6n_1x,, < 0,81,) P (911—1 x,, < 0 I 8;.)

Thus,

~T
P (A,,IBk) > P (e;eD;|9,,_,x,20,B.)p

~T
+P (5:, E D: I 6,,_1x,, < 0,Bk) p

> 6 > 0 (2.26)
me (2.26) and the definition of A,, , we have
P (I5,,I>7,,—5IB;,.)_>_P (A,,IBk)>6>O (2.27)
Thus by Theorem Al and (2.27) we have
P (I5,,I > 7,, - 5 to I Bk) =1 as NI —-> oo (2.28)

Therefore, {5"} exhibits IV and thus from (2.21) we have

 

 

~T
5:,+ 6,,_1x,, > 7,, — 5
and so we get
~T
15:11 + 611—1 $11 > 711 'T 6

 

 

21

Since {x,,} is PE, we consider the following two cases:

NT

6,,_1 x,, < 5 for all

 

1. If lim,,_.00 6,, = 6* , then there exists some Ke such that

 

k 2 K, for arbitrary 5 > 0. Therefore I5;I > 7,, — 5 for all k 2 K5 and {5;}

exhibits IV
2. If 11mm.“> 6,, 7é 6* then from (2.21) and the PE condition

~T

 

 

= I5,, — 5:;I > 77 i.o. for some 77 > 0

If we define 6,, = I5,,I — 7,, and 6;“, = 7,, — I5:,| so that 6,, + 6; = I5,,I — I5;I and if
I63] < 321 i.o., then 5:,I > 7,, — 321 i.o. and {5;} exhibits IV. Thus contradiction occurs
and the assumption here is not true. From this argument and from (2.28) and (2.2)

we conclude a.s. convergence of the QOBE estimator. 0

Theorem 2.2 Assume that the stationary sequences {u,,} and {5;} are indepen-
dent. If {u,,}, or {5;}, or both, are continuously distributed random sequences, and

if PE (2.8) holds, UCT holds, and {u,,} and {5;} are ergodic, then the estimator of

the QOBE algorithm is as convergent.

Proof: Continuously distributed {u,,} or {5;} or both implies that Lemmas 2.2 and
2.3 hold without the assumption that {u,,} and {5;} are asymptotically independent
sequences. The theorem can therefore be proved following the same steps as in the

proof of Theorem 2.1. 0

Corollary 2.1 Assume that the stationary sequences {u,,} and {5;} are independent.
If PE (2.8) holds, UT holds, {u,,} is asymptotically independent and {5;} is i.i.d.,

then the estimator of the QOBE algorithm is as convergent.

Proof: Since UT and UCT imply each other with the i.i.d. assumption, and i.i.d.
implies asymptotic independence, then as. convergence follows immediately from

Theorem 2.1. O

22

Corollary 2.2 Assume that the stationary sequences {u,,} and {5;} are indepen-
dent. If {u,,}, or {5;}, or both, are continuously distributed random sequences, and
if PE (2.8) holds, UT holds, {u,,} is ergodic and {5;} is i.i.d., then the estimator of

QOBE algorithm is as. convergent.

Proof: Since UT and UCT imply each other with the i.i.d. assumption, and i.i.d.
implies ergodic, then as. convergence follows immediately from Theorem 2.2. O 3
The following corollary asserts a.s. convergence when the probability distribution I

of the noise sequence {5;} is known.

 

Corollary 2.3 Assume that the stationary sequences {u,,} and {5;} are mutuallty
independent. If PE (2.8) holds, {u,,} is ergodic and {5;} is i.i.d. with uniform

distribution then the estimator of the QOBE algorithm is as convergent.

Proof: For a uniform distribution,

. + - _f_
P(5,, e (D, UD.)) 2 2% > 0

Thus UT holds. By Corollary 2.3, the estimator of the QOBE algorithm is as.

convergent. 0

Corollary 2.4 Assume that the sequences {u,,} and {5;} are stationary and {u,,} is
independent. If PE (2.8) holds, UCT holds, {u,,} is asymptotically independent and

{5;} exhibits IV, then the estimator of QOBE algorithm is as. convergent.
Proof: The statement falls immediately from the proof of Theorem 2.1. 0

Definition 2.16 Let (S, 8, P) be a probability space as previously defined. Let T :
(5,8) —+ (S, 3) be a measurable transformation on (S, 8‘, P), then T is said to be a
“measure preserving” if and only if P(T’1A) = P(A) for all A E 8‘

23

 

We will define the measure preserving transformation (m.p.t.) to be “one-sided
shifter”
T(vo, v1, . - . ) = (v1, v2, - - - ) where v,- , for all i, is an event defined on the sample space
31 = (a, b) for some real numbers a and b .

P(T‘IA) = P(A) implies that P(T’kA) = P(A) for k = 1,2, - ~-

Thus with S = S? we have

P{('U0,’U1, "' avn—I) 6 Ian} = P{(Uk,vk+1, '°' avn-I-lc-l) E 7871}

for all n and k and n—dimensional Borel sets 6,.

Definition 2.17 Let T be measure preserving on (S, 8‘, P). T is said to be indepen-
dent iffor all A, B 6 3‘, P (A I) T"’°B) = P(A)P(B) for all k E N. T is said to be
“mixing” iffor all A, B 6 8‘, lim;H00 P (A Fl T‘kB) = P(A)P(B).

From Definition 2.14 and since E (x,,xg) is positive definite, an upper bound is
guaranteed on E (:17an) by the stability assumption of the model in (1.1). Also we
note that if {x,,} is mixing then all subsequences of {x,,} are also mixing. Thus if
E(x,,x3:) is bounded below at the points where the updates take place then the PE
condition (2.10) with x,, replaced by x,,k is satisfied.

A key point in the convergence proof is the independence between {5;} and
{51, x,,}. In order to extend the convergence property from independence to mixing
condition we need to modify the definition of x,, in the ARX model since x,, contains
y,,-l, the output at time n — 1. Thus, independency of {5;} is required to remove the
dependency of 5:, and 5:, x,, . Otherwise, x,, can remain unchanged unless an update
takes place and therefore we can apply the mixing condition to show convergence,
provided that for large n the time difference between two updates is large. We proved
convergence before in case of {5;} is independent. We will now prove convergence for

the mixing condition case. So we will use a modified model (1.1) with

24

1B,, :- [yti-‘l ' ' ' ytt‘P utu‘ ° ° ° utr-Ql (229)

where {y,,} and {u,,} are the same as in (1.1) , and {t,} is a subsequence such that

c,,. < 0 and t,- g n < t,+1.

2.7 Convergence of the Central Estimator (Mixing

Case)

Theorem 2.3 Assume {x,,} is either ergodic or mixing. Let {5,‘.‘,} be a noise sequence
and let T be mixing on {S, S}, P}. If the modified model of (1.1) with (2.29) is em-
ployed, PE (2.8) condition holds, UCT condition holds, then the central estimator of

the QOBE algorithm is as convergent.

Proof: Since PE and UCT conditions hold, then there exists an infinite subsequence
{t,} E Z such that for all n E {t,} (2.6) and P(xn E K I 83,4) 2 pl > 0 as. hold,
where K is defined in Definition 2.12.

Following the same argument as in Theorem 2.1, we conclude that {5"} is sta-
tionary and ergodic as M —+ 00, where M is defined in the theorem statement. For
convenience we will replace {t,} with {n} throughout the proof.

Let {1),} be the sequence of time intervals of length M > N over which the
QOBE algorithm does not update its estimator. This willbe helpful in asserting a
contradiction later on.

From (2.21) we have
NT

€;+ 671—1 $1; = 5n
~T

Let A; be the event that 5:, E D; and 6,,_, x,, Z 0
~T

Let A; be the event that 5;“, E D: and 0,,__, x,, < 0

Let A,, “é" A; u A:

25

NT
Note that 911—1 3,, is 83,4 measurable.

Let Bk denote the event that A,, occurs at least once in Ik. Then V n E Ik+1,

Bk 6 831-2.
Since
P(Ltn 6 K. | 371—2) 2 p,l > O as.
then
P<5._1 x. 2 o 13,.) 2 p1 > p > o (2.30)
and
Pd.-. 113,, < 0 I81.) 2 p; > p > 0 (2.31)

Since Bk 6 83,4 C 83.1 and 6: _1 x,, is 8,, _1 measurable, it follows from (2.6) that
~ T 6
P(E;E(D:UD:)|6n_l$nZO,Bk)261>E>0 (2.32)

and

J 5
P(e;e(D;UDj)l 6,,_1:cn<0,Bk)262>;>0 (2.33)

Since A: and A; are mutually exclusive events for sufficiently small 6, it follows

from (2.30)- (2.33) and asymmetrical bounded condition with UCT that

P(AnlBk) =

PAM lBkl+P(A+lBk-)
= P(€;€ D—l 6:_1$nZO,Bk)

P (671—1 $71 2 O I Bk)

~T
+P (E; E Djl 671—1 xn < 0 33k)

~T
P (em 33,, < 0 | 3,.) (2.34)

26

Let k,- = t,- — ti_1 (recall the replacement of t,- by n previously) and define

def

~T
WtH = {9t,—1$t.- 2 0} and Vt, (g {82; E Dg'}

Then Vt, and Wt“, E ‘3 and P(Vti) = 6
By the definition of mixing in Definition 2.17,

lim P (Vt, fl Wig—k

lei—.00

) = P(Vtt) klim P(Wt,_k.) (2.35)

Suppose P (Wu—k.) 75 0, then (2.35) can be written as

 

~ P(‘ftinWti—ki) _ ~
iii“... P(Wt.—k.) ‘ 1.313.“... P (V‘i'W‘i‘k‘)

= P (Va)
Let 0 < 6 < 6 and there exits an N such that
P(Vt.) - 6 < 1’04. | Wz.-~) < P(Vz.) + 5 (2-36)

This inequality holds if no updates take place on the interval [t,~ — N, t,].

27

Now replace {ti} again with {n}, from (2.34) we have

~T ~T
P(AnlBk) = P(E;ED:I 6n_1$n20,Bk)P(0n_1$n20 lBk)

NT ~T
+P (5:; E D:- I 9n_11L‘n < 0 ,Bk) P (0n_1 {En < 0 lBk)

IV

~T

NT
[P(e; e D; ,3.) — §]P(9n_1:r,, 2 0 13,.)

+[P(5; E D2330 —€]P(6n_1113n <0 lBk)

IV

IV

[P(é‘ZEDS UDf,Bk)-€lp
(2.)...
p

From the definition of A,,

IV

P(|€n| >%-6 | Bk)ZP(An | Bk)>5-€P>0
Thus by Theorem A.1 we have

P(Ien|>’yn—ei.o. |Bk)=1aslM—->oo
Thus lenl exhibits IV, and thus from (2.21) we have

 

 

NT
and so we get
~T
*
lenl + 9,14% > 7,, — e

 

 

Since {x,,} is PE, we consider the following two cases:

1. If limnnoo 6,, = 6... , then there exists some K6 such that

 

[P(s;eD; ,Bk)-€]p+ [P(s;eD:,B,,)—g]p

~T

6n_1 32,. < e for all

 

k _>_ K6 for arbitrary e > 0. Therefore lam > 7,, — e for all k 2 K5 and {513,}

exhibits IV

28

2. If limn...oo 6,, ¢ 0... then from (2.21) and the PE condition

~T
612—1 x"

 

= [5,, — 5;| > 77 i.o. for some 77 > 0

 

Ifwe define 6n = lenI—vn and 6; = 7n— IEZI so that 6n+6,‘; = lenl — [5;] , and [6,“ < 321
i.o. then IEZI > 7,, — g i.o. and {5;} exhibits IV. Therefore we have a contradiction,
and the assumption here is not true. From this argument and from (2.28) and (2.2)

we conclude a.s. convergence of the QOBE central estimator. O

2.8 Convergence Analysis of the Membership Set

In optimizing the parameter an, QOBE does not place formal emphasis on the
contraction of the hyperellipsoidal membership set, Q", in the selection and weighting
of data. As a consequence of minimizing h,,, the volume is automatically decreased
at each update, but generally not optimally, unlike OBE algorithm, which optimizes
over the volume of 9,, and under proper data conditions, 6,, —-> 0... asymptotically as
the set 52,, converges to a point. In QOBE, therefore, n" parameterizes the ellipsoid
and has no clear connection to the ellipsoid center 6,,. However, QOBE provides
excellent parameter convergence and faster tracking accompanied by larger ellipsoid
volumes than its OBE counterpart. This is again due to the fact that QOBE becomes

extremely selective of data as its estimator approaches the true parameter vector.

2.9 Convergence Analysis of the Membership Set
(Mixing Case)

Theorem 2.4 Even under the conditions of Theorem 2.3 (leading to the central es-

timator convergence), the volume of the ellipsoid of the QOBE algorithm does not

29

converge to zero ( or in other words the sequence of hyperellipsoidal membership sets

associated with QOBE cannot converge to a point set) in probability.

Proof: Let N’ déf {n E N : cn > 0} so to consider only n E N’ that implies no update
takes place (i.e. 7,2, — 5?, > 0 over a sequence of infinite number of intervals of length
M )

(7n — l5nl) (7n +l51zll> 0

Let us define the sequence {a}:1 to be the sequence over which no update takes

place. This willbe helpful in asserting a contradiction later on.

~T
Since et, = 52+ 9t,—1 23., we have

712-— 5:2.- “ (7t.- + IQ.” (’Yt. — IQ!)

= (71; + Igtil) (Vii -

* ~T
at; + gig—1 mti

 

)>o

> O (2.37)

 

Therefore

 

 

52+ 6t-—l (131'.

I.

7‘1 .—

Thus

72. — 83', > O for all {t.,-} if and only if

~T
52+ ati—l 17“. < flit.‘ (2.38)

 

 

Let us assume that the volume of the ellipsoid of QOBE does not converge to zero
and try to assert that this assumption is true. If the volume of the ellipsoid does not

converge to zero then condition (2.38) must hold. For convenience, we will denote

30

e’— neighborhoods of noise bounds as

D: 2 [771—6] 3771]

D; = l—Vna —7n+€’l

At no update we have

< 7,, (2.39)

 

 

NT
If 6n_1 x,, 2 0 and a; e D; , i.e. (—7,, < e; < —*y,, + 6’) then since 5; is uniformly
distributed, we have

711—6, < [52' <77:

~T
lehl + 011—1 3311 < 7n +

 

 

 

NT
52+ 6n_1 1‘71 < 711

 

 

Same as defined in (2.39), therefore 5; 6 D67. Similar analysis can be repeated to
NT

Show that e; E D: when 0n_1 x,, < 0.

Given 6’, assume {5;} is symmetrically bounded with UCT, which means there exists

6‘, > 0, pt, > 0 such that for all t,

P(E; E D: l 8n_1) > 6t./pt,- and

P(e:i E D; |3n_1)>6t,/p,, as. (2.40)

31

Let there exists M > N, and let {Iki} be the sequence of infinite number of intervals
[n — 1, n — M ] such that no updates take place.
Let A; be the event that 5;", E D; and 5:4 It, 2 0
Let A: be the event that at: E D: and 5:_1 mt, < 0
Let A,,. 92‘ A: u A;
NT

Note that 6,?1 rat, is 83,4 measurable.

Since A: and A; are mutually exclusive events for a sufficiently small 6’, then

P(At.) = PW.) +P(A;t)

~T ~T
P(A..) -—— P(eieD; I ewx..20)P(o.._.x..2o)

NT NT
+P (5;, E D: l 6t.—1 1'“ < O)P(9t'_1 23;, < 0)
NT
Let k, = t,- —— t,_1 and define WtH déf {gm-.1 at... Z 0} and Vt, = {a}; 6 D57}
Then Vt, and I’ve--1 E 3 and P (Va) = 6t,” By the definition of the mixing condition

in Definition 2.17

lim P(l/tiflW,,_,)=P(Vt,)klim P(W,,_k,) (2.41)

ki-ooo i

Suppose P (Wu—k.) is not zero. Then (2.41) can be written as

. P(‘fti n Wti—ki) __ .
klgnoo P(Wti“ki) — kEEnm P(W‘ I Wti—ki)

= P(Vt.)

 

Let 0 < {ti < 6t, and there exists an N such that

lPU/t.‘ l Wti“ki) — P(l/tzll < {ti

32

Therefore

P(Vtzl - {ti < P(W: l ”fir-N) < P(l/t.) +£t.‘ (242)

Note that the inequality of (2.42) holds only if no updates take place on the interval
[t1 — N, t,].
Recall the definition of A,,, and thus we can write
NT ~T
PM...) = P (a; e D; I 61.1 as. _>_ 0) P (9H x 2 0)

NT ~T
+P (a; E D; | Htr1 :13), < 0) P (911—1 3t.- < 0)
From (2.42) and recalling the definition of Vt, and IV,,-N , we get

P(At'.) Z [P (5;, E D; ) — fig] P(5:_1 113:, Z 0)

NT
+ [P (a; e 13:; ) — £1,]P(9,i_1xt, < 0)
me PE condition and from (2.30) and (2.31)
~T
P (Oh—1 1‘". _>_ O) 2 pt.‘ > 0

and
NT
P(61,—133t1 < 0) 2 pt,- > 0

Also, from (2.32) and (2.33) we have

~T
P(e:..e(D.7UD:) I on..20)261./p..>0

and

~T
P (E; E (D; U D?) I 6t,—1$¢1 < 0) Z (Sn/Pt, > O

33

Therefore, we have

and

P(Atz‘) Z [P (5:.- E D67 ) ‘5t1-I Pt.- ‘I' IP (5:.- E D; l — 5a] Pt.-
2 [P (52'. E (D; U 03)) - 511-] pt.-
2 (5t1/Pt1 — 5t.) Pt.-
2 5t.- — 5t1-Pt.
> 0

P(Ati IAti-N)

IV

_ ~T

P 5:: E D; I {Oh—1 (Ett. 2 0} fl flu—N]
: ~T

P {01.4 113:,- Z 0} I I‘M—N]

~T
+ P [5; E D: I {Qty-1:13“ < 0} nAtl_N]

~T
P [{gti—l {Eti < 0} IAti-N]

 

34

IV

’ NT
P e; E D; | {91i-1$z, Z 0} I Aa—NI

 

-~T ~T
P 6t1—1 min" 2 OI PI{9ti—1$t1 Z 0} I Ati—NI
b ~T
+ P [5; E D: {gig-11"“ < 0} I At‘_NI
~T ~T
P Ian—1 xt.‘ < 0] P [{dt,_1 xii < 0} I Ati—N]
~T 2
[P (8;; E D67 ) — gti] {P [an—1 3t, 2 0]}

2
+ [P (ex; 6 D: ) - 4...] {10 I5.-. < OI}

6‘1 _ gtipti

IV

IV

> 0

Thus,

P(AtinAti-N) = P(Ati I Ate—N)P(Ati-N)

2 (5t. " Eupt.) (5t.+N " €t.+N.0t.+N)

> 0

P (An 0 Air-1 (1 ..... r) Ati—N) Z P (An. (7 Ati—N)

_>_ (5;,- "" felon) (5t1+N — €t,+NPt,-+N)

0 (2.43)

V

35

1‘1ng P (Ati+kN fl At.-+kN—1 fl ..... n A“) 2 lim P (At.-+kN fl At;+(k—1)N n ..... n A“)

k—->oo
k

2 [311130 (5t.~+uv — €t¢+leti+lN)

1:1
> 0

In probability, this asserts our assumption that the volume of the ellipsoid does not
converge to zero. Therefore, the sequence of hyperellipsoidal membership sets asso-
ciated with QOBE cannot converge to a point set. 0

Although IU condition is a necessary and sufficient condition for the convergence
of the central estimator in the i.i.d. case, it has not been explicitly proven in the
mixing case. The following theorem is an alternative theorem to Theorem 2.4 asserting
that even if IU is appended as an explicit condition, the volume of the ellipsoid of the

QOBE algorithm does not converge to zero.

Theorem 2.5 With the explicit condition that there exists a sequence {tflf’zl such
that IEtkI > 7% for some positive sequence {Va} appended to those of Theorem 2.4,

the volume of the ellipsoid of the QOBE algorithm does not converge to zero.

Proof: Let N’ d—i-f {n E N : cn < O} and consider only n E N’ that implies that an
update will take place; '73 — 5,2; < 0. Let us define {tfliil to be the sequence over
which IU (infinite update) take place. This will be helpful in asserting a contradiction
later on.

~T
Since et‘. = 52+ 9ti_1 33¢.» we have

’73 _ sf.- : (711‘ + IEtiI) (7h — IEtiI)

= m + Ian) (7:. —

 

 

36

Thus

~T

7t, — 52+ 6,i_1 :1?“ < 0 (2.44)

 

 

Therefore

7:. — 6:. < 0 for all {t,} if and only if

~T

e,*'.+ 6&4 :ct, > 7;, + e for sufficiently small 6 > 0 (2.45)

 

 

Let us assume that the volume of the ellipsoid of QOBE converges to zero and try
to Show that this assumption is not true. If the volume of the ellipsoid of QOBE
converges to zero then condition (2.44) must hold. For convenience, we will denote

e’— neighborhoods of noise bounds as

D: = [—’y,, — e' < e; < 47"]
D; = [7,, < e; < 7,. + 6’]
At IU we have
53, > 73, (2.46)

> 7,, + 6' for small 6'

 

* ~T
511+ gn—l x"

 

NT
If 6,,_1 x,, 2 0 and e; 6 D67 , i.e. (-'y,, — e’ < e; < —'y,,) then since 5:, is uniformly
distributed, we have

7n+6’<I€;|<7n

NT

~T
Ishl + 6n—1 1'" > 7n + 6, + 671—11."

 

 

 

~T
5;+0,,_1 £13,, > 7n+e’

 

 

37

Same as defined in (2.46) , therefore 5:, E 057- Similar analysis can be repeated to
~T

show that e; E B; when 6,,_1 x,, < 0.

Given 6’, assume {5;} is symmetrically bounded with UCT, where there exists (it, > 0,

pt, > 0 such that for all t,-

P(€; E D: l Sin—1) > (Sh/pt; and (2.47)

P(EZ E D; l3n_1) > 6(i/p“ CLS.

NT
Let A; be the event that e; 6 D57 and 9t.-—1 27;, 2 0

Let A: be the event that e; E D: and 5:4 3:“. < 0

Let A,,. “3 A: u A;

Now let us define A,, to be the event that (2.44) holds at time t,-, then

P (An) = P (At-1.) + P (AZ), since A: and A; are mutually exclusive events for a

sufficiently small 6’

3

~T ~T
P(At.) = P (E; E D; I 6t‘_1 It“. 2 0) P (Big—l 1'“ Z O)

~T ~T
+P (5;; E D: I git—1 xii < 0) P (ah—1 I“. < 0)

NT
Let k,- = t,- — t,_1 and define WtH déf {0W1 x,, 2 0} and Vt, = {e't'i 6 DE}
Then Vt, and WtH E 8‘ and P (Va) = 6,,. By the definition of the mixing condition
in Definition (2.17)

lim P(V,,nw,,_,) =P(V,,) lim P(W,,_,.,) (2.48)

ki—voo lei—+00

38

Suppose P (Wu—In) is not zero. Then (2.48) can be written as

,. P(Vt. rim—k.)
1m
lei—’00 P (Wti-ki)

 

= ,hm Pm. I WM.)

= P(Vt.)
Let 0 < %} < 6;, such that
IPO/ti I Wti-ki) — P(Wi)l < gti/pti

Therefore

5— < PM I WM.) < P(Vc.) + i (249)

P (mi) _
pti pti

The inequality of (2.49) holds for IU condition.
Therefore we can write
NT NT
P(At.) = P (er. 6 D; I 0 x,,. 2 0) P (a.-. x... 2 0)

NT NT
+p (5;; e D; I a,,_, x,,. < o) p (9,4 x < 0)
From (2.49) and recalling the definition of Vt, and Wt,—k,- , we get

NT
P(A,,) _>_ [P (a; e D; ) — EL] P(Ht,_1$t.- 2 0)
ti

a: + {ti ~T
ti
From PE condition and from (2.30) and (2.31)

~T
P(01i_1 ft,‘ 2 0) Z pig > 0

39

and

~T
P (6231-1 1'". < 0) 2 pt." > 0

Also, from (2.32) and (2.33) we have
~T
P (5:,- E (D; UDj) I 6tg—1 xii Z 0) Z (SQ/pt,- > 0

and

~T
P (52:, 6 (D67 U D?) I Oti—l (rt,- < 0) 2 6(i/p“. > 0

Therefore, we have

 

P(At,) _ P(e; E D; ) - :—:I pt, + IP (5;; E D; ) — i—I pt,
l
2 P (a; e (D; u 03)) — %I pt.-
L ti
2 (an/Pt. — £3I") Pt.
pti
2 5t.- “— t),
> 0

Let there exists M > N and M —+ 00 and {In} be the infinite sequence of intervals,

each of length M over which IU occur. Then

' NT
P(Ati I At‘._N) Z P E; E D; I {gig—15E“ 2 0} flAt,_NI

:{6:1$t> 0} I Alt—N]

~T
+P I5} E D?!- I {Bu-133% < 0} nAti‘N]

{0,_1:I:t. <0} IA,,_NI

P

 

P

40

Thus,

IV

IV

IV

’ ~71"
P a; E D; I {6ti_1$t, Z 0} I flu—N]

 

F~T ~T
P Oti-l {L‘ti Z O] P [{otr—l xti 2 O} l Att”~]

~T
+P [5; 6 D2; I {0ti_1$t, < 0} IAtg—N]

~T ~T
P [BM—1 3:“. < 0] P [{gti_1 mt, < 0} IAti—N]

6 ~T 2
[P (5:.- E D; ) _ A] {P[6ti-1$ti Z 0]}

Pt,
6.. ~T 2
+ [P (a; e D: ) — Fl {P [9t.-—1 x,,. < 0]}
ti
(Std _ gig
0

P(AtiflAti—N) : P(AtilAti—N)P(Ati—N)

_>- (6ti _ 6h) (6ti+N " Etg+N)

> 0

P(At, fl Ati—l fl ..... fl Ati—N) Z P(At'. fl Ati—N)

2 (6h _ éti) (6ti+N _ €ti+N)

> 0 (2.50)

41

llm P (Ali-l-kN fl Ati+kN—1 fl ..... F) A“) 2 lim P (Ati-HcN fl At;+(k‘-—1)N fl ..... n A“)

k—¢oo k—voo

k
2 lim ((3.-+12»! — €t,+lN) = 0

k—voo
(=1

In probability, this is contrary to our assumption that the volume of the ellipsoid
converges to zero. Therefore, the volume of the ellipsoid of QOBE does not converge

to zero under IU condition. 0

42

Chapter 3

Simulation Results

3. 1 Introduction

Simulation studies provide a visual perspective of any mathematical analysis.
In working with adaptive filtering techniques, the algorithm that models the filter’s
performance can be better understood and evaluated through experimenting with
data and simulating the results on a digital computer. For example, simulations can
illustrate improvements in the speed of convergence of the algorithm, represent the
effect of different factors on the filter’s estimated parameters, Show efficient use of
innovation in the data, and indicate order of computations.

A process 93,, is said to be deterministic if it can be predicted without error in
terms of a linear combination of its previous values. However, in many signal process-
ing applications where linear shift-invariant filters are used, the inputs to these filters
are random processes. In the simulation studies in this chapter we will investigate the
performance of the QOBE algorithm in a stochastic setting and verify its behavior
indicted by theorems that have been proven in the previous chapter. Different types

of noise sequences will be used.

43

3.2 Types of Noise Sequences

In this section and its subsections we will illustrate the behavior and performance
of the QOBE algorithm in iid and colored noise cases and when the noise bounds are

either symmetrical or asymmetrical. For our purposes of simulation, we will use an

AR(3) model of the form:
yn : 0,1,, yn—l + 012* 3171—2 + 03* yn—3 + 5:; (31)

where a1... = 2, a2, = —1.48, (13... = 0.34 are unknown parameters to be identified.

Some other model forms will also be used.

3.2.1 IID Noise Sequence

In most of the simulations presented in this section and others to follow, we will
show the performance and characteristics of the QOBE algorithm in identification
problem by way of comparison with those of the OBE algorithm under the same
system settings. Since the performance of the OBE algorithm has been investigated
with respect to other identification methods [7],[9],and [44] in the literature, such as
recursive least squares (RLS) and least squares (LS), we will restrict our comparison
to OBE in order to show the difference in behavior between the minimization criteria
used in OBE and QOBE. We have used the set membership stochastic approximation
(SMSA) version of OBE for it is used in the literature when stochastic settings are
under investigation.

In Cases 1 to 3, we will consider an AR(3) model as in (3.1) where the noise
sequences {5;} used to generate the observable output sequence {y,,} are specified
within.

Case 1: 8:, ~ U (—1, 1) is an i.i.d. sequence with zero mean and is uniformly dis-

tributed on [-1,1].

44

 

 

 

 

2-2 v r F T .T

2, ........ I . i f
”3-. ............ g ............ ................ ............... ........... W,
,_6_...._,....fi.. .. _
1 A L i 1 i

0 500 1000 1500 2000 2500 3000

 

 

 

 

,5 ; 1 1 . .‘
0 500 1000 1500 2000 2500 3000
Time (n)

Figure 3.1: Case 1: Estimators of al.,- — 2. 0 convergence using QOBE and OBE
algorithms for identification of model (3. 1) with 7,, = O. 96, where 146 points and 223

points were used, respectively, from a total of 3000 points.
0035

 

 

 

 

 

_1.4.... ...

 

 

 

 

-1.6--
_2 l l l l l
500 1000 1500 2000 2500 3000
Timem)

Figure 3.2: Case 1: Estimators of a2... = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1) with 7,, = 0.96, where 146 points and 223
points were used, respectively, from a total of 3000 points.

45

 

0'7 f T F F r
(16_.._ ........... i ........... H..: ............... an..n..n.fl.., ............... é .............. _
0.5-... .. _

 

 

 

 

 

  

 

 

 

 

OBE
0’ T 1 r Y '
0,5. ...... ...... .............. ....... ..... , ....... ............... _l
0.4.. .......... ............... g ....... ............... g ...............
0.3-W ............. 5 ..... . ....... ................ ............
0.2 ‘
500 1000 1500 2000 2500 3000
Time(n)

Figure 3.3: Case 1: Estimators of a3... = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1) with 7,, = 0.96, where 146 points and 223

points were used, respectively, from a total of 3000 points.

. Vqume of Ellipsoid

 

 

 

 

 

 

 

 

 

 

10 I 1 I 1 l
100 1
QOBE
10‘ . ~
10’ - ‘
10° ~
}
10" ~ OBE -
___‘__fi
1
1o“ 1 1 1 1 1
0 500 1000 1500 2000 2500 3000
Time (n)

Figure 3.4: Case 1: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,. = 0.96, where 146 points and 223 points were
used, respectively, from a total of 3000 points.

46

The simulation results of QOBE under the specified conditions and 7,, = 0.96
are shown in Figures 3.1 - 3.4 with relative comparison to results obtained from OBE
identification. Ftom the figures it is noticed that the estimators of al., (12..., and (13...
are converging to the true parameters in both algorithms with QOBE using fewer
data points as expected. This supports the assertions in Theorems 2.1 and 2.2 in
Chapter 2. The volume of the ellipsoid in QOBE, Figure 3.4, is obvious to be larger
than that of OBE, however, it is converging to a certain size.

Case 2: This is a case of symmetrical noise bounds where 5; ~ B(—1, 1) is an i.i.d.

Bernoulli sequence with zero mean and a binary distribution specified as

5* =2 1 with probability 0.7 (3.2)

5* = —1 with probability 0.3

The simulation results of both QOBE and OBE under the specified conditions
are shown in Figures 3.5 - 3.8 with 7,, = 1.04 . It is seen that the QOBE algorithm
has a faster convergence rate for the estimated parameters to their true counterparts
although the speed of both algorithms are not very much affected by the 6 - tail
probability, 6, defined in UCT (2.6) or UT (2.7) conditions.

Case 3: This is a case of asymmetrical noise bounds where 5;“, ~ B(—0.5, 1) is an
i.i.d. Bernoulli sequence with non-zero mean and is asymmetrically bounded with

binary distribution specified as

5" = 1 with probability 0.7 (3.3)

5* = —0.5 with probability 0.3

The simulation results for both QOBE and OBE under the specified conditions
and with 7,, = 1.04 are shown in Figures 3.9 - 3.12. It is evident that the OBE

algorithm is affected by the asymmetrical noise bounds as defined in Definition 2.7

47

 

 

 

 

 

 

 

 

 

 

 

 

 

-05 '1 1' i 1‘ i i I ‘1 '1
O 50 100 150 200 250 300 350 400 450 500
Time (n)

 

Figure 3.5: Case 2: Estimators of a1... = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 24 points and 916

points were used, respectively, from a total of 3000 points.
. ooae

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.1
_2 i '1 i '1 i 1 1 i 1
0 50 100 150 200 250 300 350 400 450 500
Time (n)

Figure 3.6: Case 2: Estimators of 612... = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 24 points and 916 points
Were used, respectively, from a total of 3000 points.

48

QOBE
I

 

 

 

 

 

 

 

 

 

 

 

 

2 I I I f T T
1 1— . . ...... n ............................................................................... _,
0W 3 ................... g ............................................................ _
_1 l. . .. . .. ..
_2 1 1 1 L 1 1 1 1 1
0 50 100 150 200 250 800 350 400 450 500
OBE
2 I I I I I I I I
1 1.. ............................................. ........................................... _.
_2 L 1 1 1 1 1 1 1 1
O 50 100 150 200 250 300 350 400 450 500
Time (11)

Figure 3.7: Case 2: Estimators of a3... = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 24 points and 916

points were used, respectively, from a total of 3000 points.
Volume of Ellipsold

10

 

 

 

 

 

 

1 o I I I I I

10' r ‘

10' ~

10‘ ) QOBE .

10’ a

10° 1- a

2 L OBE

1 0— "
4

1o" 1 l_ 1 1 1

O 500 1000 1500 2000 2500 3000

Time (n)

Figure 3.8: Case 2: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 1.04, where 24 points and 916 points were
used, respectively, from a total of 3000 points.

49

 

 

 

 

 

 

 

 

 

 

 

 

_0.5 1 1 l l l l l l I
O 50 100 150 200 250 300 350 400 450 500
Time (0)

Figure 3.9: Case 3: Estimators of a1. = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 27 points and 374
points were used, respectively, from a total of 3000 points.

 

 

 

 

 

 

 

 

 

 

 

 

QOBE
2 r r I r 1 r r 1 fl
1... ........................................................................ _.
_2 1 1 1 1 1 1 1 1 1
0 50 100 150 200 250 300 350 400 450 500
OBE
2 I I I I I I I I I
11... ............................................................ ........ ........ ..
J .................
_2 1 1 1 1 1 1 1 1 1
0 50 100 150 200 250 300 350 400 450 500
T1me(n)

Figure 3.10: Case 3: Estimators of a2. = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 27 points and 374 points
were used, respectively, from a total of 3000 points.

50

 

 

 

 

 

 

 

_2 1 1 1 1 1
OBE
I I I I I I I

 

 

 

 

 

_1._ ...... . ......... . ......... ’ .......... . ......... .......... .......... ........ ...... _
_2 1 1 1 1 1 1 1 1 1
O 50 100 150 200 250 300 350 400 450 500

Tame (n)

Figure 3.11: Case 3: Estimators of a3... = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 27 points and 374 points

were used, respectively, from a total of 3000 points.
Volume 01 Ellipsoid

 

 

 

 

 

 

101° 1 I I r I
10. r— —1
10° - -
QOBE
10‘ _ ~
10’ ~ «
4
0
1O - 'l
1o-2L\\ OBE -
1o“ 1 1 1 1 1
0 500 1000 1500 2000 2500 3000

Time (n)

Figure 3.12: Case 3: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 1.04, where 27 points and 374 points were
used, respectively, from a total of 3000 points.

51

while QOBE converges consistently and complies with Theorems 2.1 and 2.2.

Case 4: We will use an AR(2) model of the form

yn : _01 3111—1 + 056 yn-2 + 5:, (3.4)

with a; as in Case 1, in order to illustrate the trajectory of the estimates and the
final ellipsoid of the QOBE algorithm.

The simulations were performed for identification of an AR(2) model and are
shown in Figures 3.13 - 3.15. The estimators of a1... and a2... are converging to the true
parameters and the volume is decreasing but to a certain size that is not as small
(or to a point) as it would be in OBE. This is also clear from the trajectory of the
estimators in Figure 3.15 which conforms to the positiveness of Pu and Km under the

PE assumptions.

3.2.2 Colored Noise Sequence

In this section we will consider the AR(3) model as in (3.1) in Cases 5 and 6
where the types of colored noise sequences used are described within. We will also
compare the performance of QOBE and OBE when the noise is colored with both
symmetrical and asymmetrical bounds.

Case 5: This is a case of symmetrical noise bounds where a; is a colored non-zero

mean noise sequence that is related to a colored sequence {w,,} by:

5* = 1, if can > —1 (3.5)

5 = —1, otherwise

where the colored sequence {w,,} is generated by a uniformly distributed i.i.d. white

52

QOBE

 

 

 

 

 

 

 

 

 

1 ‘1 '1
0 600 1000 1.00 2000 2600 3000

Figure 3.13: Case 4: Estimators of a1. = -0.1 and 0.2. = 0.56 convergence using QOBE

for identification of model (3.4) with 7,. = 0.96, where 125 points were used from a
total of 3000 points.

 

 

 

 

 

vmum—oo-
j '. I . .
L i 3 i
10' . ................ ................ ................ ............... -
. ................ ..
104 ................................................................ ; ............................... _
’ :
. ............................................................... i .............. . ............... _
r ‘
100 ,. ............... ................ ................ ........ ..
.. ................................ i.................................Z........1.......: ............... .1
g . 1
o 000 1000 woo woo 8300 3000
Timon-1)

Figure 3.14: Case 4: Volume of the ellipsoid in QOBE algorithm for identification of
model (3.4) with 1,, = 0.96, where 125 points were used from a total of 3000 points.

1 , T

 

 

 

1 A L A A A A A A A

-1 O 1

Figure 3.15: Case 4: The trajectory of the estimators inmodel (3.4) with 7,. = 0.96,
where 125 points were used from a total of 3000 points.

 

53

noise sequence 2,, ~ U (—-1, 1) as

w,, = —0.8w,,_1 + zn

The simulation results of QOBE under the specified conditions and 7,, = 1.04 are
shown in Figures 3.16 - 3.19 with relative comparison to results obtained from OBE
identification. From the figures it is noticed that the estimators of 0.1,, (1,2,.., and (13,.
are converging to the true parameters in both algorithms with neither of them being
affected by the color of 5;. This supports the assertions in Theorem 2.3 and others
in Chapter 2.

Case 6: This is a case of asymmetrical noise bounds where a; is a colored non-zero
mean noise sequence with asymmetrical bounds generated by colored sequence {w,,}

as follows:

5* = 1, if w,, > —0.5 (3.6)

5 = -—O.5, otherwise

and where the colored sequence {w,,} is generated as in Case 4.

The simulation results of both QOBE and OBE under the specified conditions
are shown in Figures 3.20 - 3.23 with 7,, = 1.04. It is seen from these figures that OBE
suffers from the condition of asymmetrical bounds of noise while QOBE converges
rather consistently and faster as well to the true parameters. Again the volume of
the ellipsoid in QOBE is obvious to be larger than that of OBE, however, it reaches
its limited size faster than OBE.

Case 7: In this case we will use the same noise sequence as in Case 5 while we

increase the order of the system to 12. Therefore, the stable AR(12) model

yn = alt yn—l + 02,. yn—2 + ° ' ' + 0'12: yn—l2 + 5:1 (3.7)

54

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l l 1 I I I I 4
100 150 200 250 300 350 400 450 500
OBE
I I I I I I T I
. I ‘1
1- _
0.5:] ~ -
o .. ......... . ......... . ....... , _
_05 i L i i i 1 L i i
O 50 100 150 200 250 300 350 400 450 500
Time (n)

Figure 3.16: Case 5: Estimators of al., = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points and 845
points were used, respectively, from a total of 3000 points.

 

 

 

 

 

 

 

 

 

 

 

 

QOBE
2 I T I T I r T I I
1b. ............... r ................................. ........................... .-
: ‘q
_2 1 1 1 1 1 1 1 1 1
O 50 100 150 200 250 300 350 400 450 500
OBE
2 I I I I I fl I I I
1f- ...................................................................................... .4
_2 1 . 1 . "L 1 i 1 1
O 50 100 150 200 250 300 350 400 450 500
Time(n)

Figure 3.17: Case 5: Estimators of a2. = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,. = 1.04, where 26 points and 845 points
were used, respectively, from a total of 3000 points.

55

 

 

 

 

 

 

 

 

 

 

 

 

 

_2 1 1 1 1 1 1 1 1 1

Figure 3.18: Case 5: Estimators of 03.. = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points and 845 points

were used, respectively, from a total of 3000 points.

10 Volume of Ellipsoid

 

 

 

 

 

 

 

10 I I I I T I I I I
10" - ~
1
10° 1— _
4
‘0 kl QOBE -
1o2 - -1
10° 1 4
10‘2 -
"fl OBE
10“ 1 L 1 1 1 1 1 1 1
o 200 400 600 800 1000 1200 1400 1600 1800 2000

Time (n)

Figure 3.19: Case 5: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 1.04, where 26 points and 845 points were
used, respectively, from a total of 3000 points.

56

Figure 3.20: Case 6: Estimators of a1... = 2.0 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points and 207

 

 

 

 

 

 

 

l
1 50 250

OBE

 

 

 

 

 

 

250
Time (11)

points were used, respectively, from a total of 3000 points. '

Figure 3.21: Case 6: Estimators of a2... = -1.48 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points and 207 points
were used,

 

QOBE

 

...............................................................................................

 

 

 

 

 

 

...................................................................................................

 

 

 

 

respectively, from a total of 3000 points.

57

 

 

 

 

 

 

 

 

 

 

 

O 50 100 1 50 200 250 300 350 400 450 500
Time (n)

Figure 3.22: Case 6: Estimators of a3... = 0.34 convergence using QOBE and OBE
algorithms for identification of model (3.1), 7,, = 1.04, where 26 points and 207 points

were used, respectively, from a total of 3000 points.

w Volume 01 Ellipsoid

 

 

 

 

 

 

 

 

 

10 I I I I T I I I I
p
10. v- -1
10° - d
1 0‘ h QOBE -
102 r 4
4
10° ~
F
-2
1o - ose ‘
1 o“ 1 4 1 1 1 1 1 1 1
O 200 400 600 800 1 000 1 200 1 400 1600 1 800 2000
T1me (n)

Figure 3.23: Case 6: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.1) with 7,, = 1.04, where 26 points and 207 points were
used, respectively, from a total of 3000 points.

58

is used, where al.,. 2 - 0.1, a2. = 0.9175, 0.3.. = - 0.191, (14.. = - 0.2253, 05,. = 0.2601,
a6. = 0.0046, 07... = - 0.0367, as. = - 0.0209, 09.. = - 0.0082, 010. = 0.0095, all, z -
0.0052, 0.12. = - 0.0041 are unknown parameters to be identified.

The simulations were performed for identification of an AR(12) model and are
shown in Figures 3.24 - 3.25. The estimators of al., , a2. and as. are shown as an
example of the performance of the QOBE algorithm for all the other estimators as
well. It is seen that the estimators are converging to the true parameters with a
colored noise sequence and the volume of the ellipsoid is decreasing in size. These
simulations show that the performance of the QOBE algorithm is not affected by a
change in the model order.

Case 8: We will use the same AR(2) model as in Case 4 while employing the noise
sequence in Case 5.

The simulations were performed for identification of an AR(2) model and are
sh0wn in Figures 3.26 - 3.28. The estimators of al., and 02,. are converging to the true
parameters and the volume is decreasing but to a certain size that is not as small
(or to a point) as it would be in OBE. This is also clear from the trajectory of the
estimators in Figure 3.28 which conforms to the positiveness of Pa and ten under the
PE assumptions.

In all of the above simulations it is shown that the number of usable data points
are much less in the QOBE algorithms than in OBE and thus the number of updates
for the estimators in QOBE is smaller than its counterpart in OBE. This leads to the
fact that the QOBE algorithm has an improved computational efficiency due to its
simple check test and its focus on minimizing the scalar x,, rather than minimizing the
volume as is the case in OBE algorithm. Therefore we can summarize the performance
of the QOBE algorithm so far in that it retains a large volume, uses fewer points,
exhibits faster parameter estimator convergence to the true parameter, is robust to

additive noise, and its performance in colored noise is improved.

59

 

 

 

 

 

 

 

 

 

 

 

0 500 1000 1 500 2000 2500 3000

 

 

 

 

 

-0.1 1 1 1 1 1
0 500 1000 1500 2000 2500 3000
Time (r1)

Figure 3.24: Case 7: Estimators of al., = -0.1 and 02... = 0.9175 and a5. = 0.2601
convergence using QOBE for identification of model (3.7) with 7,, = 1.04, where 115

points were used from a total of 3000 points.

Volume of Ellipsold -— QOBE
36
1° F l 1 .1 '

 

10

1°25 ................ j .......... .1

 

 

 

 

 

 

 

 

1 l l 1 ‘T—k
500 1000 1 500 2000 2500
Time (n)

Figure 3.25: Case 7: Volume of the ellipsoid in QOBE algorithm for identification of
model (3.7) with 7,, = 1.04, where 115 points were used from a total of 3000 points.

60

QOBE

 

 

 

 

 

 

no
“(In

Figure 3.26: Case 8: Estimators 0f 01. = -0.1 and 03. = 0.56 convergence using QOBE

for identification of model (3.4) with 7,1 = 0.96, where 974 points were used from a
total of 3000 points. '

vmam—oo.
V

 

 

 

 

 

 

10' ............... ................ I ............. _
10‘
104 o ............. :0 ............ mo ............ ‘ ............... m ............ m ........... m

Figure 3.27: Case 8: Volume of the ellipsoid in QOBE algorithm for identification of
model (3.4) with 7,. = 0.96, where 974 points were used from a total of 3000 points.

 

 

 

 

l f.- s
F
,
.1
0
d
11 1+1.
-1 0 1

Figure 3.28: Case 8: The trajectory of the estimators inmodel (3.4) with 7,. = 0.96,
where 974 points were used from a total of 3000 points.

61

QOBE with unsatisfied PE condltlon
I

 

 

 

 

 

 

 

 

 

 

 

 

2 r p F 1 r
1 1 1 1 1
O 500 1 000 1 500 2000 2 500 3000
I
_1 1 1 1 1 1 ‘__j———
0 500 1 000 1 500 2000 2500 3000

 

  

 

_ 3 a.3.f= 0:34

 

 

 

I I l l
0 500 1 000 1 500 2000 2500 3000
Time (n)

Figure 3.29: Estimators of 01... = 2.0, 02,, = -1.48 and a3... = 0.34 using QOBE for
identification of model (3.1) when the PE condition is not satisfied.

3.3 Effect of Unsatisfied Conditions

In this section we want to Show the effect of missing conditions or unsatisfied
constraints from Theorems 2.1 - 2.3 on the performance of QOBE. This will enhance
the illustration of the validity of the proof of these theorems. It should be noted
that in all of the following simulations, the same results would be obtained even we
increased the number of points higher than 3000 points indefinitely.

Figure 3.29 shows the effect of losing the PE condition on the performance of
QOBE. It is seen that when the observation sequence is correlated then the algorithm
will tend to converge to away from the true parameters.

Figure 3.30 shows the effect of missing the UCT condition on the performance
of QOBE. In this case the noise or error sequence will not be uniformly conditionally
tailed around the neighborhood of the bounds and this effect is seen the algorithm
drifting away from the true parameters.

Figure 3.31 shows the performance of QOBE when both the PE and the UCT are

not satisfied. We notice that the algorithm in this case will not converge properly and

62

QOBE with unsatisfied UCT condition

2 f I 1 1 1

 

81‘=2.0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0.2 1 1 v I v
0 83' = O 34 , :—_1 ...... 1
_°_2 .................................................................. _.
-O.4 —
-°«6 l l 1 l l
O 500 1 000 1 500 2000 2500 3000
Time (n)

Figure 3.30: Estimators of 01... = 2.0, 02,. = -1.48 and 03.. = 0.34 using QOBE for
identification of model (3.1) when the UCT condition is not satisfied.

QOBE with unsatisfied PE and UCT conditions
3 I I I I 1
. ; a1 ' =1 2.0 ‘ '

 

 

 

 

 

 

 

 

 

 

 

 

 

1
0 500 1 000 1 500 2000 2500 3000
Time (n)

Figure 3.31: Estimators of a1. = 2.0, 02... = -1.48 and 03.. = 0.34 using QOBE for
identification of model (3.1) when both the PE and the UCT conditions are not
satisfied.

63

it will bounce in an undefined manner due to uncorrectly meeting the noise bounds
and also having a correlation factor in the observation sequence.
Figures 3.29, 3.30 and 3.31 all show that meeting the constraints of Theorems

2.1 to 2.3 are required to ensure the convergence of the QOBE central estimator.

3.4 Tracking Performance of QOBE

In this section we will illustrate the performance of the QOBE algorithm by
studying two time varying cases where the system exhibits time varying parameters.
This will help show the efficiency of the tracking performance of the algorithm to time
varying settings. We will consider an AR(2) model with time varying parameters that

is constructed as follows:
yn = a1... y(n - 1) + £121 1101 - 2) + 63; (3-8)

in which 0.1.. and a2... will have the following different variations:

Case 9: AR(2) as in (3.8) where 5:, ~ U(—1, 1) is an i.i.d. sequence with zero mean
and is uniformly distributed on [—1,1], (11., is a slow square wave that varies between
1.6 and -1.6 every 1000 points and a2... = 0.68.

Case 10: AR(2) as in (3.8) where 5; ~ U(—1, 1) is an i.i.d. sequence with zero mean
and is uniformly distributed on [—1,1], a1. is a fast square wave that varies between
1.6 and -1.6 every 500 points and a2. = 0.68.

Figures 3.32 - 3.33 illustrate the simulations for Case 9 and they show the good
tracking capability of QOBE over OBE in slowly time varying systems where the
time variation is abrupt. However, for Case 10, and from Figures 3.34 - 3.35, it is
seen that OBE loses tracking capability while QOBE performs quite well in a system
where the abrupt variation has doubled.

Case 11: AR(2) as in (3.8) where 5; ~ U(—1, 1) is an i.i.d. sequence with zero

64

 

00000000000000000000000000

 

 

 

1.5_ ................... q
1 -1
0.5 r u
0 - q
-O.5~ .
-1 _ .
-1.5~ ..........................................

1 1 1 1 1 1 1 1
0 200 400 600 800 1000 1200 1400 1600 1800 2000

 

 

 

—1.5

 

 

 

 

Figure 3.32: Case 9: Estimators of al., (time-varying parameter with slow
abrupt change) convergence using QOBE and OBE algorithms for identification of
model (3.8), 7,, = 1.1.

10

Volume 01 Ellipsold

 

10 r I 1 I I

10. I- '1

10° L 1
E’

10‘

 

 

 

 

10
10°
10" - -
‘04 1 1 1 1 g
0 500 1000 1500 2000 2500 3000

Time (11)

Figure 3.33: Case 9: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.8), 7,, = 1.1, and al.,. is time-varying parameter with slow
abrupt change.

65

 

 

 

 

 

 

 

 

T I . .r I I I I I I
1.5 ........... E 3 ....... .E E... .. E ............
1 . .
0.5
0
—0.5-
-1—
—1.5~ ............ .............
I J I L L I I
0 200 400 600 800 1000 1200 1400 1600

 

-0.5
-1
-1.5

 

 

 

 

Time (n)

Figure 3.34: Case 10: Estimators of al., (time-varying parameter with fast
abrupt change) convergence using QOBE and OBE algorithms for identification of
model (3.8), 7,. = 1.1.

‘0 Volume of Ellipsoid

‘0 I I I— —I_ I

 

1o 1— —1
10. r- n

J
10‘

 

 

 

 

10
§ 00315 1
1 0'2 ~ 4
1 0“ _P 1 1 1 1
0 500 1000 1500 2000 2500 3000
Time (11)

Figure 3.35: Case 10: Volume of the ellipsoids in QOBE and OBE algorithms for

identification of model (3.8), 7,, = 1.1, and a1... is time-varying parameter with fast
abrupt change.

66

mean and is uniformly distributed on [-1,1], (11,. is a slow sinusoidal wave that varies
between 1.6 and -1.6, specifically, al.,. = 1.6sin(27rn/1000), and 02... = 0.68.

Case 12: AR(2) as in (3.8) where 5;“, ~ U(—1, 1) is an i.i.d. sequence with zero mean
and is uniformly distributed on [-l,1], a1. is a fast sinusoidal wave that varies between
1.6 and -l.6, specifically, a1... = 1.6sin(27m/500), and 02... = 0.68.

Figures 3.36 - 3.39 represent the performance of the QOBE algorithm with re-
spect to the OBE algorithm in a system where the time variation is gradually chang-
ing. It is seen that in slow changing variation QOBE performs better than OBE that
loses track of the parameter estimate. When the time variation of the parameter al.,
increases by the double, QOBE still can keep track of the parameter estimate while
OBE can not. It is to be noted that in all of these simulations the QOBE algorithm
has been very efficient in the the use of number of updates which was much less than
that of the OBE case.

Cases 9 through 12 show the feasibility of using the QOBE algorithm in a time
varying system and indicates it superior performance over the conventional OBE
algorithm. With its less number of computations, its minimization criteria that is
independent of the volume size, and its robustness to time variations, QOBE proves

to be a well behaved class of the set membership algorithms.

67

QOBE

 

 

 

 

 

 

 

 

 

 

I I I I I I I I I
1.5 — ' ~
1 - . a
0.5 —‘.' ' 1
0 I . . . . -:
-0.5~ ‘ ‘ .~ .- _
_‘ I- . ' " ‘ a:
-1_5 l- ’ .1
I I I I L I I I I
0 200 400 600 000 1000 1200 1400 1600 1800 2000
OBE
I
...... 1
31
l—H
...... ‘
1000 1500
Time (11)

Figure 3.36: Case 11: Estimators of al., (time-varying parameter with slow grad-
ual change) convergence using QOBE and OBE algorithms for identification of

model (3.8), 7,, = 1.1.

w Volume 01 Eliipsoid

1o fir I I r I

 

 

 

 

" 1 1 1 1 1

 

0 500 1000 1500 2000 2500 3000
Time (0)

Figure 3.37: Case 11: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.8), 7,, = 1.1, and al., is time-varying parameter with slow
gradual change.

68

 

 

 

 

1 I j I I r I I I
1.5 r ‘ '1
1 . 1' —1
0'5 . . - . : 2 .' ‘
0 h I I. . C u I q

l
-0.5 '-

_1 1- -
-1 .5 i— , o . -_ -1

I I I I I I I L J

0 200 400 600 800 1000 1 200 1400 1 600 1800 2000
OBE

 

 

 

. O
. c
. I
' I
. U
, o
, . .
I . .
b . .
I ‘ '
I . .
I - .
O ' -.
O
’. . . -1
O ' “
. . . .
. . . .
. . . .
o . .‘II
a . n O
O . I '
. . . .
.

1000 1500

 

 

 

 

Time (r1)

Figure 3.38: Case 12: Estimators of 01,. (time-varying parameter with fast grad-
ual change) convergence using QOBE and OBE algorithms for identification of

model (3.8), 7,, = 1.1.

Volume of Ellipsoid
10
I O I I I I I

 

 

 

 

 

1 O
1 0°
10" ~ -
1 O" 1 1 1 1 1
0 500 1 000 1 500 2000 2500 3000
Time (11)

Figure 3.39: Case 12: Volume of the ellipsoids in QOBE and OBE algorithms for
identification of model (3.8), 7,, = 1.1, and al.,. is time-varying parameter with fast
gradual change.

69

Chapter 4

Application of QOBE in

Classification

4. 1 Introduction

Classification is a classic problem where the criterion is to associate each of a
set of events with one of a finite number of classes [16]. An event is associated with
the class to which it is “closest” according to a measure upon which each event-class
pair is evaluated [54]. In this chapter we investigate the performance of the QOBE
algorithm in classification problems to illustrate its application potential. This will
also relate to our convergence analysis in Chapter 2 by implementing classification

problems where parametric models, such as AR models, are used.

4.2 Classification Using QOBE Algorithms

Let us consider an n class problem in which class c corresponds to a model
of form (1.1) with parameters 06,, , so that class c is effectively represented by a
point in R”. The classification problem will naturally employ a metric, say (1, over

Rm, so that 6c... is a point in metric space (Rm, d). Suppose that the true, but

70

unknown, class is represented by vector 6., [or some mapping, F (6,.)]. Suppose that a
QOBE algorithm is used to classify a signal frame over some time frame ending at t.
The analysis produces the hyperellipsoidal set 0; including, in particular, the central
estimate 6%. For reference, let us assume that we have the conventional unweighed
least-square error (LSE) estimate of 19..., say HMSE. Regardless, of the estimator (or
set of estimators), the assignment rule for the current signal frame is typically of the

form

Choose class c,, , where c,, = arg min 6 (6t , 66...) (4.1)

c€[1,n]

and where 6: is the estimator derived for the frame (91153, 1%, or (2;) and 6 is a
measure of distance. To illustrate the use of these constructions, we develop the
following example where we seek to classify the output of the two AR(2) systems of

the form (1.1) with

61,. = [—1.38, —0.64]T (4.2)

02,. = [0.1, —0.56]T (4.3)

A sequence of length 3000 from each system is generated and the resulting signals
are segmented into 10 frames of 300 points each. Each of the 20 frames is classified
three times, once using 9"],33, 0:, or (2;. The classification rule is of form (4.1) with 6
(henceforth “d” in this example) indicating the Euclidean distance between the class
parameters and relevant estimate. The criteria of d(Qt, 06...) is such that at each t,
50 quasi-random estimates are chosen from Qt by selecting random directions from
the center of the ellipsoid (each angle being uniformly distributed over the interval
[0 , 271']) and random magnitudes in the chosen direction (the length being uniformly

distributed between 0 and the maximum length in that direction). If the 50 selected

71

points comprise the set 9: = {Qtd 2' = 1, 2, - -- ,50} C 9;, then

d ((2., 0....) “‘2 min d (01,.» 9...). (4.4)

i€[l,50]

In other words, (1 (Q, 66...) implies a nearest-neighbor rule in the sense of Euclidean
distance between 6c... and St. The estimator so chosen is called simply the “other”
estimate in the following. The three scatter plots, one for each estimate are shown
in Figures 4.1 - 4.3. The system identity for a given point is indicated by the symbol
used for plotting. Each point in each diagram is classified according to the relevant
distance metric. We notice the lessened variance associated with the clusters resulting
from the “other ” estimator. Of course, this effect would be entirely expected since an
exhausted search of Q, were performed for the minimum distance classifier. Although
this could be an ad hoc approach, it shows evidence of significant improvement in
classification.

An important feature of QOBE is that it does not explicitly depend upon the
bounding ellipsoid, therefore the need to assure that 0.. remains inside the ellipsoid,
which is critical in OBE processing, is not important in QOBE. Also, the ellipsoidal
set associated with QOBE has interesting convergence behavior which are depicted
in Figures 4.1 - 4.3 and can benefit QOBE tracking behavior.

One way to validate the usage of “other” estimates, can be by illustrating their effect
on the magnitude spectrum of those estimates along the major and minor axes of the
final ellipsoid with comparison to that of the true parameter. Figure 4.4 shows that
those estimates along the minor axis corresponding to data points in the direction
of error have a comparable energy to the true parameter than those along the major
axis where the data points were not in the direction of error and therefore did not
contribute much information to the algorithm update. Therefore, the potential of

using these “other” estimates is promising for application in many signal processing

72

 

 

 

a o o
O
o 9
1* +
o o + +
—o.5~ ® 0 o +* + + _
o
o +
9 8 1+
+
+
_1 l l l l
2 -15 -1 -o.5 o 05

 

31

Figure 4 1: QOBE central estimator 0, of 01,. and 02. of two AR(2) systems represented
by +’ and’ 0’ ,respectively.

I 1 I I

 

   

 

 

 

%
o
o
0690 + o"'
o— o .1 + -
o O "’
9 +
o
‘3 -: Q30
-0.51— —A
_1 I A l
-2 ~15 -1 -0.5 0 05

a1

Figure 4.2: 0,,LSE estimator of 01. and 02,. of two AR(2) systems represented by ’+’
and ’0’, respectively.

73

 

0.5 1 r I I

   

 

 

 

0 >— ’ -1
+
‘3
-0.5 *" C5) .1
_1 I l
-2 —1 5 -1 -O.5 0 0 5

31

Figure 4.3: QOBE other estimators Q, of 61... and 62. of two AR(2) systems represented
by ’+’ and ’0’, respectively.

realm. _ _
To show the potential of QOBE in classification problem with higher model order, we
develop the following example where we seek to classify the output of the two AR(14)

systems of the form (1.1) with

91.. = [1.0574, — 0.9442, 1.4281, — 1.5123, 0.5309, — 0.8630, 0.6631,
0.1423, - 0.2438, — 0.0809, — 0.2310, 0.1333, 0.0272, 0.0214]T (4.5)
62... = [0.1578, — 1.3503, 1.4395, — 0.2691, 1.8091, — 0.0284, — 0.0307,

—0.3629, — 1.0732, 0.1254, —0.5244, 0.4307, —0.1156, 0.1906]T (4.6)

In this context we will apply also the nearest-neighbor rule in which (1 (9;, 06.)
implies a minimum Euclidean distance between 6c... and St. The estimator so chosen
will be again called the “other” estimate in the following. Figures 4.5 - 4.7 show the

three scatter plots for the first two parameters of the AR(14) model, one for each

74

AR(2) System 1: True.—,Other1.o.Oth912.+,Other<3,s.Other4.:

30 I I T I I I I I I.

 

 

 

 

 

 

 

 

 

Figure 4.4: The direct 256 points FFT spectrum of the impulse response for AR(2).
The upper graph for Systeml. The lower graph for System2. In each graph: the
true parameters (-); estimators along the minor axis Otherl (o) and Other2 (+); and
estimators along the major axis Other3 (El) and Other4 (..)

estimation method: the QOBE central estimator, the LS estimator and the “other”
estimator, respectively. Although this may be a crude way of plotting, however, it can
give a sense of how the estimators are behaving in a higher order model. The system
identity for a given point is indicated by the symbol used for plotting. Each point
in each diagram is classified according to the relevant distance metric. We notice
again the lessened variance associated with the clusters resulting from the “other”
estimator.

Suppose a class C is to be classified with either members of System 1 or System 2,

where class C, for example, is on the form

class C = [0.6076, — 1.1473, 1.4338, — 0.8907, 1.17, — 0.4457, 0.3162,

—0.1103, — 0.6585, 0.0223, — 0.3777, 0.282, 0.0442, 0.1060]T

75

 

 

 

 

 

1.5 I I I I
1 '- -1
0.5 ’- .1
+ Q 0
+ 1 0° 03cm»
*1. 8g
_ - + q
0 5 +1... f O
#1? #-
+
_1 .- g d
—1.5 1 1 1 4
-1 -0.5 0 0.5 1 1.5

31

Figure 4.5: QOBE central estimator 9, of 01... and 62.. of two AR( 14) systems repre-
sented by ’+’ and ’0’, respectively.
1.5 t r r I

 

0.5 r' _.

 

-1_

 

 

.-
.-
.—

 

-1.5 1
-1 -0.5 0 0.5 1 1.5

a1

Figure 4.6: 6M3}; estimator of 61... and 02., of two AR(14) systems represented by ’+’
and ’0’, respectively.

76

 

1.5 1 r r I

0.5 ~ ..

 

 

 

_1-5 I l I I
—1 —0.5 O 0.5 1 1.5

a1

Figure 4.7: QOBE other estimators Qt of 01,. and 62... of two AR(14) systems repre-
sented by ’+’ and ’0’, respectively.

For experimental analysis, the class was chosen such that it is more emphasized to-
wards System 2. Figure 4.8 shows a sketch of how the classification works. We
trimmed the dimensions of the ellipsoid by throwing away those eigen vectors of the
covariance matrix that do not contribute useful information to the updates and cal-
culate the minimum distance between the class and the particular estimator through
the Euclidean distance measure explained previously. The minimum distance between
the class and the central estimator for both systems, “other” estimates on the minor
axes (representing the maximum eigen value of the ellipsoid matrix) for both systems,
and “other” estimates on the major axes (representing the minimum eigen value of

the ellipsoid matrix) for both systems are calculated and tabulated in Tables 4.1 - 4.4.

Table 4.1 shows the minimum distances when using the central estimators and
the “other” estimates on the minor axis for both systems. It can be seen that both the
central estimator and the “other” estimator for System 2 are having small distances,

with the “other” estimator of System 2 giving the minimum distance of all. Class

77

1x

0.5x.
0\
-0.5\

-19

 

10

 

-1O
-20

 

-30 10

 

-5

Figure 4.8: Final ellipsoids of System 1 and System 2 used for associating class C to

its membership set

 

 

 

 

 

 

dmin (Owntedysteml) 0.0057
dmin (Gothagysteml) 0.0052
dmin (gwnmr,sy3tem2) 7.6904 x 10"4
dmin (gather-,5ystem2) 7.0183 X 10-4

 

 

Table 4.1: The minimum distance between class C and estimates of System 1 and
System 2 along the minor axis

 

 

 

 

 

dmin (ankrfiystml) 0.0019
dmin (gather,Systeml) 3.5095 X 10-3
dmin (awnterfiystmg) 3.007 X 10-
dmin (gather,System2) 0.085 X 10"5

 

 

 

Table 4.2: The minimum distance between class C and estimates of System 1 and
System 2 along the major axis

 

 

 

 

 

 

dmin (Qumrfiyuml) 4.49 x 10‘5
dmin (gatherflysteml) 29 X 10-5
dmin (omnter,3y3¢em2) 1.21 x 10‘5
dmin (gatherflystem’z) 1.4199 X 10—7

 

 

Table 4.3: The minimum distance between class C and estimates of System 1 and

System 2 after rotating the major axis of System 2 by 90 degrees

78

 

dmin (Banter-Systeml) 0.0025
dmin (Homer’systeml) 5.32 x 10’5
dmin (acenter,System2) 0-0016
dmin (gather,System2) 0-0012

 

 

 

 

 

 

 

Table 4.4: The minimum distance between class C and estimates of System 1 and
System 2 after rotating the major axis of System 1 by 90 degrees

C will be correctly classified to System 2 and this can be attributed to the “other”
estimate since it is on the minor axis where the data is mostly contributing information
to update the system parameters.

Table 4.2 shows the minimum distances when using the central estimators and
the “other” estimates on the major axis for both systems. It can be seen that the
central estimators of both systems having small distances, with the central estimator
of System 1 giving the minimum distance of all. This renders faulty classification of
class C to System 1 and this is because the “other” estimates are on the major axis
where the data does not give either enough or any information useful to update the
system parameters.

Table 4.3 shows the minimum distances when using the central estimators and
the “other” estimates after rotating the major axis of System 2 by 90 degrees. It
can be seen that the “other” estimator of System 2 gives the minimum distance of
all. This renders correct classification of class C to System 2 and indicates that the
“other” estimates in this situation was much more helpful that the central estimator
of the same System 2 in correctly classifying the class C.

Table 4.4 shows the minimum distances when using the central estimators and
the “other” estimates after rotating the major axis of System 1 by 90 degrees. Here
the “other” estimator of System 1 gives the minimum distance of all. Again this is
attributed that the “other” estimator of System 2 was on the major axis and therefore
did not contribute correct information. Therefore classification of class C will be to

System 1, giving incorrect result. The above experiment illustrates that the “other”

79

estimates contribute a lot of useful information to the final classification result as long

as their selection or location inside the ellipsoid is chosen carefully.

80

Chapter 5

Conclusion and Future Work

5. 1 Conclusions

The research in this dissertation has been concerned with a specific class of SM
algorithms known as the quasi optimal bounding ellipsoid (QOBE) algorithm. QOBE
algorithm is based on a different minimization criteria than other OBE algorithms.
QOBE algorithm’s convergence properties have been analyzed and proven in a deter-
ministic framework in the literature. In this work we have analyzed the convergence
properties of the QOBE algorithm in a stochastic framework. This is an important
issue since it will provide an understanding of the algorithm’s performance and its
implementation in many of practical real world applications. We have provided the
conditions and constraints required to implement the algorithm in any stochastic set-
tings through proven theorems and their supporting corollaries and lemmas. Through
many simulations in Chapter 3 and 4 we have showed the performance of the algo—
rithm in different noise conditions ranging from i.i.d. uniformly distributed noise
to asymmetrical and colored noise sequences as well. The QOBE central estimator
converges in all cases under the right conditions given in the supportive theorems

in Chapter 2. However, we have shown that the membership set of the QOBE al-

81

 

gorithm can not converge to a point estimate and the results although expected are
now proven. Finally we have introduced the potential of using the QOBE algorithm
in classification problems. The “other” non-central estimators were shown to have

promising use in such classification applications.

5.2 Contributions and Future Work

The major contributions of this research are summarized as follows. This research

has:

1. Introduced the importance of researching the stochastic analysis of the QOBE

algorithm.

2. Proved the as. convergence and p. convergence of the QOBE algorithm central
estimator in i.i.d., mixing, ergodic, and non-stationary noise cases by applying
necessary analytical techniques and methods from probability and measure the-
ory. Theorems in Chapter 2 provide the necessary theoretical foundation for

the analysis and application of the QOBE algorithm in stochastic settings.

3. Proved that the membership set of the QOBE ellipsoid can not converge to a

point estimate.

4. Provided extensive simulations that show the behavior and characteristics of
the QOBE algorithms in the different noise cases and show its performance in

this conditions.

5. Provided several simulations to show the feasibility of using other non-central

estimators within the QOBE ellipsoid for classification problems.

Many interesting points of research can be followed in the footsteps of this work such

as:

82

 

If

1. Exploring the effect of unsatisfied UCT (2.6) and UT (2.7) conditions on the

performance of the QOBE algorithm.

2. Investigating the application of the QOBE algorithm in digital communication
problems such as inter-symbol interference where output noise will be added to

the system.

3. Exploring the potential use of the other non-central estimators in other digital
signal processing applications with more emphasis on the conditions for selecting

those estimates .

83

APPENDIX

84

 

Appendix

Lemma A.1 [13] If {23k : k 6 IC} is an ergodic stationary sequence, and g : R“ ——+ IR

is measurable then {yk : g (rk,a:k_1, ---) : k 6 IC} is also stationary and ergodic.

Lemma A.2 [13] If both {zk : k 6 IC} and {ylc : k 6 IC} are ergodic, stationary se-
quences and {ask : k 6 IC} is independent of (y;c : k 6 1C}, then {2;c = xk + yk : k 6 1C}

is also stationary and ergodic.

Theorem A.1 [13] Let T : $2 ——> Q be a measure preserving transformation (m.p.t)
andA E 8. DefinerA = inf{n Z 1 : T"(w) E A} wherew ={ ,w-.1,w0,w1, ~--} 6

9. Then
1. TA < 00 as. on A, i.e., P(w E A: TA(’I.U) = 00) = 0
2. A C {11} : T"(w) E A i.o.}

3. IfT is ergodic and P(A) > 0 then P(w : T"(w) E A i.0.) = l

85

BIBLIOGRAPHY

86

Bibliography

[1] M. H. Hayes. Statistical Digital Signal Processing and Modeling. John Wiley and
Sons, Inc., New York, first edition, 1996.

[2] T. Soderstrom and P. Stoica. System Identification. Prentice-Hall, Englewood-
Cliffs, New Jersey, 1989.

 

[3] M. Milanese and G. Belforte. Estimation theory and uncertainty intervals evalu-

ation in presence of unknown but bounded errors: Linear families of models and
estimators. IEEE Trans. on Automatic Control, vol. AC-27z408—414, April 1982.

[4] 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. on Information Theory, vol. IT-33z383—392,
May 1987.

[5] G. Belforte, B. Bona, and S. Hediani. Optimal sampling schedule for parameter
estimation of linear models with unknown but bounded measurement errors.
IEEE Trans. on Automatic Control, vol. AC—32zl79—182, February 1987.

[6] J. P. Norton. Identification and application of bounded-parameter models. Au~
tomatica, vol. 23:497—507, 1987.

[7] J. R. Deller, Jr. Set membership identification in digital signal processing. IEEE
ASSP Magazine, vol.6:4—20, Oct. 1989.

[8] A. K. Rao, Y. F. Huang, and S. Dasgupta. ARMA parameter estimation using
a novel recursive estimation algorithm with selective updating. IEEE Trans.
Acoust, Speech, and Signal Process, vol. 382447—457, March 1990.

[9] J. R. Deller, Jr., M. Nayeri, and S. F. Odeh. Least-square identification with
error bounds for real-time signal processing and control. Proceedings of the IEEE,
vol. 81:815—849, June 1993.

[10] J. R. Deller, Jr., M. Nayeri, and M. S. Liu. Unifying the landmark developments
in optimal bounding ellipsoid identification. Int. J. Adaptive Control and Signal
Process, vol. 8:43—60, 1994.

[11] M. Nayeri, M. S. Liu, and J. R. Deller, Jr. Do interpretable optimal bounding
ellipsoid algorithms converge? Part I - The long-awaited set convergence proof.

87

In Proc. 10th IFAC Symp. 0n System Identification, volume vol. 3, pages 389—
394, Copenhagen, Denmark, July 1994.

[12] M. S. Liu, M. Nayeri, and J. R. Deller, Jr. Do interpretable optimal bounding
ellipsoid algorithms converge? Part II - OBE vs. RLS: Clearing the smoke. In
Proc. 10th IFAC Symp. 0n Systems Identification, pages 395—400, Copenhagen,
Denmark, July 1994.

[13] T. M. Lin. Optimal bounding ellipsoid algorithms with automatic bound estima-
tion. PhD thesis, Michigan State University, East Lansing, 1996.

[14] M. Nayeri, J. R. Deller, Jr., and M. S. Liu. Stochastic convergence of optimal
bounding ellipsoid algorithms. J. Circuits, Systems and Computers, vol. 7:607—
639, 1997.

[15] T. M. Lin, M. Nayeri, and J. R. Deller, Jr. A consistently convergent OBE
algorithm with automatic estimation of error bounds. Int. J. Adapt. Control and
Signal Process, vol. 12:305—324, 1998.

[16] D. Joachim, J. R. Deller, Jr., and G. I. Mandour. OBE set estimates in classifi-
cation problems. In Proc. 41th Midwest Symp. Circuits and Sys, pages 259—262,
U. Notre Dame, August 1998.

[17] P. Stoica. Prediction of autoregressive lognormal processes. IEEE Trans. on
Automatic Control, vol. AC-25z292—293, April 1980.

[18] L. Ljung and T. Soderstrom. Theory and Practice of Recursive Identification.
MIT Press, Cambridge, Mass, 1983.

[19] G. H. Golub and C. F. Van Loan. Matrix Computations. The John Hopkins
University Press, Baltimore, Maryland, 1983.

[20] D. Graupe. Time Series Analysis, Identification, and Adaptive Systems. Krieger,
Malabar, Florida, 1989.

[21] S. Haykin. Adaptive Filter Theory. Prentice—Hall, Englewood-Cliffs, New Jersey,
1995.

[22] D. G. Childers, J. C. Principe, and Y. T. Ting. Adaptive WRLS—VFF for speech
analysis. IEEE Trans. on Speech and Audio Processing, vol. 32209—213, May
1995.

[23] F. C. Schweppe. Recursive state estimation: unknown but bounded errors and
system inputs. IEEE Trans Automatic Control, AC-13222—28, Feb. 1968.

[24] D. P. Bertsekas and I. B. Rhodes. Recursive state estimation for a set-
membership description of uncertainty. IEEE Trans. on Automatic Control, vol.
AC—16:117—128, April 1971.

88

[25] E. Fogel. System identification via membership set constraints with energy con-
strained noise. IEEE Trans. on Automatic Control, vol. AC-24z752—758, October
1979.

[26] R. R. Bitmead. Persistence of excitation conditions and the convergence of
adaptive schemes. IEEE Trans. on Information Theory, vol. IT-302183—191,
March 1984.

[27] G. Belforte, B. Bona, and V. Cerone. Parameter estimation algorithms for a
set-membership description of uncertainty. Automatica, vol. 26:887—898, 1990.

[28] M. Milanese and A. Vicino. Estimation theory for dynamic systems with un-
known but bounded uncertainty: An overview. Automatica, vol. 27:997—1009,
1991.

[29] S. M. Veres and J. P. Norton. Structure selection for bounded-parameter mod-
els: Consistency conditions and selection criterion. IEEE Trans. on Automatic
Control, vol. 362474—481, April 1991.

[30] Y. F. Huang and J. R. Deller, Jr. On the tracking capabilities of optimal bound-
ing ellipsoid algorithms. In The 30th Annual Allerton Conference on Communi-
cations, Control and Computing, Urbana, IL, September 30 - October 2 1992.

[31] A. K. Rao and Y. F. Huang. Tracking characteristics of an obe parameter esti-
mation algorithm. IEEE Trans on Signal Processing, vol. 41, March 1993.

[32] D. Joachim, J. R. Deller, Jr., and M. Nayeri. Multiweight optimization in OBE
algorithms for improved tracking and adaptive identification. In Proc. Int. Conf.
0n Acoustics, Speech, and Signal Processing, pages 2201-2204, Seattle, WA, May
1998.

[33] S. J. Pushparajah and J. A. Chambers. F1equency domain set membership fast
normalized lms adaptive algorithm. Electronics Letters, vol. 35(No. 11):865—867,
May 1999.

[34] A. Garulli, A. Vicino, and G. Zappa. Conditional central algorithms for worst
case set-membership identification and filtering. IEEE Trans. on Automatic
Control, vol. 45(No. 1):14-23, January 2000.

[35] D. Joachim and J. R. Deller, Jr. Adaptive optimal bounded-ellipsoid identifi-
cation with an error under-bounding safeguard: Application in state estimation

and speech processing. In Proc. Int. Conf. 0n Acoustics, Speech, and Signal
Processing, pages 372—375, Istanbul, Turkey, June 2000.

[36] D. Joachim and J. R. Deller, Jr. Some signal processing applications of set so-
lutions. In Proc. 12th IFAC/IFORS Sym. System Identification, Santa Barbara,
2000.

89

 

[37] C. Novara and M. Milanese. Set membership identification of nonlinear systems.
In Proc. 39th IEEE Conf. 0n Decision and Control, Sydney, Australia, December
2000.

[38] S. Werner and P. S. R. Diniz. Set-membership affine projection algorithm. IEEE
Signal Processing Letters, vol. 8(No. 8):231—235, August 2001.

[39] S. Gollamudi, S. Nagaraj, S. Kapoor, and Y. F. Huang. Set-membership state
estimation with optimal bounding ellipsoids. In Int. Symp. On Information
Theory and its Applications, Victoria, B. C. Canada, September 1996.

[40] S. Nagaraj, S. Gollamudi, S. Kapoor, and Y. F. Huang. Bounded error estima-
tion: Set-theoretic and least-squares formulations. In Proc. Conf. Information
Sciences and Systems, John Hopkins University, Maryland, March 1997.

[41] S. Nagaraj, S. Gollamudi, J. R. Deller, Jr., Y. F. Huang, and S. Kapoor. Per-
formance studies of a ’quasi-OBE’ algorithm for real-time signal processing. In
Proc. 40th Midwest Symp. Circuits and Systems, pages 770—773, Sacramento,
CA, August 1997.

[42] J. R. Deller, Jr. and S. F. Odeh. Adaptive set-membership identification in
O(m) time for linear-in-parameters models. IEEE Trans. on Signal Processing,
vol. 41:1906—1924, May 1993.

[43] H. S. Witsenhausen. Sets of possible state of linear systems given perturbed
observation. IEEE Trans on Automatic Control, AC-13z556—568, October 1968.

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

[45] S. Nagaraj, S. Gollamudi, S. Kapoor, and Y. F. Huang. An OBE estimation
algorithm with enhanced tracking capabilities. ISCAS, 1997.

[46] S. Gollamudi, S. Nagaraj, and Y. F. Huang. SMART: A toolbox for set-
membership filtering. In European Conference on Circuit Theory and Design,
Budapest, Hungary, August 31- September 3 1997.

[47] S. Nagaraj and Y. F. Huang. A statistical approach to set-membership identifi-
cation. In ISI T 2001, Washington, D. C., June 24-29 2001.

[48] A. J. Krener. Kalman-bucy and minimax filtering. IEEE Trans. on Automatic
Control, vol. AC—25z291-292, April 1980.

[49] S. Nagaraj, S. Gollamudi, S. Kapoor, Y. F. Huang, and J. R. Deller, Jr. Mul-
tiuser detection based on a deterministic error specifications: Theory and low-
complexity adaptive solutions. In Proc. 3Ist Asilomar Conf. Signals, Systems,
and Computers, Monterey, 1997.

90

 

[50] X.F. Sun and Y. Z. Fan. Comments on identification for systems with bounded
noise. IEEE Trans. on Automatic Control, vol. 46(No. 5):808—809, May 2001.

[51] Dale Joachim. Multiweight optimization in optimal bounding ellipsoid algorithms
PhD thesis, Michigan State University, East Lansing, 1998.

[52] J. B. Moore. Persistence of excitation in extended least squares. IEEE Trans.
on Automatic Control, vol. AC—28(No. 2):60—68, January 1983.

[53] J. R. Deller, Jr., S. Gollamudi, S. Nagaraj, Y. F. Huang, and S. Kapoor. Conver-
gence analysis of a new “quasi-OBE” algorithm for real-time signal processing.
Int. J. Adaptive Control and Signal Processing.

[54] D. Joachim and J. R. Deller, Jr. Short signal classification using set-membership
identification with application to speech labeling. In Proc. 43rd IEEE Midwest
Symp. 0n Circuits and Systems, Lansing, MI, August 8-11 2000.

91