5. filtre adaptive bazate pe mi imizarea erorii medii ...se obţine viteza de convergenţă maximă...

5. FILTRE ADAPTIVE BAZATE PE MI�IMIZAREA

ERORII MEDII PATRATICE

5. FILTRE ADAPTIVE BAZATE PE MI�IMIZAREA

ERORII MEDII PATRATICE

� funcţia cost este eroarea medie pătratică, J(n) � ecuaţiile Wiener-Hopf nu oferă o soluţie practică

� complexitate aritmetică ridicată � necesită funcţiile de autocorelaţie � se doreşte un algoritm recursiv � se doreşte un algoritm recursiv

Minimizarea unei funcții reale de variabilă complexă

Teoremă

O funcție ��, �∗�: ℂ → ℝ are direcția de variație maximă dată de gradientul complex ∇z∗��, �∗��.

, ,...,

T

z

J J JJ

z z z

∂ ∂ ∂∇ = ∂ ∂ ∂ 0 1 1

, ,...,z

�

Jz z z −

∇ = ∂ ∂ ∂

1 1j , j ,

2 2i

i i i

i i i i i

J J J J J Jz a b

z a b z a b∗

∂ ∂ ∂ ∂ ∂ ∂= − = + = + ∂ ∂ ∂ ∂ ∂ ∂

∇z ��H�� = �∗ ∇z∗��H�� = �

∇z��H �� = � ∇z∗��H�� = �

∇z��H �� = ��∗ ∇z∗��H �� = ��

5.1 Metoda pantei descendente maxime (Steepest Descent - SD)

1. - Se porneşte de la o valoare iniţială a coeficienţilor ( )0w (eventual ( ) 0w =0 ).

2. - Se evaluează direcţia pantei maxime de creştere în jurul acestui punct pe suprafaţa ( )wJ . Aceasta este exprimată prin gradientul complex ( )( )J∗∇

ww .

3. - Se reactualizează coeficienţii printr-o deplasare pe 3. - Se reactualizează coeficienţii printr-o deplasare pe direcţia pantei descendente maxime. Aceasta este echivalent cu o deplasare pe direcţia opusă gradientului cu un pas +∈Rµµ, :

( ) ( ) ( )( )1n n J nµ+ = − ∇w w

4. - Se reia procedeul din punctul 2.

5.1 Metoda pantei descendente maxime (Steepest Descent - SD)

( ) ( ) ( ) ( )[ ]nwnwnwn � 110 ,,, −= ⋯w

( )( ) ( )J n n∗∇ = − +w

p Rw

( ) ( ) ( )( )1n n J nµ+ = − ∇w w ( ) ( ) ( )( )nnn Rwpww −+=+ µ1

5.1 Metoda pantei descendente maxime (Steepest Descent - SD)Analiza stabilităţii algoritmului

Vom introduce vectorul eroare a coeficienţilor,

( ) ( ) pRwwwc =−= oonn ,

( ) ( ) ( )( )nnn Rwpww −+=+ µ1 ( ) ( ) ( )nn cRIc µ−=+1 ( ) ( ) ( )( )nnn Rwpww −+=+ µ1 ( ) ( ) ( )nn cRIc µ−=+1

( ) ( ) ( )nn H cQΛQIc µ−=+1


( ) ( ) ( )nn H cQΛQIc µ−=+1

( ) ( ) ( )nn HH cQΛIcQ µ−=+1

Vom introduce vectorul eroare rotit, v(n),

( ) ( ) ( )( )oHH nnn wwQcQv −==

( ) ( ) ( )nn HH cQΛIcQ µ−=+1 ( ) ( ) ( )nn vΛIv µ−=+1


Condiţii iniţiale:

( ) ( )( )oH wwQv −= 00

( ) ( ) ( ) �knvnv kkk ,,2,1,11 ⋯=−=+ µλ

( ) ( ) ( )01 kn

kk vnv µλ−= Stabilitatea schemei, deci convergenţa algoritmului impune ca v (n) să tindă la 0 când . Pentru aceasta este necesar şi vk(n) să tindă la 0 când ∞→n . Pentru aceasta este necesar şi suficient ca:

