tapds curs 4 filtre adaptive bazate pe minimizarea erorii medii pătratice

4. Filtre adaptive bazate pe

minimizarea erorii medii pătratice

• Introducere

• Metoda pantei descendente maxime

• Algoritmul LMS (Least Mean Square)

• Variante ale algoritmului LMS

• Algoritmul proiecţiilor afine (APA)

Introducere

wo x(n)

d(n)

y(n) e(n) +

Teoria filtrării Wiener optimale:

1o o

Rw p w R p Coeficienţii

optimi

Ecuaţiile

Wiener-Hopf

*E n d np x HE n nR x x

Introducere (continuare)

Limitările filtrării Wiener optimale:

- necesită evaluarea matricei de autocorelaţie R

şi a vectorului de corelaţie p.

- necesită evaluarea matricei inverse R–1.

- nu este adecvată mediilor nestaţionare / variabile în timp.

Soluţia:

- determinarea iterativă a coeficienţilor optimi.

w(0) … w(n) w(n +1) … wo

Introducere (continuare)

wo x(n)

d(n)

y(n) e(n) +

Filtrul Wiener optimal:

Filtru “iterativ” (adaptiv):

w(n) x(n)

d(n)

y(n) e(n) +

Metoda pantei descendente maxime

(Steepest descent)

w(n) x(n)

d(n)

y(n) e(n) +

Ne “deplasăm” pe suprafaţa de cost,

în direcţia inversă pantei maxime de creştere a gradientului,

cu un anumit pas μ.

1n n J ww w

Metoda pantei descendente maxime (continuare)

J w p Rw

1n n J ww w

1n n n w w p Rw

Notaţie: on n c w w vectorul eroare a coeficienţilor

1 o o o on n n w w w w p Rw Rw Rw

1 on n n c c p Rc Rw

1n n c I R c(ecuaţiile Wiener-Hopf)


1n n c I R c

1n n n w w p Rw

Pasul μ poate lua orice valoare?

• Analiza stabilităţii algoritmului

HR QΛQ descompunerea matricei de autocorelaţie

det 0 , 1,2,...,i i N R I

, 1,2,..., 0,Hi i i j ii N i j Rq q q q

!

1 2[ , ,..., ]NQ q q q1 2diag[ , ,..., ]N Λ

matricea vectorilor proprii (! QHQ = I)

matricea valorilor proprii

matrice

unitară


1n n c I R c

HR QΛQ 1 Hn n c I QΛQ c

1H Hn n Q c I Λ Q c

Notaţie: Hn nv Q c vectorul eroare rotit

1n n v I Λ v

Condiţii iniţiale: 0 0 0H Ho v Q c Q w w

1 1 , 1,2,...,k k kv n v n k N

1 0 , 1,2,...,n

k k kv n v k N

1 0 , 1,2,...,n

k k kv n v k N


Convergenţă (stabilitate):

0 1 1, 1,2,...,k knv n k N

0 2, 1,2,...,k k N

max 1 2max , ,..., N

max

20

Condiţia de

stabilitate


• Analiza convergenţei algoritmului

1 0 , 1,2,...,n

k k kv n v k N

/0

1, 1,2,...,

ln 1

knk k

kk

v n e v

k N

H Hon n n v Q c Q w w on n w w Qv

/

1 1

0k

N Nn

o k k o k kk k

n v n e v

w w q w q


/

1

0k

Nn

o k kk

n e v

w w q0 | n → ∞

1, 1,2,...,

ln 1k

k

k N

!

1,2,...,max min

1 1

ln 1 ln 1k k N

“rapid” “lent”


max

, 0 2

"lent"min

max

1 1

ln 1 ln 1

R

Numărul condiţional

al matricei R max

min

R

Matrice “rău” condiţionată max min

! convergenţă lentă


• Curba de “învăţare” (learning curve) a algoritmului

on n c w w

H H Hoe n d n n n d n n n n n w x w x c x

Hoe n n n c x

2?J n E e n

eroarea filtrului optim

2 *J n E e n E e n e n

*H Ho oE e n n n e n n n

c x x c


*

*

Ho o o

H H Ho

J n E e n e n E e n n n

E n n e n E n n n n

x c

c x c x x cJmin

