Processamento Estatístico de Sinais - O erro quadrático médio em excesso do algoritmo LMS - Prof. Magno - POLI-USP - Engenharia Elétrica

Prévia do material em texto

PSI-2533 Modelagem em Processamento de Sinais
15/10/2012 - Magno T. M. Silva
O erro quadra´tico me´dio em excesso do algoritmo LMS
1 Introduc¸a˜o
Uma expressa˜o anal´ıtica que preveˆ o desempenho na me´dia quadra´tica do algoritmo LMS (least-mean
squares) facilita sua comparac¸a˜o com outros algoritmos adaptativos e da´ informac¸a˜o sobre estabilidade,
taxa de convergeˆncia, erro quadra´tico me´dio etc. Como o algoritmo LMS e´ obtido a partir de uma
aproximac¸a˜o instantaˆnea do gradiente da func¸a˜o custo do erro quadra´tico me´dio, seu desempenho sofre
uma degradac¸a˜o em comparac¸a˜o ao algoritmo do gradiente exato (steepest descent). Por isso, uma ana´lise
estat´ıstica e´ importante para medir a degradac¸a˜o de desempenho em relac¸a˜o ao algoritmo exato.
Filtros adaptativos constituem sistemas variantes no tempo, estoca´sticos e na˜o-lineares. Consequen-
temente, sua ana´lise estat´ıstica e´ baseada em aproximac¸o˜es de simplificac¸a˜o, tambe´m conhecidas como
hipo´teses simplificadoras. Na maioria dos casos, essas hipo´teses consistem em desprezar a dependeˆncia
entre varia´veis aleato´rias, aproximando o valor esperado do produto de duas varia´veis E{xy} pelo produto
de seus valores esperados, isto e´, E{x}E{y}. No caso do algoritmo LMS, essas aproximac¸o˜es sa˜o boas
para adaptac¸a˜o lenta (µ→ 0).
Para medir o desempenho do algoritmo LMS, a medida mais usada e´ o erro quadra´tico me´dio em
excesso (EMSE - excess mean-square error) em regime (n→∞), definido como a distaˆncia entre o MSE
em regime e o valor mı´nimo da func¸a˜o custo (Jmin = E{e
2
o(n)} = σ
2
o)
EMSE = MSE− Jmin. (1)
O EMSE em regime pode ser calculado como
EMSE , lim
n→∞
E{e2
a
(n)}, (2)
sendo ea(n) o erro a priori, dado por
ea(n) = u
T (n)w˜(n− 1) (3)
em que w˜(n− 1) e´ o vetor de erros dos coeficientes, ou seja,
w˜(n− 1) = wo −w(n− 1). (4)
O EMSE mede quanto JMSE(∞) excede seu valor mı´nimo Jmin devido a` adaptac¸a˜o: se o algoritmo fosse
capaz de encontrar a soluc¸a˜o o´tima wo em cada instante, o EMSE seria zero. Como os coeficientes do
1
LMS nunca sa˜o exatamente iguais aos valores o´timos, o EMSE mede o efeito dessa diferenc¸a na variaˆncia
do erro. Uma outra medida de desempenho, relacionada ao EMSE, e´ chamada de desajuste, definida
como
M ,
EMSE
Jmin
=
EMSE
σ2o
. (5)
A seguir, e´ obtida uma expressa˜o anal´ıtica para o EMSE e o desajuste do algoritmo LMS. Para isso,
necessitamos verificar a relac¸a˜o entre o erro de estimac¸a˜o e(n) = d(n) − y(n) e o erro a priori ea(n).
Usando o modelo de regressa˜o linear para o sinal desejado, ou seja,
d(n) = uT (n)wo + eo(n), (6)
e as definic¸o˜es (4) e (3), chega-se a` seguinte relac¸a˜o
e(n) = d(n)− y(n)
= uT (n)wo + eo(n)− u
T (n)w(n− 1)
= uT (n)w˜(n− 1) + eo(n)
= ea(n) + eo(n). (7)
2 O EMSE e o desajuste em regime do algoritmo LMS
A equac¸a˜o de atualizac¸a˜o do vetor de coeficientes do algoritmo LMS e´ dada por
w(n) = w(n− 1) + µe(n)u(n), (8)
sendo µ o passo de adaptac¸a˜o, e(n) = d(n)− y(n) o erro de estimac¸a˜o e
u(n) = [u(n) u(n− 1) u(n− 2) · · · u(n−M + 1) ]T
o vetor regressor de entrada.
Devemos reescrever (8) em termos do vetor de erro dos coeficientes w˜. Assim, subtraindo ambos os
lados de (8) de wo, obtemos
wo −w(n) = wo −w(n− 1)− µu(n)e(n),
w˜(n) = w˜(n− 1)− µu(n)e(n). (9)
Substituindo e(n) = ea(n) + eo(n) em (9), chega-se a
w˜(n) = w˜(n− 1)− µu(n) [ea(n) + eo(n)] . (10)
Calculando a norma Euclidiana ao quadrado de ambos os lados de (10), obtemos
‖w˜(n)‖2 =‖w˜(n− 1)‖2 + µ2‖u(n)‖2
[
e2
a
(n) + e2o(n) + 2ea(n)eo(n)
]
− 2µu(n)T w˜(n− 1) [ea(n) + eo(n)] . (11)
2
Note que para sinais reais uT (n)w˜(n − 1) = w˜T (n − 1)u(n) = ea(n). Calculando a esperanc¸a de ambos
os lados de (11), obte´m-se
E
{
‖w˜(n)‖2
}
=E
{
‖w˜(n− 1)‖2
}
+ µ2E
{
‖u(n)‖2
[
e2
a
(n) + e2o(n) + 2ea(n)eo(n)
]}
− 2µE {ea(n) [ea(n) + eo(n)]} . (12)
Assumindo que o filtro e´ esta´vel e atinge o regime permanente, temos
lim
n→∞
E
{
‖w˜(n)‖2
}
≈ lim
n→∞
E
{
‖w˜(n− 1)‖2
}
. (13)
Para simplificar (12), assume-se ainda que para n→∞
H1. o erro o´timo eo(n) e´ independente e identicamente distribu´ıdo (iid) e independente de u(n) (na˜o
apenas na˜o-correlacionado como diz o princ´ıpio da ortogonalidade). Assume-se tambe´m que eo(n)
e ea(n) sa˜o independentes e ambos de me´dia nula;
H2. ‖u(n)‖2 e´ independente do erro a priori ea(n).
Usando (13) e as hipo´teses simplificadoras H1 e H2 para n→∞ em (12), chega-se a
µ2E
{
‖u(n)‖2
} [
E{e2
a
(n)}+ σ2o
]
≈ 2µE{e2
a
(n)}. (14)
Notando que E{‖u(n)‖2} = E{u2(n) + u2(n− 1) + · · ·+ u2(n−M +1)} = Mru(0) = Tr(R), obtemos as
seguintes expresso˜es para o EMSE e o desajuste do LMS em regime
EMSE ≈
µσ2oMru(0)
2− µMru(0)
(15)
e
M≈
µMru(0)
2− µMru(0)
(16)
sendo M o nu´mero de coeficientes do filtro adaptativo, ru(0) a autocorrelac¸a˜o em zero do sinal de entrada
u(n) e Tr(R) o trac¸o (soma dos elemento da diagonal principal) da matriz de autocorrelac¸a˜o R.
A partir das expresso˜es (15) e (16), e´ poss´ıvel verificar que o EMSE e o desajuste aumentam com
o passo de adaptac¸a˜o µ e com o nu´mero de coeficientes M do filtro LMS. Portanto, quanto maior a
velocidade de convergeˆncia, maior sera´ o desajuste (e o EMSE) do algoritmo. Consequentemente, deve-
se sempre levar em conta o compromisso entre velocidade de convergeˆncia e desajuste.
Na Figura 1, e´ mostrado o EMSE simulado e estimado pela expressa˜o (15) em func¸a˜o do passo de
adaptac¸a˜o µ do algoritmo LMS com M = 3, considerando a identificac¸a˜o do sistema H(z) = 2+0.5z−1−
1.5z−2. Note que a medida que o passo de adaptac¸a˜o aumenta, o EMSE tambe´m aumenta. Ale´m disso,
o valor do EMSE estimado por (15) e´ menos preciso quanto maior o passo. Na Figura 2, o EMSE e o
MSE do LMS e´ mostrado para quatro passos de adaptac¸a˜o distintos. Note que o MSE oscila em torno de
Jmin e por isso, o EMSE na˜o e´ zero. O LMS com passo µ = 0.0777 fica pro´ximo da divergeˆncia e nessa
situac¸a˜o o resultado (15) na˜o e´ muito preciso.
3
0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08
−40
−38
−36
−34
−32
−30
−28
µ
EM
SE
 (d
B)
Simulaçao
Analise
Figura 1: EMSE em regime teo´rico e simulado em func¸a˜o de µ; identificac¸a˜o do sistema H(z) = 2 +
0.5z−1 − 1.5z−2 com o LMS, M = 3 σ2o = 0.01, u(n) obtido a partir de um sistema autoregressivo de 1.a
ordem com po´lo em 0.2; me´dia de 100 realizac¸o˜es.
0 2000 4000 6000 8000 10000
−50
−40
−30
−20
−10
0
10
µ=0.0141 − 100 realizaçoes − valores em dB
MSE
EMSE − simulaçao
Jmin
EMSE − analise
0 2000 4000 6000 8000 10000
−50
−40
−30
−20
−10
0
10
µ=0.0777 − 100 realizaçoes − valores em dB
0 2000 4000 6000 8000 10000
−50
−40
−30
−20
−10
0
10
µ=0.0071 − 100 realizaçoes − valores em dB
MSE
EMSE − simulaçao
Jmin
EMSE − analise
0 2000 4000 6000 8000 10000
−50
−40
−30
−20
−10
0
10
µ=0.0351 − 100 realizaçoes − valores em dB
MSE
EMSE − simulaçao
Jmin
EMSE − analise
Figura 2: EMSE teo´rico (em regime) e simulado ao longo das iterac¸o˜es para quatro valores diferentes de
µ; identificac¸a˜o do sistema H(z) = 2 + 0.5z−1 − 1.5z−2 com o LMS, M = 3 σ2o = 0.01, u(n) obtido a
partir de um sistema autoregressivo de 1.a ordem com po´lo em 0.2; me´dia de 100 realizac¸o˜es.
Refereˆncias
[1] S. Haykin, Adaptive Filter Theory, 3.ed., New Jersey, Prentice Hall, 1996.
4
[2] A. H. Sayed, Fundamentals of Adaptive Filtering, John Wiley & Sons, NJ, 2003.
[3] V. H. Nascimento, M. T. M. Silva, Adaptive Filters, to appear in E-Reference Signal Processing, R.
Chellapa and S. Theodoridis, editors, Elsevier, 2013.
5