�kk ⋯,2,1,2

0sau11k

=<<<−λ

µµλ

max

20

λµ <<

max

20

λµ <<

5.1 Metoda pantei descendente maxime (Steepest Descent - SD)Analiza convergenţei

⇒∈ +Rkλ vk(n) va descreşte către 0 fără oscilaţii. Distingem cazurile:

a) ( )nvkk

k ⇒<<<<λ

µµλ1

0sau10 descresc uniform

( )nvk( )nvk

( )0kv ( )0kv

n n

( ) ( )( )k

kkn

k vnv k

µλττ

−−== −

1ln

1,0e /


b)

kkk λ

µλ

µλ21

011 <<<−<− sau - şir alternat

( ) ( ) ( )( )1ln

1,01e /

−−=−= −

kkk

nnk vnv k

µλττ

( )nvk( )nvk

( )0v ( )0v( )0kv ( )0kv

n n


c) ( ) 1,001 ≥=⇒=− nnvkkµλ

( ) ( )

( )

/e 0 ,

1, sgn 1

ln 1

kn n

k k k

k k k

k

v n s v

s

τ

τ µλµλ

−=

= − = −−

Coeficienţii wk(n) se pot exprima sub forma

( ) ( ) ( )

( ) ( )( )( ) ( )( )∑∑

∑

=

−

=

=

+=−+=

+=+=

�

k

nnkkikoi

�

k

nkkikoii

�

kkkoo

ksvqwvqwnw

nvnn

11

1

e010 τµλ

qwQvww


( ) ( ) ( )

( ) ( )( )( ) ( )( )∑∑

∑

=

−

=

=

+=−+=

+=+=

�

k

nnkkikoi

�

k

nkkikoii

�

kkkoo

ksvqwvqwnw

nvnn

11

1

e010 τµλ

qwQvww

� Convergenţa coeficienţilor are loc după o sumă ponderată de exponenţiale. � Se obţine viteza de convergenţă maximă atunci când qikvk[0]

sunt nuli, pentru toţi k, exceptând valoarea corespunzătoare lui λMax. � Dacă nu sunt precizate condiţiile iniţiale, în cazul cel mai

defavorabil, viteza de convergenţă este determinată de minλ .


10,1

max<<= rr

λµ

( ) ( )∑=

−+=

�

k

nk

kikoii rvqwnw

1 max10

λλ

∑=

k 1 maxλ

Termenul cel mai lent descrescător este acela care conţine factorul

n

r

−

max

min1λλ

R rău condiţionată (raport λMax/λmin mare) ⇒ convergenţă lentă.

5.1 Metoda pantei descendente maxime (Steepest Descent - SD)Curba de învăţare

( ) ( ){ }( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )nnnennnnndnnndne

nenJ

Ho

HHo

H xcxcxwxw −=−−=−=

= 2E

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )nnnennnnndnnndne oo xcxcxwxw −=−−=−=

( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ){ } ( ) ( ){ }

( ) ( ) ( ){ } ( ) ( ) ( ){ } ( ) ( ) ( ) ( ){ }nnnnnennnnne

nenennnennnenJ

HHo

HHo

ooH

oH

o

cxxcxccx

cxxc

EEE

EE

+−−

−=−−=∗

∗∗

c[n] este determinist, eo satisface principiul ortogonalităţii ⇒

( ) ( ) ( )nnJnJ H Rcc+= min


( ) ( ) ( )nnJnJ H Rcc+= min

sau

( ) ( ) ( ) ( ) ( )nnJnnJnJ HHH ΛvvcQΛQc +=+= minmin sau scalar:

��

( ) ( ) ( ) ( )

( )∑

∑∑

=

−

==

+=

=−+=+=

�

kk

nk

�

kk

nkk

�

kkk

vJ

vJnvJnJ

k

1

22min

1

22min

1

2min

0e

01

τλ

µλλλ

Curba obţinută reprezentând J(n) este curba de învăţare a algoritmului. Indiferent de condiţiile iniţiale vk(0), eroarea medie pătratică tinde către Jmin dacă este îndeplinită condiţia de stabilitate.


( ) ( ) ( )nvnvJnJ� 222

