Nonlinear prediction ladder-filters for higher-order stochastic sequences

Lecture Notes in Control and Information Sciences Edited by M.Thoma 73 III IIII IIIIIIIIII IIIII J. Zarzycki Nonli...

Author: J Zarzycki

61 downloads 610 Views 5MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Lecture Notes in Control and Information Sciences Edited by M.Thoma

73 III

IIII

IIIIIIIIII

IIIII

J. Zarzycki

Nonlinear Prediction

Ladder-Filters for Higher-Order Stochastic Sequences I

IIIIIII

II

IIIIIIIIIIIIIIIIIIII

IIIIIIIIIIIIIII

Springer-Verlag Berlin Heidelberg New York Tokyo

Series Editor M.Thoma Advisory Board A.V. Balakrishnan • L. D. Davisson • A. G. J. MacFarlane H. Kwakernaak • J. L. Massey • Ya Z. Tsypkin • A. J. Viterbi Author Jan Zarzycki Institute of Telecommunication and Acoustics The Technical University of Wroclaw ul. B. Prusa 5 3 / 5 5 50-317 Wroclaw - Poland

ISBN 3-540-15635-6

Springer-Verlag Berlin Heidelberg New York Tokyo

ISBN 0-38?-15635-6

Springer-Verlag New York Heidelberg Berlin Tokyo

Library of Congress Cataloging in Publication Data Zarzycki, J. (Jan) Nonlinear prediction ladder-filters for higher-order stochastic sequences. (Lecture notes in control and information sciences; 73) Bibliography: p. 1. Stochastic sequences. 2. Prediction theory. 3. Filters (Mathematics) I. Title. I1. Series. QA274.225.Z37 1985 519.2 85-12668 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under c:354 of the German Copyright Law where copies are made for other than private use, a fee is payable to "Verwertungsgesellschaft Wort", Munich. © Springer-Verlag Berlin, Heidelberg 1985 Printed in Germany Offsetprinting: Mercedes-Druck, Berlin Binding: LiJderitz und Bauer, Berlin 2161/3020-543910

PREFACE

In t h i s w o r k w e s h a l l b e c o n c e r n e d with t h e p r o b l e m of n o n l i n e a r

least-squares linear

prediction of h i g h e r - o r d e r stochastic s e q u e n c e s

orihogonal

digital

filters. The

nonlinear

problem

as a generalization of the lineaLr least-squares The cond-order

linear l e a s t - s q u a r e s

will be

prediction problem.

for w h i c h

white noise

when

ven sequence)

or s h a p i n g

filters ( w h o s e

modeling

statistically equivalent to the given s e q u e n c e ,

when

sire p r o c e d u r e s ,

in w h i c h

one

will not h a v e

e a c h time the permitted complexity derlies both the ladder-structures ry, a n d

the theory of orthogonal

the gi-

output is

driven b y white noise)

remarkable

implemented

Hence,

expa~sions

means

plemented

using

(namely CORDICS

of a n

any

orthogonal filter w h o s e

via recur-

the w h o l e

the s a m e

in m o d e r n

inherent numerica/

result of this theory is t h a t

alized b y

The

assures

computed

to r e c o m p u t e

is increased.

(Fourier)

be

of the m o s t importa~nt proper~y of the orthogonal

vat[on of 'energy' w h i c h A

driven b y

established° In practice, the linear or£hogonal filters c a n

One

with s e -

the orthogonal prediction or

innovations linear filters ( p r o d u c i n g

can be

considered

estimation theory is a s s o c i a t e d

stochastic s e q u e n c e s ,

as well a s

using non-

filter

idea u n -

digital filters theo-

in Hilber~

spaces.

digital filter is p r e s e t stability of the filter.

transfer function c a n modular

structure c a n

sophisticated 'building-blocks' with V L S I

be be

reim-

integrated circuits

processors).

linear theory results in the o p t i m u m

approximation of s e c o n d - o r d e r

sequences.

(least-squares)

Therefore,

stochastic

the linear estimation

IV filter b e c o m e s properties

the best possible

are completely c h a r a c t e r i z e d

If the undertyin~ s e q u e n c e may

be

In this w o r k least-squares

we

wish

sequence

the s e c o n d - o r d e r

(whose

statistics).

the linear estimation a c c u r a c y

a norz[inear a p p r o a c h

in order to i m p r o v e

to the p r o b l e m

the a c c u r a c y .

to p r e s e n t efficient algorithms of nonlinear

prediction filters for higher-order stochastic s e q u e n c e s ,

sulting in the o p t i m u m

approximate

re-

nonlinear digital filters of the Volterra-

class, ri~hese nonlinear ladder-filters will generalize the linear fil-

ters, p r e s e r v i n g zations, a m o n g order

by

is non-Gaussio.n,

not satisfactory. In that c ~ e ,

shot~Id b e introduced

Wiener

filter for ~ Gatlssi~n

m o s t of their properties

will mention h e r e

reali-

for higher-

stocha.stic s e q u e n c e s .

only t h o s e p a p e r s

ted to the subject of this work, the p a p e r s

modular

others), a n d yielding better estimation a c c u r a c y

(o.nd non-CTaussi~.n)

We

(orthogonality a n d

which

reffering for m o r e

citied ( a n d the r e f e r e n c e s

are closely c o n n e c -

complete

bibliography to

therein),

ACKNOWLEDGMENTS

I am p a r t i c u l a r l y indebted to Professor Patrick DewZlde of the D e l f t University of Technology for ~is helpful suggestions and h i n ~ introduced in many stim~at~ng and f r u i t f ~

disc~sio~,

~ p e c i a ~ l y d~ring my o n e - y e n s t a y

in Delft, which h ~ undoubtedly inspired t h i s work. I am ~ o

g r a t e f u l to P r o f ~ s o r M~ian S. P i e k ~ s k i of the Technical

Unive~Zty of Wro~aw for his valuable commen~ and d ~ c ~ s i o n s

concerning

t h ~ work. I wish to thank ~ . manuscript.

Zdzislawa Zabska for her c ~ e f u l typing of t h i s

CONTENTS

CHAPTER

i, I N T R O D U C T I O N

CHAPTER

2. N O N L I N E A R A UNIFIED

.......,........................................... ............... PREDICTION APPROACH

I

FILTER PROBLEM: .................................................... 1 3

2.1 H i g h e r - o r d e r stochastic sequences ........................................... 1 3 2.2 N o n l i n e a r lea~st-squares prediction: Algebraic a p p r o a c h ......... 20 2.3 N o n l i n e a r least-squares prediction: Geometric a p p r o a c h ........ 24: 2.3.1 S p a c e of t h e r e g u l a r V o l t e r r a f u n c t i o n a l p o l y n o m i a l s .......................... ............................................ 2 4 2.3.2 S p a c e of g e n e r a l i z e d c o e f f i c i e n t - m a t r i c e s .................. 26 2.3.3 S p a c e of g e n e r a l i z e d z - p o l y n o m i a l s ........................... 2 9 2.3.4 I s o m e t r i e s ........................................................................ 3 2 2.3.5 S t o c h a s t i c n o n l i n e a r e s t i m a t i o n .................................... 3 5 2.3.6 O p t i m u m generalized matrix approximaUon ................. 36 2.3.7 O p t i m u m generalized polynomial a p p r o x i m a t i o n .......... 3 8 CHAPTER

3.

GENERALIZED

NONLINEAR

LA/DDER-F'ILTERS

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

4O

3.1 I n d e x - s e t s a n d their o r d e r i n g ...................................................... 4 1 3.2 N o n l i n e a r filter algorithm: t i m e - d o m a i n a p p r o a c h ....................... 4 8 3.2.1 'Local' e s t / m a t e s a n d errors..• ......................... ............. 5 1 of s u b s p a c e s ......................................... 5 5 3.2.2 D e c o m p o s i t i o n b a s e s .......................................................... 5 7 3.2.3 O r t h o n o r m a l Cholesky factorizat.[ons ............................ 6 0 3.2.4 G e n e r a l i z e d F o u r i e r s e r i e s e x p a / n s i o n ..................................... 6 1 3.2.5 M - D r e c u r s i o n s ................................................ 6 2 3.2.6 O r d e r - u p d a t e approxim~ion of t h e M - D impulse 3.2.7 O p t i m u m responses•..•••....•.••••.•••••....••.•.•.•...•......•..•.....••••...•.••.•.•.....7 0 3.2.8 E s t i m a t i o n a c c u r a c y ........................................................ 7 1 3.3 N o n l i n e a r filter algorithm: t r a n s f o r m - d o m a i n a p p r o a c h .............. 7 4 3.3.1 'Local' e s t i m a t e s a n d e r r o r s ......................................... 7 6 3.3.2 D e c o m p o s i t i o n of s u b s p a c e s , ON bases and M-D ~'~ourier e x p a n s i o n ................................................. 7 9 3.3.3 0 r d e r - u p d a t e r e c u r s i o n s ................................................ 8 3 3.3.4 Optimum ON approximation of t h e s e t of M - D t r a n s f e r f u n c t i o n s ............................................................ 8 5 3.4 N o n l i n e a r time-variax:t ladder~-filter.............................................. 8 6 CHAPTER

4.1

4. T I M E - I N V A R I A N T LADDER-FILTERS Shift-invariance

AND 'QUASI-LINEAR' ................................................................ 9 1

of inner--produc~......... ........................... ...........

91

6.2 T i m e - i n v a r i a n t n o n l i n e a r ladder-filter ~Igorithm......................... 4.3 ' Q u a s i - l i n e a r ' l a d d e r - f i l t e r s............................................................ 4.4 E x p e r i m e n t a l e x a m p l e.....................................................................

93 98 106

CONCLUDING

REMARKS

REFERENCES

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

109

............................................................................................. II0

APPENDIX

i .................................................................................... 116 • , * • t • • •,,• •

APPENDIX

2

.................................................................. ........... ....•........ ..... .

127

i. I N T R O D U C T I O N

(a,B,u)

Let

tract set w h o s e sets of

elements

a, a n d

will u n d e r s t a n d which

~s

denote

U

are

12du

<

oo. W e

inner-product

the metric

will b e

d(.~v,v) =

a Hilbert s p a c e .

t + Yt = wt(u) ce if for all {y}. T h e ence

will b e

and

I.q-th o r d e r

w:~

sense

~ + ]lq

on

we

for

IL2(n,B,~ )

llwll 2 = ]E { Iwl 2}

some

index-set.

sequence a

K-th

will b e

order

A

map sequen-

denoted

stochastic

the joint probability

assumed will b e

so

called

k=l,...)I~

known,

by

sequ-

distribu-

that the fiFst

to b e

,

lu2(c,B,u)

a Hilbert stochastic

by

if for

of s u b -

IL2(~ ,B,•)

completeness,

bein~

called

{x}

abs-

I.~ a-

Two

sto-

statistically e q u i v a we

will h a v e

the fol-

]E{ ytl...Ytk } = ~ {xtl...Xtk}

problem

variable

maps

inner-product

called

are

a-algebra

B. B y

the n o r m

described

in a n

bar s t ~ d i n g for complex con-

, T

will b e

f~

on

{Ytl,...,ytk } , k=l,...,K

{y}

equalities

The random

tET

IE {ytl...ytk } , k=l,...,K

lent in a w e a k lowing

introduce

llw-v]I . A s s u m i n g

will b e

tions of the subfamilies

sequences

is a

measure

will i n d u c e

Let

{y }

if its properties

chastic

u, B

]E{ ly t 12 } < co . T h a t

collection

verages

where

by

- ~{~%},

~ IL2(%B,~) t aT,

space

of C - m e a s u r a b l e

(w,v) ~ fa w 0 ) : ~ ( u ) d ~

a~d

denoted

is a probability

a collection

5n~ w ( u )

jugation. T h i s

me

a probabilit~

of prediction

being

'past' subfamily

A Yt = Ytl t-l,t-2,...

is to c o m p u t e

a fixed function

from

{y}

conditional

{yt_l,Yt_2,... } . Statin~ the p r o b l e m

within the Hilbert s p a c e

framework,

the estimate

will b e

upon

, a so-

~eome£rically, optimal

if

A y%

will b e the orthogona]

projectior~

b y %hat 'pas%'. In that case, A ^ et = Yt - Yt

error spanned

by

upon

the closed

the length

will b e

sp~ned

H et]}2 = ]E {] etl 2}

minimized.

{yt_l,Yt_2,...}

subspace

Denoting

, a~nd b y

P

by

~

of the

the s u b s p a c e

the or~hogona/

projection o-

perator taking projection o n the s u b s p a c e ~f , the o p t i m u m estimate ^ _t of Yt will b e Yt = p Yt since the coprojection et = P Yt will be orthogonal

to

~f . Consequent/y,

the p r o b l e m

of prediction

is to corn-

pure t h a t p r o j e c t i o n .

Projection

of

Yt

on

~f

determines

ting o n the 'past' of the s e q u e n c e the least-squares

sense)

a prediction

{y}, a n d yielding the 'best' (in

approximation

of that r a n d o m

notion of 'best' approximation

relies n~turally o n

between

filter

the 'ideal' prediction

a/nd the o p t i m u m The

distance

squares

approximate

between

discrepa/qcy

input collection; ver~ the p r o b l e m able

yt)

'ideal' filter

F)

into the s p a c e e.g., Victor a n d

notion

where

~

indicates

(producing fo b e

a~sser~ed

yt) , ~t ) .

the lea~t-

o v e r the entire

permits

approximation

form

mapping

a vector

one

to c o n -

(of the r a n d o m

approximation

the s p a c e

space

vari-

~f the

choice

the

multiplication

the a v e r a g e

over

a/'e taken)

see

is equivalent

corresponds

of input s e q u e n c e

filters

of excitations

in a natural way,

Addition in %hat s p a c e

of filters, a scalar

between

Fa

observation

from ~Nhich the excitations

o~ ' d i s t ~ c e '

The

of filters.

(1979).

of the filter gain. T h e

babili~ s p a c e

This

as d e v i c e s

of r e s p o n s e s Knight

be

output is just

of 'best' deterministic

in a s p a c e

parallel connection ch~ge

12 }.

of 'best' stochastic

Pilters, c o n s i d e r e d

filter

variable.

a notion of 'distance'

their ou%tputs, a v e r a g e d

]~ ~yt-y t

into the p r o b l e m

(whose

filters c a n

between

i.e.,

F

prediction

the two

filter, o p e r a -

to

to a

(i.e., of the pro-

yields naturally a

il FI-F2112 = E{IFI(') - F2(')I 2} the input probability space.

The

3

inner-product (FI,F2) We

the s p a c e

notice that w e

however, Such

on

A - E{FI(.)~52(-

might h a v e

tion s c h e m e

by

tive to the e n s e m b l e be

completed

ximation p r o b l e m ted a s

~'

to form

= 15"/F °

non-zero

filters,

of excitations.

subspace

will contain

Consequently,

excitations). T h e Hence,

problem

in the s p a c e

of the s p a c e

eus t i m e - i n d e x e d

will c o n s i -

filters (rela-

space

K~'

the stochastic

variables

c~

all

identifica-

we

of the distinguishable

of the r a n d o m

Considering the e l e m e n t s

II FII 2 = ] E { I F ] 2 } .

in the e n s e m b l e

a Hilber~ s p a c e .

in the s p a c e

ats follows

from the zero-filter in a n

of the u n d e r l y i n g

tors or, equivalently,

for s o m e

. That

o

introduced

the n o r m

0

the input e n s e m b l e .

the filter a p p r o x i m a t i o n

(1910)

K~

not distinguishable

implied

=

a~e. z e r o

a subspaee

der the quotient s p a c e

now

will i n d u c e (F,F)

will b e

filters will f o r m are

of filters will b e

) } , and

their outputs

filters w h i c h

~'

now

may

approbe

trea-

of fitters.

of filters

K~'

functionals, it follows

as

opera-

from F r e c h e t

that the r e g u l a r Volterra functional p o l y n o m i a l s

M

GM; t =

Z m=l

Vm; t

(1.1)

where

Vm; t

with

am;jl...j m

0

=

for

2

Jl

...

~

Jm

subspace

ble, a n d

the Volterra functionals

theorem,

in the s p a c e

nomials

will f o r m

is a natural genera/ization

(sufficiently regular) form

functions

a complete

(see

Volterra

of filters. H e n c e ,

stating that p o l y n o m i a l s

span

so

countable

(,.2)

m;Jl'"Jm YJ l'"YJm

Jr >t , r = l ..... m

a dense

sis). T h l s

a

(to functionals)

that the s p a c e set.

that s p a c e

a countable

a dense

(1959))

span

is sepe~ra-

complete

set

(ba-

of the W e i e r s t r ~ s

subspace

in the s p a c e

is s e p a r a b l e ,

and

of

poly-

4 Consequently, exists) c a n

e~ch

filter

be approximated

5'