= 0 (principiul ortogonalităţii)

R

minHJ n J n n c Rc

minH HJ n n c QΛQ c

minHJ n n v Λv


minHJ n J n n v Λv

2

min1

N

k kk

J v n

22

min1

1 0N

nk k k

k

J v

minnJ n J

în condiţii de stabilitate

22 /

min1

0k

Nn

k kk

J e v


• Aplicaţie

Se cunosc:

- lungimea filtrului N = 2

- valorile iniţiale ale coeficientilor

- matricea de autocorelaţie a semnalului de intrare

- vectorul de corelaţie

1,1 0,5

0,5 1,1

R

0,5272

0,4458

p

1

01

w

Măsura performanţei:

210

2

20logo

o

nw w

w- dezalinierea (misalignment) normată = [dB]


• Aplicaţie (continuare)

1o o

Rw p w R p Coeficienţii

optimi

Ecuaţiile

Wiener-Hopf

10

1

1,1 0,5 0,5272 0,8363

0,5 1,1 0,4458 0,7854

oo

o

w

w

w

max

20

Condiţia de

stabilitate

Algoritmul

steepest descent

1 2det 0 0,6 1,6 1,25 R I



1n n n w w p Rw

Algoritmul steepest descent

Iniţializare: w(0)

For n = 0, 1, 2, …, nr_iteraţii

end

Date: R, p, μ



Cod MATLAB:

R=[1.1 0.5;0.5 1.1];

p=[0.5272;-0.4458];

wo=[0.8363;-0.7854];

w=[-1;-1];

mu=0.01;

W=w;

for n=1:1000

w=w+mu*(p-R*w);

W=[W w];

m(n)=20*log10(norm(wo-w)/norm(wo));

end


• Aplicaţie (continuare) μ = 0.01

-1.5 -1 -0.5 0 0.5 1 1.5-1.5

-1

-0.5

0

0.5

1

1.5

h0

h1

0 100 200 300 400 500 600 700 800 900 1000-60

-50

-40

-30

-20

-10

0

10

Iteratii

mis

alig

nm

ent

[dB

]

w0

w1

-1.5 -1 -0.5 0 0.5 1 1.5-1.5

-1

-0.5

0

0.5

1

1.5

h0

h1

0 100 200 300 400 500 600 700 800 900 1000-100

-90

-80

-70

-60

-50

-40

-30

-20

-10

0

Iteratii

mis

alig

nm

ent

[dB

]


• Aplicaţie (continuare) μ = 1

w0

w1


• Aplicaţie (continuare) μ = 1.3 (! μ < 1.25)

-1.5 -1 -0.5 0 0.5 1 1.5-1.5

-1

-0.5

0

0.5

1

1.5

h0

h1

0 100 200 300 400 500 600 700 800 900 10000

100

200

300

400

500

600

700

Iteratii

mis

alig

nm

ent

[dB

]

w0

w1


• Aplicaţie (continuare) μ = 0.001

-1.5 -1 -0.5 0 0.5 1 1.5-1.5

-1

-0.5

0

0.5

1

1.5

h0

h1

0 100 200 300 400 500 600 700 800 900 1000-5

-4

-3

-2

-1

0

1

2

3

4

5

Iteratii

mis

alig

nm

ent

[dB

]

w0

w1

Algoritmul LMS (Least Mean Square)

Metoda steepest descent :

- necesită cunoaşterea matricei de autocorelaţie R

şi a vectorului de corelaţie p.

- nu necesită evaluarea matricei inverse R–1.

Soluţia:

- permite determinarea iterativă a coeficienţilor optimi.

- estimarea matricei de autocorelaţie R şi a

vectorului de corelaţie p.

Algoritmul LMS (Least Mean Square) (continuare)

1n n n w w p Rw

Metoda steepest descent :

* *ˆE n d n n d n p x p x

ˆH HE n n n n R x x R x x

Cea mai simplă metodă de estimare:

*1 Hn n n d n n n n

w w x x x w

* Hn n d n n n

w x x w

e*(n)


Algoritmul LMS:

*1n n n e n w w x

w(n) x(n)

d(n)

y(n) e(n) +

LMS

Filtru

adaptiv

Algoritm

adaptiv


Algoritmul LMS