211min2 λλ +=−⇒=

Intersecţiile cu plane J=const sunt elipse cu semiaxele

( ) ( ) 21

2

min21

1

min ,

−=

−=

λλJnJ

bJnJ

a

5.2 Algoritmul gradientului stohastic

(LMS)

În cazul metodei SD ajustarea coeficienţilor se face pe baza gradientului erorii medii pătratice:

( )( ) ( ) ( ) ( ){ } ( ) ( ){ }; E ; EHJ n n n n n d n

∗∇ = − + = =p Rw R x x p x

Mediile statistice în general nu sunt însă cunoscute. Se recurge la o estimare a gradientului utilizând nişte valori estimate pentru cele două matrice renunţând la operaţiile de mediere statistică: la operaţiile de mediere statistică:

( ) ( ) ( ) ( ) ( ) ( )ndnnnnn H ∗== xpxxR ˆ;ˆ

( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )ˆ HJ n n d n n n n n e n∗ ∗∇ = − + = −x x x w x

( ) ( ) ( ) ( ) ( ) ( )( )( ) ( ) ( ) ( )nennn

nnndnnn H

∗

∗

+=+

−+=+

xww

wxxww

µµ

1

1


(LMS)

x(n) xH (n)( )nd∗

( ) ( ) ( ) ( ) ( ) ( )( )( ) ( ) ( ) ( )nennn

nnndnnn H

∗

∗

+=+

−+=+

xww

wxxww

µµ

1

1

w(n)w(n+1)

( )ne∗

µ

1−z


(LMS)

( ) 0w =0

⋯,2,1,0for =n

( ) ( ) ( )nnny H xw= ( ) ( ) ( )nyndne −= ( ) ( ) ( )nyndne −=

( ) ( ) ( ) ( )nennn ∗+=+ xww µ1 end


(LMS)

Observaţii

- Complexitate aritmetică: 2N+1 înmulţiri şi 2N adunări pentru fiecare iteraţie - Având în vedere criteriul de optimizare se întâlneşte în limba engleză sub denumirea Least Mean Square (LMS). limba engleză sub denumirea Least Mean Square (LMS). - Fiind calculat de fiecare dată utilizând setul de eşantioane x[n], ce au un caracter aleator, fără a efectua o mediere, gradientul estimat va avea de asemenea un caracter aleator.

- Înmulţirile cu x[n] din schema algoritmului dau acestuia un caracter neliniar


(LMS)

Analiza convergenţei Probleme de convergenţă - Tinde valoarea medie a vectorului w(n) către wo atunci când

∞→n ? În caz afirmativ, se zice că algoritmul este convergent în

medie. medie. - Tinde J(n) către o valoare finită atunci când ∞→n ? In caz afirmativ se spune că algoritmul este convergent în medie

pătratică.


(LMS)

Ipoteze de independenţă: - ( ) ( ) ( )nxxx ,,2,1 ⋯ sunt statistic independenţi. - x(n) şi d(n) sunt statistic independente faţă de d(1),...,d(n-1).

- vectorul de intrare x(n) şi d(n) formează împreună un set de variabile aleatoare gaussiene.

Datorită lipsei medierii în calculul gradientului apare un zgomot de gradient

( )( ) ( )( ) ( )nnJnJ �+∇=∇̂

( ) ( )( ) ( )( ){ } ( ) ( ) ( ) ( ){ }( )ˆ ˆE En J n J n n e n n e n∗ ∗= ∇ − ∇ = − −� x x

( ){ } 0� =nE


(LMS)

Pe de altă parte, relaţia de reactualizare a coeficienţilor devine ( ) ( ) ( ) ( )( ) ( ) ( )( ) ( )1n n J n n n n nµ µ µ+ = − ∇ + = + − −w w � w p Rw �

( ) ( ) ( )( ) ( )1o o o

n n n nµ µ+ + = + + − − −w c w c p Rw Rc �

( ) ( ) ( ) ( )1n n nµ µ+ = − −c I R c �

( ) ( ) ( ) ( )1 Hn n nµ µ+ = − −v I Λ v Q � ( ) ( ) ( ) ( )1n n nµ µ+ = − −v I Λ v Q �

( ){ } ( ) ( ){ }nn vΛIv E1E µ−=+


(LMS)

Având în vedere analogia formală dintre această ecuaţie şi cea corespunzătoare în cazul algoritmului SD, concluziile trase acolo pentru vectorul eroare a coeficienţilor se pot transpune aici pentru media acestui vector. Algoritmul LMS este convergent în medie dacă:

max

20

λµ <<

wk(0) wk(n)

w0

n


(LMS)

Analiza convergenţei în medie pătratică

( ) ( ) ( ) ( ) ( ){ }nnnnJnJ HH cxxcEmin +=

( ) ( ) ( ) ( ){ } ( ) ( ) ( ) ( ){ }{ } ( ) ( ) ( ) ( ){ }{ }( ) ( ){ } ( ) ( ){ }{ } ( ){ }nnnnn

nnnnnnnnnnnn

HH

HHHHHH

RCccxx

ccxxcxxccxxc

trEEtr

trEtrEE

==

===

( ) ( ){ } ( ) ( ){ }{ } ( ){ }nnnnn RCccxx trEEtr ==

( ) ( ) ( ){ }nnn HccC E= ( ) ( ){ } ( )nJJnJnJ ex+=+= minmin tr RC


(LMS)

( ) ( ){ } ( )nJJnJnJ ex+=+= minmin tr RC

unde Jex(n) reprezintă o eroare în exces.

( ) ( ){ } ( ){ } ( ){ }nJnJnJnJ HH KΛQCQΛCQΛQ trtrtr minminmin +=+=+= unde

( ) ( ) ( ){ } ( )QCQvvK nnnn HH == E ( ) ( ) ( ){ } ( )QCQvvK nnnn HH == E

( ) ( )∑=

=�

iiiiex nknJ

1

λ

În raport cu filtrul optimal, apare deci o eroare medie pătratică suplimentară, sau în exces, notată cu Jex, ce poate fi pusă pe seama zgomotului de gradient. Pentru evaluarea sa sunt necesari termenii de pe diagonala principală a matricei K(n).


(LMS)

( ) ( ) ( )nJJnJ trexex +∞=

Comp. staţionară Comp.tranzitorie

Comp. staţionară Comp.tranzitorie

( )∑

∑

=

=

−−

−=∞

�

i i

i

�

i i

i

ex JJ

1

1min

21

2

µλµλ

µλµλ


(LMS)

Se defineşte dezadaptarea (misadjustment) prin

( )

∑

∑

=

=

−−

−=

∞=

�

i i

i

�

i i

i

ex

J

JM

1

1

min

21

2

µλµλ

µλµλ

= −i i12 µλ

Pentru max

2

λµ <<

( ) ∑∑==

===≅�

ii

�

ii

�

�r

�M

1medmed

1

1unde,

20

22λλλ

µµλ

µ


(LMS)

Are în general o tendinţă de scădere cu micşorarea pasului µ , de creştere cu ordinul filtrului N, şi e proporţional cu puterea medie a semnalului de intrare. Componenta tranzitorie ( ) 0trJ n → când ∞→n dacă

12

20

max<

−∩<< ∑

=

�

i

i

µλµλ

λµ

21max −∑=i iµλλ

Dacă 10 <<< µ ambele condiţii sunt îndeplinite dacă

∑=

<<�

jj

1

20

λ

µ


(LMS)

( ) ( ) ( ) ( ){ } 1,,1,0,E0,01

−==−−== ∗

=∑ �kPknxknxr�r x

�

jj ⋯λ

Px reprezintă puterea secvenţei ( ),nx deci o formă simplificată a condiţiei de convergenţă este:

xx

P�

M�P 2

;2

0µ

µ =<<

Se poate introduce o constantă de timp medie:

medmed 2

1

µλτ =

care caracterizează viteza de scădere a părţii tranzitorii a erorii. Se constată că dacă µ este mic, constanta de timp e mare, conducând la o

adaptare lentă, dar dezadaptarea este mică.

x

Exemplu – efectul valorii pasului µ

0.3

0.35

0.4

0.45

0.5

Identificare de sistem-curba de invatare

min=0,3

miu=0,03