(for -vvhich s u c h

representation

arbitrarily %yell b y the Vol£erra series

oo 5` =

wT h i s

means

subspaces

~

t h a t the given filter

v {V

}

whose

v

F

(i.3)

m

is a p p r o x i m a t e d in the s u b s e q u e n t

elements

are nonlinear Volterra-type filters

m

of the s u b s e q u e n t be the s u b s p a c e

degrees

of nonlinearity. W e

of linear filters; v {V2}

notice that

v {V 1 }

will

will consists of the s e c o n d -

degree

nonlinear filters, etc. C o m p u t a t i o n

series

(1.3) will therefore consist in determination of the set of multi-di-

mensional

(M-D)

impulse r e s p o n s e s ,

•

,

of the subsequer~t terms in the

see

e.g., S e h e t z e n

(1980),

rn=l,2,...}

(1.4a)

{ at;jl..4m

of the approximate

nonline~.r filter

ly, of the set of M - D

(in time-dom(~/n)

(in f r e q u e n c y - d o m ~ d n ) ,

i@ m)

, m--l,2 .... }

t

is station~y, the approximate

is r e m o v e d

remark

means

f i l t e r will r e s t r i c t

v { v 1}

o n l y . In t h a t c a s e ,

b y the I - D

caSe. If the

nonlinear filter will b e time(1.4)

provided the varia-

(following the shift-invariance of inner-product in sta-

tionary c6use). W e of a l i n e a r

(l.4b)

in the time-variant (nonsfationary)

invaria-nt, a n d will b e r e p r e s e n t e d b y the sets ble

or, equiva/ent-

transfer functions

{ At( eiSl

input s e q u e n c e

F a

members

that approximation of the 'idea/' filter

the

the

considerations

approximate

of the sets

(1.4).

linear

9"

by

to t h e s u b s p a c e

f i l t e r will b e

described

5 The sense

series-expansion

is valid only for the analytic

or Gateatax) elements

of F r e c h e t

5-'or non-analytic

F

filters, the W i e n e r - t y p e

sort of e x p a n s i o n

This

(1.3)

can

be

of the s p a c e

expansion

introduced

via

lization of the Volterra functional polynomials inner-product

considered.

(Gram-Schmidt)

orthogona-

(i.I)

relative to the

Orthogonalization

complete

implying the orthogonal

of

set

orthonormal

{WM , M=I,2,... } , being actually a n ON basis of the s p a c e and

]5"

be

G M

will yield a countable

basis

of filters

should

implied b y the input probability- space.

the Volterra-type

(in the

of filters,

decomposition

(Do

~'

=

Z

•

v

{w M}

(i.s)

M=I

where

(WM'WN)

W M

= 6M,N

of that

ON

basis

being

the

M-th

ments Wiener

cla~s. H e n c e ,

represented

F

will b e

orthogonal

=

co • M=I

M-D

filters, m u c h

class

F

orthogonal

Fourier

=

Z (F,Wm) m= 1

< co , will

series, with

of orthogonal

series

series

That

be

of nonlinear

series ks c o n v e r -

is c o n v e r g e n t

(1.6)

(F,WM)

the 'ideal' fil-

than the cl~ss

expressible

expansion

Volterra-

(1.6)

input s e q u e n c e ) .

of analylic

for a wider

in terms of c o n v e r g e n t can

b e partitioned into

(relative tO the rvl-th term)

components

M

F

2

ele-

series-expansion

of filters (functionals)

the two, mutually orthogonal,

I] F{J

kernel. In other words,

in terms

orthogonal

the

filters of the

functional Fourier

than the functions

series. T h e

with

W M

like the 'usual' Fourier

cleuss of functions

orthogonal

member

delta. E a c h

subspaee

, for w h i c h

(F,WM)

filters (for a given

Kronecker

or£hogona/

nonlinear

auny filter

represented

gent for a wider

Taylor

degree

being the

is actually the stochastic

being the genera/ized ter

will span

b y the W i e n e r - t y p e

F

which

~M,N

'

co

W m

+

Z re=M+ 1

(F,Wm)

W m

(1.7)

6 :l~he first c o m p o n e n t lhogonal

esf/mate

F~

a~ the orthogonal subset

will e x p r e s s

the o p t i m u m

of the 'idea/' filter

projection of

{WI,,.,V~M}°

The

F

second

component

the first R H S

mad M - t h

approximate

nonlinear

F

degree

, and

can

o n the s u b s p a c e

fion error. In other words, desree

M-th

nonlinear

b e interpreted

spanned

will e x p r e s s

term in (i.7)

or-

b y the

the a p p r o x i m a -

will b e the opti-

filter; i.e.,

M

F

Observing optimum

~

FM =

~ m=l

(F',Wm)

Wm

that the output of the 'idea/' filter

M-th

ximate filter

degree F~

nonlinear

estimate

ar filter will yield the o p t i m u m

M-th

de~ree

cha.stic approximation

since

the n o r m

spondin~

to the s e c o n d

computation 2M-th

of (I.8)

order

(i.e.,

It s h o u l d will c o r r e s p o n d F

by

means

RHS

sequence,

Yt

of that approximate

of the error will b e

eM; t

minimized.

will b e

that the linear p r o b l e m

the first

approximation

-

F ,~

Hence,

2M

covariances ~iven.

prediction p r o b l e m

prediction filter

to

M=I

F a In that c a s e i "

v{ W l }

with the c o v a r i a n c e

(1.9)

will b e data

only, so

in (i.7), a n d

= ( m , w I) w I

the linear estimation p r o b l e m

of

of the 'idea/" prediction filter

restricted to the s u b s p a c e

will c o r r e s p o n d

(corre-

of the o p t i m u m prediction of the

provided

of the linear a p p r o x i m a t e

nonline-

solution to the sto-

~{yjl...yjmYkl...yku } , m,u=l,...,IV[) are

to the o p t i m u m

while the

is the output of the appro-

be noted that the linear least-squares

the considerations

Consequently,

equa/s

nonlinear

term in (1.7))

solves the p r o b l e m

stochastic

that sequence

B"

A YM;t

, %re notice that computation

problem

(1,8)

associated

cond-order

sequences

cond-order

statisf/cS are sufficient in order to characterize

with s e -

IE{yJlYkl}.~ . If the sethe underly-

7 ing s e q u e n c e fi/ter F ~

completely

will b e c o m e

and non-C~aussian saHsfactory.

(the G a u s s i a n

case),

the best possible

sequences,

In that c ~ e ,

the linear approximate

filter. In c a s e

the linear estimation

estimation a c c u r a c y

of higher-order

accuracy

may

may

be improved

cing the linear estimation s c h e m e

b y the nonlinear procedure,

higher-order

to

terms

corresponding

fact that in the linear case, Fourier

kernel

M=2,3, .... T h i s

the n o r m

degree

lleM;til2 .

Orthogonal who

i(~. wl)

nonlinea/~ c a s e

llytii2 _

Gram-Schmidt

expansion

Hermi%e polynomials,

and s h o w e d

by Cameron

of the IO2-funcdono/

Ito (1951)

and

~A~a~ c o n s i d e r e d who

introduced

process.

(194:7)

using C O N

following K a c z m a r z

problem

I(F,WM ) 12

Martin. Introducing the Volterra functiona/ polynomials ries, W i e n e r

(1958)

presented

orthogono/ ON

nonlinear

development

of C O N

sys£ems

Bomret

mathemcLtical representation,

The

orthogonal

and

into the latter s e approximation

the theory

(1963)

for a functional of a stationary s e q u e n c e ,

polynomial-functiona/s.

the

and Wie-

of C a m e r o n

form, underlying

with m e m o r y .

of

proposed

his theory of the orthogonal

of a IL2-functional in the W i e n e r - s e r i e s

work

(1935),

a deeper

series

for

set of multi-variate

direct orthogona/

its relation to the Pourier-Hermite

process

The

who

Steinhaus

from

(1.10b)

to W i e n e r

or%hogono/ization

o/nd Martin

preceded

viewpoint b y

the first

(1.1oa)

of a IL2-functional is d u e

Wiener

The

by

wile h a v e

I(F,Wl) I 2 _ ... _

representation introduced

we

of the W i e n e r

ner (1938).

introducing

i 2.

the Volterra functional polynomials

orthogonal

repla-

only; i.e.,

while in the M - t h

was

by

follows from the

of the error is r e d u c e d

[[ el;tl[ 2 ,~ ii ytll2

(194:2,1958)

b e not

proposed

of the the

using £he set

'gate-functions'

approach

8 was

introduced

pansion

by Bose

(1958).

for a functional of P o i s s o n

"l~he orthogonal

development

processes

introduced

was

functional Fourier was

discussed

were

Ogura

series

by Yasui

also c o n s i d e r e d

Knight

(1979).

The

developed

systems

with m e m o r y , class

b y 5egall

the O N

ex-

using Charlier polynomials.

a/qd I<[0/lath (1976).

Stochast/c

for a functional of 'orthogonalizable' (1979).

Or£hogono/

Hida and

in m a n y

(see

process

considered

for a functional of independen£-itlcrement

Volterra a n d

ted a n d

Wiener

by

(1972)

Wiener

works,

later t e r m e d

Schetzen

Ikeda

expansions

(1965),

and

processes

of that sort

b y Victor a n d

theories h a v e

been

investiga-

yieldin~ the theory of the nonlineau ~ the nonlinear

(1980),

and

systems

of the Volterra-

the references

therein).

In t h i s work we w i s h to i n t r o d u c e efficient adgorithms for c o m p u tation of t h e n o n l i n e a r o r t h o g o n a l approximate prediction filters (1.8)

the Volterra-Wiener ved

on

class, for higher-order

a finite time-interval. W e

stochastic

will derive

recursive

sequences

of

obser-

algorithms

of the

n o n l i n e a r digital ladder-filters, in which estimation a c c u r a c y c a n be improved succesively

nonlinear

via updating

the order of the filter. W e

prediction filters with or£hogonal

sections

are introduced

updated,

without aitering the existin~ structure

sequen£1y,

we

wish

to present

filters, yielding better for higher-order -

obeying

to the filter e a c h

structures,

and

a closs

and

only 'new'

its parameters.

of nonlinear

sequences

the attractive properties

where

consider

time the order of the filter is

(tharL in the linear treatment) non-Gaussian

will

of m o d e r n

on

o~hogonal

Con-

prediction

estimation a c c u r a c y

one

hand,

o n the other

linear orthogona/

digital

filters.

The me The

orthogonal

linear ladder-filter

and~or in f r e q u e n c y - d o m a l n s , Levinson

(1947)

using

algorithms

algebraic

algorithm cox~ s e r v e

o.s a n

can

be

derived

o~nd~or geometric example

in ti-

methods.

of time-domain

9 algebraic solution in the autoregressive ( A R )

stationary- case, s e e also

Kailath (1974), If the underlying s e q u e n c e

is

(1982)), the S c h u r pa~ametrization m e t h o d

(see Lev-Ari (1982); Kailath

(1982);

L e v - A r i and Kedlath

efficient realizations generalized salve,

mials,

~chur~Levinson

Genin

Levinson

of the

and

method

and

Kamp

(1983)

to the

cetn be applied in o r d e r to obtoin

innovations/modeling

linear

methods

is closely

related

(1982))

of Deprettere

can

be

connected

Schur

Kailath (1978); Delsax~e, G e n i n

s-statlonary (see Kailath

used

theory

algorithm

and K a m p

and

Lie

of ON

(see

(1979a)).

The

(1980);

in nonstationar~

to the

(1917)

ladder-filters.

case.

Szeg~l

Dewilde, The

DelThe polyno-

Vieira

and

linear filter

problem can be equivalently considered in the s p a c e of functions squareintegrable w.r. to the spectral m e a s u r e

of the underlying s e c o n d - o r d e r sta-

tionary stochastic sequence, u n d e r the I
filters

(see

Deprettere

and

(1981); Deprettere (1981)1 Dewilde

Dewilde

(1979),

(1982)), T h e

realizations of

Dewilde

and

Dym

problems of Darlington

and c a s c a d e synthesis, a n d interpolation with positive real matrices, considered

in

Piekarski (1971,197~=); Piekarski and S a e e d

(1980; Piekarski

and Uruski (1984), are closely c o n n e c t e d to those topics, T h e S z e g ~ theor%& resulting in the approximate rea/izations of the A N ving a v e r a g e

(MR)

Levinson~d

mo-

filters a n d equivalent to the S c h u r method, can be ge-

neralized to the rational ( A R M A ) (1978); De%vilde a n d D y m

case

(see Dewilde, Vieira a n d I
(1981)), This approach, introducing the S c h u r

algorithm in geometric context, underlies the theory/ of the linear A R M A

innovations~modeling

orthogoned filters, which c a n be applied in order to

solve the lossless inverse scattering problem; the Neva/nlinna-Pick interpolation problem; the optimum stochastic modeling problem; the m a x i m u m entropy spectral approximation problem, in discrete- and/or in continuoustime c a s e s

(see Dewilde and O y m

(1981,1984), Dewilde

(1982,1984);

Deprettere (1981); Mort, Vieira, L e e a n d Kailath (1978); I-
I0 Delsarte, G e n i n

and Kemp

theel a n d D e w i l d e (1982),

(1979b); Deprettere a n d D e w i l d e

(1979); P r a b h a k a r a

Rao

a n d the references therein). T h e

and Helmond

(1979), Bul-

(1983); W i d y a

linear ladder-filter algorithms can

b e equivalently derived using projection m e t h o d in time/or in frequencydomains The

(see Delosme

and Morf

(1982);

adaptive properties of the filters c a n

M o r f a n d F'riedlander (1981); Deprettere

(1982)). T h e

Kailath (1982); D e w i l d e also be c o n s i d e r e d

Kallath (1982); Deprettere

(1982)).

( s e e Lee,

a n d Lie (1980);

orthogonal linear ladder-filters c a n b e efficiently

i m p l e m e n t e d using V L S I technology, if the standard filter sections are interpreted in terms of hyperbolic or circular rotations, a n d then realized using C O R D I C S Ahmed

processors

and Morf

Depre£tere

(see Wolder

(1982); Lev-Ari

(1959); T u s z y n s k i

(1983); D e w i l d e

(1983); Deprettere, D e w i l d e

and Udo

(1980);

(1982,1983,1984b);

(1984); Deprettere a n d

~alnand~nsing (1984)). Generalizing the linear ladder-filter algorithms, the nonlinear prediction filter p r o b l e m c a n b e stated a n d solved algebraically ( s e e a~d Dewilde method

(1983); Z a r z y c k i

(Zarzycki

(1983))

(1984a-e,1985a))

Zarzycki

or, equivalent/y, using p r o j e c • o n

yielding or£hogona/ representations

of the nonlinear prediction filters of the Volterra-VJiener class

(see

Za-

rzyck] ( 1 9 8 5 5 ) ) .

T h i s work c a n be outlined a~ follows: In c h a p t e r 2 we introduce the nonlinear least-squa/~es prediction problem algebra/caJ/y, and geometrically in the t h r e e following isomorphic v e c t o r s p a c e s : of the r e g u l a r Volterra functional polynomials; of g e n e r a l i z e d (block, multi-indexed) matrices; ~nd of g e n e r a l i z e d (block, multi-vari-

ate)

z-polynomials. W e

lem in the first s p a c e p r o b l e m of o p t i m u m

can be

that the nonlinear stochastic estimation probequivo/ently c o n s i d e r e d

as a deterministic

approximation of the set of I~-D impulse r e s p o n s e s

the filter in the s e c o n d terministic p r o b l e m

show

space. In the latter space, this will b e c o m e

of polynomial approximation of the set of M - D

of

a de-

transfer

11 functions of that filter, In chapter

3 we

present

recursive

stationary nonlinear prediction spaces

of the generalized

V~e derive nonlinear

solutions to the n o n -

usin s projection m e t h o d

mettrices~ a n d

a nonstationary (Levinson)

problem,

geometric

of the genera/ized

nonlinear ladder-filter

time-variar, t prediction

in

the

z-polynomla/s.

algorithm, yielding the

filter with the orthogonal

stru-

cture°

Chapter

tO the p r o b l e m

4 is d e v o t e d

nonlinear ladder-filter. W e

introduce

following the shif£-inva/~iance ry case. Further

complexity

quence

stocha~stic

reduction

is l o w

(in a s e n s e

In A p p e n d i x

nonlinear

b y introducin s a cl~ss

with the o p t i m u m

whose

of

'dlstance' from the G a u s s i a n

matrix

(mu/ti-indexed)

2 the 'loca/' order-update

filter sections

prediction

se-

defined).

i the generalized

lined while in A p p e n d i x ponding

to b e

in the

in the higher--order stationa-

is a c h i e v e d

associated

sequences

reduction

a time-variant nonlinear filter algorithm,

of inner-products

of 'quasi-linear' ladder-filters, higher-order

of complexity

theory

recursions

i s out-

a/nd corres-

are presented,

USAGE: Capitals

~f,Z,... will usually denote

multi-indexed used

(multi-dimensional)

for their entries, m A

spaces;

matrices

-~viU denote

2A

a 'domain'

will denote

be matrix;

of the

a rect~/ngular

etc, T h e n ,

(ro'vv) matrix %vhose

. Thus,

a m-indexed

block-entries block

]lq . T h e

IA

... M A

ore

(square)

"~ will indicate the unit-circle

will indicate

matrix with entries

mA : DmA

(or 'usual')

{ M }A ,ffi [ I A

stand for a generalized entries.

mA

A,H,...

while lo%ver cause letters will b e

a. , a n d will b e interpreted as at m a p JlO0O]m m-variate index-set DmA into the reals termed

caplta/s

DmA

wil/ b e matrix;

-~ ]R , m a p p i n g

will therefore

a row-matrix 3A

] ~vill b e

(or vector);

a generalized { M×M

matrix with multi-indexed { z:

Iz I =

be

will stand for a cu-

m - i n d e x e d matrices.

'~-

the

i }

while

block }A

will

blockm,,~

12 will b e

the

unit m-tor,ls

integrals a r e gration

are

collection

taken

m.~. =

over

sequences

gular

of the H e r g l o t z

assumed

to b e

are

absent.

will sta~nd for 'lhe s p a n will d e n o t e

will indicate index-sets, dex-set

mL

Hermi%io/% 'outer' and =

ring. ~f'he s y m b o l

yj

and,

j

eJ

(relative

-

tro2%spose;

purely

used

will be

s

product.

will d e n o t e (m-copies),

sequence;

for c o m p l e x (or

Capital

L

a 'symmetric obtained

will sto.nd for expectat/on.

i.e., a All

measure) operators;

is v

conjugation;

orthogonal) will b e

part' of the

due

of inte-

i.e., the sin-

Lebesque

projection

all

index-set).

stochastic;

direct

noted

the limits

some

to the

will indicate

will b e

hence,

(J b e i n g

mea~sure P

othe~ise

a stochastic

to b e

or K r o n e c k e r

IE

~K~

assumed

of';

... x L

. Unless

will d e n o t e

C~pi%al

symmL L×

{ y}

variables

stocha~tlc p~

® ... ® ~

the unit-circle

not indicated.

of r a n d o m

~

~

sum; ®

reserved m-varia%e

to l e x i c o g r a p h i c

for in-

orde-

2. N O N L I N E A R

PREDICTION

In this chapter filter p r o b l e m

me- and

We

responses

the M - t h

can

be

sequences

APPROACH

nonlinear observed

and

predict/on on

a finite

~eometrica~/ly,

in ti-

that the nonlinear lee~st-squa/es

equivalently

approximation

considered

ms:

of the set of M - D

impulse

of gene~'a//zed

(block,

matrices;

of deterministic

approximation

functions of th~£ filter, in %he s p a c e

of the set of M - D

of genera/ized

transfer

(block, multi-varia-

z-polyno mio/s.

2.1 Hi~her-order

Let

[y}

stochastic

denote

sequence

will b e

sequences

a scalar,

cond--oFder Silbert s e q u e n c e This

UNI~'IED

degree

of the nonlinear filter, in the s p a c e

the p r o b l e m

re)

A

adgebr~dcally

showing

of deterministic

multi-indexed) -

state the p r o b l e m

estlmatLon p r o b l e m

the p r o b l e m

PROBLEM:

order stochastic

in frequency-domal/ns,

stoch~£ic -

%re introduce

for 2 M - t h

Ume-inteFvaL

FILTER

zero-mean

observed

represented

on

and

purely

stochastic,

the time-interva/

b y the ra~ndom variables

L = [0,oo) y_j

col

[y_~ ]j E b

.

contai-

n e d in the followin~ column-matrix

Y =

se-

(2.1)

14 The

following t w o - i n d e x e d

H -- I E { Y

whose

(second-order)

® "}}

covariance

meLtrLx is

(2.2)

,,, [ h j , k ] j , k ¢ L

entries are given b y

h j , k = ]E{ Y-j'Y-k }

Given

the c o v a r i a n c e

d~tet (2.3), w e

(2.3)

c a n introduce the following 2-D tq'ou-

tier transform pair

W ( e i O, e i ~ ) =

1

hi, k =

where

W ( e i8 ,eI ~J)

co E j=-oo

5 d 8 [d~

is the 2-D

n=0,...,N

axed let

the finite time-interva/ (offset) a n d then

X

n

hj,k

e - i J O eik~

we

(Z.4b)

{y}, satisfying

. - '/V(e*" ,e'. e)

(2.4c)

x=0,...,N-n . If the s e q u e n c e

L x _A_ { x,...,x+n } , w h e r e n

x

is o b s e r v e d

is ~ reference

will b e repleced b y the submattrix

will associate

covariaz~c e

with

{y}

the

following

(2.5a)

Hermitian,

positive-definite

matrix

Hx E{yX n = n

~ ~x} n

(2.5b) =

[hj,k]

(],k) £ b x x L x n n

on

point

indicates the rax~ge (or 'order' of past observ~ttions),

y X = col [ y_j]

and

(2.4a)

e ije W ( e i e , e i ~) e-ik a

spectral function of

W ( e i e,e i ~)

Let

oo E k=--oo

15 Assuming we

that the s e q u e n c e

will obtain for

is stationary

{r

}

second-order

sense),

j,k~...,-l,0,1,...

hi,k = hj+l,k+ 1 - h k _ j = r

where

(in a w e a k

is t h e

cova~ciance

,

P

sequence.

p=k-j

From

(2.6a)

(2.6a)

it follows tha£

P

Hx = H x+l~ n n

regardless

rely stochastic)

Now

can

noHce

consider

j EL

and

introduce

of %he rat*don v ~ i ~ b l e s

(j,k) c

LO

block-entries

display the Toeplitz proper-

m~trix of the s e c o n d - o r d e r (2.4)

~sociate

stationary

will b e replaced (since

se-

b y %he I-D

the s e q u e n c e

is p u -

sequence.

a 2M-th

order stochastic

sequence

{y}, sa-

m=l,0..,M

ly_jl 2m }

<

(2.7)

oo

the following M - b l o c k a n d £heir products

[my]

(column),

(see

m = 1 .....M

e/~e the followin~ m - i n d e x e d

with t h a t s e q u e n c e

m-indexed

also A p p e n d i x

matrix

i)

(2.8a)

matrices

my = [y_ji...y_j m ] Jl ..... Jm E We con

(2.6b)

×L O n n

%/qat (2.6)

the rela£ions

{ M }y ~. col

whose

]

rela~in~ the spectra/ d e n s i ~

~{

we

hk-j

£o the covariaunce

let u s

#/sfying foF

- [

cova~i~ce

{y}. In tha£ c ~ e ,

Fourier transforms,

Then

n

of the x-shift. W e

ty of £he t w o - i n d e x e d quence

T

the generalized,

(2.8b)

(MxM)-block

(squ-

16 are), ( m + u ) - i n d e x e d c o v a r i a n c e

matrix

N

iB{{M}y ® {M}y}

{MXM} H .

(where

®

Appendix

m~u H

=

=

[meuH]

(2.9a)

m,u=l,...,M

indicates 'outer' product of generm/ized matrices, s e e also I), w h o s e

~{r~®

(m+u)-indexed

block-entries are e x p r e s s e d

u.2} =

. [hj1""Jmkl"'ku]

as

(2.9b)

.

]l,...,]m,kl,...,k6 b

with

h

Each

-

submatrix

(2.9b)

c a n therefore b e interpreted as the (m+u)-th or-

der c o v a r i a n c e

matrix of the 2 M - t h order s e q u e n c e

that

will r e d u c e

{MXM}H

second-order

(2.9c)

-

JI'""jm k i' '"ku ~ ~D { y_j 1 "".y-jm y-k 1"""Y-ku }

sequence

quent p a r a g r a p h s

to the t w o - i n d e x e d

we

if

assume

M-I.

[ y }. Let u s

matrix

We

will

H

prediction problem, m u c h

like the t w o - i n d e x e d

the linear problem. W e then f o r

--

~ll

=

stands for the s u m m a t i o n

pariitioning the (re+u) pairs, s e e

e.g., W i e n e r

the G a u s s i a n

i 0'iH of the

least-squares

matrix (2.2) is associated

sequence

random

}

-k ?

0

symbol

matrix

is

m,u=l,...M

{Y-J1"" " y - j Z - k l " ' ' y - k )

where

the s u b s e -

notice that if the hitcher-order s e q u e n c e

I~llE{y_j --

in

of this chapter that the generedized c o v a r i a n c e

with the M-th d e g r e e nonlinear

Gaussian,

(2.2) of the

show

(2.9) will b e associated

with

observe

, (re+u)

even

, (re+u)

odd

S

{ 2.1o)

o v e r a H distinct w a y s

variables into products

(1958). tl~his m e a n s

of a v e r a g e s

of of

that the 'information' about

is contoined only the t w o - i n d e x e d

submatrix

{MxM}I-I , as the entries of all higher-order (i.e., even-

17 order)

covariance

matrices

meuH

are expressible in terms of the

entries of the left-upper submatrix

101H

Consequently,

to the p r o b l e m of o p t i m u m pr.ediction

a nonlinear a p p r o a c h

of a 2 M - t h order stochastic s e q u e n c e cy if the s e q u e n c e

is n o n - G a u s s i ~ n .

(in the s e n s e

of (2.10)).

will yield better estimation a c c u r a Otherv¢ise, ~he higher-order covari-

a n c e matrices will not cont~dn o.ny 'new' information about the s e q u e n c e , and the linear prediction filter (associated with

l e IH)

will b e c o m e

best possible filter (in the least-squares s e n s e )

for a O a u s s i a n

the

sequence.

Introducing a s h o r t h a n d notation

e

we

can

tom

m

(e

tel ....,eiota )

consider for

[email protected](eiOm

m,ual,...,M

i u ,e

;

co )

=

~

the M - D

co E

j m,= - o o

kl=.-oo

-ij 1 01

1

}l'"Jmkl"'ku

(2z) m + u

IdOl...

i~ I

(e

E

e

h.

.~-

co ..-

j1=-CO

• u

e *~

(2.11)

co ...

E

h.

ku~--oo

-iJn~ m ...e

Id8 m /d%...

.

Jl"'Jmkl'"ku

ikl~ 1 e

• u

•

iWu)

P'ourier transform pair

m e U % v ( e ] em,e ~(~ ) e

The

.....e

iku~ u ,..e

Id~u

-ikl~

e

(2.12a)

iJlSl

i o..e

...e

-ku~ u

~Jmem

(2.12b)

U

m @UVV( e i Om , e 1 0 J )

c a n be interpreted as the ( m + u ) - d i m e n s i o n a /

s p e c t r a / function of the 2M-th o r d e r s e q u e n c e , satisfying

m ~ ) U W ( e i e m , e i u ) ,,~ m® u~V(e i ~u , e ibm)

(2,13)

18 "Dhen w e

c~n

introduce

the f o | / o ~ n g

MxMIN =

[

containing precisely as the generalized second-order

being

Let u s

.

m

information

covaria.nce

matrix

=

for

. We

to M--i)

[ielw(eiei

.....M

(2.3.4)

about the 2 M - t h

we

order s e q u e n c e

notice that for a would

have

' ,e~i)]

actue]/y the two-dimensiona/

introduce

m,u=l

{MxM}H

(corresponding

i×l~v

1 elM/

u'VV(elO "ei~U)]

m ~

the s a m e

sequence

spectral matrix

(2.15)

spectral function

n=0,...,N , x=0...,N-n

and

(2.4a).

m=l,...,M

the

following multi-varia~e index-sets

mLx

n

where

Lx =

=h

{x,...,x+n} . B y

m}

n xn

{(Jl .....Jm )1 ire

the 'symmetric

part'

symmL x

n

set

(2.i6a)

r = 1 .....

of the index-

n

mLx

we

will u n d e r s t a n d

n

•

~ x

,

.

symmLXn "~ { ( J l " ' " J m ) : J1 E ~ n ; J r " J r - 1 ..... x + n , r = 2 ..... m }

We

notice that aunti-lexicographic

ordering

can

be

(2.i~b)

equivadently introduced

in (2.16b). If the 2 M - t h terval

Lx n

me

order s e q u e n c e

{ M }y

(2.8)

will b e

{y}

is o b s e r v e d

replaced

on

a finite time-in-

by

~

(M},~

n

.

c o l [ my:~] n

m=l,...,M

(2.ira)

19 whose

block-entries

n~n

where

x

ance

matrix

=" [ Y_jI.*oY_jm ]

is s o m e

(M~M

are e x p r e s s e d

{MxM]

H

(2.9)

n

m~uHx = E(myX ® n n

will h a v e

for

{y}

= [ m®%:. ]

® (M}~}

n

(2.za~) m,u,,l,...,M

U[/X} .. n

]

(Jl ..... Jm'kl ..... % ) ( symmLX × s y m m L X

is stationary

(in a w e a k

2M-th

order

(2.zab)

sense),

we

jl,...,Jm,kl,...,k u ,= ...,-1,0,1,...

hjl+l...jm+l,kl+i...ku+ I = h.jI "'']'mkl'''ku

so

covari-

given b y

] I.-4 mkl-.-ku

that

the generalized

will b e c o m e

n

with the block-entries

Assuming

(2.17b) (Jl .....Jm ) ¢ s y m m L X

reference point. Consequent/y,

}H* = E{ { M } x x

-[h

as

(2.19a)

that {IVIxM}HX = { M X M } H X + I n n

regardless

of the x-shift. T h u s ,

(2.19)

__A { M × M } T

(2.19b) n

display the Toeplitz structure of

the generetlized cov~rit).nce matrix of the stationary 2M-th order s e q u e n c e . In that case, the block-Hankel, matrix

{MxMJ'H

w i n b e replaced

plitz, positive-definite matrix (2.*9) will r e d u c e

multi-indexed Hermitian, positive-definite

to (2.6).

{M×M

b y the block-Har~kel, }T. W e

multi-indexed "Doe-

a/so notice that a s s u m i n g

M=I,

20

2.2 N o n l i n e a r l e a s t - s q u a r e s

Let u s observed random way,

o~sume

prediction:

approach

that the 2 M - t h o r d e r stochastic s e q u e n c e

o n the time-interval

variables

Algebro#c

L~

and, h e n c e ,

y_i,...,y N M^

YN;o

nonlinear, N-th o r d e r predictor

, we

of

YO

is

is r e p r e s e n t e d b y the

yo,y_l,...,y_N . In o r d e r to predict

given its N-th o r d e r post

{y}

YO

in a nonlineo.r

define the M-t/q d e g r e e a s the M - t h

d e g r e e Vol-

terra functional polynomial

M^

We

notice

assume

M

N

N

~

~

~

that

(2.20)

will

A =

YN;o

N

m-1 J l - 1 j2=,jl

M=I

""

~

e

jm=Jm_l

reduce

to

(2.20)

"" " N d f " J m Y-Jl"'Y'Jm

the

linear

s o that the linear a p p r o a c h

nonlinear treatment of the problem. T h e

N-th

order

estimate

if we

will b e the first step in the

M-th

degree

nonlinear, N-th o r d e r

prediction e r r o r w i l l then b e

M~

A

M^

N;o = Y o

a n d the m e a n - s q u a r e

M

error

(2.21)

IMsN;o

con be

M

eN; o = aN;oY o +

(2.21)

YN;o

error, a s s o c i a t e d

e;N

The

-

~ m=1

}

r e w r i t t e n in a

with

(2.21), will b e

>

expressed

0

(2.22)

r e n o r m a l i z e d form a s

N N N Z ~ ... ~ aN;il...j m y_jl...y_j m J l = l j2---jl jm=~Jm_l

(2.23a)

where

aN; o =

Md~ql

;

aN;Jl.,,jm

In o r d e r to solve the M - t h

= -

degree

as

N;JI...j m

nonlinear, N - t h o r d e r leo.st-squ~res

21 prediction problem, w e

wish to c h o o s e

the coefficients

such w a y that the m e a n - s q u a r e

error (2.22)

achieved if for

u i (kl,...,ku) ¢ s y m L N _ 1

u=i,...,M

and

aN;Jl...j m

in a

is minimized. This will

be

OIVIR c~N

=

(2.24~)

o

8 aN;kf..ku

Conditions

will imply

(2.24a) M

aN;oho,kl...k u +

Moreover,

E m=l jl=l

N ""

j m=Jm_i

aN;jl...j m h.Jl...Jmkl..*k . u

-

0

(2.2,~b)

get

we

M

5q;ohoo +

N

E

N

N

X E ... E h. Md N m = l jl=l jmmJm_l aN;Jl'"Jm Jl""Jm '° =

G e n e r a l i z i n g t h e notion of 'matrix', we c a n i n t r o d u c e t h e following M-block ( r o w ) ,

m - i n d e x e d coefficient-matrix

{M}AN = [ m A N

whoso

each m-indexed

block-entry

from the m-variate index-set

m%

DmAN

con be considered

D mA N

=

numbers

(2.2~b)

can talk e~bout the 'doma/n' of the m-indexed

that m - v a r i a t e index-set, and

~s a m a p

into the real (or complex)

m%. D m%, -~

Hence, w e

(2.25a)

] m = l .....M

matrix es being

we will have

symmLNI-I

if

m=l

if

m=2,...,M

(2.25c)

22 Consequently,

we write

for

m-2,,,,,M

mAN .. [ °N;Jl""Jm ] and for

m

(Jl .....jm)

e

(2.25d)

i

sym LN_1

m=l

1AN -', [ aN;ill JlC LN Thus,

the M-block,

considered

m-indexed

as a m a p

(2.25e)

coefficient-matrix

{M ~AN

(2.25a)

can be

from the vector of simple d o m a i n s

D{M} %

[DmAN] m~,l,00,,M

=

(2.26a)

into the reat (or complex) numbers

{ M}AN. D{M }AN + ~

see

a/so

Appendix

Using

where

1_yo N

1 mYN_ 1 can

i.

(2.25),(2.26)

{M}YN

=

a n d introducing

M

col [ 1 Y No

is e x p r e s s e d

( m - 2 .....M )

(2.26b)

by

(2.17b)

are given b y

rewrite the error (2.23)

with

(2.17b)

re=l, x = 0 with

in a generalized

MeN; ° = {M }AN. {M}YN

where

•

l

YN-1 ]

"'"

x=l

(2.~T~)

and and

n=N

while

n=N-:i , w e

matrix form a.s follows

(2.27b)

indicates product of generalized matrices ( s e e Appendix 1),

23

Introducing the following matrix [ M~ N

where

Md N

i

(2.28a)

ON_ 1 ] { M}~I

is e x p r e s s e d b y ( 2 . 2 2 ) , and

M-block ( r o w ) ,

1

ON-1

u

block-entries

u

=

1 ON_ I

[Uol_1 ]

are u-indexed

(see also A p p e n d i x

mad equat/ons'

in a generalized

rzycki and Dewilde

denotes the

(2.28b)

u=i,...,M

i i D ON_ l - symuLN_l (2.24)

UN-I

zero-matrix

u-indexed

{M}

whose

{M}

zero-mafrices i), w e

with domains

can rewrite the 'nor-

mafrix form a~s follows (see Za-

(1983a))

t =N where {M}Y N

{ M×M}H N

is e x p r e s s e d b y (2.18)

( 2 . 2 7 a ) , Rewriting

{ M x M }HN

(2.29)

with

{M}YXn r e p l a c e d b y

in a generalized

block-column

form

{MXM}HN.,

[{M}x%

] U-1 .....M

(2,30a)

where for u-2,...,M

{M}xUHN .

[ {M} 1 1 HN;kl"'ku] (kl...,ku)¢ myrau LN_

(2.30b)

and {M}×XHN = [ {M}HN;k 1 ]

0 kI ¢ LN

(2,30C)

with { M}H N;kl...ku - [ h.]l...Jmkl...ku . ] (Jl ..... Jm ) ~ D{M}YN

(2.30d)

24 we

c a n express the 'normal equations' (2.29), for

u=l,...,M

and

for

i

( k 1 ..... ku) ~ s y m u L N _ l , a s follows

(M}^

~'4"

{M) H

{M }AN.( M }HN;o

These

(2.31a)

N;kl..,k u = 0

=

MdN

(2.31b)

are the 'normal equations' associated with the M-th degree nonli-

near, N-th order prediction problem. W e

can observe

that they will reduce

to the 'normal equations' corresponding to the linear problem, if Equations

(2.31)

M~I.

can be recurslvely solved via the nonlinear Le-

vinson algorithm, presented in Zarzycki and Dewilde (1983). q)his algorithm computes

(1983a); Z~vzycki

the coefficients of the optimum nonlinear

approximate prediction ladder-filter, a n d implies the generalized C h o l e s k y factoriza~on of the block, multi-lndexed covariance matrix

{ M×M

}HN ,

generalizing the linear case, considered in meprettere a n d Lie (1980).

2.3 Nonlinear ! e ~ t - s q u a r e s

prediction: Geometric

approach

In the s u b s e q u e n t sections of this paragraph w e

will introduce the

nonlinear prediction problem in the following spaces: of the regular Volterra function~/ poIy/qomials; of the generalized coefficient-matrices;

~nd of

generalized z-polynomials.

2.3.1 S p a c e

o f tlae r e q u l a r V o l t e r r a f u n c t i o n a l . p o l y n o m i a l s

G i v e n the M - b l o c k , m - i n d e x e d matrix of the r a n d o m veu~iables [M} YNI-I

(expressed

by

(2.17) with

x=l

and

n=N-l) , ea~d a s s u m i n g

25 that the entries are linearly independent,

{ M}__I

A

Each

wil/

element from that s p a c e

M

where

<0N

...

{

M

be

the s p a c e

(2.32)

expressed

as

i {M}FN'{M} YN-I

(2.33a)

coefficient-matrix

. [mFN]

}PN

consider

--N-1 }

M-block (row), m - i n d e x e d

the

can

M}yI

{

X N _ 1 =" V {

we

is given b y

(2.33b)

m = l .....M

with

m F N = [ fN;Jl""Jm ] (Jl ..... ]m )

From

Appendix

i it follows that (2.33)

M~

.=

observe

that

M

m

Z; m=,1 M

can

be

(2.33c)

m 1

¢ sym

LN_ 1

rewritten as

:I. • FN " Y N - I

Thus, w e

can

functional

p o l y n o m i a l o f t h e form ( 1 . 2 ) . W e a l s o n o t i c e t h a t a s s u m i n g

we

obtain the s p a c e

diction problem.

M~ N f

(where

replaced

duct o n

{i}~_

Given

G

[ M }yiN_ I

is the regular M - t h

1 , associated

degree

and

Will

be

VoIterra

wihh the lineeuc N-th

two Volterra functional polynomials

the l a t t e r element by

0N

(2.33d)

expressed

g , respectively), w e

by

can

M

(2.33)

introduce

order pre-

~N

and

with

F" a n d

inner-pro-

~s

(M~oN,

M~N)~f

=A IE{M~ N

M-

~N }

M:I

(2.34a)

26 inducing the n o r m

ii M

2.3.2 S p a c e

1,,,jl 2

lowing M-block,

jl...j m

where

m-indexed

=A [ 10N_ll "'"

U O Ni_ I

each

m-indexed

(2.34b)

of .qenera/ized coefficient-matrices

Let u s introduce for

{M}I.

IM ~PNj 2}

E {

=

m=l,...,M

(jl,...,jm) ¢ s y m

m

i

LN_ I

m-l_l UN_ I

.

ml.

M ON_ll ]

m+l_lON_l

jl...jm

is the u-indexed

(2.35a)

"'"

zero-matrix of the form

(2.28b); the

is given b y

J1-0OJm

mi.

(2.35b)

Jf"Jm

with

6

t h e fol-

matrices

ml.

matrix

and

- [ 6 ]'l " 4 m' ; k l ' " k m

] (kl,...,km)

1 1 E s y m m LN_

denoting the m-dimensional

Kronecker

delta

Jl...Jm;kf..km .I 1

if

kl=Jl ,..., km=J m

(2,,35c) Jl"4m;kl'"km

This

means

thai

0

ml.

Jl""Jm

unit-entry with coordinates le ~II remaining

otherwise

~ad, hence,

{ M}I.

contains only o n e

J1"" "jm

(jl,...,jm) , placed in the m - l n d e x e d

entries ore equat[ to zero. Now let for

=

[ { M )l.

] Jl""Jm

block, whi-

m=l,...,M

m 1

(2.36a)

(,i 1 ..... jm ) ~ sym L~_ 1

and, fina/ly, let {M} i = [ m 1 ] IN-I I N - I m=l,...,M

(2.36b)

27 We

can observe

that the entries

{ M }I.jl...jm

ly independent, a n d they C a n b e c o n s i d e r e d

of the

{IV[}_ i_ I IN

are linear-

~s the 'natural' b ~ i s

of

the

space

{M}_I | N - I a v {.{M}IX N-X} whose

{M

elements will b e e x p r e s s e d

}5,N

where space

M

N

=

[mFN] m = l . . . , M

E

Given

by

m-indexed

(2.33c). T h i s

and

means

the generalized c o v a r i a n c e matrix

with

x=l

and

n=N-l)

N

is e x p r e s s e d

that

{M} i

IIN - I

by

{ MxM

}HN_II

{M}I_IN _ I

(expressed

as

A {M}5,N.{MXM}HI N-I .{I~@GN (2.381

with

5'

and

f

Hermitian a n d posltive-definite,

we

can check

({M}FN'{M }GN)Ir = ({M}GN'{M}FN)~~

(2.39a)

replaced by

g , respectively. Recalling that the genera/ized c o v a r i a n c e

multi-indexed

is the

of the 2 M - t h order stochastic s e q u e n c e

define the w e i g h t e d inner-product o n

{M}G

jl...jm

coefficient-matrices.

( {M}FN' {M) GN) ][ where

{M} I

(2.38)

is e x p r e s s e d

of M-block,

{y}, w e

N

E ... ~ fNijl...j m m = l J1=1 j 2 = J l jm,,,,,Jm_l

mF N

by (2.18)

N

a.s

=

E

(2.37)

G

matrix is

that

(2.39b)

(a.{M}AN + b.{M}BN,{M}I~N)I = a({M}AN,{M}FN)II+ b({M}BN,{M}FN) (2.39c)

28

({M}FN {M}FN)Ir = {M}FN"{NIXM}H.NI_I {M}FN z 0 with equality in (2.39d)

If{M}

We

con

II

observe

]if

{M}PN

=

{M} ONi -I " T h e

norm

(2.agd) is then

2 = ({M {M} FNII I }FN, FN)]I

(2.39e)

that

{M}I

Ii 2 J J.'"Jm R

{M}1.

{MxM}. 1 .{M}~ ji...j m" I-IN-i jl...jm

,.,

=

h..

0

>

(2.~0a)

JiJi...JmJm We

also notice that the 'natural' basis

amd

m

(jl,...,Jm,kl,..,,ku) c s y m

{M}I

({M}I

]l...Jm' if the underlying accordance

as we h a v e

basis of t h a t space,

general, an orthogonal

2M-th

{M halN _ 1

of the s p a c e

for

is not, in

m,u=l,...,M

I m i LN_ 1 x sym LN_ 1

.

kl,,,k u) l

h.

.

(2.40b)

]l...]mkl--.ku

order s e q u e n c e

was

Gaussian,

we

would

have

(in

with (2.10) )

m eUHl~-i

Consequently, f o r

(re+u)

({M}I

= m eu~i~N_i

'

(m+u)

odd

(2.41)

odd,

{M}I

]l-..Jm'

kl...k u

)~

0

(2.~2~)

=

and we would have the 'block' orthogonality of the 'natura/' basis in the Gaussian ca~e. Moreover, if the sequence was white, we would write ({M}I']I...jm,{M}Ikl...km)]l = EFI~ . Jr,ks

(2.42b)

29 in

accordance with (2.10). In genera/,

if

({M) FN,{M}GN)I[ = 0

we

shall s a y

that two M - b l o c k

(2.43)

(row), m - i n d e x e d

or£hogonal with respect to the genero/ized matrix of the underlying quence

was

stationary

coefficient-matrices

block, multi-indexed covariance

2M-th order stochastic s e q u e n c e (in a w e a k

2M-th

are

sense),

order

indexed Toeplitz covarlance matrix {MxM}TN_I

{ y }. If the sethe block, multi-

would replace

{ MxM }H

in ( 2 . 3 9 ) , in ~ccordance with (2.Z9).

2.3.3 S p a c e

of

.qenerallzed z-polynomials

Let u s introduce for

m..l .....M

and

(jl,...,jm) e s y m

rn 1~

LN_ 1

the

following row-matrices

Jl [6m,p'Zl""Zm

M zjf..jm

"

=

and

...

[0

0

Jm ] p=l, .... M

Jl Jm zl ...zm

0

...

0]

(2.43a)

let

mXM_l

=

ZN-I

[~.~" o.A~.~ ~'-''/

M

[

zJf"Jm]

(Jl .....Jm ) ¢ s y m

m

1

LN_ 1

so Lhat we c a n introduce

{M)

Then

we

can

1 m×M 1 ZN-1 = [ ZN-1]

consider

the

following

{M}_I A LN_ I =

m=l,...,M

space

{M}_I v {

(2.43c)

~N-I

)

(2.4~)

3O

whose

elements

M#

will be

N

M

.

N

E

j

m-.1

"

expressed

~

M E [0 m-1

as

N N z. . ~ "'" E, fN;jl..j m M 1 12 Jl Jm='Jm-1 ll"'Jm

... 0

¢N(Zi,..0,Zm)

0

=

... 0 ]

(2.4:5a)

= [~N(Zl ..... Zm)] m=:l.,...,M where

~N(Zl, ....Zm)

Given

is the s p a c e

{M}_I ZN_ 1 two elements

is given b y

the foUowing

M ~N

(2.45)

with

of the M-block,

arld F

MS N

and

f

vely), a n d using the spectra/ matrix sequence

m-variate

z-polynomial

N N N Jl Jm E E "' Z z i...z j l = : l j2=1 jm,~Jm.1 fN;jl...j m m

~N(Z"l ..... Zm) "

Thus,

denotes

{y}, w e

(M NMVN)~.. =

introduce

(2.14)

inner-product

.[d0{M} :d~{M} M~

A

M

M

m=l

u=l

E

=

E

m-variale

from that s p a c e

replaced

N

(2.45b)

by

G

z-polynomials. (where

and

g , respecti-

of the underlying on

{M}zI_I

the latter

2M-th

order

as follows

M x M w . M" "~N

.l'dOm [ d ~ u ~ N ( z l ..... z m)

i

(2~) m + u

m ®'~'W(e 'e ,e" ~ ) ~'N (wl ..... w )

1

(2o46a)

iSr , r~--l,...jm zr=e i ~s Ws=e

where

we

~dOm

used

=

the following shorthand

fd81

... f d O m

;

, s=l,...,u

notation

~d~ u =

~d~j....

;doJu

(2.46b)

31

Using

(2.13),

(M¢ N,

M

~N)Z

we

can

.

M ~

show

,hal

M ~ u=l

m-1

1 (2 7) m + u U

:dO m f d u

~ N ( W l ..... W u)

171

m®'~V(e"~ 'eie )~ ~N(=I ..... ~m)

ie Z

r

~e

$ r~it...tm

r W

s

=~e

, Sm1~...tu

(2.46C)

- (M~N ,M ¢N)~.

We

a/so

have

(a-M FN + b,MAN,M~N) Z - a(Mr N , M ~ N ) X + b(MAN,M¢ N) Z

(2.46d)

and, finally,

(M~ N , M ¢ N ) Z, " II M ~ N 112

If

(M

riate) MXMw

REMARK:

¢N,M ,N)Z

= 0 , we

z-polynomials (2.14)

aye

of the

shall s a y

or,hog.hal

2M-th

Let

"~D: {e io }

mnJD

we

m~

.~ ~ e

order

denote

sequence,

(M-block,

to the spectral

on

matrix

the unit ( m + u ) - t o r u s .

will h a v e ... e~jD : {e i8 )® ... ®

{ e ie}

= { e

meu~

we

ie 1

iOm

...e

m

for the unit ( m + u ) - t o r u s

= mT

®u~/D:

m-va-

the unit-circle. "/}hen for the unit m - t o r u s

i OI m @u T

(2.,~6e)

generalized

with r e s p e c t

In

while

that t w o

>-- 0

{e

i 8m ...e } ® ie I

•. { e

i 8i {e

i0 m ...e

i~ 1 e

get

i Ou ...e } =

i~tt ...e

}

}

32

2.3.4 Isometries

We isomorphic

observe

can

spaces;

{M }[i {M "}.y1 N-I N-1 '

thai:

i.e., w e

and

{M

}zl N-1

i~.re

have

y

.

i~.y

-Jl

.

-3m

d {M} 1.

%

(2.47~)

Mz.

~

Jl,,,Jm

Jl.,4m

so that M

q0

N

(2.47b) { M}F N

We

wish to s h o w

4-~

M@ N

that the following isometries hold

(Y_jI'°°Y.jm'Y-kl""Y-ku ) Y z/

( {M}I.

%

~ M}

jl...jm

(2.47c)

(M ikl...k u) II

]3 ...jm

Mzkl...k u) Z

s o that ( M //

(~M} FN( M} GN)~

~N' M ~ N) Y

(2.eva)

%

(M ~N'

M~,~)Z

33 |n o r d e r to do that, let u s o b s e r v e

(following ( 2 . 9 c ) , ( 2 . 3 4 a )

and (2.40b))

that

(Y-jI"'Y-jm ' Y - k l " ' Y - k u

)y

: ~{ Y_jl-..Y_jmY_kl...Y_ku

}

:

= hjl...Jmkl...ku "

= ({M}I.

. ,{M}i

)

(2.48a)

k l , . . k u 1/

]1...$m F r o m (2.lib) and (2.46a) we obtain

Mz (

M

ji...jm'

1

z k l . . . k u) Z :

I dO m

(2 7) m+u

Jl

id u

Jm

zl ""Zm

-k × m®%v(~i ~'ei~) ~I-k I ""~u uI

IZl~:eiOr |ws=e

,

r=1,...,m

• sl: ll...|u

Jl...Jmkl...ku

= ({M} :

{M}

(y_jl...y_jm, y _ k i . . . Y _ k u ) y

s o that ( 2 . 4 7 c )

(Mq°N'M~N)~"

ij1"" j m'

is valid. F r o m ( 2 . 3 ~ a ) , ( a . 3 9 a )

M ]E{ M (PN

~N } =

M

E Z m=l u = l

zk z...k u) ~

and (2.48a)

m_

re@u_ ~'N"

2.

(2.~ 8b)

it follows that

m ~_

MN-I" ~'*N "

" { M }FN'{M×M} t41--N-t'{M }GN~ "~

( {M} F N , {M} GN);I

(2.49a)

34

Finedly, using

(2.12b),(2.3~a),(2.~Sb),(2.46eL)

M (MeN

Z ~ViVN) -

.

×

~

mml

M

$

U-i

(2~) m + u

fdO m

"®~w(Je~,j~)

(2.48b), we o b t a i n

and

/d~u C N ( Z l .....z m) ×

,F-N(~I,...,,%) z]c=e

~ M

M

N

T

T ... ~

m - I u-I

1

x

N

Jl-i

I d8 m

=

M

~

~

m - i u=l

N

kl=l

-iku~ u ...e

N

~

j1=l

...

~

m e U w ( e i e m ,e

u)

;kl...ku

N

jm=Jm_l

~ s=i~...tu

~ .~f~r;jl...jm x ku=ku_ 1

eX]XSl...e iJm e m

-ikl~ I

s

i r ~ ip.••pm

N

~ ...

Id u

e M

---e

N

j m-Jm_i

i8r

N

~

kl--i

...

~

ku=ku_ 1

~.f~,;jl...jm

h.Jl...Jmkl---ku . &;ki...k u M M 2 r m = l u=1

mF. N"

(M}F,N {M×M} •

-,

This proves

m • u.. _i

~-i"

_i

H N _ I,

(M~N,M~N)~f

=

U~

GN

{M}~N

-

=

({M}FN,{M}GN)I

(2.49b)

( 2°~7d).

Prom

(2.47) it follows t h ~ the M-th degree nonlinear, N-th o r d e r {M }_.I stochastic estlma£ion problem considered in the space X N _ l , c ~ be equivalently interpreted ~s the deterministic

problem in the space

{ M } KI~-_

35 of ~eneralized matrices, or as the de£ermlrdst/c p r o b l e m in the s p a c e {M}_IzN_I

of generaJ/zed z-polynomieds. "l~he i s o m o r p h i s m

nera/ization of the i s o m o r p h i s m tima~on p r o b l e m ruing

M=I), Now

c o n s i d e r e d in the linear least-squares es-

the K o l m o s o r o v

isomorphism

are in a position to s h o w

~/m~t[on p r o b l e m minist/c)

is a ge-

( w h i c h c a n b e immediately obtained from (2,47), a~ssu-

and becomes we

(2.47)

optimum

in stationoA-y c~se.

that the nonlinear s t o c h ~ U c

c o n b e eqtdvo/ently c o n s i d e r e d

es-

a s the p r o b l e m of (deter--

approximation of the set of M - D

impulse r e s p o n s e s

and~

or tra/qsfer functions of the nonlinear prediction filter.

2.3.5 StochaStic nonlinear . e s t i m a U o n

Given

{M}_X N1 _ 1

the space

(2.32),

let us

introduce

{ M } ~ N - v{ Yo . {M}yN_,I }

nonlinear, N-t/~ order lea.st-squares predictor

The

M-th degree

Yo

will b e e x p r e s s e d

{ M }p

l Y;N-I

o n the s u b s p a c e

Yo

(W0 Y N*- I

E

{ M ) _X Ni- I

" We

notice t h ~

N-th order prediction error, c o r r e s p o n d i n g

A {M}_l 1 N;o = ~Y;N-I

and can

of

(2.5,a)

is the ortho~onml projection operator, ta/~n~ projection M AY N ; o

linear estimate (2.20), introduced alsebralcallyo T h e

M E

M^ YN;o

as

MgN~o "A {M} P Y ; NI- I

where

(2.50)

be expressed

Yo

-- Y o -

to

M^ YN;o

is precisely the n o n M-hh desree

nonlinear,

M^ Y N ; o ' is given b y

{M}yl ±

in ~ renorma/ized form ~s

N-I

(2.51b)

36

M eN;o '= M C N ; o where

{M}AN

vely. W e

and

It M ¢N;o I1~

{M}YN

{ M}AN'{M }YN

=

(2.51o)

a r e given by (2.25) and (2.27a), r e s p e c t i -

notice that this is precisely fhe nonlinear normalized

prediction

error, introduced algebralca/ly in ( 2.27b). The

orthogonality conditions

(2.51b)

imply for

u=l,...,M

and

(kl,...,ku) ~ s y m U L l _ l

(MeN;o , y_kl...y_ku) Y

Moreover,

the n o r m

Volterra functional polynomials. W e precisely the 'normal equations'

(2.52b)

%vith the M - t h

introduced in the s p a c e can

observe

degree

nonline-

of the regular

that conditions

(2.52)

are

(2.31), derived algebralca//y. M o r e o v e r ,

rema/~k that the 'normal equations' for the linear N-th order predictor

are given b y

(2.52)

2.3.60pfimum

generalized

Considering

with

i%4=i .

matrix approximation

the s p a c e

{ M}_I~N_I

M}~q = v {{M} l o ,

The

as

= ]] Me N;o[I y

are the 'norm~l eque~tions', associated

ar lea~st-squares prediction p r o b l e m

we

(2.52a)

of the error will be e x p r e s s e d

(MEN; O , yo) Y

These

-- 0

N-th order estimate

{ M } ^iN; °

(2.37) , w e

define

iN_l }

of the element

{M} 1 °

will be introdu-

37 ced a.s follows

{M}^

A

{M}_

IN;o =

where

;%'M'P 1 lI;N-3.

space

-"IM)|l -N-I

{M}AN

{M} 1

~

o

(2,54a)

{M}.I

a N-I

indicates the orthogona,1 projection operator on the sub-

°

=~ { M } ~

1

z-'U;N-I

The

N-th order approximation

1 {M}I I;N-1 0 =

{M}I

0

[0

-

error is then given by

{M}IAN| o ]

± {M} 1

KN- I

(e.54b) and can be rewritten in a r.enorma/ized form as

{M}AN = {M}A N II { M } A ~ [ ~ I

Let us observe tatives of the phism

(2.s~c)

that

{M}^IN; O , {M}A N {M} A N and are the represenM ^ M M YN;o ' eN ~nd eN; ° , respectively, in the isomor-

(2.47). Prom

and

w [ m A N ] m = l ..... M

t h e orthogonality conditions l

(k I .....k u ) ~ y m % ~ _

(2.54b), w e obtain f o r

I

( { M } A N ' { M } I k l . . , k u)]I

w h i t e t h e n o r m of t h e e r r o r

(2.54b)

({M}AN'{M}

under

the isomorphism

-, 0

(2.55a)

iS g i v e n by

io) ~ =

We n o t i c e f.hat ~he 'normal equations' (2.52),

U.-I,..,,M

(2.47).

{{{M}A~ I I

(2..55)

are

(2,55b)

actually equivalent to

38 2.3.7 O p t i m u m ~qeneralized p o l y n o m i a l

Given

the space

(2.44), l e t u s c o n s i d e r

{M} ZN_II

{M}ZN

The

a~pproximation

v{ M z

=

°

M^

N-th order estimate

{M}Z Ni_ I }

,

of t h e

ZN; °

element

(2.26)

M

z O -- [I 0 ... 0 ]

will

b e obtained as

M^

{M}p

A

ZN;o =

where

{M}p

1

I

M

Z;N-I

{M}zI

error will then b e e x p r e s s e d

as

A {M}~

N;o =

(2.57a)

-1

d e n o t e s the orthogonal projection operator, taking

z ;N-1

projection o n the subspa~ze

MA

{qVI} z l

e

Zo

1

Z;N-I

M

Zo

N-i

M

=

"

The

Zo "

N-th order approximation

M^

ZN;o

.t

{ M}Z1N_ 1

(2.57b)

or, in o. renormalized form,

M A N A MA :

Let u s o b s e r v e of the

M

-1

N;o II AN;oll Z

that

M^ZN;o ' MA N;o

M^ Y N ; o ' M eN;o ' MeN;o

respectively, in the i s o m o r p h i s m The

(a.~Tc) ** [ ~ ( Z

l .....Z m )

and

~d~or

MA N

of the

] m - - X .....M

are

the representatives

{M}iN;o ^ ' {'M}AN , {M]AN

(2.47).

orthogonality conditions

(2057b)

will imply for

u=l,...,M

and

1

( k i ..... k u ) ¢ s y m U L N _ i

(MAN

' M Zk .... k ) Z

= 0

(2.~8a)

39 Moreover,

we

obtadn

(MA'N' Let u s

observe

=

liMa N;o lI:z

the~ the 'normal equations'

clitlons (2.55),(2,52)

Finally, w e filter p r o b l e m

MZo) Z

and

can

(2.31), u n d e r

conclude

(2.58b)

(2.58)

e q u i v a l e n t to the

are

the i s o m o r p h i s m

that the n o n H n e ~ "

con-

(2.47).

lea.st-squares

prediction

ca/n b e equiva/ent/y stated in the s p a c e s :

- of the r e g u l o / "

Volterra functioned polynomiads;

- o~ the genere~tized coefficient-matrices; - of the gener0dized 'l~his f o l l o w s seen

from

z-polynomieds.

from the fact that the three s p a c e s (2,47). Therefore,

(Le., the p r o b l e m

of o p t i m u m

the nonlinear

}Ylq

can

be

- the o p t i m u m

equivalent/y

deterministic

stochastic

stocha.sfic approximation

'ideal' prediction filter) in the s p a c e

{M

considered

approximation

~

mat/ices

- the o p t i m u m

deterministic

the hi~her-order are

gher-order

sequence

are

of:

{M}K N

covariance

impulse

respon-

of the generali-

dat~ of the underly-

given);

approximation

tions of that filter, in the s p a c e mia/s - in the Alq co.se

of the output of the

of the set of M - D

zed

sequence

estimation p r o b l e m

the p r o b l e m

of the 'ideal' prediction filter in the s p ~ c e

ing stochastic

as it is

of the Volterra functional polynomials

ses

(provided

are isomorphic,

(provided known).

of the set of M - D

{M} Z N the M - D

trarzsfer func-

of the generalized

z-polyno-

spectral flxnctions of the hi-

3. G E N E R A L I Z E D

NONLINEAR

In flue previous prediction

problem

tly introduced

LADDER-FILTERS

chapter

we

for higher-order

algebraically a n d

mains. Algebraic

showed

solution of the problem, algorithh~, w a s

(i983a, b); Z a r z y c k i

(1983);

in Z a r z y c k i

in the s p a c e s :

can

in time- a n d

be

in Z a r z y c k i

derivation

equivalen-

in frequency-dogenera/iza-

o/qd D e w i l d e

of the nonlinear predicti-

of the Volterra functional polynomials

(1984~a-e).

lutions of the nonlinear

sequences

yielding the nonlineom

proposed

geometric

o n filter algorithm in the s p a c e

method

stochastic

geometrically,

f/on of the L e v i n s o n

introduced

that the nonlinear lea.st-squares

Here

least-squares

we

wish

to present

prediction problem,

of the generalized

matrices,

was

recursive

so-

using projection

o2ud of the generalized

z-polynomials. The

nonlinea/" p r o b l e m

will b e p r e s e n t e d This

approach

in c a s e

will s h o w

as

a straightforward

the m o s t i m p o ~ a n t complexity

We riant)

M

while its solution

of the filter nonlinearity.

fealures

of the nonlinear treat-

of the derivations

of the s e c o n d - d e g r e e

estimates

will b e of the s e c o n d - d e g r e e perscript

cO~e

on one

ho.nd, o n

nonlinear prediction filter algorithm will b e

extension

tities (i.e., s u b s p e c e s ,

stated in ~eneral

of the s e c o n d - d e g r e e

menf~ avoiding u n n e c e s s a / ' y the other - the general

was

and

(R4=2)

errors) , we

case.

considered

shall drop

Since

obtained all q u a n -

in this chapter

from n o w

o n hhe su-

in order to simplify notations.

will s h o w

nonlinear

that the solution will result in a generalized

ladder-filter

algorithm, being

o r ~ h o g o n o / linear ladder-filters.

(time-va-

a natural generalization

of the

41 3.1 Index-sets

Let u s

(see

sets

euad their ordering

consider

a J s o (2.16)

for

n=0,...,N

with

rn=l,2)

ILx= n

2Lxn

and

{Jl} xX+n = {x .....x+n}

x+n

A)

can

for

introduce

the two types

u Lx÷ i n-I

U {x+n+l}

where rence

x

of the index-sets:

point 0),

ber of elements v--0~...,n

Lx,v A=

u s y m 2.~ nx + 1i -

U { ( x + n + l , x + n + l ) .....( x + n + 3 - m , x + n + l ) }

will denote

usly c o m p l e t e d

for

J2ffiJl

m.=O,...,n+2

= Lx A {x} n~m

B)

(3,b)

x+n

J l •X

we

(3.1a)

- Lx~ × Lxn " { q'J2 }jl,ja=~. +n

s y m 2 L x = { jl,j2}

Then

the following index-

x=0,...,N-n

n

a 'globa/' offset ( b a c k w a r d

while

in the l~t, o/ud

set, a n d

of previo-

%%~iliindicate the 'local' order

being completed,

{x} U {(x,x) ....,(x,x+v)}

(num-

column);

u

LX+ I

u

n-i

U {x+n+l}

x

and

m

(number

m = v + l,...,v+n+3

n,m

where

shift from the refe-

will stoJnd for the 'global' order

columns)

(3.2a)

will ago/n

U { ( x + n + l , x + n + l ) , ....( x + n + 4 - m , x + n + l ) }

denote

in the top-row

the 'globa/' offset

(3.2b)

(in the 'uni-v~riate'

of the 'bi-variate' part of the

x~v Ln,m),

v

subwill

42 indicate the last element der while tow

m

~nd

will ind/cate the s u m

C~a~ o b s e r v e

3"LX n

Considering

forward'

will b e

of the n u m b e r

a~edn the '.q/obal' or-

of elements

in the top-

th~

u

s y m 2 L nx

a n d f/nat the ordering is m o d u l o

introduce

n

the last column.

in

We

in the top-row,

x,n

(3.2c)

Ln,n+ 1

(n+2)

as w e

have

LXn,m+n+2

= LX+l,m

(3.3a)

L x'v n,m+n+2

- L x'v n+l,m

(303b)

the element

for fur'£her u s e (B-forward)

~

{ x}

a n d the elements

of the top-row,

the 'linear- for~va/'d' (L-for-ward),

index-sets

and

we

'bilinear -

of the n-th 'global' order, as follows

L-forward

L* - {x} n,o

B-forward

LX+l,n-1 n-i,n

(3.4a)

(for v---0....,n)

{x,x } u

Lx

{x,x+v }

u

njo

Lxl v _ <[ n,v+ i

These

u

index-sets

cal' forward

v=0

if

v=l,...,n

(3.4b)

will b e

approximation

Considering

if

Lx,v_l n~v

applied later, in order to introduce

sets

of 'lo-

errors.

the element

{ x÷n+1 }

and

the elements

of the last

43 column

of the index-sets

ckward

(l,-backward),

L x'v n,m

' we

define

for further u s e

a.~d 'bilinear - b a c k w a r d '

of the n-th 'global' order,

as

the 'lineew - b a -

(B-backward)

index-sets

follows

L-backward

Lx, n - i n,o

B-backward

"

Lx, n

. LX, n-I n,n

The

Lx, n-1 n,m-1

backward

Using

will b e

will b e

(3.4:), w e

can

used

,

m.~l,°..,n

(3.5b)

,

m..n+ 1

(3.5c)

later, w h e n

sets

of 'local' b a c k w a r d

considered.

consider

the following

collection

of the 'local'

[ Lx n,o

Lx, O n,l

collection

Lx,n-1 n,n

""

Lx, n n,n+1 ]

of the 'local' b a % c k w m r d

(3"6'~)

index-sets

results

(3.5)

L x m b;n

ceun o b s e r v e

[ b x'n-I n,o

L x,n-I n,l

cursive

way,

and

°'"

L x,n'1 n,n

that the 'globe/' f o r w a r d

of the (n+1) order (i.e., Lf~+ Ix

L~;n

(3.5a)

index-sets

while the folIowin~

We

{x,x+h }

U

index-sets

ILx ,, f;n

from

{x+n}

u { x+n+l-m,x+n}

a p p r o x i m a t i o n errors

forward

U

(for m--1 .....n + l )

Lx, n - i n,m

n,n+1

.~ LX, n-i n-l,n

~iven

~d

the n-th o r d e r

ILx . The b;n

hlgher-order

and

L x'n n,n+l ]

backwetrd

L~;n+ I) c ~

(3,6b)

index-sets (3.6)

be obtained in a re-

'~lobal' for-ccard a/ad b a c k w a r d '~[obal' i n d e x - s e t s

will b e

index-sets derived

via

44 a 'global' order-update step (3.4) a n d

n

(3.5) of the sets

-+ n + l

, executed

o n the 'local' entries

(3.6), a n d d e s c r i b e d sehemaf/c~l/y in FiS,3.1,

x ]Lb;n+ J_

l,-ba c k w a r d L nl,oX'n +

B-b ackward Lx, n n+ i,m

Lx, n+ 1 n+ l,n+ 2

m = l|...In+1

Lx,n+ Jn+ l,n+ 2

XiV

Ln,v+ 1

LXl v n+ l,v+ 1

v=0~...In ]Lx f;n+l

~[jx f;n

L-forward

L-forward Lx n~o

L:+1,o

B -b ackwo/'d

L-backward LX+1,n -I n~o

LX+l,n-i n,m

Lx+l,n n,n+l

m=lj...tn ILX+ 1 b;n

F i g . 3 . 1 0 r d e r - u p d a £ e step n-+ n + l o~nd L-backwo.rd index-sets.

for the 'global' L-for"ward

45 The

four types

Fig. 3.1 , c a n

be

of the 'local' recursions,

L-forweurd ~ n d -

recursions:

the 'local'

for the 'uni-variate' parts of the

L-backward

index-sets;

order-updates for the 'bi-variate' part of the

L - f o r ~ v ~ d index-set, ~ n d

the 'local' o r d e r - u P d a t e

'uni-vari~te t p~rt of the B - b a c k v c a r d BIu - recursions: the 'loco/' o r d e r - u p d a t e B-forward

recursions:

index-sets, a n d

the 'local' o r d e r - u p d a t e s B-forward

For

example,

from (3.~a)

lows that the L L

'local' o r d e r - u p d a t e

for the

index-set;

for the 'bi-variate' parts of the index-sets.

(with

(3.5a)

index-sets;

the 'loca/' o r d e r - u p d a t e s

eund B - b a c k w a r d

and

for the

for the ~uni--v'ariate' part of the

'bi-voriate' part of the L - b a c k w a r d RB-

of

interpreted m.s follows:

L L - r e c u r s i o n : the 'local' o r d e r - u p d a t e

LIB

indicated in the d i a g r a m

x

replaced

index-set recursion

by can

x+l), be

it

fol-

expressed

LX+l,n-i nwo = Lx Lx nil n,o

u

L x + l'n-I n,o

=

{x} %

u L X + l , n-I u n-l,n ; ..g.......

{x+n*l}

(3.7)

Lx n~o

and

can

be

schematically d e s c r i b e d

a s the following L L

index-set section

Lnxl Lx

n,o

3

~~

(3.8)

r- Lx

n~ 1

!

LX+ 1 , n - 1 n,o

q?he r e m a i n i n g 'local' index-set r e c u r s i o n s

can

be

obtained in a similar w a y .

46

T h e s e recursLons, together with the corresponding index-set section are presented in Appendix I. W e '~ob~9/' order Lndex-sets

notice that the number of entries of the (n+l)

~U~n+l

and

ILb;n+l x

comparison with the n-th order sets

]LXf;n and

B-fozwea'd and B-backweurd index-set

x,n+l 2 Ln+l,n+

'ri.qht-upper' element

is augmented by one i n ~UXb;n ' since the 'new' (a.ssociated with the

{x,x+n+l} ) is arriving to the s c h e m e of Fig. 3.1 al:

the 'global' order-updaLe step

n + n+l. T h e 'local' structure of this order-

update step is presented in 5"[g. 3.Z. Lx,n+ 1 n+ i,n+ 2 >

I2nX~flto Lx-,n ~ - ~ n,n+l T

x~n

xtnl,n Ln+

LnX,fl,o

".__> Lx~n _ ~ .... n+l,n-i ~

Lx,n÷l n+l,n+2

Ln+ I,n+ l

Lx,n + n+l,n

Lnx'+~,n+1

Lx,n-I n,n+ I

Lx,n-I n+ l,n-I

Lx, n-i n+ l,n

LXP 0 n,2

LX, O n+l,o

LX, O n,n+l

f X~O

f

-

. .

-'~ Ln,n+l--~

n,2

Lx n,n+ i Lx

--~

n,o " t Lx+ l,n-i n~o

Lx

nsl

>

--~ L x sin

~

LX~O n+l,l

X~O

1'n+l,o +

Lx n,n+l

Lx+ l,n-i ntn

Lx n+ I,o ~

LX+iio

LX+ l,n n~n+l

Fig. 3.2 'Local' structure of the 'global' order-update index-set step.

n + n+l

47

o

0

t-" ILb;0"% k

•

..

ILb; 1

T[ •

f A

lb ° b ; 2 .............. % A

Lo

b| 3

f

•

A

,%

'

•

~

l

x=l

Ibm3

1

lLf; 2

-J

! x=2

x=3

3 ) Lf; 0

.J Initi~zations:

IL _

'I~Iew" elements:

T'

~

LX oeo

>

(x=O .....3)

5"i~.

3.3

n,n+l

(n=i,2,3 ~ x=O,.,.,3-n)

'Local' structure The symbols 0

cursions

a

of the third-order (N-3) indicate corresponding

of l~'ig. 3.2.

index-set recursions. 'local' index-set re-

48 From

Fig.

the L-forward

3.2 it f o l l o w s t h a t t h e will work

index-set

a)

initialization: L x n)o

b)

'uni-variate ) step: L x + n)o

C) )bi--vaLrlate' steps: L x

n)l

d) For

o)

)bi-variate'

d)

termination: L x)v n+l)v+l*

The

L- ~und B - b ~ c k w a r d

d)

for

follows:

-~ L x n)2 -~ "'"-~ nLX)n+l ~" L xn+l,o

we

steps:

i~U~za~ons:

x)v Ln)v+2-~

Lx)v n,v+2 x,v Ln,v+3

index-sets

L x+1'n-* ntm L x+l'n n,n+l

'uni-varla[e'

get:

(v=0) ....n)

x)v + step: Ln)v÷ 1

'uni-vari~te'

c)

recursion

Lx n) l

the B-for~vard index-sets

b)

b)

order-update

termination: L x n+l)o °

initializat[on: L x'v n,v+l

a)

~s

'global'

+ "'"

Lx,V x)v -~ Lx,v n)n+l ÷ n+1,o ÷ ...-~ L n + l , v + 1

are u p d a t e d

o.s follows:

( m = 0 .....n) (m=n+l)

stepS: L x+l'n-I ~. L x nim n)m+l L x+l'n -~ L x n)n+ l n+ l,o

'bi-variate' steps: L x + n,m+l

L x)O n)m+2

( m = 0 .....n) ( re=n+ i)

-~ L x'l n,m+3

+

"'"

-~ L x'n-I L x)n n + l ) m - i "~ n + l , m

termination: L x)n n+l)m"

We notice that e a c h is associated (N=3)

'local' order-update

with 'label-update'

index-set recursions The

index-set

n e a r ladder-filter

step. T h e

is p r e s e n t e d

recursions,

6dgorithms

step for the b a c k w a r d

of the third-order

in Fig. 3.3.

derived

presented

'Iota/' structure

index-sets

in this section, will underly

in the s u b s e q u e n t

paragraphs

nonliof

this chapter.

3.2 Nonlinear

filter a/~orithm: time-domain

In this p a r a g r a p h degree

we

will derive

nonlinear prediction problem,

of generalized

coefficient-matrices,

approach

a recursive

using projection

introduced

solution to the s e c o n d method

in p a r a g r a p h

in the s p a c e 2.3.2.

49 Let

{y}

denote a fourth-order ( M = 2 )

v e d o n the time-interval riables

[ 0,-l,...,-N ]

stochastic s e q u e n c e ,

and represented

yo,Y_l,...,y_N . C o n s i d e r i n g the index-sets

(3.2b), w e

define for

of the r a n d o m

n-0,...N

and

b y the r a n d o m

Lx n,m

(3.23)

va-

a n d L x'v ntm

the following submatrices

vorlatbles o.nd their products

Y-Jl

nmm yX

=~

(3.9)

=

n,m

2yx

n,m a n d the s u b m ~ t r i c e s L x'v . T h e n n,m

x=0,...,N-n

obser-

we

ly_j~

yX,V ntm

, expressed

(jl,J2) ,xnt m

by

(3.9) with

c o n consider the following ( 2

variance submatrices

Hx n,m

and

H x'v n,m

the former is given b y

le2HX n,m

H xn~m = E { ~ n , m

replaced b y

2)-block, multi-indexed co-

, where

lelHX

Lx nsm

] n,m

@ ~n,m } "

2 • 1HX

2 • 2HX n,mJ

ntm

Ik kk21 J12kl hJlJ2klk2

(Jl,J2,kl,k2)

a n d the latter is e x p r e s s e d

by

(3.10)

with

Lx n,m

replaced b y

(3.1o) ~ ~,m×L xn,m L x'v . n~m

Now let Ix

=

n~m

where

ljl

for

"~

[

(ki,k2)

~kl;j. I

[llX n,m

21x

] =

[i.

n,m

Jl

1..

(3.11~)

] ( j l , J 2 ) • L xn0m

JlJ2

• L xn~rtl

2o ]

~jlj2

[ lo

~

kzk2;jlj2 ]

(3.11b)

50 with

I0

and

20

ctively, w h o s e

being the o n e -

domains

Lx respectively. n,m |

Let us

and

~wo-indexed

are hhe uni- a n d

In a similar w a y

introduce

the

respe-

bi-variate parts of the index-set

we

following,

zero-malrices,

con

introduce

x-labeled

and

the mah-i~

Ix'v n~m

(x,v)-labeled,

sub-

spaces

I nx , m =

We

notice

{IX, mn

11'N-I -N-I,N

thai

by (2.37) with element

v

M.-2)

Fx nmm

}

will b e

se

n,m

domain

Ix'v ntm

is

Ix n~m

will b e

a two-block

F x'v nsm

(row),

with d o m a i n

x

expressed

multi-indexed

Gx

= Fx

n,m) ~x n,m

element

o n the s u b s p a c e s

.H x

n,m

n,m

x=0,...,N-n

the

to

(3.4~)

subsequent

and

(3.5),

subspaces

we

EMh

as

(3.12b)

coefficient-matrix w h o of the s u b s p a c e (2.39a),

(3.12a)

.%x

we

as

(3.13~)

n,m

X,V G X , V ~ --b~X'V°HX'V-G x'v Fn, m ' n,m j ]~x,v n,m n,m n,m ntm

According

(expressed

_o,N KN,N+ 1 °

will b e

D b ~ % v .. b x'v . Following n~m n0m

a family of inner-products

(Fn,m '

{ 2} K ~ _ I

fx ] n'm;jl-x'J2-x (Jl'J2) ¢ LXn,m

DF x - .Lx . Similarly, e a c h n~m nsm

will b e

introduce

v

precisely the s p a c e

of the s u b s p a c e

will b e

F x

.

n~m

while the 'biggest' s p a c e

b"Xn,m m [ f~n,m;Jl_ x

i.e.,

,xv

;

can

of the

(3.13b)

introduce

for

n=0,...,N

and

~o,N

-N,N+I

L-for-Nard

I~n~o = ~ (I~o) i

(3.14~)

51 B-forward

(for

v = O .... , n )

IX, v n,v+l

=

IX'v v { n,v+l }

(3.14b)

itx,n-i n,o

x,n-i = v { In, O }

(3.14c)

L-backward

(for

B-backward

m - i ....,n+l)

N x'n-I n,m

,, v { Ix'n-i } n,m

1[x'n n,n+l

3.2.1 'Local'

v

estimates

Denoting ta/dng projection subsequent

=

by on

,

xln {In,n+1}

and

,

m-.l .....n

(3.14d)

m=n+l

(3.14e)

errors

P l ; nx , m

("--I;n,m" p x,vj

the s u b s p a c e s

'local' estimates

and

the o r £ h o g o n a / ]ix n,m

errors

as

(Ix'vJ " n,m-

'

projection

we

operators,

will introduce

the

follows:

L-forward Following

(3.~a),(3.11),(3.12)

Itx n,o =

v

and

(3.14a),

we

{ix

x+l,n-i ' In-i,n }

can

rewrite

a~

Itx

n~o

(3.i5a)

A

We

define

the L - f o r w a r d

n-th o r d e r

p

estimate

x÷i,n-i i 11;n-l,n

x

'ix

n,o

of the

ix+l,n-1 n-l,n

i

x

as

(3.15b)

52 Let

0jl

denote the zero-entry with 'coordinate'

the L-forward ^ n-lh order approximation error, c o r r e s p o n d i n g to the estimate ix , will n,o

be expressed

as

x =A p l x+i,n-I i - I - [0 An,o --~ ;n-l,n x x o

(since the estimate x ~n,o). This

pace

Jl " T h e n

'%1 x nto

~x I ± n,o ~

is c o n s i d e r e d h e r e ~

~x+l,n-I n-l,n

(3.16a)

etn element of the s u b s -

error caxl b e rewritten in a renormalized form

AX n,o "

x An,o

x

C:

1{ An,o [

=

n,O =

[x

ax ] n,OlJl-X,J2-x (jl,J2) • L x n~o

n,o;Jl-X

in accordance

the errors

with

(3.16)

respec~vely, if

B-forward Using

(3.12b).

can

observe

are precisely the

M~2

( for

We

, x=0

and

that the

estimate

{M) IN;o , { M }A N

~d

c a n rewrite the s u b s p a c e s

I

v { Ix, x

'

Ix } n,o

n,v+l

Let

'

X x'v n,v+ 1

if

Ix'v-I } n,v

car* introduce the B - f o r w a r d

0jl,j2

A

i

(2.54)

(3.14b)

as

v=0 (3.17a)

{v { iX,x+v [

ix, v

{M)A N

and

v=0,...,n)

(3.4b), w e

we

(3,15b)

n=N.

Xx'v s < n,v4-I I

Then

(3.16b)

p I;n,o x Ix,x

c

if

v--l,...,n

estimates

Itxn,o

if

v=0

IIX'V-i n,v

if

v--l,...,n

(3.17b)

p

x,v-i 11;n,v

i

X,X+V

E

stand for the zero-entry- with 'coordinates'

(jl,j2) . T h e n

53 the B-forward

approximation

will be e x p r e s s e d

j

A =

n,'%r%'- ~

to the estimates

(3.17b),

a~

. p±

ax,v

errors, c o r r e s p o n d i n g

x

a

Xx

I[ ;n,o Ix,x

if

v=O

if

v=l,...,n

n,o

(a.18a)

/

[ p l x,v-i

i

1

ITX'V-I n)v

x)x+v

H ;n)v

i.e., Ax ' v

nsv+ 1

as the estimates B-forward

-

Ix,x+v

~x,v n,v+l

(3.18)

errors

AX'V = n,v+ 1

=

[0

~X)V ] n,v+ 1

O)V

are treated here

can

be e x p r e s s e d

(3.18b)

as elements

of

x,v I[n,v+i). The

in the renorma/ized

form as

ax'v llAX'Vl[l-lnv+ n,v+ 1 , llx,v n,v+ 1 x,v

(3.1So)

x,v

= [ an,v+l;Jl-x

an,v+l;Jl-x,J2-xl

(jl,J2)

x,v £ Ln,v+ 1

(3.14c), using

(3.5a), as

L-backward Let us

K~;n-i nuo

rewrite

n" x , n - 1

~' V {In~.q:nl -- )

lq)O

so

that

we

will define

-1 ~x,n n,o

The

n,o

A

x,n-1

= P~;n-l,n

L-backward

k p x,n-i = R;n-l,n i x + n

L-backward

B x,n-1

the

approximation

lx+n

=

-

ix+n}

estimate

(3,19a)

as

l[x,n-i n-l,n

e

error

:1. x+n

!

will then

Vx'n-1

[ln,o

(3.19b)

be

On]

i

I x'n-1

n-l,n

(3,20a)

54 or, in a renormalized

B x'n-I n,o

form,

B x'n-1 IIB x'n-1 -i n,o n,o ]l~x,n-i n,o

=

-- [b x'n-1 n'°;x+n-Jl

(for

B-backward

F'ollowing (3.5)

Hx'n-I

m = l ....,n+l)

and

V

(3.14), w e

{ Ix'n-I

c a n write

'

i x + n + l-m,x+n}

'

mml"°°tn

(3.21a)

x~n . ..xln--I Kntn+l , v [in~ n

,

ix,x+n }

,

m=n+l

(3 21b)

"

the B - b a c k w a r d

~x,n-1 n,m

~= _ x,n-I P~;n,m-i

ix, n A= P x,n-i n, n+ 1 ]I;n,n

Consequently,

estimates will be e x p r e s s e d

C

B x,n nmn+l

IIx'n-I n,m-i

,

ix, x+ n

Nx'n-1 n, n

'

the B - b a c k w a r d

c

approxima£ion

;n,m-I i x + n + l-m,x+n

A= Pli x,n-1 ;n,n

as

i x + n + l-m,x+n

i

x,x+n

±

!

~[x, n-i n,m-1

ix, n-i n,n

i

m=l,...n

(3.21c)

m=n+l

(3.21d)

errors will be defined as

,n-1 n,m

so

(3.20b)

n,m-i

n,m

Hence,

bY.n-1 ] n'°;x+n-Jl'x+n-J2 (jl,J2) E L x'n-I nlo

'

m=ii...,n

(3.22a)

m=n+l

(3.22b)

that Bx,n-1 n,m

~,n

~n,n+l

-

[~x,n-1

= i x + n + l-m,x+n

=" lx,x+n

-

r~ ~ ' n

~ n,n+l

n,m

0

o,n

On+ i-m,n ]

(3.22c)

]

(3.22d)

55 "Dhe B - b a c k w a r d

errors c a n b e e x p r e s s e d

in a renormalized

illx, n_l-i

Bx'n-ln, m I1 Bx'n-ln,m

Sx'n-ln,m "

form

,

m n l .....n

(3.22e)

,

m-n+ l

(3.22f)

n~m Bx,n

x,n n n,n+1 .. Bn, n+ I U 5~n,n+111 -* ~x~n n~n+l

similarly as the L - b a c k w a r d

3.2.2 D e c o m p o s i t i o n

PoUowing

error

of s u b s p a c e s

B x'n-I nmo

(3.20b).

'

the considerations

consider the 'local' decomposlf/ons

o f the previous

paragraph,

we

can

of s u b s p a c e s :

L-for~rard Since

Ax n,o

is in

from (3.16), w e

Ix n,o

'

but is or%hogonal to

n,o

=

fix+ 1,n-I

n-l,n

•

x

v { An, o}

w h i c h implies the 'local' decomposition

x . p x+1,n-1 PII;n,o K;n-l,n

x

P~n,o

denotes of

B-forward

v=O,...,n)

Since

+

(3.23a)

of projectlon operators

x PA;n,o

(3.23b)

the om£hogone/ projection operator, taking projec-

£ion o n the s p a n

(for

, as it follows

c a n write

Kx

where

~x+l,n-i n-l,n

Ax n~o

AX'Vn,v+l belongs

to

~n,v+X'V1

but is orthogonal to:

]iXn, o

(if

v=O),

56 and to

I x'v-I n~v

Ix'v

(if

v--1 ..... n ) ,

I IIx n,o

=

in accordax,c e witkl ( 3 . 1 8 ) , we o b t a i n

o

Ax, o v{ n,l }

v~O

~

x,v v { An,v+ I}

v=l,...In

(3.24a) n,v+ I

This

11x'v- 1 n,v

implies

p

xtv Pl;n,v+ 1

p

where

< l

xtv A;n,v+l

X l[;n,o

+

,

V~0

,

v=l,---,n

(3.24b) X,V--I ][;n,v

p

+

is the projection

operator

on

the s u b s p a c e

spanned

by

Ax, v n,v+ i " L-b ac k w a r d Observing

h a l to

that

I xn-l,n 'n-1

B x'n-I , see

(3.20),

I x'n-I n,o

resulting

PB;n,o

IB-backwvi~rd From

we

to the s u b s p e t c e

]Ix'n-I

n~O

but is o r t h o ~ o -

car* write

= ITx'n-1 n-l,n

(9

v

{B x'n-I n,o }

(3.25a)

in lhe d e c o m p o s i t i o n

p

v~here

belongs

n~o

x,n-i ~;n,o

_ x,n-i = ~]l;n-l,n

is the projection

( for

(3.25b)

+

opereltor o n

the s p a n

of

Bx'n-ln,o "

m=l,...,n+l)

(3.22)

it follows

that

]ix,n-1 n,m

= ~x,n-1 n,m-i

•

v {Bx~n-1 } n~rfl

,

m=l,...,n

(3.26a)

57 ix, n = I x'n-I n,n+ I

This

•

V {B x'n . }

m=n+l

(3.26b)

imp)/es

p

x,n-1 ]I|n,m

p

x,n

= o x,n-1 --~;n,m-i

+

x~n-i I[;n,n

+

~

p

W;n,n+l

p B ; nx,n-i ,m

where spanned

by

We

can

x,n PB;n,n+l

n +i ) ( P B ; n~tn

B n x'n-I .m

3.2.30rthonormal

(Bx:nn+ I )

that the L - a n d

In o r d e r

to s h o w

A x'u n,u+l

'

that, let u s

a/qd let u s

m=n+l

~sume

belongs

£o

we

can

that •x,v n,v+l

show

A x'v nlv÷1

B-forward

set in the s p a c e

consider

A x'v n,v+ 1

Consequen~y,

,

operator

(3.Z6c)

(3.26d)

on

the s u b s p a c e

ba~es

observe

In a similar w a y

m = l,...,n

"

(v--0,...,n) f o r m the O N

A xn ', vv + l

,

is the projection

A x'v n,v+ I

and

,

two

~

errors

A x'u ± n,u+l

a2ud the matrices.

A Xn,,Vv + l Ix'u-I n,u

and

D N x'v n,v+l'

v=0,..,n

A x'u n,u+ I

that for

±

obtain for

A x n~o

of g e n e r a l i z e d

B-foFwca'd

v < u. S i n c e ' we

errors

( 3.27 a)

v:O,...,n

A x n~o

(3.27b)

the entries of

A x = n will f o r m the O N

[A x

n~o set.

AX, o n~o

"'"

An,n x • n - 1 A nx:n ,n+

11

(3.28)

58 If w e

introduce, a c c o r d i n g to (3.15a)

[Ix

iX, x

...

and

(3.1?a), the following set

Ix,x+n_ 1

ix, x+n]

(3.29)

J/~en (3.28) wiU be the orf/,1onormalized version of that set. Using (3.28) we cain write the following 'global' orthogona/ decomposition of subspaces

x,n

~n,n+ i

:

f<+i,n-i n-l,n

{A~}

•

(3.30~)

v

where v{A x}

= v {A x n,o }

~l~he d e c o m p o s i t i o n

(3.30)

•

n ~ v=O

will r e s u l t

x,v V {An,v+l}

•

in t h e

'global'

(3.30b)

decomposition

of p r o j e c -

t / o n operators

p

x,n _ - p x+l,n-I II;n,n+l X;n-l,n

+

x PA;n

(3.30c)

with n p

x p x A|n : A;n,o

+

x,v ~ PA;n,v+ 1 v:0

(3.30d)

T h i s result implies the f o U o w i n g 'global' or£hogonal d e c o m p o s i t i o n of the 'biggest' s u b s p a c e

~,N

N

,N+i =

Z

®

{ x

v ~_~}

(3.31)

x,=,0

Consequent/y, the s p a c e of (3.28) We

(3.28)

ca~% b e interpreted eu~ the 'global' O N

of the two-block, multi-indexed coefficient-m~trices. T h e c a n therefore b e treated a s the 'local' O N

shall call

matrices.

A x n

A x n

the 'forwe~d' O N

b~is

b~sis of entries

basis of that space.

of the s p a c e

of generalized

59 In a s i m U ~ r B x'n-I n, m

(m=0,...,n)

the g e n e r a l i z e d B x'n-I n~w B x'n-1 nlw

way

we

matrices.

± Zx, n-I nlw-1

=

%hat

can

and

w

, we

1

c~n

errors

set in %he s p a c e errors

B x'n-1 npm

observe

ge% for

and

£ha£

m,w..l,...,n

B x'n-1 ntw

that (3.32a)

of

(3.32a)

holds

for

m,w,=0,1,...,n

, and

moreover,

m=0,...,n

for

Therefore,

]Bx n

the entries

=

I

B x'n n,n+l

Bx, n-i n,l

set. C o n s i d e r i n g

[ Ix+ n

notice that (3.33)

(3.32b)

of

[ Bx, n-I n,o

will f o r m the O N

f/y, w e

m

B-baokwaFd

ON

B-backward

Bx, n-I q~hus, w e n~m "

a

B x'n-I n,m

we

WiU form a n o t h e r

assumin 8

~[x,n-1 npm

show

%h~t the L - a n d

C o n s i d e r i n s two

B x'n-I n~m

Similarly, w e

show

BX, n n,n+ I

~nd

(m,w=l,...,n),

can

Ix+n,x+ n

""

Bx, n-I n,n

(due

to (3.19)

...

nmn+l

version

'global' or+~hogonal

n-l,n

~

and

Ix+l,x+ n

is the o r t h o n o r m a l l z e d

obt~dn the following

x,n . Bn~n+l ]

(3.33)

(3.21))

the set

ix, x + n ]

(3.34)

of (3.34).

decomposition

Consequen-

of s u b s p a c e s

v

where

%' { B x } n

=

n ~ m--O

x,n-i ~) V{ Bn, m }

~)

x,n V{Bn,n+l}

(3.35b)

6O The

(3.35)

decompositions

i m p l y the 'g/ob~l' d e c o m p o s i t i o n

of the projection

opera~ors p

x,n = p x,n-i l[{n,n+l ll;n-l,n

p +

x B;n

(3.35c)

where n X

=

PBIn

Hence,

we

~ m=0

obtain the s e c o n d

'biggest' s u b s p a c e ,

shadl call

neralized

B x n

ON

3.2.4 G e n e r a / i z e d

Let u s

kind

=

N Z n=O

entries

basis

x,n B;n,n+l

(3.35d)

of the 'global' d e c o m p o s i t i o n

of the

~

V {B:}

Cholesks/

introduce

(3.33)

of

(3.36)

ON B x n

basis

of the s p a c e

will therefore

be

of the g e termed

the

of that s p a c e .

factorizations

%he following multi-indexed

= c o 1 [ ~ _ x ] x = o .....~ =

and

p +

the global ' b a c k w a r d '

matrices. T h e

'local' b a c k w a r d

x,n-i B;n,m

in the f o r m

]i°,N N,N+I

We

p

coI [ ~

'upper-triangular'

matrLx

...

Axn "'" ANo ]

(3.374

"'"

B ° n

(3.37b)

let

B N -- COl [ B ° ] n n=O,...,N

=

COl

[B:

"'"

o ] BN

be the corresponding multi-indexed 'lower-tri~ungula~' matrix. Recalling the inner-product,

introduced

in

the 'biggest' s u b s p a c e

of g e n e r a l i z e d

matrices

61 and expressed

by

(3.13b)

with

x--0 , v - N

, n=N

, reraN+l), w e

can

obser-

v e that

(AN'

AN)_o,N ~N,N+l

o,N " AN*HN,N+I

.T ~N

-

"

~

-

•

(3.38a)

"N,N+I

where

~

is the unit (2x2)-block, multi-indexed matrix (i.e., the unit-ent-

ries of the

I[

will h a v e

L N°'N ,N+I

madn equals

writing the matrices ving that the L H S

x

coordinates

L NO'N ,N+I

A N

" The

I[ . E q u a t i o n

ConsequenUy,

(3.38b)

the O N

can be shown

matrix while the R H S

s o that the R H S

caJn b e s h o w n

conditions

'backward' generalized C h o l e s k y

(jl,Jl,J2,J2)) w h o s e

(3.38)

of s e c o n d - o r d e r b l o c k - e n t ~ of

is u p p e r -

in a similar w a y . express

the 'forward', resp.

factorization of the block, multi-indexed co-

c a n b e generalized to the 2 M - t h order s e q u e n c e s

forward w a y . W e

obser-

is the unit multl-inde-

variance matrix of the fourth-order stochm.stic s e q u e n c e . W e thai (3.38)

do-

by

'on the paper' a n d then,

is a s y m m e t r i c

h'iangulam (with unit diagonal-entries) x e d matrix

and

relations (3.38a)

HO, N ,NN + I

~ud

of (3.38a)

(jl,jl)

also r e m a r k that, a s s u m i n g

c~n

observe

in a straight-

thai the underlying s e q u e n c e

is

(and, hence, is r e p r e s e n t e d b y the t w o - i n d e x e d left-upper

o~N

H N , N + I ) , conditions

(3.38)

wiU reduce

to the C h o l e s k y

fac-

£orizat[on of the t w o - i n d e x e d covaria/qce m~trix associated with the linear least-squares prediction p r o b l e m

3.2.5 M - D

We

Fourier series e x p a n s i o n

can observe

that the 'biggest' s u b s p a c e

to the biggest 'estimation space' The

( s e e Deprettere a n d Lie (1980)).

latter s p a c e

has been

_ I,N-I YN-I,N

considered

_I,N-I RN_I, N

will c o r r e s p o n d

, u n d e r the i s o m o r p h i s m

(2.47).

in order to obtain the generalized O N

62 expansion

(in the form of the stochastic

for the r a n d o m

variable

Yo

functional M - D

, in the s p a c e

lynomials, yielding the o p t i m u m predicUon

that the

is actually the represento.£ive

(2.47) above

i°

problem

(see

s o that the s u b s p a c e

of

development

of the element

Yo

nonlinear

(1984b)).

We

not/ce

in the i s o m o r p h i s m

will play the role of the m e n t i o n e d

'estimation space'; i.e., it will b e u s e d

red O N

(second-de.~ee)

e.g., Z a r z y c k i

_I,N-I ~N-I,N

series)

of the Volterra functional p o -

solu1~on to the

least-squares

Fourier

i

in order to o b ~ n

. B'ollowln~

o

(3.35), w e

the desiget

N-I

~I,N-I

-i,N

"

~ ~ v { B nI } nmO

(3.39a)

s o that p

This

decomposi~don

ties e x p a n s i o n

i,N-i I[;N-I,N =

c~n

N-I ~ n=0

be used

for the

1

PB;n

1

(3.39b)

in order to obtain the M - D

Fourier

, in the form

o

N-i

i

We

shall s e e

~

O

later that (3.39)

for the set of M - D

impulse

filter, yielding the o p t i m u m tion problem. solved

once

is obtedned,

and

w i U imply a generalized

responses

we ON

that the basis

will s h o w basis can

sulting in the nonlinear ladder-filter

3.2.6 O r d e r - u p d a t e

We

wish

of the

be

Fourier

(second-de~ree)

solution to the non)/near

In other words, the 'backward'

(3.39c)

B i~) ~ in

(io'

~'

n=0

se-

expansion nonlinear

least-squares

predic-

that the nonlinear p r o b l e m

of the s p a c e computed

of generalized

in a recursive

is

matrices

way,

re-

algorithm.

recursions

to s h o w

Lhat the 'glob~[' forward

as well as b a c k w a r d

ON

63 bases

be

can

recursively, via a set of appropriately defined

introduced

'Ioc~Ll' e~nd '.~oba1' o r d e r - u p d a t e show

how

the

(n+l)

and

of

A x n+l

xtn (In,n+1) A x n+1

'glob~l' o r d e r t f o r w a r d

A x n+l

B x+l n

. Let u s

( B nx+ l )

observe

should

be

that the

B x n÷l

can

'local' o r d e r - u p d a t e backward

w i s h to

eund b a c k w a r d

(mutually orthonorma/)

all oi~hogoned to the s u b s p a c e

. Using the decompositions (3,35)

and

we

]~.x n+l

b e obtained recursively f r o m the n-th 'global' o r d e r solutions

solutions c a n A x n

recuLrsions. In other w o r d s ,

the index-set

and ( 3 . 3 0 ) , we will s h o w

executed

A x n

and

on

the L - a n d

]~x+l • These n

recursions, c o n s i d e r e d in p a r a g r a p h

errors A nx+ I

entries of the

that

B-, f o r w a r d a n d

recursions 3.3)

after e a c h

'local' o r d e r - u p d a t e

]~x n+l

and

(based

will p r e s e r v e

ed orthonormality of the 'local' entries of the 'globe/' f o r w a r d approximation

Kx + i ' n n,n+l

b e obtained via a set of appropriately introduced

recursions,

entries of the

entries

and

on mutu-

backward

step. C o n s e q u e n t l y ,

the

' obtained that w a y , wi]/ form the O N

seLs age/n. Reinterpreting the index-set s c h e m e order-update

step c a n

be

described

as

of Fig. 3.1, the d e s i r e d 'globe/'

follows

~x n+1

'new'---).

A x n

x

(3.40)

An+l

Bx+l n

Considering (3.28)

and (3.33)

that the number of entries of one,

during

the

order-update

with Ax n

step

n

replaced by

and of

Bx n

n -~ n + l

, yielding

n+l

, we notice

will be augmented b y Ax n+1

and

Bx n+l

'

64 ( m u c h like in the index-set s c h e m e

of Fig. 3.1). Thus,

e a c h '~lobal' order-

update step will introduce the following 'new' B-for%yard a n d B - b a c k w a r d approximation error

A x'n+l n+ l,n+ 2

whose

=

B x'n+l n+ l,n+ 2

unnorma/dzed version will be e x p r e s s e d

Ax,n+l n+1,n+2 =

as

Bx,n+1 = pl x,n n+l,n+2 If;n+l,n+l ix,x+n+l

(~s i£ follows from (3.18a) from (3022b)

The

(3.41a)

with

n

with

n

replaced b y

I

x,n In+l,n+ 1

replaced b y

n+l , a n d

(3.41b)

v=n+l; a n d

n+l).

four types of the 'local' order-update recursions, indicated in

the diasram

(3.zi0), car* be interpreted as follows:

LL-recursion: 'local' order-update for the submatrices

LB-recursions:

iAx

and

~x+l,n-I

'locai' order--updates for the submatrices 2AX and nlm 2ix n,n+l a n d

1Bx+l'n-i ntm iBx+l'n n,n+ ~i

(m=l,,00,n) (m=n+l)

BL-recursions: 'local' order-updates for the submatrices iAx'° n,1

arid

IAX'V n~v+1 and

2 B Xn,l

(v,-0)

2BX'V'l n,v÷l

(v=$, ....n)

BB-recursions: 'local' order-updates for the submatrices 2AX'° n,m 2AX'V n,m

As

and and

an example, w e

2BX n,m 2BX'V-i n,m

(v=0

(v=l,...,n a/nd

shall discuss in s o m e

update recursion while the remainin~ LB, B L ted in A p p e n d i x

2.

and

m = 2 .....n+2) m = v + 2,...,v+n+2)

detail the LL 'local' order-

and BB

recursions are presen-

65 PROPOSITION

Given we

3.1

(q)he L L

the L - [ o z w a r d

have

and

=

Sx = n,l

x

{i-

[ Pn,1

]2

}

-~

x ]2 - ½ {I- [Pn, l }

{[

recursion)

L-backward

the following r e c u r r e n c e

Ax

n,1

(3.16)

normalized

(3.20)

approximation

errors,

BX+l,n-i ] } n,o

(3.42a)

relat/ons

A x n,o

x

0n+l]

x A x {-P n,1 [ n,o

- Pn,1 [ 0 o

0n+l

] - [0

BX+l'n-l]} n,o

o

(3.42b)

where

x l = Pn,

([

A xn,o

0n+l ] ' [ 0o

(3.42c)

Bx+l'n-l]) n~o - ix n,l

PROOF. LL-fo~vard Let u s

recursion

consider

]TX

n,l

This

subspace

Ix n,l =

~

x

{ In,l }

v

caJn b e rewritten, in a c c o r d a n c e

v {i x

,

[x+l'n-3"} n,o

=

v {i x

'

with (3.7), a.s

Ix + l ' n ' l n-i,n

SO that it contains the 'new' uni-variate e l e m e n t with

Kx n~o

(3.15). T h e

variate' submatrix;

i.e.,

L-forward

estimate of the

AX In, 1 , wi~l b e e x p r e s s e d

^ = p x+l,n-1 IX, l H;n,o

IX

E

v{I x+l'n-I } n,o

' ix+n+1}

ix+n+ 1 I as

x

, in c o m p a r i s o n

with u p d a t e d

'uni-

The

error

~,A~I , a s s o c i a t e d

Ax s pl x+i,n-i n,l K ; n,o

and

D Ax

n,1

(3,25b)

=

m,

Ix

1

66 A i~, I~

with

x

-[ 0

, will b e

^x ] in, l

o

Lx ,= L x U {x+n+l} n~i m,O

, in

expressed

as

Ex+l,!d-I n,o

l

accordance

with

(3.7).

Prom

~ve o b t ~ n

Ax

=

(I-

P

n,1

=

- P

(I

x+l,n-1 ~|n-l,n

"

x+l,n-l% i x _ p x+i,n-i ix K;n-l,n " B;n,o ,% ix n,o

_

= ix

_ x+l,n-l~ - • B ; n,o ] ix

[0o

=

x+l,n-i - PB;n,o

0n+l ]

1

x

Therefore,

ax = n,l

~o

DI

= Lx : n,l

x

Since

p 0n+i]

by

-

x + l,n-i B;n,o

(3.16a). S i n c e

{x} u L x + l ' n - i n,o

, we

x

=

x+l,n--i

Rx + l , n - I n-l,n

but

L x+l'n-1 nlo

but

have

X

AX £ in, o

1

DB x+l'n-i n~o

[G,o % + i ] - (Ix'[°o B ,o

a ,l "

we

expressed

Ax

with

[A x n,o

BX+l,n-$]

rlsll

IB x+l'n-i n,o

(in & c c o r d a n c e

%vith (3.20)),

obtedn

ax

n)l

= [ax

n,o

According

([a~, °

on+ i]

-

( Ax

to (3.16), w e

o+ 1],[o o

[ n)o

' [0o

x+l,n-i Bn,o ] )lx [0o n,l

get

x+lm-i ] ) I x

Sn, o

0n+l]

=

x

IIA n,o

llo xn,1

Bx+l,n-i] n,o

67 where

we

defined

x Pn,1 "A ( [ A ~ , o

B Xn,o + 1,n-l] ) 11x

On+l]'[Oo

nll and we

can observe

Ax,1 =

x [p n,1 ~ -< i. C o n s e q u e n t l y ,

that

flAX n,o II {[A xn,o

Renormalizing

A xn,l ' w e

observing

B x+l'n-I ] } n)o

0n,x [0 o

get

Ax x -I x A x n,l = ]IAn,II] [IAn,o H {[ n,o

Finally,

x

On+ 1] -

0n+l]

B x+l'n-I ] } n)o

x - p n,l [ 0 o

that

x 1 , A:,l)llX (An,

x lll-2 IIAXn,o llAn,

= I =

II2 (i-[ Pn, lX ]2)

n,l we

obtc~dn t h e

LL-backward

normalized L L forwox'd recursion

recursion

Let u s r e w r i t e

In)l x

=

v

ITx ) in accordance n)3.

{I x

,

n,o

ix+n+l

} =

v {

with (3.7)i as

+l'n-I i x ' 1xn-l,n

so that it contains the 'new' element (3.1Q). T h e

L-backward

estimate

1

x

~:,i

Vx ~ p x ln, l X;n,o i x + n + l

The

(3.42a).

, in c o m p a r i s o n of the

~

' Ix+n+l )

ix+n+ I

with

is given b y

v{ lXn,o }

approximation error, c o r r e s p o n d i n g to that estimate, is then

X I x 8n, 1 = P W ;n,o l x + n + l

=

Ix+n+l

Vx - [In,l

0n+l ]

Kx+l'n-3" nlo

±

ix n,o

68 and

]9 Bx = Lx = n,1 n,l

From

(3.23b)

5~n,l

(I - P

(I-

=

=

U L x+l'n-I n,o

in a c c o r d a n c e

'

with

(3.7)°

get

we

=

{X}

x+l,n-i x ~;n-l,n - PA;n,o ) ix÷n÷l

P

x+l,n-l~

K;n-l,n

ix+n+l

"

-

p

" Ix+n+l

--=

x

A|n,o I x + n + l

[x+l,n-i

[0o

=

0n+l ]

n,o

_ p

x

A;n,o

ix+n+l

ConsequenUy,

~n,l =

where

B x+l'n-I

=

=

BX+l,n-I n,o

Lx

:

n,l

"

nlo

p

x A;n,o

ix+n+l

(3.20). S i n c e

Lx n,o u { x + n + l }

BX+l'n-l]

[0 °

n, i

] -

is g i v e n b y

rlsO

Dlx+n÷l

Bx

[ 0o

(lx+n+

, we

1

'[ A

= Lx n~o

DA x

n~o

but

h~ve

xn,o

0n+l])~x n,1

Since

~x+l,n-I n~o

(3,20)),

Bx

n,l

=

we

[0°

but

i A x nto

(~cco[ding

to (3.16)

.a/qd

obtain

[ Ax

B x+1'n-1 ] - ([0 ° B x+1,n-l] nso

nio

!

n~o

°~+1])

x [AX,o n,l

:

II~ +I'n-I il { [ 0 n,o

Renormalizing

o

sx+1,n-1 ] n,o

-

B xn,l ' 6und o b s e r v i n ~

x x (Bn, 1 , Sn, l)]Tx

1

=

IIB x

x

Pn,l [ A X , o

0n+l] }

that

x+l,n-i 2

n,1 II-2 llBn, o

II

n~l we

obtain the n o r m a l i z e d

LL

backward

recursion

x

(l_[pn,1

(3.4~2b).

]2)

0 n + l ]=

69 rl~he remaining 'local' order-updette recursions c~.n be obtained in a similar m a n n e r , We

can observe

(1983a);

a n d o/~e s u m m a r i z e d

in A p p e n d i x

2.

that these recurslons will constitute the generalized

nonlinear L e v l n s o n Dewilde

LIB, IBL a n d BIB ,

ed~orithm, introduced a/~ebraicaJ/y in Z a r z y c k ~ Zarzycki

vinson algorithm h a ~

been

and

(1983). Here, the generalized nonlinea/" L e introduced geometrica/ly, using projection m e -

thod, a n d c a n therefore b e interpreted e~ a m e t h o d for ( ~ r a m - S c h m i d t ) orthogonalization of the ba.sis of the s p a c e ent-matrices. W e

of the generalized coeffici-

notice that, neglecting all 'bi-variate' terms

entries of the t w o - i n d e x e d

submatrices

quently, reducing the s c h e m e obtain the generalized

and

to the L L recursions

(nonstationary)

ciated with s e c o n d - o r d e r

2A...

sequences),

(i.e., the

2B...) and, only, w e

linear L e v i n s o n

conse-

immediately

algorithm ( a s s o -

reported in Deprettere

a n d Lie

(1980).

'I'he p a r a m e t e r s

p, c o m p u t e d

as the reflection coefficients. F o r

b y the algorithm, c o n b e interpreted

example, the

x P n,1

calty equal to the L L reflection coefficient c o m p u t e d sented in Ze~rzycki a n d D e w i l d e

(1983a)

This follows from the i s o m o r p h i s m

b y the algorithm pre-

(1984:b), a n d similarly

b y the L B , B L

and BB

'global' order-update

x-labeled 'level' ( w h e r e

x=0,...,N-n

step and

of the reflection coefficients is c o m p u t e d gorithm:

recursions.

(2.47).

C o n s i d e r i n g the 'local' order-update recursions, w e that during e a c h

is numeri-

and/or b y the time-variant n o n -

linear ladder-filter algorithm p r e s e n t e d in Z a r z y c k i for the reflection coefficients c o m p u t e d

(3.420)

n

+ n+l

can observe

, executed

at the

nf0,...,N), the following set b y the nonlinear L e v i n s o n

al-

70 x~n

/~n n+l,n

pX, n

...

P

xln-1 P n,n+ 1

x,n-1 On+ i,o

""

x,n-I P n+ 1,n-I

°

"

P n+l,o

BL

n+1,1

BB

P

xsn n+1,n+3.

x,n-i Pn+ 1,n

:

(3.43)

i

X~O

xlo

P n,2

Pn,3

x Pn,1

P n,2

xlo

P

"'"

P n,n+l

x

xto P n+1~1

n+1,o

"'"

x

LL

x P n÷l,o

LB

3.2.7 O p t i m u m

approx/maH0n

Considering

'O f ~ h e M - D

impulse

responses

'we obtain the following oz'£hogonal e x p a n -

(3.39b),

sion for the N-lh 'global' o r d e r L-forward approximation e r r o r A o N,o Ao ( a s s o c i a t e d with the d e s i r e d N-th order estimate IN, ° of the I o )

o

_±

I,N-I

A N,o " lJI[;N-I,N

1o =

o B 1 -- l o - Po,1 o,o N-1 -

Interpreting f/mum

Z n=l

A °N,o

-

N-I ~ o _ l,n-1 n,=l Pn, l ~:~n,o

n o Bl,n-I ~ Pn,m+l n,m m=1

nonlinear

io

(equiv~lenf/y - b y

o 1,n Pn+l,o B n , n + l

impulse

approximate

~hat (3.4:4) is ach/ally the genera/ized

(3.4&a)

(3.&&b)

n=O

~s the set of the M - D

(second-degree)

element

N -i ~ -

+

prediction

Fourier

the r a n d o m

responses

of the op-

filter, .Are notice

series, g e n e r a t e d

variable

Yo

, under

by the

the

71 isomorphism words,

(2.47)),

in t h e s p a c e

this is the desired

reflactlon coefficientS, rithm, a r e (3.39c)

actually

ana/or We

gorithm,

of t h e

expansion

computed

@eneralized

(3.39c).

We

also

by the nonlinear

the generalized

Fourier

matrices. remark

prediction

coefficients

In other that the

filter algo-

in t h e

expansion

(3.44).

can

therefore

introduced

nonlinear L e v i n s o n

conclude

in this chapter algorithm, c a n

that the nonlinear ~nd be

prediction tilter al-

equivalent to the generalized

interpreted

~s the m e t h o d

cursive (actually Grarn-Schrnidt)

o~ho~ona/iz~/on

ce of the generalized

resulting in the o r t h o n o r m a l

matrices,

for re-

of the ba~sis in the s p a exparlsion

for the desired

estimate. In other %,vords, the n o n l i n e ~

le~t-squ~ires

diction p r o b l e m

for higher.-order stochastic

ca/n b e

fly c o n s i d e r e d M-D

impulse

as the p r o b l e m responses

of o p t i m u m

of the desired

nonlinear filter a/gorithm, p r e s e n t e d method for computation the Volterra-Wiener

Let u s

class, since the ON

for the I-D

observe

impulse

'bi-variate' terms

response

(3.44~b) in the O N

of P r o p o s i t i o n

prediction

of the o p t i m u m

by

an

a4oproximate

expansion if

of the set of

treated as

o~hogonal

(1.8)

(3.~)

Uqe

effective filter of

is actually a n

M=2.

to the Fourier line~

expansion

pcedictlon filter, if

in the nonlinear

the existence

equiva/en-

filter. M o r e o v e r ,

be

will r e d u c e

will be improved

son with the linear a p p r o a c h )

Recalling

approximation

are ne~_/ected. In the next p a r a S r a p h

estimation a c c u r a c y

3.2.8 Estimation

expansion

that (3.4~)

ON

here, c a n

of the nonlinear

explicite form of the Fourier

sequences,

pre-

we

wiJ/ s e e

case

that

(in c o m p a r i -

of the s e c o n d

component

expaJnsion.

accuracy

(3.42a))

and

3.1) w e n o t i c e

comparing

with equation

that the norms

(i)

in t h e p r o o f

of t h e L - f o r w a r d

approxima-

72 tion errors in the L L 'local' order-update

recursion

can

be related as

follov~s

(3.-[p x

IIA x I1 --11A x II n,1 n,o

Considerin~

the L B

similar w a y

that

flAx, roll =

'local' recursions

Combining

II

(3.45&)-(3.45c),

'global' order-update

step

llA~+1,oll =

where

= ]1Anx , n + l

x lqLL:n+l

we n

(3.45a)

of A p p e n d i x

(J_- [Pn,m ] 2 ) ½

IIAnX, m_111

x I]An,n+ 2 II ,~ IIA xn + l , o

]2)½

n,l

,

2, w e

m=2 .....

n+1

]2) ½

,

11( 1 - [ p x + l , o

obtain the error-norm + n+l

can show

(3.,~5b)

re=n+2

(3.45c)

relation in the

as

IIA~n,o IIR LxL ; n + I R xLI3~n+l

is the factor associated

(3.4~a)

with the L L 'local' recursion

~L~n+x ~ ~ (i- [~,i]2) ½

while

RLB;n+IX

RLB;n+I

order-update

{3,46)

express

case,

]fAn+iX II =

'local' recursions

the

(l-[pX+l,o]2) ½

error-norm

step, in the ( s e c o n d - d e g r e e )

In the linear L e v i n s o n

to the L B

as

Lm=a (1- [pnXm]2) ½

"£'hus, e q u a t i o n s

(3.¢6b)

is the faLctor c o r r e s p o n d i n g

(3.45b,c), a n d is e x p r e s s e d

in a

(3.4=6) w o u l d

reduction

(3.46e) in t h e

nonlinear L e v i n s o n be replaced

II A xn H (i- [Pn+iX ]2)½

'global'

scheme.

by

(3.4=7)

73 see a/so Deprettere a n d Lie (1980). Therefore, better estimation a c c u racy is a c h i e v e d

d u e to the factor (3.4~6c), associated with the L B 'lo-

cal' recursions. Considering

(3.~6)

for

x II AN_x, o II =

where

R LxL

x~0,...,N-x , w e

obtain

x x x II A o,o III~LL lqLs

(3.383)

is the factor associated with all L L recursions

at the x-labeled 'level' in the N-th order s c h e m e ,

x

RLL

while the

N-x-1 n Rx = n=0 LL;n+ 1

R LxB

=

N-X-1 II n=0

a n d is given b y

x

2

( 1 - [Pn,1 ] )

f~ctor is associated with all L B

executed

(3.48b)

"

'local' steps, e x e e u -

ted at that 'level', a n d c a n b e w r R t e n as

x RLB

"

N-x-i H n=0 N-x-i

11

[ n+1

n=0

Equations

(3.48)

x

(1-[Pn,m])

2 ½ ]

]2)½

(3.48c)

in the

N-th order, s e c o n d - d e g -

at the x-labeled 'level'. Interpreting the p a r a m e -

as a backward

b=0, the relalions (3.~8)

shift (i.e., time-delay) from the reference point will c o r r e s p o n d

Since the desired estimate

I

o

to the time-instant

corresponds

racy for that estimate will b e e x p r e s s e d In the linear N-th order s c h e m e ,

c o n s i d e r e d for

x

( 1 - [Pn+l,o

m=2

relate the error-norms

ree nonlinear s c h e m e , ter

x

II

by we

to

t=x .

t=0 , estimation a c c u -

(3.48)

with

x=0

.

get (accordin~ to (3.47)

n=.0,...,N-x)

N-x-1

o [I IIAN- xll = IIAX

n

( 1 - [%+,]2) x

(3.~9)

n~o so that better es~dmation a c c u r a c y

in the nonlinear s c h e m e

will b e achie-

74 d u e to the factor (3.4=8c)

ved

recursions

(since the n o r m s

associated with the L B

(i.e,, nonlinear)

of ~l/ reflection coefficients c o m p u % e d

by

the nonlinear filter algorithm are less than l).

algorithm, introduced here

*l~he generoli~ed nonlinear L e v i n s o n

geome£ric~lly using projection m e t h o d in the s p a c e matrices, ~ d

of the generalized

interpreted in terms of the o p t i m u m o ~ h o n o r m ~ l

malion of the set of M - D

impulse r e s p o n s e s ,

will imply the time-variant

orthogonad nonlinea/~ digital prediction filter. Its s t r u c ~ r e ties will b e d i s c u s s e d

in p a r a g r a p h

n=0,...,N

zx n,m

[izX n,m

o~nd

a n d proper-

3.4.

3.3 Nonlinear filter o/~orithm: t r a n s f o r m - d o m a i n

Let for

approxi-

approach

x=0,...,N-n

2zX ] n,m

[z

z

Jl

]

.

(3.50a)

(jl,j2)¢ L x

JlJ2

him where

r ]I -x = Lz I

z. J1

;

z..

z x

=

n,m

= [0

Z x'v . "ghen w e n0m

v {z x } n,m

sho/l denote b y

_I,N-I ~N-I,N

Pz;n,m

;

zx, v . v {zX, v} n,m n,m

"~-~Z;n,m )

_o,N raN,N+ I .

the

(3.51)

orthogonal projec%ion o p e -

Z xn,m

will b e the 'estimation s u b s p a c e '

u n d e r %he i s o m o r p h i s m be

(3.50b)

c a n consider the following s u b s p a c e s

rator, t~xking projection o n the s u b s p a c e that

zJ#-XzJ22-x]

Jl]2

exnd simil~rly for

We

0 ]

'

( Z nx,v , m). W e (see

notice

(2.44) wi%h

(2.47), while the 'biggest' s u b s p a c e

M=2),

will actually

75

Each element

cx n,m

~:,m(Z )

from the s u b s p a c e

[ }:,m(Zl)

=

Z x n, rn

wiU be expressed

%:,m(Zl.Z2) ]

as

(3.52a)

where

(>X'm(Zl)

-- Jl ~,

(3.52b)

f~n,m;Jl_x zJll-x

and

~x

(~I,=2)-

n,m

E

Jl

w h e r e the summations

E

O

J2

.

zi

zJ~-x

(a.52c)

n'm;]l-X'J2-x

a r e over the uni-variate, respectively,

in (3.52b,c)

over the bi-variate parts of the index-set introduce inner~-product on

jl_x •

.

~x n,m

Lx . Pollowing ntm

(2.46a), w e

as

( ~,.(z), ~x.,. (z))

. ~

(2") 2

;d@l

fd~l Cx

n,m(Zl)

i

e~V(e

iel

-x

"

,eI°~I) ~n,m(Wl)

+

1 x 2 e l W ( ie 1 i8 iw~ + --(2.)3 ~d81 Sd@ 2 [ d ~ 1 ~n,m(Zl,Z2) e ,e 2,e u.) -:,re(w1 ) + •

fde i fd~ I Sd~ 2 ~nX,m ( Z l ) l e 2 w ( e * 8 1 , e

i~

1

i~

,e

2

-x

) ~n,m(Wl,W2)

+

(2-) ~

(2.) 4

m e I f de 2 Sd~ 1 m ~ 2 ~ , m ( = l , z2) 2 ~ 2 W ( e i ~ l , e

i@2

,e

i~ 1 i~2) ×

× "~Xn,m(Wl,W2)

where

..m . i~ m e U w ( e ' 8 ,elm ) , re,u=1,2

(3.53)

a r e the entries of the ( 2 × 2 )

ral matrLx (2.14) of the fourth-order stochastic s e q u e n c e relations can be written for the s u b s p a c e s

~x,v nlm

,e

spect-

{y}. Similar

76 Pollowing

the o r d e r i n g

scheme

of p a r a g r a p h

3.1, let u s

introduce

the 'loc~l' s u b s p a c e s :

L-forward

z xn,o B-forward

(for

v {z

X

'

Z x + l,n-1 } n-~i~n

(3.54a)

v-0,...,n)

Iv Z x'V n,v+ i

=

{ z

Zx X,X '

l

v { zx,x+ v

}

v=0

n,o x,v-1 , Zn, v }

'

(3.5~b)

,

v=l,...,n

L-backward

X x,n-I v { Z x'n-I n,o --" n-l,n ' Z x + n + l

B-backward

(for

m = l,...,n+l)

Z x'n-I V { Z x'n-1 n,m = n,m-1

' Zx+n+l-m,x+n)

Z x,n n,n+l

' Zx,x+n }

= v { Z x'n-I n,n

3,3.1 'Local' estimates

Following forward

and

}

(3.54)

and

,

m=l

.... ,n

,

m=n+l

(3,55b)

(3.55c)

errors

and

(3.55), w e

back~v~J:'d estimates

and

can

errors

introduce

the L - a n d

IB-,

of the n-th '~lobad' order:

J_,-fo r v v a x ' d A

"]~he L-for-~ard estimate

zx n,o

of %he e l e m e n t

^x A P x + l,n-I Zn,o = Z;n-l~n Zx

£

z

x

~ x + 1,n-i n-l,n

will b e

defined

as

(3.56a)

77

while the corresponding

L-forward

Ax h _ i x+l,n-1 n,o = ~'~Z;n-l,n

Its normalized

version

AX, o ( Z ) = ix

I]Ax

njo

We

can observe

n=N

B-for~vomd The

]]-1

F~m°

n,v+l

(for

Ax n,o

Zn, °

(z_,z.) ] .L

a n d the errors

and

(3.56c)

-"

n,o '

(2.57), if

MAN; °

,o

1.-2 , x=.0

v=0,..0,n)

=A

^x,v Zn,v+ I

I p_ X z x~;n,o x,x p

x,v-1 Z;n~v

approximation

h

of the elements

C

~x n,o

z x~x+v

errors

Z

Pz;n,o

£

are

X~X

will be

V==0 (3.57a) v=l,...,n

by

Zx

v=O

nso

(3.57b)

l

Z x'v-1 nsv

'

v=l,...,n

form,

o

,

z x,x+v

'

Z x'v-I n~v

given

l

p ± x,v-I Z;n~v Zx~x+v

or, in a r e n o r m a l i z e d

n,v+ 1

as

[AXo(Zl)

M AZN; ° , M AN; °

± x

A X,V

(3.56b)

.

n,v+l

while the

expressed

=

error will be

zx+l,n-i n-l,n

±

Z

B-for-ward estimates

zAX,V

Zx

that the estimate

are precisely the and

will be

approximation

n,v+ 1 I[Z

cA

:L1(z1

x v

An,v+l(zl,z2)]

(3.57c)

78 L-backward The

L-backward

zVX,n-i n,o

estimate of

~= p

z

x,n-i Z;n-lpn Z x + n

a n d flee c o r r e s p o n d i n g

(for

"l~he B - b a c k w a r d

( 3.5 sa)

Z x , n-i n-l,n

±

(3.58b)

version

[~.Xln--it

= r x,n-I IF x'n-iI -i njo npo Z

B-backward

a~

error is given b y

£x,n-I =A p i x,n-1 z n,o 2;n-i,n x+n

B x'n-I (Z) nto

expressed

z x , n-i n-l,n

e

L-backward

EogeEher with its normalized

will b e

x+n

= ~n,o

s:,o (zi,~2)] (3.58~)

~Zl)

m = l .....n+l) estimates of the elements

zx+n,x+ n ~...i Zx~x÷ n

a/~e

given b y

zVX,n-I ~ _ x,n-i n,m l"Z;n,m-i Z x + n + l - m , x + n

VzX,n & p x,n-I n,n+l Z;n,n Zx,x+n

"l~he c o r r e s p o n d i n g

F x,n-i n~

B-backward

~ _ I x,n-i P Z;n,m-i

F x,n A= p ± x,n-i n,n+l Z;n~n

T h e i r normalized v e r s i o n s a n d are e x p r e s s e d

are

Z x'n-I n,m-i

m=l,...,n

(3,59a)

m=n+l

(3.59b)

'

Z x'm-I n,n

~

errors are

Zx+n+ l-m,x+n

Zx~x+n

(

l

1

Z x'n-I nlm- I

,

Z x'n-I n,n

'

Bx'n-~z) n|m

similarly ~s in ( 3 . 5 8 ) .

a/ad

m=$,...,n

(3.59c)

mmn+l

(3.59d)

B x'n _ ( Z ) n,n+l

respectively,

79

Let us o b s e r v e tes

that the L-- a n d B-, forward

z~n,m ' zAx'Vn, m ' vX,Vn,m a n d

Ax A x'v B x'v njm ~ nlm * njm

) ' A nx,v .m(Z)

AXm(Z

of the estimates

the representatives errors

errors

-I X m

of p a r a g r a p h

s

~ n d b~ck%vard

~_x,v n#m

'

~ xn,m ,v

3.2, u n d e r

estima-

, B xn,m 'v(z)

and

are

of the

the isomorphism

¢2.~v).

3,3,2 Decompositio n of s u b s p a c e s !

x x,v ' l--I_ x,v I-IA; ,m ' l-'I~ ~;n,m ~:~;n,m

Let

opera~r~ o~ ~

a n d NI-D Fourier

denote

~ub~p~es span~.a by

respectively. T h e (3.59c,d)

uON b a s e s

the ort/nogon~l projection

A~,m(Z)

orthosonalit'y conditions

expansion

'

A ~n , m (Z)

B~'V(z) n,m '

'

(3.56b) ,(3.57b),(3.58b)

will imply the following ort/nogonal decompositions

and

of s u b s p a c e s

and of projection operators:

L-forward

z x

n,o

= z ~+I,n-I n-l,n

X Pz;n,o

S-forward

~x,v

(for

v

X+ l,n-i Z;n-l,n

x z)} {An,o (

(3.~0a)

l-I x A;n,o

(3.60b)

+

v=0,...,n)

---

n,o

n,v+1

| z x'v-I

~.

I =

(3.61a) e

v ( A x'v

n~v

p

x,v PZ;n,v+I

= p

®

p

(Z) }

n~v+ 1

v = l .....n

'

x Z;n,o

+

I-I x,o A;n,1

'

v=0

x,v-I g;n,v

+

r-I x,v A;n,v+l

'

(3.61b) v=l,...,n

8O L-backward

Z x , n-I ~x,n-I n,o = n-l,n

p

x,n-1 ~ p x,n-I Z;n,o Z;n-l,n

(for

B-b~ekward

• V {

(3.62a)

I-I x,n-i B;n,o

(3.62b)

+

re=l, .... n+l)

2x,n-i Zx,n-I n,m = n,m-i

~

x,n-i V{Bn,m (Z)}

Z x'n = Z x'n-I n,n÷1 n,n

$

V {B:::

p

Bx, n-l( Z ) } n,o

,

+l(Z)}

m=1,..n

(3.63a)

m--n+l

(3,63b)

x,n-i p x,n-i Z;n,m = Z;n,m-i

+

x,n-i lqB;n,m

,

m=l,...,n

(3.63c)

p.. x~n _ = p x~n-I Z;n,n+l Z;n,n

+

x,n I-IB•,n+ 1

,

m=n+l

(3.63d)

We

can observe

A~(Z) - [ A~,o(Z)

that the entries of

Ax'o(Z) n,~

"'"

A x'n

(3.64a)

n,n+i (z) ]

as well as of

~(z)

- [B

x,n-I n, o

will form the O N much

Bx, n-1 (z)

(z)

n,n

sets in the s p a c e

s~.n

n~n+1

lized v e r s i o n s

(3.64b)

of the generalized z-polynomials,

like their time-domain counterparts form the O N

of the generalized matrices. T h e

(z)]

sets (3.64)

sets in the s p a c e

are actually the o r ~ h o n o r m a -

of

[zx

Zx, x

...

Zx, x + n ]

(3.64c)

81 and of

[z

z,

x+n

respectively. Therefore, backward

...

x+ntx+n

o~hogonal

we

z

x~x÷n

]

(3.64d)

c a n write the following '~Iobal' forward

decomposi£ions

and

of s u b s p ~ c e s

zxn',nn+l m zx+l'n-ln-l,n •

v {AnX(Z)}

(3.65a)

z~, n

v {B~(z)}

(3.65b)

. zx, n-i

n,n+ 1

®

n-l,n

where n

~{A~(z)}-

~ {A:,o(Z)}

•

Z

• ~ { A X'~ .(Z)}

(3.~Sc)

~ {B X'n _(z)}

(3.65a)

n

~{B<(z)}.-

~

•

~ {B~'~-i(z)}

m=0

These

n,n+l

orthogonal decomposition

decomposi£ions

•

n,m

of s u b s p a c e s

imply the following 'global'

of projec£ion operators

= p

x+i,n-i

p

x,n Z;n,n+l

p

x,n = ID x,n-i Z;n,n+l --Z;n-l,n

Z;n-l,n

+

+

x

l-IA;n

x 1-1B;n

(3.65e)

(3.65f)

where n

x

x

I-IA;n ~

r-IA;n,o

x I-'IB;n =

n ~ m=0

Consequently, ~,N ,N+I =

we

+

~ v-,O

l'q x,n-i B;n,m

+

m

x,v

A;n,v+ 1

l-I x,n B;n,n+l

ge£ the following orthogonal

N x ~ • v {~_x(Z) x~O

}

=

(3.65g)

(3.65h)

decomposifion

N o ~. @ v { B N _ n ( Z ) } n,,,O

(3°66)

82

,~

Hence,

se~

A~(Z)

and

bal' forward, resp. b a c k w a r d

ON

mbdti-variate z-polynomia/s, Ms

B~(Z)

o~

b~sis

be in~erp~te~ as

of the s p a c e

square-integrable

We

stocha~/c

sequence

'~lo-

of the generalized,

o n the generalized

with respect to the spectral matrix of the underlying

(Le., four~-order)

the

unit-to-

hi,her-order

{y}.

also obtain the following or£hogonal

decomposiL%on

of the 'es-

t/matio n space'

N-I

zI,N-I

Z ® v {B~(Z)}

N-l,N

which

=

(3.6w)

n~0

implies

p

Let u s

observe

representative

that h e r e of the

"l~hus, the Fourier

the element

Yo

Following

z

and~or of the

series for the

terpart of Lhe o p t i m u m problem.

N-1 Z i = I-IB; n n=,0

I,X-I Z;N-I,N

z

(3.67b)

o

~

[i

10

0]

will actually b e the

in t h e i s o m o r p h i s m

will b e the tra/nsform-domadn

o

solution to the nonlinear least-squares

(3.67b),

that O N

expansion

will b e

(2.47). coun-

prediction

expressed

as

N-1

%

~

z

(%.~,~(z))

z ~(z)

(3.67c)

rx=O

We

will s e e

of o p t i m u m

later that the a b o v e approximation

ON

series

can

be

interpreted in terms

of the set of transfer functions

of the nonlinear

predication f/Iter. We (3.67a)

notice that the O N

shoudd

be

derived

In the next p a r a g r a p h the tra/asform-domaln

we

backward

polynomial

basis

in order to get the Fourier will s h o w

version

that the desired

of the nonlinear

of the s p a c e

expaJnsion

basis

(3.67c).

is c o m p u t e d

prediction filter a/gorithm.

by

83 3.3.3 O r d e r - u p d a t e

recursions

In this poragrexph w e ce of the generalized

w i s h to s h o w

polynomials

c~

that the O N

basis of the spa-

b e recursively

computed

b y the

transform--domain counterpart of the nonlineo.r filter algorithm, derived in paragraph

3.2.6. In order to do that, it is sufficient to s h o w

higher-order sets of the generalized

polynomials

~:+I(Z)

can be derived recurslvely from the lower-order B:+I(z), be d o n e

preserving

that the

ON

and

sets

~x+l(Z

A:(Z)

and

the mutual orthonormolity of their entries. This

can

b y introducing a set of appropriately derived 'local' ordeF-upda-

te recursions,

executed

sets

and

~k:(Z)

the L L , L B ,

BL

o n the multi-variate z-polynomial

IBx+l(Z)

and BB

much

'local'

entries of the

(3.40)

l i k e in t h e s c h e m e

recursions

of that scheme,

will

Here,

be inter-

p r e t e d as follows:

LL-recursion: order-update x An, ° ( z I) LB-recursions:

step for the polynomials _x+l,n-l, ~ n,o [ zl )

and

orders-update steps for the polynomials x An, m(Zl,Z2)

x+1,n-i 8.r'~d Br],m (Zl)

BL-recursions: order-update x~o

An, l ( % ) A

X$V

BB-recursions: order-update

m = l .....n

,

m=n+l

steps for the polynomials 2£

and

.i(~ ~)

~x+l,nz ~ ~n,n+lkZl)

and

A : , n + l (Zl,Z2)

,

Bn, a(zl,~ 2)

~d

,

~-0

B~;+~(~IZa)n

v l .....n

steps for the polynomials

An, m(Zl,z 2)

and

B~,m(z1,~ 2)

X,V An, m(Zl,Z2)

and

B X'v-I (Zl,Z2) n,m

, v=0 ,

and

V= l,...,n

m= 2,...,n+ 2 and

re=v+ l,...,v+n+ 2.

"I'hese 'local'

recursions

can

be introduced

by considering

the

)

84

orthogona/ decompositions

of the sub.paces

and of projection operators,

m u c h like in the tlme-domaRn solution considered

in the previous para-

graph. For example, the LL 'local' recur.ion is introduced via

PROPOSITION Gi~

m~

3.2

>fo~=d

error

A~

(Z)

(~.~6c), ~ d

the L - b a c ~ d

~O (3.58c), w e have the following recurrence

Bx+I'n-I(z) nmo

~r~o~

relations

(3.68a)

where

@n,1

2 )-~ A (i-[0 x n,1 ]

1IX :I

(3.68b)

Pn,1

,

x ~n,i : (AX,o(Z) ' Z'BX+I'n-i(Z))zn,o

(in accordance

and

(3.68C)

with (3.53)), with

Z'BX'v(Z)n,m

XtV

=A [ zl.Bn,m(Zl )

•

X)V t

\

ZlZ2 Bn,miZl,Z2 ) ]

PROOF. Pm-a/lels the proof of Proposition 3.1, and is omitted.

(3.68d)

85 We

can observe

ly equal t O

that the reflection coefficient (3.68c)

(3.4~2C), u n d e r the i s o m o r p h i s m

(2.47), a n d t h a t

transform-domain counterpart of the L L L e v i n s o n mo/ning transform-domadn versions be obtained in a similar way,

recursion

of the LB, B L

in numerical(3.68)

iS the

(3.42). "i~he re-

a n d BIB recursions

a n d are p r e s e n t e d in A p p e n d i x

can

2. C o n s i d e -

red accordingly together, they w i l . t constitute the transform-domain version of the generalized nonlinear L e v i n s o n

algorithm, w h i c h

c a n b e interpreted

in the tro.nsform-domadn context, o~ the m e t h o d for recursive or£ho~onalizaUon of the basis in the s p a c e

3.3.4 O p t i m u m

ON

Recalling

of the genera/ized z-polynomials.

approximation of the set of M - D

tro.nsfer functions

(3.67b), o~nd considering the 'local' fro.helots-domain re-

cursions of A p p e n d i x

2, w e

ca/n write the following O N

expo/nsion for the

AN,o(Z )

error

~,o(Z)

_ ! I,N-I = I'JZ;N_I, N

zo N-:l.

ffi Z o - pOo,1 Bo,o( 1 Z)

+

N-I •

n ~

n--i m = l

I'n-I (Z) • P no, 1 B n,o n= i

-

o B i'n-I (Z) Pn,m+1 n,m

+

+

(3.69a)

N-l ~ po i,n n+l,o B n , n + 1 (Z) n-0

(3.69b) which is the genero/ized z

o

=

[1

0 ]

(M-D)

Fourier series, g e n e r a t e d b y the element

with respect to the O N

backward

polynomial basis of the

' e s U m a U o n space' in the transform-doma/n. In other words, this is the expi[cite version of the e x p a n s i o n va/ent to the Fourier e x p a n s i o n

(3.67c). W e

notice that (3°69)

(3.44), and~or to the stochastic functional

Fourier serles for the nonlinear estimate in the s p a c e ctional polynomials

(see

is equi-

e.g., Z a r z y c k i

of the Volterra fun-

(1984:b)), u n d e r the i s o m o r p h i s m

86 (2.&7). W e

can

therefore

nonlinear lea~t-squares sequences,

lea~st-squares

lc~th ( 1 9 7 8 ) ,

can

be

approximaf/on

the time- a n d

of

stochoistic

filter.

transform-domain considered

version

of the set of M - D

all bi-vari~te terms, this result will r e d u c e

predict/on problem,

to the c o n -

solutions to the linear

in Dewilde,

D e w i l d e a n d D y m (1983-), D e w i l d e

3.4 Nonlinear

We

ON

for higher-order

of the nonlinear prediction

Ne~lectin~ between

that the transform-domain

prediction p r o b l e m

is actually the o p t i m u m

transfer functions

nection

conclude

Vieira a n d

I~ai-

(1982)o

time-variant ladder-filter

can

observe

interpreted

that the L L

'local' order-update

a.s the following L L

recursion

(3.68)

section

B ~n,l (z)

Ax

(z)

n,~J

~- A~,I(Z)

(3.70)

B x + l,n-1 (Z) nlo

of the nonlinear

digital prediction filter. T h e

date recursions

can

a/qd B B

sections

b e interpreted

of that filter ( s e e

remaining

in a similar way, also A p p e n d i x

'local' order-upyielding the LIB, B L

2). C o n n e c t e d

dingly together, they will constitute the 'global' section nonlinear

filter (at the x-labeled

'~lobal' filter section

is p r e s e n t e d

n ÷

accor-

n+l

'level'). q~his 'local' structure

of the

of the

in Fig. 3.4 while the 'local' structure

87 of the t/~ird-order (N=3)

nonlinear prediction ladder-filter is s h o w n

in

Fig. 3.5. IBx,n+ 1 n÷l,n+2 Bx,n n+ 1,o n,n+l -f

x,n B n + 1,n n+l,o -)""'" -'~

n+l,n-l- ~

Bx,n n+ l,n+ 3_

An+l,n'~'~" An+3-,n+l

Bx, n-1 n+l,n-i

Bx,n-i n,n+ 1

~_ -- Ax, n+l n+ l,n+ 2

Hx, n-i n+l,n

:

f Ax,o n~2

Ax,o n,l

I

BXIO n+l,o

Bx, O n,2

x° + A x ° n+l,o ~% Bx n n+l

A~.~

nto

-~...-

.~ a~. n

..........×... ~

ax

Bx, v n,m+l ;

Ax n+l,o

,n+l

Bx+l,n n,n+l

Bx,v A x,v n,m+l

Bx,v_ 1 n~m

An+l,l

Bx n+l,o

Bx+l,n-I n,n

B X + l,n-Â nto

Ax, v n,m

x°

--'~"" ' > An,n+l

Bx Ax

xiO Bn+l,l

. AX, v n,m

AX,V n,m+l B x,v-I n,m

Fig. 3.~ 'Local' structure of the 'global' section of the timevariant nonlinear ladder-filter.

88

"l

,--Bo°(Z)-~

¢---

B

(

'(z)-m

[I

~~(z)

--J

u ---.~ ~a(z)

I

x--1

J ~(z) x=2

J ~3(z) o

x=3

> Initia/izations:

lu

~=

T

.)

'New' elements:

B2;2(z)

'

ao~,o(Z)

u

Bx'n _ (z)

'

n ~ n-l- 3

>

x=O,...,3)

Fig. 3.5 'Local' structure of the third-order (N=3) time-variant prediction filter. T h e symbols ponding 'local' 8-recursions of Fig. 3,4.

(n---i,2,3 ~ x=0,.,.,3-n)

nonlinear (Levinson) O indicate corres-

89 Let u s nested

observe

'local' 8-transformations

the s u b s e q u e n t m6dn

that the filter structure consists

sets of the forward

mutually orthonorma/

hal' order-update solutions

(actually - ~ i v e n ' s

step

in Figs,

a.s we]/ ~

after e a c h

(see

3,4: a n d

3.5). T h i s

means

of the 'local" ol~hogonal

Vieira a n d

De~vilde

(1982)).

cients

is associated

Kailath

These

(with n o r m s

(1978),

matrices

being

will re-

after e a c h

'~lo-

resp. horizontal

orthogon~9/it'y requirements, a/nd norma/ized

aJnd D y m

are specified b y

less than one),

errors

with the J-lossless

Dewilde

s o that

that the structure of this

as the filter consists

Dewilde,

backward

the subsequent-vertical,

will satisfy the desired

section

rotations)

'local' a/qd, hence,

nonlinear ladder-filter

sections. E a c h

of a cluster of

'local'

8-matrix

(see

(1981,1984),

the reflection coeffi-

actually the Fourier

coeffici-

enhS. Since the p a r a m e t e r observation, ar prediction

the reflection coefficients x , being the b a c k w a r d which

We

can

input s e q u e n c e

notice t h a t ON

ar prediction p r o b l e m

that

interpreted

(not Toeplltz)

well a~ back~vard

obtained

be

to the generalized

in meprettere

and

Lie

be solved

of the generalized the s p a c e

is reflected in the H e r m i cova/'iar*ce matrix. computes

the forward

~s

the solution to the N-th order nonlinein the innovations

context)

is

@/so r e m a r k

terms, the filter of B~i~. 3.5 Will immediately

(time--vari~/nt) linear L e v i n s o n

filter c o n s i d e r e d

(1980).

~Ve car, c o n c l u d e lem c a n

, and

'level' in the filter structure. W e

ne.qlectin~ all nonlinear

reduce

{y}

(actually c o n s i d e r e d

at the 0-1abeled

point of

is implied b y the nonstationarity

the nonlinear ladder-filter and

on

~s the 'current' time, this nonline-

of the genera/ized

b~es,

)galns )) d e p e n d

shift from the reference

filter is time-variant. T h i s

of the higher-order tian propet~y

(i.e.)the f i l t e r

Uqat the nonlinear

geometrically, (block,

using

multi-indexed)

of the genera/ized

least-squares

projection

method,

prediction

in the s p a c e

coefficient-matrlces,

(block, multi-variate)

prob-

and#or

z-polynomials

in

(provi-

9O d e d the higher-order c o v a r i a n c e

dmt~ or, equdva/ent|y, the higher-order

spectral functions of the underlyln~ s £ o c h ~ t i c former a p p r o a c h fine M - D

results in the o p t i m u m O N

impulse r e s p o n s e s

sequence

approximation of the set of

of the nonlinear prediction filter of the Volte-

rra-Wiener class. In the latter case, the o p t i m u m O N mation of the set of M - D

polynomial approxi-

transfer functions is obta/ned. W e

the results p r e s e n t e d he~'e ~ e s e n t e d in Z a r z y c k i

are given). "imhe

and Dewilde

equlv~/ent to [he algebraic solution pre(1983a),

a n d to the ~eometric solution

of the stochasf/c esf/mation problem, d i s c u s s e d in Z a r z y c k i

The

non]/near a p p r o a c h

(1984a, b)o

to the lea.st-squares prediction p r o b l e m

(for higher-order stoch~.~tic s e q u e n c e s ) the linear treatment)

r e m a r k that

may

estimation a c c u r a c y

result in better (than in

(if the s e q u e n c e

is n o n - G a u s -

sign), ho'vvever, complexity of the genera]/zed nonlinear filter p r e s e n t e d here [ n c r e ~ e s

rapidly ( s y n c h r o n o u s l y

step), a n d b e c o m e s

rather big e v e n

with e a c h

'global' order-update

in re~tively low-order nonlinear

filters ( c o m p a r i n g to the complexity of the linear filter), as it c a n b e seen

in Fig. 3.5. "l~herefore, the complexity reduction p r o b l e m will b e

the subject of the next chapter, w h e r e

time-invariant as well as 'quasi-

linear' ladder-filter algorithms will b e presented.

4. T I R I E - I R V A R I A N T

We

AND

noticed in the

'QUASI-LINEAR'

~DER-F'ILTERS

previous chapter that complexity of the ~enerali-

z e d nonline~gx' ladder-filter i n c r e a s e s

rapidly ( s y n c h r o n o u s l y

'global' order-update step), a n d b e c o m e s nonlinear filters. Consequently,

with e a c h

rel;~tively 'big' e v e n

in this chapter w e

in low-order

w i s h to c o n s i d e r the

problem of complexity reduction in nonlinear ladder-filters. In order t o obtadn efficient nonlinear filter algorithms, w e

w i n first d i s c u s s the nonlinear

least-squares prediction problem for stationary (in the higher-order s e n s e ) stochastic s e q u e n c e s . W e

~Nill s h o w

near Ume-invariant filter w h o s e

that the solution results in the nonli-

complexity is m u c h

reduced

(comparing

to

the genera/ized algorithm). Purther complexity reduction will b e a c h i e v e d by introducing simplified nonlinear estimation s c h e m e s ,

ca/led 'quasi-linear'

filters a n d associated with the o p t i m u m prediction of higher-order stochastic s e q u e n c e s

whose

'distar,ce' from the G a u s s i a n

s e n s e to b e defined). T h a t Zarzyckl and DewJ/de

problem

(1983b),

has been

is l o w

(in a

introduced algebraically in

and considered

ce of the Volterra functional polynomials)

sequence

geometrically

in Z a r z y c k i

(in the s p a -

(1984c,e).

4.1 Shift-invaria~nce of inner-products

Let u s

a~sume

stationary (in a w e a k

Ulat the underlying stochastic s e q u e n c e four~h-order s e n s e ) ,

Then,

{ y }

is

following (2.19), w e

92 will

obtain

I-Ix n,m

H x'v n,m

regardless

of t h e x - s h i R

with d o m a i n s

respectively.

- H e = "9 n,m n,m

-- H x + l ' v , , n,m.

are the g e n e r e d i z e d ces

= H x+l n,m

nom

Applying

T v n,m

(4.1b)

(i.e., the time-shift), where

(block, DT

H O'v ~ n,m

(4.la)

multi-indexed)

= L° x LO n~m n~m

(4.1a)

x x (b-~n,m ' G n , m ) xx

Toeplltz and

in (3.13),

we

"1"

n,m

covariance

DT v n,m can

and

= L °'v nlm

T v n,m

subma%rix L O'v nlm

,

write

= (_x+l _x+i~ - b ' n , m ' ('Zn,m) E x + l ~"

n,m

n,m

=

(FOn, m ,

A

F

G°m)

.T n,m

=

o

.~_T nmm

n,m

= ( F ~ , m ' Sn,~)~o

(~.2~)

n~m where

F

[fn,m;jl

=

f . . ] L° n'm;Jl'J2 (Jl'J2) ~ n,m

n,m

Applying

(4.1b),

we obtain similar relations

for t h e

(x,v)-labeled

(4.2b)

quanti-

ties

.,v

x,v

~ Fv

(Fn,m'Gn,m)ix,v

.~ v

n,m

.Sv

n,m

n,m

v

n.m "

(Fn, m ' G n ,

v

(4.z~) m)i[o,v n,m

wiLh

F v = l-l,m

[ fv . • n'm;Jl

fV . . ] L O'v n'm;JlJ2 (Jl']2) ¢ n , m

(~.2d)

93 Equations product next

(4~.2) e x p r e s s

the x-shift (i.e., time-shift)

in the h i g h e r - o r d e r

paragraph

simplifications

we

(i.e., fourth-order)

will show

of the nonlinear

4.2 "l~ime-lnvarlan% n o n l i n e a r

Following

Ao

n,m

A A

~__-

a

significant

inner-product

(4.2), w e

will satisfy the following

=

.

]

.

n'm;J1]2

notice

relations

[a v n'm;Jl

(¢.3a) (jl,J2) c L °

n,m

(v=O,...,n), w e

: A °,v n~m

Similarly, for the L- a n d

obtain

=

a

] n'm;]lJ2

B-backward

(jl,j2) E

errors,

we

L O'v n,m

can

write

= B x + I , n-I = B°, n-I = n~m n~m

A Bn-1 n,m

m=0~...,n , a n d

~':,~ n,n+l

in

=

errors

A x,v = A X + l , v n,m n,m

if

Of the

errors

n'mlJl

the B - f o ~ a r d

Bx, n-I njm

will result

In the

ladder-filter e d ~ o r i t h m

[a

==

A A v : n,m

property

case.

n,m

n,m

For

stationary

of inner-

ladder-filter algorilhm.

approximation

~ Ax+I=

n,m

this

the shift-invariance

that the L-forwc~rd

Ax

that

invariance

[bn-I n,m;n-Jl

for

~ Bn n,n+l

bn-1 n,m;n-Jl,n-J2

(4.40.)

] (jl,J2) ( Lo,n-i n,m

m-n+l

-_ [ b n , ~ + l ; n _ q ~

bn . . 1 n,n+ l;n-] l,n-] 2

(jl,ja)

e Lo, n n,n+l

94 Consequently,

the forward a n d b a c k w a r d

'global' O N

bases

will

satisfy

A x = Ax+£= n n

A ° £ A n n

(4.5a)

B *n - ~ +n * =

B ° ~: B

(4.5b)

n

n

wihh

A

B

We

n

-

n "

[A

A ° n,l

n,o

[ 13 n - I

n,o

"'"

"""

A n ntn+l ]

B n-I n,n

B n n n +.I]

notice that in stationary case, the entries of

initializations in the 'g/obal' order-update step higher-order forward a n d b ~ c k w a r d

solutions

(4.5c)

(4.5d)

B n

n ~ Z~n+ l

will be u s e d

n+l

as

, yielding the

and

l~n+ 1 . C o n -

sequentiy, in the stationoxy case: a)

there

is n o 'nesting' b e t w e e n

the x-labeled 'levels' in the structure of

the nonlinear ladder-filter; b) the nonlinear filter atgorithm c a n b e e x e c u t e d

at e a c h

x-labeled 'level'

s ep arately; c)

it is sufficient to run the a/gorithm at the (x::0)-labeled 'level' only,

following (4.5). Hence,

the stationary version of the generalized nonlinear ladder-filter

algorithm -#vil/b e obta/ned if w e

c o n s i d e r the 'loca/' LL, LB, B L

recurslons ~t the (x=0)-labeled 'level'. F o r sion of the L L "local' ordeP--updatte recursion

An,1 = ( 1 - [ P n , 1 1 2 ) - ½

Bn, I

( l - [ p n,1] 2) -P~

([An, o 0n+l]

(-Pn,l[An,o

and BB

example, the st~ttionary ver(3.42) will take the form

- Pn,1 [ 0o Bn-1])n,o

0n+l ] +[0o

B nn,o -l])

(4.6a)

(4.6b)

95 with

P~,I" ([A,,,o o . i] . [0o Bn-:t])Io~,o

(4.6~)

n,1 The ssed

transform-domain as

counterpart of the L L recurSion

(4.6) will b e expre-

(following (3.68))

InlzI 0. Fnozl

(4,7~)

with

69 n,l =" (I- [Pn, l]2) -½

(4.7b) -P n,l

and ~,i

The

remaining LB, B L

tionary c a s e

"

(A~,o(Z)'z'~.oi(z))z

and BB

'local' order-update

will be the 'local' recursions

(4.7=) recursions

of A p p e n d i x

in the sta-

2, provided the

x-label is r e m o v e d . The

L L 'local' recursion

[ion of the corresponding

(4.7)

cart b e interpreted a~ the L L - s e c -

nonlinear ladder-filter

B~,I(Z) A o(Z)

~

-- A i(Z)

B~-i(z) n

(~.Td)

g6 "l~he remaining

'local' LL, L B

and

filter will again b e

expressed

v i d e d the x-labels

~/'e r e m o v e d .

BB

sections

of the stationary nonlinear

a s the 'local' sections These

of A p p e n d i x

sections, c o n n e c t e d

together, w i U constitute the 'global' section

accord[n~y

n÷l

of the filter. W e

notice that the "set o f reflection coefficient~ c o m p u t e d

b y the alsorithm

the 'global' step x-labels Pn,m

n -~ n + l

are again

removed.

P vn,m

~qd

paraJneter

x

, will b e

(being

Observing

me

(N=3)

rithm c ~ n

can

observe

~s

lying stochastic On

sequence

(block,

mu/ti-indexed)

moving

all nonlinea~r terms, w e

sequences,

~

Toeplitz

considered

Comparing (Fig. 4,1)

in the time-variant

of the generalized

Kailath

(in a w e a k

higher-order

Levinson

matrix. W e

(1982),

Vieira a n d

Deprettere

ladder-filters, has

been

be con-

also notice that re-

a~nd Lie

we

achieved

ase

with e a c h achieved

sense).

the classical linear stationary

i~[ai%ath (1978),

of the time-variant

of the quaint[ties p r o c e s s e d

WiLl b e

the u n d e r -

algorithm c a n

will immediately o b t a i n

in Dewllde,

algo-

factorization of the generalized

Uqough, the n u m b e r

ty reduction

ca~e.

a/qd/or of the

prediction filter for s e c o n d - o r d e r

nonlinear

synchronously

matrices

provided

covari~nce

the structures

tion of the filter complexity

is

or%hogonaliza-

z-polynomials,

for C h o l e s k y

(Levinson)

(1981),

'local'

nonlinear ladder-filter

for ( G r a m - S c h m i d t )

the stationa/q~" nonlinear

a~ the fast m e t h o d

variant

considered

is stationa/'y

sidered

time-invariant A R

o n the

conclude

is time-invariant. T h e

t[me-invariant

of the generalized

the other hamd,

a.nd D y m

o n 'current' time), w e

b e treated as the fast m e t h o d

in the s p ~ c e

do not d e p e n d

that the time-invariant nonlinear ladder-filter

tlon of the ba.sis in the s p a c e basis

the

notice that the filter satisfies precisely the sa-

or£hogonality requirements, We

(3.43), p r o v i d e d

at

that the reflection coefficients

prediction ladder-filter

in Fig, zi.l. W e

by

actual/y the filter gains)

structure of the third-order presented

expressed

(i.e., they d o not d e p e n d

that the nonlinear

n +

2, pro-

Dewilde

(1980).

(Fig. 3.5)

and

time-in-

notice that significant reducin the stationary case,

al-

in the filter ~ill still incre-

'global' order-update

step. Further

in 'quasi-linear' prediction filters.

complexi-

have

structure

All s y m b o l s

F i g . 4.1 ' L o c a l '

III

IL]I the s a m e

meaning

of t h e t h i r d - o r d e r

time-invarlant nonlinear a s in Fig. 3.5.

(N=3)

ladder-filter.

(D

98 4.3 'quasi-linear' ladder-fiite[s

In this p ~ r ~ g r ~ p h ladder-filter

algorithms

we

w J ~ consider

which

we

ters will yields better estimation le their complexity considered

nonllneam

Let u s ce

{y }

riables

will b e

a~sume

accuracy

(than in the linemr cruse)

in c o m p a r i s o n

filwhi-

with the previously

algorithms.

that

is r e p r e s e n t e d

of simplified nonlinear

w J ~ c~i[ 'qu~si-lhqear' filters. T h e s e

reduced

filter

a class

the underlying

fourth-order

b y the following s u b m a t r i c e s

stochastic

sequen-

of the r a n d o m

va-

( a n d their productS)

yl,n n,n+l

.

__

_

n=0,...,N-i

Y-JlY-J2J

(4.8a)

(Jl,J2) ¢ L n,n+ l,n 1

where L l'n = LI 2Ll,n n,n+ 3. n u n,n+l

with

LI = n

{ 3,...,n+l }

2Ll'n n,n+l

Now win~

let u s

(4.Sb)

and

= sym2L I n

introduce

for

× sym2Ln1

n=0,...,N-1

(4.8c)

and

~ =0,...,n+l

the foUo-

index-sets

~(~) n

& L I u 2L(~) n

n

(4.9~)

99

where

the bi-varia~e part of the i n d e x - s e t

2L(n~)

"l~hen w e

if ~ = n + l

- i f

If w e

0

<

n

eL(~)

-

by

(4.9b)

~}

then

(~));

(since

2L(n+l)

n

n,n+l

L(°) n

c

L (~) n

c

n

L (n+l) n

="

2_ 1,n

,

D n , n + l );

.

the i n d e x - s e t

=

=

-

j 2 - j l , ....

2L(°)-

=. L l ' n

n

A 2L~,n

n

-

L (n+l)

B < n+l

L n1 i

(since

n

then

Jle

is g i v e n

that:

L ( ° ) - L1

introduce

then w e

{(jl,j2):

observe

then

~='0

-if -

can

~

(4.9a)

2L(~)

n,n+l

\

n

=

((kl,k2) : k l = B + i .....n , k 2 = k 1 ....,n }

(4.10)

notice that:

if

B =0

if

15 = n + l

if

0 < B < n+l

Following

then

eL(°) n

then

=

2Ll'n n,n+l

eL(n+1) n

= ~ ;

then

(4.9), w e

eL(B) n

can

c

consider

;

2Ll'n n,n+l for

"

n.=0,...,N-i

and

~ =0,...,n+l

the

s u b m a t r i ce s

y(n~)

A

(4.il)

~

[~-~-~

J

(~.J~) ~ 4 ~

a~nd we mention that:

- if -

if

~-0 ~mn+l

Following

then then

y(O)

-[

n

y(n+l) n

(4.10), w e

]

=

L1;

Jl E

n

_- y l , n n,n+1

will i n t r o d u c e

ey(8) n

Y-J1

"

the s u b m a t r i c e s

[Y-JlY-J2 ] (Jl'J2) ~ eL(B)n

(4.12)

I00 If the fourth-order (2.10)

with

M=2

for the submatrix

stochastic

would

hold. N o w

sy(5)

sequence let u s

only; i.e., w e

{y }

suppose

was

Gaussian,

that (2.10)

then

applies

nave

n

IF.{ y o Y _ k l Y _ k 2 }

This

means

ssian', a n d

.

~o~

0

that t h e s e q u e n c e its G a u s s i a n

(kJ.'k2) ~ %(~)n

{y}

(4.13)

is 'partially' G a u s s i a n ,

port is determined

or, ' 5-C~au-

b y the submatrix

ey(~)

•

n

From (4.9) -

and

(4.10)

it f o l l o w s that:

the s e q u e n c e

is just G a u s s i a n

if

B=0

(since

the s e q u e n c e

is n o n - C T a u s s i a n

if

B--n+l

eyn(e)

(since

=

% 2 I~ n Yn, n + l ) ;

D ' Y (n+x)

= (~);

n

-the

sequence

is ' 5-Gaussi~-u'

indicating the n o n - G a u s s i a . n

if

0

<

B < n+l

, with

part of that s e q u e n c e ,

and

with

O Y (B) n

being its G a u s s i a n If the value

part.

of the p a r a m e t e r

3

is low, w e

will s a y

that the s e q u e n c e

is 'qua~i-G a u s sian'.

PoUowing (2.~7))

(4.8)-(&.1~),

the s u b s p a c e s

(for

we

con

consider

n = 0 .....N - 1

and

(under

the i s o m o r p h i s m

~ = 0 .....n+l)

n,n+ 1

,,(B) =~ v {i(B)} n

(4.15b)

o~(B) =A v (el(B)} n n

(¢.isc)

where

~(~) n

~ h. J1

1.. ] J1J2 (jv.i2) ~ L(~)

(4.15o)

101

%(~) £ Then

we

can

[iklk2

observe

= ~(~)

n,n+l

n

(4.15),(4.16),

(4.13)

be

can

and

rewritten

define

the

An,o (~) and let

A (~) nee

(4.16)

n

according

no'~ orthogono/)

P

(~) H;n

]I(~)). Then ~q

we

±

%(B) n

following

approximation

J

its normalized

is the o r [ h o g o n a l show

i n(#)

version;

projection

-

% (n~ )

let

i n,o (~)

error

(4.18~)

i.e.,

(4.~8~) operator o n the s u b s p a c e

that

A(~) n,o Indeed,

conditions

(4.17)

~ p~ ;n(~) i o

denote

can

o£ s u b s p a c e s .

to (2.47), the o ~ h o g o n ~ U ~

~(~) ~ A n(~), A (n,~o),-1 n~o io ]I (where

sum

as

i0 let us

(4.i5e)

n

• %(~)

q) sto~nds for direct (o/though

Usin~

Now

(kl'k2)

that

?.n

where

~ %(~)

]

n

=~ P ]l';n(~)

1o

(4.19)

102 b-'Pom (4.3.7) it follows tha~

(•)

i

~(~) n~o

" PX|

O

An,o (B)

- I o _ ¢(~) n,O

1,n P~[;n,n÷l 1 o

"

T h i s implies

•

~i,~ n,n+l

~nd, consequently,

A(~)

•

e~(~)

n,o

as

e=(S) ~

,i,n

n

n~n+l "

n

Hence,

A( ~ ) n,o

This

means

tha% the u s e

estima~don accuracy,

iklk 2

of the s u b s p a c e

the o p U m u m

in the G a u s s i a n slan part

e~ O )

estimation s c h e m e

S. = pe~'t ~ N - I This

means

~)

case

into the

(corresponding

2_l,N-i RN_I, N )

for that s e q u e n c e

will be

( e x p r e s s i n g the n o n - G a u s s i a n

u n d e r the i s o m o r p h i s m

=

will not imply better

fop the underlying ' ~-Graussian' s e q u e n c e .

~ssocia~ed with the s u b s p a c e of the s e q u e n c e ,

e~B,(% n

a n d it is u s e l e s s to include that s u b s p a c e

nonlinear estimation s c h e m e Consequently,

for' (k1.,k2) ¢ eL(~ ) n

(2,47)). W e

to

~ m0

can observe

part that

and, hence, to the G a u s -

it is sufficient to c o n s i d e r the 'uni-variate'

v {i , jS=I,.,.,N} Jl

in

the o p t i m u m

that the best filter fop a G a u s s i ~ n

estimation s c h e m e .

sequence

is the linear

ladder-filter (being actually the 'most simple nonlinear filter'). ThePefore) it c ~

b e e x p e c t e d that% the o p t i m u m nonlinear ladder-filter, associated

with a ' ~-Cvaussia.n' s e q u e n c e complex

(where

0

< S < n+l)

s h o u l d b e less

than the general nonlinear filter, while estimation a c c u r a c y

s h o u l d b e still betteP than in the linear tPeatment.

103 In o r d e r to s h o w

thai, it is c o n v e n i e n t to introduce a notion of the 'nonli-

n e a r ro.nk' of the filter, a ~ the n u m b e r ling in the filter structure after observe

(see

Zarzycki

' 6-Gaussi~.n' s e q u e n c e T h i s filter will b e S

is low, w e

N

(1984~c))

of the v-labeled

'levels'

'.global' o r d e r - u p d a t e that the o p t i m u m

iS the filter w h o s e

, exis-

steps. W e

cam

nonlinear filter for a

nonlinear r a n k

equals

~ .

called the ' B-linear' filter, If the v a l u e of the p a r a m e t e r

shall s a y

that the filter is 'quasi-linear'. T h e n

we

c~

ob-

s e r v e that: - if

S =0

then w e

obto/n the linear ladder-filter a/gorithm

(of the smallest

complexity) ; -

if

~ =lq

then w e

get the g e n e r a l t~me-invariant nonlinear ladder-filter al-

gorithm, introduced in the p r e v i o u s - if

0

< ~

< 1"4

paragraph

(of biggest complexity);

then the filter complexity will b e

algorithm but smaller than in the g e n e r a l

bigger than in the linear

nonlinear case, s i n c e the o r d e -

ring in the ' ~-]/near' filter algorithm is

modulo

(n+2)

if

n-0,..., ~-i

modulo

(8 +i)

if

n-s ....N

(~.2o)

This

means

is g r o w i n g date step

that the n u m b e r from (for

1

up

to

~

n--0,...,B-l)

and B-backward

of the v-labeled 'levels' in the f i l t e r structure synchronously

s i n c e at e a c h

v-labeled 'levels' is kept constant 'length' of the filter. T h u s ,

for

starting with (and

equals

n = ~ ,.,,,N

much

n-B

'global' o r d e r - u p 'new' B - f o r w a r d like in the g e n e -

, the n u m b e r

scheme.

This

ters (S-0,1,Z,S) Now

let u s

reduced,

of the

S ), regeLrdless of the

the filter algorithm c o m p u t e s

reflection coefficients p e r 'global' order-update. Therefore,

filter c o m p l e x i t y is c o n s i d e r a b l y (8=N)

step the o n e

error is introduced to the s c h e m e ,

ral nonlinear filter algorithm. T h e n ,

(~+I) 2

with e a c h

in c o m p a r i s o n

is illustrated in Fig. 4.2 w h e r e

the

the

with the g e n e r a /

the 'qu~i-linear' fil-

are presented, evaluate estimation a c c u r a c y

l:~ollowing (3.48), w e

can

observe

in the 'S-llnear' filters.

th;~t the e r r o r - n o r m

relations in the g e -

104

D)

C)

B)

A)

F i g . 4.2 ' Q u ~ i - t i n e ~ c '

A) ~ - o B) ~ - 1 t3=

3

l~dder-filters.

105

neral time-invariant nonlinear ladder-filter are given by

tl ,4 N,o II

=

II A o,olI RI.,I.,RLB

(4.21,~)

where

IqLL

= N-1 n [n~l

Then

we

(1- [Pn,:l.]2) ½

can observe

(4:.21b)

]2) ½ 1 ( i - [ P

( i - [P

n,m0 L m = 2

RLB

N-I I] n=O

=

n,m

n+l,o

tha.t in t h e

' ~-linear' s c h e m e

]2~ "

(~.21c)

II A(~)N,oIt = llAo,oll RLL "'LB'C'(B)

(4-.22a.)

where

with

RI(B) = BI~I F n ~ 1 (l-[p (B)]2)½] (l-[p (~) ]2-~% n=0 Lm=2 n,m n÷l~o"

(4.22c)

"

(13) R2

We

N~I F ~ = n=~ Lm --2

(1_ [_(~)]2 ) %1 (1-[p (B) Pn,m

~]

n+l,o

]2)%

(4:.22d)

notice that the norm of the error in the '~-linear' case is reduced

(with respect to the linear case) can observe

by the factor

R L(~) B

(4.22b), and w e

that:

- if

~=0

then

R/uLR

-if

~=N

then

RLLR(~)

Consequently,

we

) = lqL = = RLLRLB

N-I If n=0

(1-[p n+ 1 (with

RLB

can associexte with each

j2) % given by

(4.21c)).

' B-Cxaussia/a' s e q u e n c e

the optimum ) B-linear' filter and) working with not too complex nonlinear orthogon~d structures

(whose

complexity m a y

be successively

incre~used

106 until

the

desired

accuracy

estimation

than in

accuracy

the linear

is

achieved),

we

will

obtain

better

treatment.

4.4 Experimented example

The sian a n d

' P-linear' ladder-filters h a v e non-Gaussian

20 m s

1.0 0.9 0.8

(MSE)

t)

k:

of the input G a u s s i a n

|

0.9 0.8

t

0.7

0.6

0.6

0.5 0.4 0.3

0.5 0.4 0.3

0.2

0.2

0.1 0.0 0

0.i 0.0 i0

A)

(N=8),

non-C, a u s s i a n

' S-linear'

a s s o c i a t e d with time-series.

1.0

beta=@

--4--

0.7

a~d

present compu-

in the adaptive

innovations filters of the eight-order

samples

H5£(@

tested u s i n g p s e u d o - G a u s -

excitations. In Figs. 4.3 - 4.6 w e

ter plots of the m e a n - s q u a r e - e r r o r s (~=0,i,2,3)

been

20 m s

0

I0

20

ms

B)

Fig. 4.3 M e a n - s q u a r e e r r o r in the 'O-linear', 8-th o r d e r ladder-filter, inputted with: A ) O aussia~n B) non-G aussian excitations.

107 bCta:l

t)

1.0

o.9

~

0.8

....

1.0 ]

mmmmmm-mmmm m I mmmmmmmmmmm • mmmmmmmmmum wmmmmmmmmm 11! , m m m m m m m m m 1 ,~ , m - , m m m m m m m

0.9 0.8

o7

07

0.6

0.6

o.~ [ 0.4 i J 0.3-'L,i

~

0.5 o.~ 0.3

L f

0.2 0.I

mmmlmm,---

0.2 0.i

0.0

Q.0

0

i0

20

~ 0

ms

A)

i0

20

ms

B)

5'ig. 4.4 M e a n - s q u a r e - e r r o r in the 'l-linear', 8-th o r d e r ladder-filter, inputted with: A) G aussian B ) non-Gaussia/n excitation.

1.0

t)

beta=~

1.0 0.9

0.9 ~ 0.8

0.8

0.7

-

0.6

~ ~

-

A

.

.... , . . . . .

;

,,

0.7 0.6

,.

]

o.5)

_

o.4Ji ) 0.3 0.2 0.1 0°0 0

10

A)

20 ms

0.5 0.4 0.3 0.2 0.1 0.0 0

I0

20

ms

B)

Fig. 4.5 M e a n - s q u a r e - e r r o r in the '2-I/near', 8-th o r d e r ladde~-fJ/ter, inp u ~ e d with: A) Gaussian B) non-G aussian excitations.

108 1.0

,MS~ (8

t)

beta =3

1.0

0.9

0.9 I

O.8 0.7

i1 i

0.5

O.8 0.7 ....

00

I

0.4

I

0.5

0.~ k

0.3 i_ 0.2 0.I

0.3 O.2 0.i

0.0

0.0 0

i0

20

ms

i0

0

A)

20

ms

B)

Fig. 4.6 M e a n - s q u a r e - e r r o r putted with: A) Gaussian B) non-Gaussian excitations.

in the '3-1inear', 8-th o r d e r

ladder-filter, in-

Comparing Fi~s. 4.3a and 4.3b, we c a n o b s e r v e that the linee~C esti-

mat[on

accuracy

the G a u s s i a / ~

in the non--Gaussi~Ln

excitation. T h i s

filter o p e r a t e s

on

Comparing schemes This

do

Figs.

is m u c h

to c h a r a c t e r i z e

not i m p l y better estimation

non-Gaussian

the m o s t vement

simple)

Figs.

It s h o u l d ally d e p e n d s

on

be

filter is u s e d .

4.3b - 4.6b, w e

accuracy

which

signa/s. estimation

in the G a u s s i ~

noted

con

observe

estimation p r o c e d u r e s

accuracy

case.

filter is the b e s t p o s s i -

that the i m p r o v e m e n t

ca/q b e

that the u s e

introduce

in cause of n o n - G a u s s i a / q

the h i g h e r - o r d e r

ever, that i m p r o v e m e n t

of

signal.

nonlinear

of estimation

in c a s e

notice that the n o n l i n e a r

resttlts f r o m the fact that the linear estimation

Comparing

th~n

statistics of the input time-series:

4 . 3 a - 4.6a, w e

ble filter for a G a u s s i a n

worse

follows from the fact that the linear l a d d e r -

the s e c o n d - o r d e r

a r e not sufficient in o r d e r

case

significant impro-

excitation.

of estimation

accuracy

statistics of the u n d e r l y i n g

achieved

if a

of ( e v e n

(suitably c h o s e n )

sequence,

actuhow-

nonlinear

5. C O N G L U D I N G

The can

be

REMARKS

nonlinear

prediction filter a/gorithms,

directly i m p l e m e n t e d

modular

memory.

A

in this work,

in a soft- a/nd/or in a h a r d - w a r e

structure of the nonlinear

w@/'e reetlizations,

presented

way.

orthogonetl laddeP-filters implies soft-

requiring relatively small capacity of the operational

hard-ware

realization follows from the fact that the basic

thogonetl 'building-block'

of the nonlinear

a s in the linear ladder-filters.

That

block' c a n

using V L S I

(namely

DICS

implemented

processors),

introduced

hal filters ( s e e

e.g., A h m e d

ret£ere, D e w i l d e

and

nonlinear cessors

Udo

(1984);

a s well, taking a d v ~ t a g e

versions

of those

troduced

(see

having

Zarzycki

like in the linear c a s e

(1981).

Consequent/y,

in this work,

(1983b);

Consequently,

of the para/lel computations. orthogonat

by

the

adaptive

directly o n

capability, c a n

q'he nonlinear

considered

Dep-

It s h o u l d

filters. M o r e o v e r ,

filters, operating

least-squares'

COR-

'building-blocks' a s s u -

adaptive

a

also b e

in-

filter algorithms

solution at e a c h

time-ins£artt,

Lee, M o r f a/nd FriedlaJnder

the nonlinear prediction filter algorithms,

are a/so suitable for on-line nonlinear

order time-series.

'building-

b e realized with those pro-

parameter-tracking

result in the 'exact nonlinear much

here, c a n

ro-

of the linear orthogo-

(1983)).

Dewilde

prediction

(1984d)).

circuits

Deprettere

stability of the nonlinear

nonlinear

of data, a n d

(1982);

of the norma/ized

res inherent numerical

stream

Morf

digital filters, c o n s i d e r e d

b e noted that the u s e

integrated

in the rea/izettions

and

or-

filter (actually the G i v e n ' s

tor) is precisely the s a m e be

The

processing

introduced of higher-

110 REFERENCES

AHMED

H.M.

1982

BARRET

M.

VLSI a r r a y architectures f o r m a t r i x factorization, in Outils e t m o d , e l e s m a t h e m ~ i q u e s pour l'automatique, l'analyse d e syst e m e s e t le fr0/£ement ' du s i q n a l , E d . C N R S , Paris, VOI.2, p p . 691-704. J.F.

1963

BOSE

and M O l q F

"/~he u s e Of functionals in the ~nalysis o f nonlinear physical systems, J.Electr.Contr, vol.15, pp.567-615.

A.G.

1958

theor~ of nonlinear systems, "l~echn.Rept., IVIlq?.

A

R.H. a n d

CAMERON

1947

MAR"I~IN W . ' I '

T h e or~ho~onal development of nonlinear functionods in series of Pourier-Hermite functionals, Ann.Math., voi.48, pp. 385-392.

DELSARTE

P., @ E N I N

Y. and R A M P

y.

1979 a

S c h u r parametrization of positive definite block-Toeplitz matrices, SlAIVI J.Appl.Math., voi.36, pp.33-~6.

1979 b

"l~he Nevanlinna-Pick problem for matrix-valued functions, S I A M J.Appl.NIath., voi.36, pp.4~7-61.

1983

CTeneralized S c h u r positlvity test and Levinson recursion, P roc.ECC'i~D' 83, Stuttgar%. J.M. and M O R F

DELOSME 1982

M.

Fa~t algorithms for finite shift-rank p r o c e s s e s : geometric approach, in Outils et modeles mathematiques pour l ' a u t o matique, I S ~ a l y s e de s y s t e m e s et le tr~dtement du siena/! E d . C N R S , Patois, voL2, pp.4:99-529.

D EPlq E'IVI~ER E EQ 1981

Orthogonal filters, Ph.D. Thesis, De]/t Univ. ~i~echn.

1982

Mixed

form

time-va~vi~t

lattice

recursions,

in Outils

et

mo-

deles ma~thema~ques pour l'automat/que! l'analyse de systemes et le tro/tement du si~n6d, E d . C N R S , Paris, vol.2, pp.5~5-562. 1983

a

Synthesis and fixed-point implementation of pipelined true or~hogona/ fJ/ters, Proc.ICASSP'83, Boston.

1983

b

C O R D I C - 1 0 : A n expoJndable VLSI implementaJ01e or~hogonal filter module, P r o c . E U S I P C O ' 8 3 , Erlangen.

111 DEPRETTERE

E. a n d D E ; W I L D E

P.

Genere/ized ort4hogonal fJ/ters for stochastic prediction a n d modeling, in Digital signo/ processing, Ed.V.CapeUlnL~ A c a d . Press, N.Y.

1979

DEPRETTERE

E., D E W I L D E

P., a n d U D O

R.

Pipelined C O R D I C architectuz'es for fast VLSI filtering m~nd array pz'ocesslnS, P r o c . I C A S S P ' 8 4 .

198&

DEPRETTERE

E. and J A I N A N D U N S I N G

K.

1984

D e s i g n and VLSI implementation of a concurrent solver for N coupled systems of linear equations, Techn.Rept., Delft Univ, T e c h n .

DEPRETTERE 1980

E. a n d LIE S.C. Generalized Schur-Darllngton algorithms for lattice-structured matrix inversion end stochastic modeling, ~echn.Rept., Delft Univ. T e c h n .

DEWILDE

P.

1982

Stochastic modeling with orthogone/ filters, in Outils et toodeles mathematiques pour l'automatiquem l'anedyse de s y s tames et le tra/tement du si~ne/j E d . C N R S , Paris, vol.2, pp.331-398.

1983

O ~ h o g o n e d filters: Pipelining a n d VLSI implementation, Proc. E C C T D ' 83, Stuttgart.

1984a

Spectral approximation a n d estimation with scattering functions, in Mathematice/ T h e o r y of Ne£v~orks a n d Systems, Lecture Notes in Control a~nd Information Sciences, vol.ziS, Ed.P.A.Fuhrma~n, Springer-Verlag, pp.234-252.

1984b

O£thogone/ filters: A Ibid., pp.253-267.

DEWILDE 1979

DEWILDE 1984

DEWILDE 1981a

P. a n d B U L T H E E L

numerJce/ a p p r o a c h to filtering theory,

A.

Orthogonal functions related to the Nevanlinna-Pick problem, h Mathematical "l~heor~ of N e t w o r k s a n d Systems, Ed.P.Dewilde, vol.3, Delft~ pp.207-212.

P., DEplqE'I~TEIqE E. a n d N O U T A

R.

ParaJ/el ~ d pipelined VLSl implementations of signa/ processing algorithms, in V L S I e n d signal p r o c e s s i n ~ Ed.S.Y. Kung.

P. and D Y M

I-I.

S c h u r recursions, error formulcms e n d c o n v e r g e n c e of railone/ e s t i m a t o r for stationaz'y stochastic processes, I E E E Trans. on IT-27, pp.44=6-461.

112 1981b

L o s s l e s s chain s c a ~ e r i n g matrices a n d o p t i m u m linear prediction: T h e vector case, Circuit T h e o r y a n d Appl., vol.9, pp.135-175.

1984

L o s s l e s s inverse scaltering with rational networks: ~l~heory a n d applications, I E E E T r a n s . o n I'f'-30.

DEWILDE

P., V I E I R A

1978

A.C. a n d K A I L A T H

T.

O n a generalized S z e g b - L e v i n s o n realization algorithm for optimal linear predictors b a s e d o n a n e t w o r k synthesis approach, I E E E T r a n s . o n C A S - 2 5 . pp.663-675.

I~'RECHET

M,

S u r l e s fonctione~es c o n ~ n u e s , Sup. 3-me, S e n V . 2 7 .

1910

Ann. de ~Ecole

Norm.

ITO K.

Multiple W i e n e r pp.157-169.

1951

KAILATH

Integral, J . M ~ h . S o c . , Japan, vol.13, nr i,

T.

1974

A v i e w of three d e c a d e s in linear filtering theory, I E E E T r a n s . o n IT-20, pp.146-181.

1982

Time-variant a n d time-invariant lattice filters for nonsta~io n a r y p r o c e s s e s , in Outils et m o d e l e s m ~ h e m a t i q u e s pour l'aut0matique , l'analyse d e s y s t e m e s et le traitement d u si.@nal, E d . C N R S , Paris, vol.2, pp.4~17-464:.

LEE

D.T.L., M O R F

3.981

LEV-ARI

M. and FRIEDLANDER

B.

R e c u r s i v e lea~st-squares ladder-estimation algorithms, I E E E T r a n s . o n C A S - 2 8 , pp.467-481.

H.

1982

Parametrization a n d modeling of nonstationary p r o c e s s e s , Ph.D.Thesis, S t ~ f o r d Univ.

1983

M o d u l a r architectures for adaptive mulfichannel lattice a/gorithms, P r o c . I C A S S P ' 8 3 .

LEV-ARI

H. a n d K A I L A T H

1982

LEVIN SON 1947

T.

Lattice filter parametrization a n d modeling of nonstationary p r o c e s s e s , T e c h n . R e p L , Stanford Univ.

N. T h e W i e n e r l q M S error criterium in filter design a n d prediction, J.Math.Phys., voi.25, pp.261-278.

113 MORF

M., VIIi;IRA A.C., L E E

1978

0GURA

Recursive tion, I E E E

D.T.L. a n d

KAILATI4

T.

mu/tichannel m a x i m u m entropy spectra/ Trans. o n O E - 1 6 , pp.85-94.

estima-

H.

1972

Orthogon~II functionals for the P o i s s o n Tra/ns. o n IT-18, pp.4:73-481.

PIEKARSKI

process,

IEEE

M.S.

1971

R e c i p r o c a l D~rlington section suitable for a~n integrated circuit, IDlectron.Let%., vol,7, pp.475-4:77.

1974

A minimal ~ r o u n d e d c a s c a d e synthesis cuits, P r o c . E C C T D ' 7 4 ~ , L o n d o n .

PIEKARSKI

M.S., S A E E D

1980

A

PlEKARSKI

M.S.

1984:

1983

Warsaw.

and

URUSKI

M.

RAO

C.V.K.

and

HELMOND

J.

O n the theory of All spectra/ approximation for p r o c e s s e s containing deterministic signals, P r o c . E C C T D ' 8 3 , Stuttgar[.

SEGALL

A.

and

KAILATH

T.

Orthogoned functionals of independent-increment p r o c e s s e s , I E E E T r a n s . o n IT-22, pp.287-298.

1976

SCHETZEN

M.

1980

Volterra-Wiener

theories

of nonlinear

systems,

Wiley, N.Y.

J. U b e r potenzreichen, die in innern d e s einheitskreises beschralakt sind, J.Reine Ang.Math., voi.147, pp.205-2320

1917

STEINHAUS

H. a n d

1935

TUSZYNSKI 1980

K.

test for positive real function, P r o c , E C C T D ' 8 0 ,

Interpolation with positive real matrices, P r o c . I S Y N T ' 8 4 , S araj evo.

PRABI-LZkKA/~A

SCHUR

for in%esra£ed cir--

KACZMARZ

Theorie

S.

d e r or%ho~onedreihen,

Warsaw.

A.A. A COIqDIC pp.68-79.

~ithme%ic

processor

chip, I E E E

Trans.

o n C-29,

114 VICTOR

J.

and

1979

VOLTERRA

Nonlinear ~nalysis with arbitrary stimulus Quar%.AppLMath., vol.XXXVIl, pp.115-136.

ensemble,

'l~heo~ of functiona~s a n d of integra/ a n d %~al equations, D o v e r Publ.

integro-differen-

V.

1959

WIDYA

KNIGHT B .

I. Continuous-time stochastic modelin~ with lossless lures, Ph.D.']~hesis, Delft U n i v . T e c h n .

1982

N.

WIENER 1938

"l~he h o m o g e o u s

1958

Nonlinear ley N.Y.

WOLDER

chaos,

problems

A m e r . J.Math., vol.60, pp.897-936.

in r a n d o m

theory, M I T

Press

- Wi-

P.

1959

YASUI

stm/c-

rl~he C O R D I C trlgonometric o n E C - 8 , pp.330-334,

computing

technique,

IRE

Trans.

S.

1979

ZAIqZYCKI

Stochastic functional Fourier series, Volterra series a n d nonlinear s y s t e m a~qalysis, IEIDE Tra/qs. o n A C - 2 1 , pp. 230-242.

J.

1983

Nonlinear L e v i n s o n prediction filter for higher-order dos sequences, Proc.ECCTD'83, Stuttgart.

1984a

N o n l i n e a r prediction of higher-order submitted for publication.

1984b

G e n e r a l i z e d ladder-filters for nonlinear prediction of higher-order r a n d o m s e q u e n c e s , submitted for publication.

1984c

F a s t algorithms for £he least-squares submitted for publication°

198~d

A d a p t i v e proper1~ies of nonlinear for publication

1984e

Nonlinear ladder-filters for the least-squares A R prediction of hi~her-order r a n d o m s e q u e n c e s , P r o c . I S C A S ' 8 4 , Montreal.

1985a

Nonlinear L e v i n s o n algorithm: A g e o m e t r i c Proc.ECCTD'85, Prague.

1985b

O ~ / ~ o g o n a l ladder-form representations of nonlinear prediction filters of the Volterra-Wiener class, in Mathematica/ Theorsf of N e t w o r k s a n d S y s t e m s , to b e published.

random

r~n-

sequences,

nonlinear prediction,

ladder-filters,

submitted

approach,

115 ZARZYCKI

J. a n d D E W I L D E

P.

1983a

Nonlinear least-squares predichion of higher-order d o m s e q u e n c e s , submitted for publication.

1983b

"l~he L e v i n s o n - t y p e filters for fast nonlinear A R tion, Techn.lqept., W r o c l a w Univ, T e c h n .

ran-

predic-

APPENDIX

i

MUI/~I-INDEXED

Let

I

MATRICES

denote

a

real n u m b e r s .

AND

contiguous

We

define

GENERALIZED

subset

of integers,

a m-indexed

m A : ml ~

where ml

mI = I × . . . × I

can

will b e

be

c~/led

denoted

domain

DmA.

Lo£ n

mL°n =A LOn x . . . .

matrix

let

mA

THEORY

~ as

be a

the set of

map

(A.1)

~

( m - c o p i e s ) . A c c o r d i n g to ( A . 1 ) , the i n d e x - s e t

the

~s

MATRIX

of the

Let u s

(j } n . o

m-indexed

introduce

matrix

the

mA,

This

index-sets

{0,I .....n }

L On = { ( J l ..... Jm ) :

domain

(A.2)

Jk E L :

, k = l ..... m }

(A.3)

m A m-indexed

matrix

mR ~n

DmA

This

matrix

entries

as

ca/n b e

W e will c o n s i d e r operations and

type

(A.4),

n-th order

m a t r i x if

(A,4a)

expressed

in t e r m s

of its m - i n d e x e d

follows

[ a.

=

-n

order

the

rnL° n

~

--n

equivalently

mA

duce

will be called

here

some

on those

domain unless

]

~l""Jm

of t h e

(A.4b) ( J l . . . . . 4 . ) ~ m~o

n

properties

matrices. matrices,

otherwise

of m u l t i - i n d e x e d

W e will u s u a l l y assuming

stated.

matrices,

drop,

and

intro-

for simplicity, the

that all matrices

are

of t h e

117

matrix

Symmetric

A

m-indexed

matrix will b e

co/led s y m m e t r i c

if for a n y

permutation

ul,..., m

of integers

l,...,m w e

shadl h a v e

a.

_51...jm

sm

--J nl...j m

Consequently, symmetric ~jl...jm

matrix instead denote

corresponding

n m

o

Ln

a,

-ll...jm

of equai

elements

(jl,...,jm) . W e

matrix

= [ a, . )l...]m

- m -

'different' entries of the

%n

by

mA

of the s y m m e t r i c shall denote

let

matrix,

the

'symmet-

, where

]

(A.Sb) (j:l,...,jm)

to lexicographic

~ symmbno

port' of the m-varlate

or anti-lexicographic

a

of m A c a n then b e e x p r e s s e d Jl...jm n of the s y m m e t r i c matrix mA as --n

ajl...jm

matrix. N o w

entries of n o n - s y m m e t r i c

denoting the 'symmetric

obtained a c c o r d i n g entries

n

t o the s e q u e n c e

mA

sym

of

the n u m b e r

ric part' of a m - i n d e x e d

with

(re+n)

it is sufficient to consider m

(A.Sa)

= 7jl...jm

a. , -Jl...Jm

index-set,

ordering. T h e

in terms

of the entries

(A.5c)

"!~ranspose matrix

Let

r~ b e

represented

a permutaf/on

of the index-set

{ (Jl'""Jm) ¢ m L °n }. u

may

by a map

1 , a ,..., ~ ) ( ~ l ' ~ 2 .... ' ~ m

(A.6~)

be

118 where xed

( nl' ~2 .....nm)

matrix

n

tion

mA~

is a permutation

A

{1,2 .....m } . T h e n ,

will b e co/led the transpose

a m-inde-

matrix due to the permuta-

if

( mAn )jl...jm

Z

of

:

( mA )rt (jl,...,jm)

(A.6b)

ero-m~trix

m-indexed

indices

matrix

will be called a zero-matrix if for e a c h s e q u e n c e

(jl,...,jm) c D m A

we

have

ajf..jm

0 . This

of

matrix will be de-

noted b y

mo

=

[0jl...jm ]

where

O.

.

J1..,Jm

(A.7)

(Jl .....jm) c D m O n

n

will b e the z e r o - e n t r y

wlth 'coordinates'

(jl,...,jm) .

Unit-matrix

A

2m-indexed

and

matrix will be called the unit-matrix if for e a c h

(k1'""km)

¢ D2mAn

~.

(Jl .....Jm )

we have

.

=

]1.,,]mkl,,,km

~

(A.Sa)

Jl,0.Jm;kl---k m

where X

5

.

]f " ] m ; k l " ' k m

=

I

0

if

Jl=kl

,..., J m = k m (A.Sb)

otherwise

119 This matrix will b e d e n o t e d

as

2m I

n

=

[

.

.

6 ]l...3m;kl...km

]

(jl,...,Jm,kl,...,km)

D2mi[n

(A.8c)

Block-matrices

A block-matrix w h o s e

block-entries are m-indexed, n-th orde• mmtrices

{ M } A n = [ m a n ] m = l ..... M

will b e called a M - b l o c k

row d o m ~ d n

D {1%4}A

n

(A.9a)

(row), m-indexed, n-th order matrix. Its block-

will b e a vector of simple d o m a i n s

D{M}An

"

[DmAn]

(A.gb)

m=l,...,M

Similarly, a block-matrix

{M}Bn

= col [ m B

will b e called a M - b l o c k block-column

(column),

n

]

(A.10a)

m = 1,...raM

m-indexed,

n-th order matrix with the

domain

D {M} B n

= col [ D m B n

] m=l,...,M

(A.10b)

Finally, a block-mc~trlx

{M×M }H

= [ meu H n

whose

block-entries are

] n

(m+u)-indexed

m,u= I,°..,M

matrices

(A,11a)

120

meuI-I

will b e c a l l e d

[h.

=

n

" k

Jl'"Jm

k ]

i"' U

a (MxM)-block

Its b l o c k - s q u a r e

(jl,...,Jm,kl ....,ku) ¢

(square),

D{M×M}H

domain

=

[DmeUH

observe

'block-column'

that the matrix form. T o

DUll n , w h e r e

(A.11)

can

order

matrix.

(A.:lc)

be described

d o that, l e t u s s u p p o s e

( J l ..... Jm ) ¢ D m H n

n-th

(m+u)-indexed,

n ] m,u=l,...,M

n

Let us

(A,1lb)

is g i v e n b y

n

D { M x M }H

DmeUHn

and

that

in a generalized

DmSuH ~ DmI-I x

( k l ..... k u ) E D u l l

n

n

. ~hen

n

we can

write {MXM) H

=

[{M}xu

H

n

] n

u=I,.o0~M

(A.laa)

where

{M}x UHn -

col [meuH n]

m = l ..... M

(A.12b)

or, equivalently,

{M} xu H

-

[{M} H

n

] n;ki...k u

(A.12~) (kl,...,ku) ~ DUll n

with

(M} Hn;kl.o.k u = [ 51***Jmkl,..ku ]

(A.12d) (jl,..,,jm) ¢ DmH n

Equal. matrices

Two

m-indexed

mA = [a.

matrices

] Jl""Jm

; (Jl ..... Jm ) ~ DmA

ms = [b.

] (A.13) "~l""Jm (Jl ..... Jm) ~ Drab

121 will b e called e q u a l matrices if of indices

..(Jl,*-*,Jm] ¢

DmA

=

Given the matrices

if for e a c h

sequence

(A.14)

b.

ll...Jm

ll...Jm

of multi-indexed

, and

DmA

a.

Sum

= DraB

matrices

we shall s a y that the m - i n d e x e d

(A.13),

.

mG

[gjl...j m

matrix

(A.15a)

]

(Jl

.....jm ) c D m G

is the s u m mG

Drag

,= D m A

- Dn~

=

mA

, and

mB

+

(A.15b)

if for e a c h

(jl,...,jm) ¢ D m A

A

gjl...j m = ajl...j m

Sum

of bl.ock, ' multi-indexed

Given two M-block (row),

matri.ce.s

m-indexed m a t r i c e s

{M}A = [ mA] m=l ..... M

we

sh~U

say

;

that the M - b l o c k

{M} G

{M }m = [ m B ] m=l ..... M

(row),

=

m-indexed

[raG] m=$,..,M

where

mG

is given by

(A.15c)

b.Jl...Jm

+

( A . 1 5 a ) , is the sum

(A.16a)

matrix

(A°16b)

122 {M} G .

if for ce

m~l,...,M

of indices

we

have

{M} A

DmA

+ {M} B

= Drab

(jl,...,jm) E D m A

(A.16d)

= DmG-,

the entries

and

gjl...jm

if for e a c h are

sequen-

expresed

by

(A.1~o).

Product

Given say

of a s c a l a r

a scalar

and

c ~ ]~q

and

that the m - i n d e x e d

lar ~ n d

the m - i n d e x e d

a m-indexed

a m-indexed

matrix

mG

matrix

(A,15a)

mA

(A.13),

is the p r o d u c t

we

shall

of the s c a -

m~£rix

mG

if for e a c h

matrix

= c-mA

(Jl .....Jm ) ¢ D r a g

(A.17a)

(where

Drag

= DmA)

we

have

A

gjl...j m = C.ajl...j m

Product

Let

of mul#/-indexed

mA

replaced

be

given

by

by

s , where

(A.iYb)

matrices

(A.13), m

and

let

< s . Let

sB

be

u, ~ , 9

given be

(A.13)

by

some

given

with

m

integers,

satisfying u

and

moreover

and

the

s

+

~

let indices

= m

r ;

;

(u + ~))

of the

sB

~

*

+

Partitioning

9

= s

the

in accordance

(A.18a)

m with

indices (A.18a),

of the

mA

and

assu-

t

123 rning that

mA

DmA

=

= DUA

×D~A

and

DSB

= D~tB x D 9 B

We

c a n write

[~ki...k~l...j ]

(A.18b) (kl)...,ku) ~ D U A

SB =

, we

[b ] Jl'"J~ii'"i9 (Ji ..... J~) ~ D ~ B

shall s a y that the

r =

; (jl)...,j~) E D ~ A

; ( i i ..... i~) ~ D9B

(u + 9) -indexed

matrix

] r'(u+ whose

(~ lSd)

9) G = [ g k l . . . k u i l . . . i 9 domain

is

DrG

= DUA

(A.18c)

(k 1 .....k u ) ~ D U A x DqB

; (i i ..... i 9) ~ D g B

, is the

~t-product of the matrices

ue~ A" ~ e g B

(A.18e)

(,aL,18b,c)

rG

if

Dt~A = D ~ B

= UD

= mA.s B

=

, a n d if for e a c h

(kl,...,ku) ¢ D U A

, a n d for e a c h

(iI,....i 9 ) ~ D g B

gki'"k uil "''i9

where

the s u m

(jl,...,jt~)

Product

Given

=

~~D

in (A.i8f)

over the

~i...ku Jl...J ~

denotes

square-matrix u-indexed

(row)

{ M x M }H

matrix

~-fold s u m m a t i o n

~-variate index-set

of block) multi-indexed

the M - b l o c k

the

matrix

b. . il...i~ J1 '''J p.

(A.i8f)

with respect

~D .

matrices

{M }A

(A.il), w e

(A.9),

shall s a y

a n d the

(MxM)-block

that the M - b l o c k

(row),

to

124 {M}

G

=

(where

[uG]

for

u..1 , . , M

u=l,...,M

UG

we

have

: [ g k l .....k u]

DUG

= Dull

is the block m - p r o d u c t of the matrices

{M}G

for

:

{ M }A

(k 1 .....k u)(

(A.19a)

DUG

, with

D m~u H

and

{MXM} H

= DmH,DUH)

{M}A'{MXM}H

(A.19b)

u=l,...,M

uG

M )-] m A ' m S UH

A

(A.19C)

m=l with

"

denoting

9 =u , we

the

product

.(A.18e).

t e n rewrite (A.19)

Using

(A.18)

with

u :0

,

k =m and

e~

M

gkl...k u =

where

=

mD

(A.12d), w e

DmA

~

:

mD

mffil

- DmH

'Outer' or K r o n e c k e r

m

mA

(kl,...,ku) ~ D U G

{M} A {M} •

, Equiva/ently, using

(A.19e)

Hk1,..k u

SB

be expressed

by

shall s a y that the

(m+s)-indexed

matrix

(A. 13), a n d let

s . We

=

domain

is

DmesG

(A.13)

with

(A 20~)

]

[gJl'"Jmkl"'ks (whose

~nd

(A.19d)

h j .... l j m k .... i ku

product of mudti-indexed matrices

b e given b y

replaced b y

m *s G

jl...jm

c a n write

gkl...k u =

Let

a.

(Jl ..... jm ) c DmA ; (k 1 ..... ks) ~ DSB :. D m A ×

DSB)

is the 'outer' (or lqronecker)

125

product of the matrices

mA

m • s G

if for e a c h

and

mA ®

.

( J l ..... jm ) c D m A

SB

and

(A.2Ob)

sB

( k 1 ..... k s ) ¢ D S B

we have

A g j l . . . J m k l o . . k s = %l...jm b k l * . ) k s

From

(A.20)

(A.20¢)

it f o l l o w s t h a t if

iy

= [yj]

(A.21a)

J CDIY

then m

my=

,~ i y

=[yjl...yjm ]

(A.21b) ( J l .....jm ) E D m y

where

Dmy

= DIy

(A.21C)

×...× D I y m

'Outer'

product of b l o c k ,

multi-indexed

matrices

Let

{M}y = [my]

(A.22~)

m=l,..o)M

where

my

is given

by

(A.21),

and

{M×M} G = [ m ~ u G ]

moreover

m)u=l,.oo)M

let

(A,22b)

126 with

m ~ u G = [gJl°"]mkl"'ku]

We

(Jl ..... jm ) c D m y ; (k 1 ..... ku) ¢ DUy

shall say that the matrix

{MxM} G

if for

{MxM}G

(A.22c)

is the block, outer-product

=

{M}y

(~ { M } y

m@u G

} my

~ Uy

(A.22d)

re,u= 1,...,M

or, equivalently, if for each

gji...Jmkl°..ku

(]i.....Jm ) ¢ D m y

=

(A.22e)

and

yjl..°yjmYkl.--Yku

(k i .....ku) E D u y

(A.22f)

APPENDIX

2

MULTI-VARIATE

INDEX-SET

LB-recursions:

RECURSIONS

'loc~' o r d e r - u p d a t e s

l,-for-vvard index-set, a n d index-sets; i.e., for

for the 'bi-variate' part of the

for the 'uni-va~iate' part of the B - b a c k w a r d

m=2,...,n+l

Lx+l,n-I n,m-I Lx . Lx n,m n,m-I

u

L x + I'n-I n,m-i

=

u LX+l, n-I nsm-2 2 T

(x} k

u {x+n+ 3-re,x+ n + I}

(A.2a~)

Lx n,m-I and

for

m=n+2

LX+l,n n,n+l

Lx . Lx n+l,o n,n+l

L x+l'n U n~ n'~l-- m

f U L x+l'n-I n,n

{x}

• U {x+l,x+n+l}

(A.23b)

Lx

n,n+l

These

recursions

can

b e schematically d e s c r i b e d

a s the L B

index-set

sections

Lx

x

n,m

nmm_ 1

~

LX+l,n-i n,m-i

Ln+ljo

>

Lx

n=m

Lx

~

nln+l

f

LX+l,n n,n+l

Lx

n+ljo

(A.23~)

128 BL-recursions:

'loco/' order-upda£es

for the 'uni-variate' part of the

B-fo~va/~d index-se£s, a n d for the 'bi-varia£e' part of %he L - b a c k w o 2 d index-se~

i.e., for

v=0

n~l L x'O nt2

=

L x'O n~l

u

Lx n,l

.

{x,x} %,....

u Lx U {x+n+l} n,o ~, 2

( A . 2Zia)

LX~ O n,l

a n d for

v=l,...,n

Lx,v-I n,v+ 1 LXt v

n,V+2

= L x'v L x'v-I ~ { x , x + v } n,v+l U n~V+1

u Lx, v-I ntv

u {x+n+1}

(A,2a~b)

T LX, v *%~V+ i

These

recurs[ons will b e in£erpre£ed as the B L

Lx, o n, 2

Lx~° n,l

~I .~

LX, v n,v+ 2

~ r

LX'° n,2

Lx'v n,v+l

'"

Lx n, 1

BB-recursions:

index-set sec%ions

~ "~

"2

(A.2~c)

LX, v 2 n,V+

Lx, v-I rl,v+1

'local'

order-updates

B-foF%va~d a n d B - b a c k w a r d

for

the

Jbi-v~iate

index-sets; i.e., for

v=0

~ parts

and

of

the

m=3,...,n+3

129 LX

n,m-1 Lx. ° _- Lx, ° n,m n,m-I

u

A

f

Lx n,m-I"

{x,x} k

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

u L=,m_ 2 U {x+n+4-m,x+n+l} J

%

(A.25a.)

Lxs O

n,m-i

arld for

v~.l,...,n e ~ n d m m v + 3,...,v+n+ 3

ijxlv'l n,m--i [ L x'v n,m

m

L x'v n,m-I

u L xn ,' vm--12

- { x,x+v}

U

•

u {x + n + 4 + v - m , x + n + 1 }

Y LXl v

n,m-1

These

recursions will result in the B B

index-set sections

L~,o

LXi v r'isi-n

ntm

Lx, O n,m-1

~ ~

(A.e5b)

>

L x'° n,m

Lx ' v n Im - 1

-~ "~ |

Lx n,m-i

Lx,v-I n,m-I

~

Lx'v n~m

(A.25c)

130

'LOCAL' 0 R D E R - U P D A T E

LB-recursions:

for

RECUI~SIONS

m=2,...,n+l

A~,m_z(z) ]

AX, re(Z)

lB~,m(Z)J =

X

n,m

and for

,.

@

x n,,m

(A~,m(Z)

(A.26a) z.Bx+I,n-L(Z) [ n, m-i ~ j

x+i,n-l.

, Z'Bn,m_ l

(Z))Z

(A.26b)

re=n+2

(A. 26C:)

Sn,n+i(z) (A.26d)

x P

BL-recursions-

for

n+l,o

v=O

~"~(~)] . 0~.o XsO = Pn,2

( A X~, , I (O z)

-A::~(=~I

, B~,I(Zl) z

(A.2Va)

(A.27b)

131 for

v=l,...,n

[]:::+~(~1 .o.,v [ n,v+2

px,o ~ n,m

BB-recursions:

for

v=0

(AX, O (Z) n,v+l

and

(A.27c) B x'v-I ( Z ] I n,v+ 1 ~

"J

B x'v-I (Z~) n,v+l ~ " Z

'

(A.27d)

m=3,...,n+3

Ax'O ~ (Z)l n,m-I | =

<::(~)J p~,o . n,m

for

~-- l~...,n

and

n~,m

CAX,O ~

(A.20,,)

0x, °

~:.,,,_l(=)J

~z~

n,m-i ~

B:,~_1(z))

(Ao28b)

Z

" '

re=v+ 3,...,v+n+3

A:::,(~) 0x~v ntm

i

IB ~'v (z' m

n, rn

~,v n,m

'

CA~,V (Z)

"- -n,m-i

(A.28~)

L<: v=.t(~)-'J '

B ~ ' v - I ~z Z,~,

(A.28d)

n,m-i

where

e~n , m

= (i_[o~

n,m

12)-½ -

(A.29a)

x n,m

o~''

nsIT).

= (1-[p

gl~lffl

12) X~g Pn, m

1

(A.29b)

132

'LOCAL' FILTER

SECTIONS

LB-sec[ions: BX n~rn AX ~ n,m-i

+

AX n~m

AM n+l,o

Ax

n,n+l

BX+l,n n,n+l

BX+l,n-1 n~m

for re=n+2

for m-=2,...,n+ 1 BL-s ections:

Bx~v n,v+2

n,2 AX, O

n,l

_

~

A x,o ~ n,2

Ax'v

~

AXsV

n,n+ 1

n,v+

BX,V-I n,V+1

Bx n,1

for v=l,...,n

for v=0 BB-sections: BX~O rl~lll A x'° ~ n,m-i

B x~v nmln

A x'° n,m

~ Bx n,m-I

for v=0

and

m=3,...,n+3

AX'V ~ nsrn-i

AX'V n,m BX,V-i n,m-1

for v=l,..,n and m=v+3,...,v+n+3

2