Iniţializare: w(0) = 0N x 1


end

Date: μ

*1n n n e n w w x

e n d n y n

Hy n n n w x N x , N – 1 +

1 +

N + 1 x , N +

2N + 1 x , 2N +


• Analiza convergenţei algoritmului LMS

Criteriul 1 Convergenţa în medie

onE n

w w

constantn

J n J

Criteriul 2 Convergenţa în medie pătratică


• Convergenţa în medie a algoritmului LMS

*1n n n e n w w x

* Hn n d n n n

w x x w

*Hn n n n d n I x x w x

1E n E n w I R w p

on n c w w

1E n E n c I R c


1E n E n c I R c

HR QΛQ

Hn nv Q c

1 0 , 1,2,...,n

k k kE v n E v k N

0 1 1, 1,2,...,knE n k N

v

Condiţia de convergenţă în medie

max

20

on

E n

w w

1E n E n v I Λ v


• Convergenţa în medie pătratică a algoritmului LMS

constantn

J n J

He n d n n n w x

H H Ho od n n n n

w x w w x

Hoe n n n c x

*1n n n e n w w x

* Hon n e n n n

w x x c


*1 Hon n n e n n n n w w x x x c

*1 Hon n n e n n n n c c x x x c

– wo – wo

*Hon n n n e n

I x x c x

1 1 1Hn E n n K c c

2minn J I R K I R R

Notaţii: Hn E n nK c c matricea de autocorelaţie

a vectorului c(n)

*min o oJ E e n e n varianţa erorii minime


2 *J n E e n E e n e n

*H Ho oE e n n n e n n n

c x x c

minH HJ E n n n n c x x c

min exJ J n eroarea în exces

exH HJ n E n n n n c x x c Pp. x(n) – secvenţă aleatoare

gaussiană

ex tr H HJ n E n n n n c x x c tr urma unei matrice

= Σ valorilor proprii

tr tr 0H HE n n E n n n x x c c RK


ex trJ n n RK

HR QΛQ tr trH n n ΛQ K Q ΛZ

2min1n n J K I R K I R R

ex ,1

N

l l ll

J n z n

QH· QH· ·Q ·Q

2min1n n J Z I Λ Z I Λ Λ

2 2

, , min1 1 , 1,2,...,l l l l l lz n z n J l N

elementele diagonalei matricei Z(n)

convergentă dacă 1 1, 1,2,...,l l N

ex tr HJ n n QΛQ K

max

20

Condiţia de convergenţă

în medie pătratică

2 2

, , min1 1 , 1,2,...,l l l l l lz n z n J l N


n → ∞ 2 2

, , min1l l l l l lz z J

min, , 1,2,...,

2l l

l

Jz l N

ex , min1 1 2

N Nl

l l lll l

J z J

min exnJ n J J J

min1

1 constant2

Nl

ll

J


• Criterii pentru alegerea pasului algoritmului LMS

max

20

?! λmax – dificil de determinat în practică

max1

trN

ll

R

2tr 0xx xNr N R

2

20

xN

Dezadaptarea (misadjustment): ex

min 1 2

Nl

ll

Jm

J

Dacă μ << 1/λmax

2

12 2

N

l xl

m N


• Performanţele algoritmului LMS depind de:

- Pasul de adaptare μ

(compromis între viteza de convergenţă şi dezadaptare:

pas mare convergenţă rapidă dar dezadaptare mare;

pas mic dezadaptare scăzută dar convergenţă lentă.)

- Valorile proprii ale matricei de autocorelaţie a

semnalului de intrare

(matrice rău condiţionată convergenţă lentă)

- Lungimea filtrului adaptiv N

(lungime mare convergenţă lentă, dezadaptare mare)


• Aplicaţie

Identificare de sistem

Sistem

necunoscut

Filtru

adaptiv

x(n)

y(n)

d(n)

e(n)

+

v(n) zgomot


Semnalul de intrare x(n)

zgomot alb gaussian [randn]

semnal AR(1) (autoregresiv de ordinul 1)

x(n) = ax(n – 1) + g(n)

[x = filter(1,[1, -a],g)]

Sistemul necunoscut

Zgomotul v(n) zgomot alb gaussian [randn], σv2 = 0.001.

zg. alb gauss.