0 500 1000 1500 2000 2500 3000 3500 40000

0.05

0.1

0.15

0.2

0.25

0.3

5.3. Metoda gradientului stohastic normalizat

(Metoda normalizată a minimizării erorii medii pătratice -

�LMS)

Poate fi privită ca o problemă de optimizare cu constrângeri. Ne propunem să determinăm noile valori w(n+1) ale coeficienţilor astfel încât să se minimizeze norma euclidiană a variaţiei:

( ) ( ) ( )nnn www −+=+ 11δ cu condiţia ca:

( ) ( ) ( )ndnnH =+ xw 1 (1)( ) ( ) ( )ndnnH =+ xw 1 (1)deci noii coeficienţi să aibă acele valori care, cu un tact mai înainte, ar fi anulat eroarea. Vom constitui funcţia cost reală:

( ) ( ) ( ) ( ) ( )[ ]{ }ndnnnnJ H −+++= xww 1Re1 2 λδ

care îşi atinge minimul odată cu ( )1+nwδ dacă este îndeplinită condiţia (1)



�LMS)

( ) ( ) ( )( ) ( ) ( )( )( ) ( ) ( )( ) ( ) ( ) ( )( )[ ]

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( )( )ndndnnnn

nnnnnnnn

ndnnndnn

nnnnnJ

HH

HHHH

HH

HH

∗∗∗

∗∗

+−++++

+++−+−++=

=−++−++

+−+−+=

λλλλ

λλ

111

11111

112

111

wxxw

wwwwwwww

wxxw

wwww

( ) ( ) ( ) ( )( ) ( ) ( )( )ndndnnnn HH ∗∗∗ +−++++ λλλλ2

111

2

1wxxw



�LMS)

Pentru a găsi vectorul w(n+1) ce minimizează această expresie vom aplica metoda gradientului complex.

( ) ( ) ( )( ) ( )

( ) ( ) ( ) ( ) ( )( ) ( )1

1

1 1 1

1 1

H

n

H H

n

n n n

n n n n n

∗

∗

+

+

∇ + + = +

∇ + + + =

w

w

w w w

w w w w w ( ) ( ) ( ) ( ) ( )( ) ( )

( ) ( ) ( ) ( ) ( )( ) ( )1

1

1 1

1 1

n

H H

n

n n n n n

n n n n nλ λ λ

∗

∗

+

∗

+

∇ + + + =

∇ + + + =

w

w

w w w w w

w x x w x

Rezultă:

( ) ( )1

1n

n∗ +∇ = +

ww - ( )nw + ( )1

2nλx

( ) ( ) ( ) ( )1

11

2nn n nλ∗ +

∇ = ⇒ + − = −w

0 w w x



�LMS)

λ se obţine punând condiţia

( ) ( ) ( )ndnnH =+ xw 1 Pentru aceasta se înmulţeşte la stânga cu xH(n) relaţia:

( ) ( ) ( )nnn xww λ2

11 −=−+

( ) ( ) ( ) ( ) ( ) ( ) ( )

( )( ) ( ) ( )( )

( )( )ne

nnnnd

n

nnnnnnn

H

HHH

∗∗ −=−−=

−=−=−+

22

2

222

1

2

11

xwx

x

xxxwxwx

λ

λλ



�LMS)

Noii coeficienţi se vor calcula deci cu formula:

( ) ( )( )

( ) ( )nenn

nn ∗+=+ xx

ww2

11

Se obişnuieşte să se introducă o scalare a pasului cu o constantă µ , deci:

µ( ) ( )( )

( ) ( )nenn

nn ∗+=+ xx

ww2

1µ

Poate fi echivalat cu algoritmul gradientului stohastic pentru:

( )( ) 2n

nx

µµ =

în care pasul este variabil. Convergenţa în medie pătratică este asigurată dacă:

20 << µ



�LMS)

Evită prin normare amplificarea zgomotului gradientului, în expresia coeficienţilor w(n+1). Apar în plus un număr de � înmulţiri şi �-1 adunări la calculul fiecărui coeficient, ca

urmare a necesităţii evaluării lui ( ) 2nx . Eventual