N = 64

0 10 20 30 40 50 60-0.1

-0.05

0

0.05

0.1

0.15

0.2

0.25

Esantioane

N = 128

0 20 40 60 80 100 120-0.06

-0.04

-0.02

0

0.02

0.04

0.06

Esantioane

căi de ecou electric

(ITU-T G168)



Funcţie MATLAB pentru algoritmul LMS:

function [m]=lms(x,d,mu,N,wo);

L=length(x);

xf=zeros(N,1);

w=zeros(N,1);

m=zeros(L,1);

for n=1:L

xf=[x(n);xf(1:N-1)];

y=w'*xf;

e=d(n)-y;

w=w+mu*xf*e';


end


0 500 1000 1500 2000 2500 3000-30

-25

-20

-15

-10

-5

0

5

10

15

Iteratii

Misa

lignm

ent [

dB]

= 0.005

= 0.01

= 0.015

= 0.03

N = 64 x(n) - randn • Aplicaţie (continuare)

2

20.0312

xN


0 500 1000 1500 2000 2500 3000-20

-15

-10

-5

0

5

10

15

Iteratii

Misa

lignm

ent [

dB]

= 0.005

= 0.01

= 0.015


2

20.0156

xN


N = 64 x(n) - AR(1), a = 0,6 • Aplicaţie (continuare)

0 500 1000 1500 2000 2500 3000-30

-25

-20

-15

-10

-5

0

5

10

15

Iteratii

Misa

lignm

ent [

dB]

= 0.005

= 0.01

= 0.0152

20.0186

xN



0 500 1000 1500 2000 2500 3000-30

-25

-20

-15

-10

-5

0

5

10

15

Iteratii

Misa

lignm

ent [

dB]

= 0.005

= 0.01

= 0.015

2

20.0077

xN

Variante ale algoritmului LMS

• Algoritmul NLMS (Normalized LMS)

Algoritmul LMS: *1n n n e n w w x

Avantaj: simplitate / complexitate redusă

Problema: alegerea pasului algoritmului

μ = constant = ?

Soluţia: alegerea unui pas “variabil” μ(n)

Variante ale algoritmului LMS (continuare)

*1n n n e nn w w x

He n d n n n w x

1Hn d n n n w x

eroarea a priori

eroarea a posteriori

Scopul: ε(n) = 0

H Hn d n n n n e n n w x x

H Hd n n n n n n e n w x x x

1 Hn n n e n

x x

1Hd n n n w x


[ e(n) ≠ 0 ] 1 0Hn n n e nn

x x

1

Hn

n n

x x

1

2 2

20

2 pentru 1

NH

k

x

n n x n k n

N N

x x x

μ(n) depinde de “puterea” semnalului de intrare


Consideraţii practice:

H

nn n

x xPasul algoritmului NLMS

η – pasul normalizat

realizează “compromisul”

între viteza de convergenţă

şi dezadaptare

δ – parametrul de regularizare

evită împărţirea prin numere mici

în situaţia când xH(n)x(n) ≈ 0

Se poate calcula recursiv:

2 2

1 1H Hn n n n x n x n N x x x x

1.

2.

1 x , 2 + N x , N – 1 +

Stabilitatea algoritmului NLMS


1 Hn n n n e n

x x

H

nn n

x x(Pp. δ = 0)

1n e n

Condiţia de stabilitate: n e n 1 1

0 2 Parametrul de regularizare δ > 0 nu influenţează stabilitatea algoritmului

Algoritmul NLMS



end

Date: 0 < η < 2 , δ > 0

*1n n n n e n w w x

e n d n y n

Hy n n n w x N x , N – 1 +

1 +

2N + 2 x , 2N + 3 + , 1 /


H

nn n

x x1 x , 3 + , 1 /

N + 1 x , N +


Observaţie:

Algoritmul NLMS poate fi privit ca o problemă de

optimizare cu constrângeri.

Funcţia cost:

2

21 Re 1HJ n n n d n n n

w w w x

constrângerea ε(n) = 0 multiplicator Lagrange

norma variaţiei

coeficienţilor

111HNn

d n n nJ n

w

w x0

Anularea

gradientului:

1

1

11

2n

N

J n n n n

w w w x

0


1

12

n n n w w x

1

12

H H Hn n n n n n x w x w x x

xH(n) · xH(n) ·

d*(n) – d*(n) –

* 10

2

He n n n x x

*2

H

e n

n n

x x

*11

Hn n n e n

n n w w x

x x NLMS


• Aplicaţie


Sistem

necunoscut

Filtru

adaptiv

x(n)

y(n)

d(n)

e(n)

+

v(n) zg. alb gauss. σv2 = 0.001 (ITU-T G168)

N = 64 / N = 128

zg. alb gauss.

[randn]

semnal AR(1) zg. alb gauss.

x(n) = ax(n – 1) + g(n)

css_st – ITU-T G168


0 500 1000 1500 2000 2500 3000

-30

-25

-20

-15

-10

-5

0

5

Iteratii

Misa

lignm

ent [

dB]

= 0.1

= 0.5

= 1

= 1.5

= 2


!



0 500 1000 1500 2000 2500 3000

-30

-25

-20

-15

-10

-5

0

5

Iteratii

Misa

lignm

ent [

dB]

= 0.1

= 0.5

= 1

= 1.5

= 2



0 500 1000 1500 2000 2500 3000-25

-20

-15

-10

-5

0

Misa

lignm

ent [

dB]

Iteratii

LMS - = 0.015

NLMS - = 1



0 500 1000 1500 2000 2500 3000-30

-20

-10

0

10

20

30

40

50

60

Iteratii

Misa

lignm

ent [

dB]

LMS - = 0.015

NLMS - = 1

x(1500)↑


N = 64 x(n) – css_st • Aplicaţie (continuare)

(G168)

0 500 1000 1500 2000 2500 3000-14

-12

-10

-8

-6

-4

-2

0

2

Iteratii

Misa

lignm

ent [

dB]

LMS - = 0.015

NLMS - = 1


• Algoritmul GAL (Gradient Adaptive Lattice)

Algoritmii LMS şi NLMS au la bază o structură

transversală de filtru cu răspuns finit la impuls:

z– 1 z– 1 z– 1

w0 w1 w2

wN–2 wN–1 d(n)

x(n) x(n–2) x(n–1) x(n–N+1) x(n–N+2)

e(n)

+

–


Algoritmul GAL are la bază o structură latice-scară:


Structura celulei latice:

11 1ff b

m m mme n e n k e n

*1 11

fb bm m m me n e n k e n

fme n

“forward”

“backward”


1mm m p kk n k n J n

Funcţia cost: 2 2

f bm mJ n E e n e n

* *1 1... 1

m

ff b bk m m m mJ n E e n e n e n e n

* *1 11 1

ff b bm m p m m m mk n k n e n e n e n e n

(prin renunţarea la medierea statistică)

Abordare

de tip

“normalizat”

2 2 1

111

1 1

1

p nmf b

mmk

nW n

e k e k


2 2

1 111

2 2

1 11

1

1 1

nf b

m mmk

f bm mm

W n e k e k

W n e n e n

Reactualizarea coeficienţilor structurii “scară”:

*1 bNn n n n e n h h e

0 1, , ,T

Nn h n h n h n h

0 1, , ,T

b b b bN Nn e n e n e n

e

! Avantaj GAL:

“decorelarea”

datelor de intrare


Algoritmul GAL


• Aplicaţie

Suprimarea interferenţelor

Filtru

adaptiv z(n)

sursă

zgomot y(n)

d(n)

e(n)

+

z1(n)

z2(n)

u(n)

semnal

util

≈ z2(n)

≈ u(n)

[randn]

[sin]



0 100 200 300 400 500 600 700 800 900 1000-4

-2

0

2

4

0 100 200 300 400 500 600 700 800 900 1000-4

-2

0

2

4

Iteratii

NLMS

GAL

Algoritmul proiecţiilor afine (APA)

- Poate fi interpretat ca o generalizare a algoritmului NLMS.

- Algoritmul NLMS are la bază anularea erorii a posteriori:

1 0Hd n nn n w x

- APA are la bază anularea a p valori ale erorii a posteriori:

p = ordinul de proiecţie

1 011 1 Hd n n nn w x

1 0Hd n nn n w x

11 01 1Hd n nn p np p w x