( ) ( ) ( ) ( ) ( ) 2221

22 1 �nxnxnxknxnx�

−−+−=−= ∑−

( ) ( ) ( ) ( ) ( ) 222

0

22 1 �nxnxnxknxnx

k

−−+−=−= ∑=

Frecvent

( ) ( )( )

( ) ( ) 0;12

>+

+=+ ∗ anenna

nn xx

wwµ

unde a este o constantă mică, adăugată pentru a evita împărţirea prin zero.

5.4 Metoda gradientului pentru structuri latice (GAL)

Ne punem, pentru început, problema proiectării unui predictor latice adaptiv. Vor trebui deci optimizaţi coeficienţii km iar funcţia cost poate fi definită pornind de la eroarea de predicţie directă, inversă, sau compusă. Să considerăm o celulă m a filtrului şi să determinăm km aşa încât să fie minimizată eroarea medie pătratică de predicţie, în forma compusă,

( ) ( ) ( )

+=22

E nenenJ bm

fmm

z-1

km

*mk

)(1 nef

m−

)(1 nebm−

)(nebm


Abordarea SD. Conform metodei gradientului, va trebui luat km(n+1),

( ) ( ) ( )( )1m m m m m

k n k n J nµ+ = − ∇

Va trebui deci evaluat gradientul complex în raport cu k*m:

( )( ) ( )( ) ( ) ( ) ( )( ){ }( )( ) ( ) ( ) ( )( ){ }

nenenenenJ

bbbb

fmm

fm

fm

fmmmm

∇+∇+

+∇+∇=∇∗∗

∗∗E

( )( ) ( ) ( ) ( )( ){ }nenenene bmm

bm

bm

bmm ∇+∇+ ∗∗E

Vom folosind relaţiile de recurenţă:

( ) ( ) ( )( ) ( ) ( )1

1

11

11

−+=

−+=

−−∗

−−

nenekne

neknene

bm

fmm

bm

bmm

fm

fm (2)

im

rmm kkk j+=


( )( ) ( ) ( )( ) ( )

( )( ) ( ) ( )( )

*1 1 1

1 1

1 1

1 0m

m

f f b b

m m m m m mk

f f b

m m m m mk

e n e n k e n e n

e n e n k e n

∗

∗

∗ ∗ ∗ ∗− − −

− −

∇ = ∇ + − = −

∇ = ∇ + − =

( )( ) ( ) ( )( ) ( )( )( ) ( ) ( )( )

1 1 1

1 1

1

1 0m

m

b f b f

m m m m m mk

b f b

m m m m mk

e n k e n e n e n

e n k e n e n

∗

∗

∗− − −

∗ ∗ ∗− −

∇ = ∇ + − =

∇ = ∇ + − =

( )( ) ( ) ( ) ( ) ( ){ }1 1E 1f b b f

m m m m mJ n e n e n e n e n∗ ∗

− −∇ = − +


Rezultă deci:

( ) ( ) ( ) ( ) ( ) ( ){ }nenenenenknkf

mbm

bm

fmmmm 11 1E1 −

∗∗− +−−=+ µ

sau aplicând (2)

( ) ( ) ( ) ( ){ }( ) ( ){ }

2 2

1 1

1 1

1 1 E 1

2 E 1

b f

m m m m m

f b

m m m

k n k n e n e n

e n e n

µ

µ

− −

∗− −

+ = − − + −

− −

Condiţia de stabilitate este: Condiţia de stabilitate este:

( ) ( ) 11E12

1

2

1 <

+−− −− nenef

mbmmµ

( ) ( ){ }2 2

1 1

20

E 1m

b f

m me n e n

µ− −

< <− +


Abordarea LMS

Cum însă mediile statistice nu sunt în general cunoscute, se preferă de obicei utilizarea gradientului stohastic, renunţând la operaţiile de mediere:

( ) ( ) ( ) ( ) ( ) ( ){ }nenenenenknkf

mbm

bm

fmmmm 11 1E1 −

∗∗− +−−=+ µ

( ) ( ) ( ) ( ) ( ) ( )( )nenenenenknkf

mbm

bm

fmmmm 11 11 −

∗∗− +−−=+ µ


Abordarea %LMS

Se poate utiliza un algoritm normalizat, normând incrementul la energia erorii de predicţie compusă, corespunzătoare intrărilor celulei m:

( )( )1

m m

m

nW n

µµ µ

−

= =

( ) ( ) ( ){ }2 2

( ) ( ) ( ){ }2 2

1 1 1 1f b

m m mW n E e n e n− − −= + −


Aproximativ

( ) ( ) ( )

( ) ( ) ( ) ( )( )

2 2

1 1 11

2 2

1 1 1

11

11 1 1

nf b

m m m

i

f b

m m m

W n e i e in

n W n e n e nn

− − −=

− − −

+ − =

= − − + + −

∑≃

Uneori se introduce un parametru 0<ß<1, care permite alocarea unor ponderi diferite pentru eşantioanele precedente şi cele actuale:

( ) ( ) ( ) ( ) ( )

−+−+−= −−−−

2

1

2

111 111 nenenWnW bm

fmmm ββ

5.5 Algoritmul LMS pentru structuri latice-scară

Algoritmul GAL permitea obţinerea unui predictor. Pentru a obţine un Filtru adaptivse adaugă o structură în scară.

1k �k 2k

x(n)

)(0 nef

)(0 neb )(1 neb

)(1 nef )(2 ne

f

)(2 neb )(neb�

)(ne f�

)(0 neb )(1 ne )(2 ne )(ne�

( )nh∗0 ( )nh∗1 ( )nh∗2 ( )nh�∗

( )ny


Abordarea SD

Punem condiţia ca ieşirea să estimeze cât mai corect un semnal dorit d(n).

( ) ( ) ( ) ( )( )

( ) ( ) ( ) ( )( )Tb�

bbo

b�

T�

nenenen

nhnhnhn

,,,

,,,

1

10

⋯

⋯

=

=

e

h

( ) ( ) ( ) ( ) ( ) ( )nnndnyndne b�

H eh−=−= Coeficienţii ki se calculează cu algoritmul GAL, iar hi din condiţia minimizării funcţiei cost

( ) ( ){ }2E nenJ =


Conform ecuaţiei Wiener-Hopf, coeficienţii optimi sunt daţi de

edoe rhR = unde

( ) ( ){ } ( ) ( ){ }ndnnn b�ed

bH�

b�e

∗== ereeR E;E În cazul coeficienţilor ki optimi, ieşirile laticei sunt ortogonale, În cazul coeficienţilor ki optimi, ieşirile laticei sunt ortogonale,

( ) ( ){ } ( )

==

≠

=∗lrJne

lr

nene br

br

bl

br ,E

,0E 2

{ }b�

bbe JJJ ,,,diag 10 ⋯=R

( ) ( ){ }ndneJ

h bkb

k

ko∗= E

1,


Pentru un algoritm recursiv, recurgem la metoda gradientului. În varianta SD: ( ) ( ) ( )1

�n n J nµ+ = − ∇h h

( )( ) ( )� ed eJ n n∇ = − + =r R h

( ) ( ){ } ( ) ( ){ } ( )E Eb b bH

� � �n d n n n n∗= − +e e e h

Abordarea LMS

Cum valorile medii nu sunt în general cunoscute, aplicăm metoda gradientului stohastic (LMS),

( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )ˆ b b bH b

� � � � �J n n d n n n n n e n∗ ∗∇ = − + = −e e e h e

( ) ( ) ( ) ( )nnennb�ehh ∗+=+ µ1


Variantă pentru generarea erorii de estimare.

1k �k 2k

x(n)

)(0 nef

)(0 neb )(1 neb

)(1 nef )(2 ne

f

)(2 neb )(neb�

)(ne f�

Avantaj: convergenţă mai rapidă, datorită decorelării datelor, de către structura latice. Dezavantaj: complexitate aritmetică mai ridicată

)(0 neb )(1 neb

)(2 neb )(neb�

( )nh∗− 0 ( )nh∗− 1 ( )nh∗− 2 ( )nh�∗−

( )ne

d (n)

5. filtre adaptive bazate pe mi imizarea erorii medii ...se obţine viteza de convergenţă maximă...

Documents