Algoritmul proiecţiilor afine (APA) (continuare)

Notaţii:

, 1 , , 1T

n e n e n e n p e

, 0,1,..., 1He n k d n k n n k k p w x

p x 1

, 1 , , 1n n n n p X x x x

, 1 , , 1 ,

0,1,..., 1

Tn k x n k x n k x n k N

k p

x

N x p

, 1 , , 1T

n d n d n d n p d p x 1


Funcţia cost:

2 *

21 Re 1H HJ n n n n n n

w w λ d X w

constrângerile (anularea

erorilor a posteriori)

norma variaţiei

coeficienţilor vectorul

multiplicatorilor

Lagrange

0 1 1, , ,T

p λ

*11

1HNnn n n

J n

wd X w

0Anularea

gradientului:


1

1

11

2n

N

J n n n n

w w w X λ

0

1

12

H H Hn n n n n n X w X w X X λ

XH(n) · XH(n) ·

d*(n) – d*(n) –

* 10

2

Hn n n e X X λ

1

*2 H n n n

λ X X e

1

*1 Hn n n n n n

w w X X X e APA

1

12

n n n w w X λ


Consideraţii practice:

1

*1 Hpn n n n n n

w w X I X X e

η – pasul normalizat

realizează “compromisul”

între viteza de convergenţă

şi dezadaptare

δ – parametrul de regularizare

evită situaţia când

det[XH(n)X(n)] ≈ 0

Condiţia de stabilitate: 0 2 (similar NLMS)


APA (Affine Projection Algorithm)



end

Date: 0 < η < 2 , δ > 0, p – ordinul de proiecţie

* * Hn n n n e d X w

1

*1 Hpn n n n n n

w w X I X X e

! Calculul matricei inverse complexitate/stabilitate.

! p = 1 APA este echivalent cu NLMS.


• Aplicaţie


Sistem

necunoscut

Filtru

adaptiv

x(n)

y(n)

d(n)

e(n)

+

v(n) zg. alb gauss. SNR = 20dB (cale ecou acustic)

N = 512

zg. alb gauss.

[randn]

semnal AR(1) zg. alb gauss.

x(n) = ax(n – 1) + g(n)

semnal vocal

0 50 100 150 200 250 300 350 400 450 500-8

-6

-4

-2

0

2

4

6

8

10

12

14x 10

-3

Esantioane


Funcţie MATLAB pentru APA:

function [m]=apa(x,d,eta,delta,p,N,wo);

L=length(x);

w=zeros(N,1);

xf=zeros(N,1);

D=zeros(p,1);

X=zeros(N,p);

m=zeros(L,1);

for n=1:L

xf=[x(n);xf(1:N-1)];

X=[xf,X(:,1:p-1)];

D=[d(n);D(1:p-1)];

E=conj(D)-X'*w;

w=w+eta*X*inv(delta*eye(p)+X'*X)*E;


end


0 2000 4000 6000 8000 10000 12000-30

-25

-20

-15

-10

-5

0

Iteratii

Misa

lignm

ent [

dB]

APA - p = 1 (NLMS)

APA - p = 2

APA - p = 4

APA - p = 8


x(n) - randn • Aplicaţie (continuare) η = 0,2

!

0 2000 4000 6000 8000 10000 12000-30

-25

-20

-15

-10

-5

0

Iteratii

Misa

lignm

ent [

dB]

APA - p = 1 (NLMS)

APA - p = 2

APA - p = 4

APA - p = 8


x(n) - AR(1), a = 0,7 • Aplicaţie (continuare) η = 0,2


x(n) – semnal vocal • Aplicaţie (continuare) η = 0,2

0 0.5 1 1.5 2

x 104

-15

-10

-5

0

Iteratii

Misa

lignm

ent [

dB]

APA - p = 1 (NLMS)

APA - p = 2

APA - p = 4

APA - p = 8


• Aplicaţie (continuare) p = 2

0 2000 4000 6000 8000 10000 12000-30

-25

-20

-15

-10

-5

0

5

Iteratii

Misa

lignm

ent [

dB]

APA - = 0.1

APA - = 0.2

APA - = 1

APA - = 2.1

x(n) - randn

tapds curs 4 filtre adaptive bazate pe minimizarea erorii medii pătratice

Documents