ANALISE DE TRANSIENTE DOS ALGORITMOS ´ ℓ0-SIGN-LMS E ℓ0-SIGN-NLMS

Prévia do material em texto

ANA´LISE DE TRANSIENTE DOS ALGORITMOS ℓ0-SIGN-LMS
E ℓ0-SIGN-NLMS
Leonardo Oliveira dos Santos
Projeto de Graduac¸a˜o apresentado ao Curso
de Engenharia Eletroˆnica e de Computac¸a˜o
da Escola Polite´cnica, Universidade Federal
do Rio de Janeiro, como parte dos requisitos
necessa´rios a` obtenc¸a˜o do t´ıtulo de Enge-
nheiro.
Orientadores: Mariane Rembold Petraglia
Diego Barreto Haddad
Rio de Janeiro, RJ - Brasil
Janeiro de 2017
1
UNIVERSIDADE FEDERAL DO RIO DE JANEIRO
Escola Polite´cnica - Departamento de Eletroˆnica e de Computac¸a˜o
Centro de Tecnologia, bloco H, sala H-217, Cidade Universita´ria
Rio de Janeiro - RJ CEP 21949-900
Este exemplar e´ de propriedade da Universidade Federal do Rio de Janeiro, que
podera´ inclu´ı-lo em base de dados, armazenar em computador, microfilmar ou adotar
qualquer forma de arquivamento.
E´ permitida a menc¸a˜o, reproduc¸a˜o parcial ou integral e a transmissa˜o entre bibli-
otecas deste trabalho, sem modificac¸a˜o de seu texto, em qualquer meio que esteja
ou venha a ser fixado, para pesquisa acadeˆmica, comenta´rios e citac¸o˜es, desde que
sem finalidade comercial e que seja feita a refereˆncia bibliogra´fica completa.
Os conceitos expressos neste trabalho sa˜o de responsabilidade do(s) autor(es).
4
DEDICATO´RIA
Ao meu pai Delcides.
A` minha ma˜e Moˆnica.
Aos meus amigos do Zueira.
5
AGRADECIMENTO
Eu gostaria muito escrever um texto bonito pra mostrar o qua˜o grato eu sou a`s
pessoas que percorreram comigo esse caminho tortuoso ate´ aqui, mas essas mesmas
pessoas sabem que me expressar na˜o e´ uma das minhas qualidades. Enta˜o, eu queria
apenas agredecer a toda minha famı´lia e aos meus amigos Carlos Lordelo, Diego
Freitas, Fa´bio Oliveira, Felipe Feitosa, Felipe Gonza´lez, Felipe Petraglia, Gabriel
Torres, Gustavo Nunes, Henrique Dias, Joa˜o Victor, Ju´lio Vargas, Lucas Oliveira,
Michel Morais.
Gostaria ainda de fazer um agredecimento em especial aos meus orientadores:
prof. Diego Haddad e profa. Mariane Petraglia por todo apoio e disponibilidade.
6
RESUMO
Sistemas esparsos sa˜o comuns nas mais diversas a´reas de aplicac¸a˜o da filtragem
adaptativa, dentre elas controle, engenharia biome´dica e cancelamento de eco. Algo-
ritmos capazes de usar essa propriedade para acelerar a convergeˆncia e/ou melhorar
o erro em regime permanente veˆm ganhando cada vez mais destaque na comunidade
acadeˆmica.
Motivado por essas experieˆncias positivas, este trabalho apresenta uma ana´lise
teo´rica do transiente e do regime permanente dos algoritmos ℓ0-sign-LMS e ℓ0-sign-
NLMS, a qual e´ efetuada atrave´s do ca´lculo recursivo da matriz de autocorrelac¸a˜o dos
desvios. Durante a ana´lise sa˜o assumidas algumas suposic¸o˜es comuns na literatura,
embora tenha sido evitada a hipo´tese muito frequente de que o sinal de entrada
e´ branco. Ao final, sa˜o efetuadas diversas simulac¸o˜es para avaliar o desempenho
do modelo estoca´stico proposto perante simulac¸o˜es computacionais dos algoritmos
adaptativos sob ana´lise.
Palavras-Chave: filtragem adaptativa, ca´lculo recursivo da matriz de autocorrelac¸a˜o
dos desvios, ℓ0-sign-LMS, ℓ0-sign-NLMS, identificac¸a˜o de sistemas esparsos, ana´lise
de transiente.
7
ABSTRACT
Sparse systems are common in the most diverse areas of application of adaptive fil-
tering, including control, biomedical engineering and echo cancellation. Algorithms
able to use this property to accelerate convergence and/or improve steady state error
has been gaining increasing prominence in the academic community.
Motivated by these positive experiences, this work presents a theoretical analy-
sis of the ℓ0-sign-LMS and ℓ0-sign-NLMS algorithms, which is done by calculating
recursively the autocorrelation matrix of the weight vector deviations. During the
analysis some assumptions already present in the literature are assumed, without
the restriction of a white input signal. The derivation of the proposed model is
presented in details. At the end, several simulations are performed to evaluate the
performance of the proposed model compared to the practical realization of the
adaptive filter.
Key-words: Adaptive filtering, recursive autocorrelation matrix calculation, ℓ0-sign-
LMS, ℓ0-sign-NLMS, sparse system identification, transient analysis.
8
Lista de Figuras
2.1 Diagrama de blocos de um algoritmo adaptativo. . . . . . . . . . . . 16
3.1 (a) Valores dos coeficientes do filtro adaptativo w(k) ao longo das
iterac¸o˜es. (b) Fρ[w(k)] para ρ = 2, ρ = 4, ρ = 6 e ρ = 20. . . . . . . . 24
3.2 (a) fρ[wi(k)] quando i = 7 e ρ = 6. (b) fρ[wi(k)] quando i = 3 e ρ = 6. 25
5.1 Desempenho do algoritmo ℓ0-sign-LMS. Emp´ırico (em azul) e teo´rico
(em vermelho). (a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . 40
5.2 Desempenho do algoritmo ℓ0-sign-NLMS. Emp´ırico (em azul) e teo´rico
(em vermelho). (a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . 41
5.3 (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-LMS com β variando.
Emp´ırico (em azul) e teo´rico (em vermelho).(b) Comportamento de
β ao longo das iterac¸o˜es. . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.4 (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-NLMS com β variando.
Emp´ırico (em azul) e teo´rico (em vermelho).(b) Comportamento de
β ao longo das iterac¸o˜es. . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5 (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-LMS com σ2ν variando.
Emp´ırico (em azul) e teo´rico (em vermelho).(b) Comportamento de
σ2ν ao longo das iterac¸o˜es. . . . . . . . . . . . . . . . . . . . . . . . . 44
5.6 (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-NLMS com σ2ν vari-
ando. Emp´ırico (em azul) e teo´rico (em vermelho).(b) Comporta-
mento de σ2ν ao longo das iterac¸o˜es. . . . . . . . . . . . . . . . . . . . 45
5.7 (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-LMS para κ = 10−10, κ =
10−7. Emp´ırico (em azul, com 10000 me´dias de Monte Carlo) e teo´rico
(em vermelho).(b) “Zoom” na regia˜o de interesse demarcada por um
retaˆngulo em (a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
9
5.8 (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-NLMS para κ = 10−10, κ =
10−7. Emp´ırico (em azul, com 2500 me´dias de Monte Carlo) e teo´rico
(em vermelho).(b) “Zoom” na regia˜o de interesse demarcada por um
retaˆngulo em (a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.9 Desempenho do algoritmo ℓ0-sign-LMS em regime permanente para
diferentes valores de β. Emp´ırico (em azul) e teo´rico (em vermelho).
(a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . . . . . . . . . . 48
5.10 Desempenho do algoritmo ℓ0-sign-NLMS em regime permanente para
diferentes valores de β. Emp´ırico (em azul) e teo´rico (em vermelho).
(a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . . . . . . . . . . 49
5.11 Desempenho do algoritmo ℓ0-sign-LMS em regime permanente para
diferentes valores de κ. Emp´ırico (em azul) e teo´rico (em vermelho).
(a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . . . . . . . . . . 50
5.12 Desempenho do algoritmo ℓ0-sign-NLMS em regime permanente para
diferentes valores de κ. Emp´ırico (em azul) e teo´rico (em vermelho).
(a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . . . . . . . . . . 51
5.13 Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-LMS em regime perma-
nente para diferentes valores de ρ e para σ2ν = 10−2, σ2ν = 10−3 e
σ2ν = 10−4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.14 Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-NLMS em regime perma-
nente para diferentes valores de ρ e para σ2ν = 10−2, σ2ν = 10−3 e
σ2ν = 10−4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
10
Suma´rio
1 Introduc¸a˜o13
1.1 Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Conteu´do do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Filtragem Adaptativa 15
2.1 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Algoritmo LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Algoritmo NLMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Algoritmo Sign-error . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Conclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Identificac¸a˜o de Sistemas Esparsos 22
3.1 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 PNLMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 ℓ0-LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 Conclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Ana´lise de transiente 27
4.1 Me´todos de ana´lise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Alguns comenta´rios sobre as hipo´teses . . . . . . . . . . . . . . . . . 28
4.3 Descric¸a˜o dos momentos de primeira e segunda ordens . . . . . . . . 29
4.4 Conclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5 Resultados 39
11
6 Conclusa˜o 54
12
Cap´ıtulo 1
Introduc¸a˜o
1.1 Contexto
Historicamente, a abordagem parame´trica tem sido a abordagem principal
da engenharia para processamento de sinais, sendo baseada em modelos derivados
de conhecimento a priori concernente ao problema em questa˜o. Por outro lado, a
abordagem na˜o-parame´trica e´ baseada no uso de modelos mais gene´ricos, treina-
dos para replicar comportamentos desejados usando informac¸o˜es estat´ısticas de um
agrupamento de dados. Filtros adaptativos sa˜o, na verdade, baseados em uma abor-
dagem situada entre esses dois extremos [1, 2]. Quando o conhecimento pre´vio de
um processo dinaˆmico e de suas estat´ısticas e´ limitado, o concurso de filtros adapta-
tivos pode resultar em uma melhora no desempenho, comparativamente aos filtros
parame´tricos convencionais. Ale´m disso, eles podem oferecer outras vantagens para
o processamento de sinais. Consequentemente, filtros adaptativos esta˜o sendo usa-
dos em diversas aplicac¸o˜es, incluindo comunicac¸o˜es, controle, robo´tica, biome´dica,
entre outros [3, 4, 5]. Motivado por isso, este trabalho propo˜e um estudo sobre o
comportamento desses algoritmos para ajudar o projetista a entender como e´ o pro-
cesso de aprendizagem do filtro de sorte a possibilitar a escolha do algoritmo mais
apropriado (ou de seus paraˆmetros) para o problema em questa˜o.
13
1.2 Objetivo
O objetivo deste trabalho consiste em efetuar uma ana´lise dos algoritmos
ℓ0-sign-LMS e ℓ0-sign-NLMS e, enta˜o, propor um modelo estoca´stico capaz de pre-
ver o comportamento dos algoritmos citados. Desta forma, tem-se como objetivos
espec´ıficos: (1) estimar de modo recursivo a matriz de autocorrelac¸a˜o dos desvios
dos coeficientes; (2) calcular me´tricas de desempenho a cada iterac¸a˜o, no caso, o
erro quadra´tico me´dio (MSE, do ingleˆs: Mean Square Error) e o desvio quadra´tico
me´dio (MSD, do ingleˆs: Mean Square Deviation).
1.3 Metodologia
Este trabalho visa estimar o comportamento me´dio dos algoritmos sob ana´lise.
Para tanto, usa o me´todo do ca´lculo recursivo da matriz de autocorrelac¸a˜o dos des-
vios. Tal te´cnica consiste em determinar equac¸o˜es a diferenc¸as recursivas que con-
sigam prever o comportamento de Rw˜(k) = E[w˜(k)w˜T (k)], onde w˜(k) e´ o vetor
de desvio dos coeficientes adaptativos na k-e´sima iterac¸a˜o. Estimada tal matriz
de autocorrelac¸a˜o para cada iterac¸a˜o, podemos inferir a evoluc¸a˜o das me´tricas de
desempenho MSE e MSD.
1.4 Conteu´do do Trabalho
Este trabalho foi dividido em treˆs partes. Na primeira parte, formada pelos
Cap´ıtulos 1, 2 e 3, e´ feita uma introduc¸a˜o sobre o trabalho e uma revisa˜o sobre
filtragem adaptativa e sistemas esparsos. Na segunda parte, formada pelo Cap´ıtulo
4, e´ feito todo o desenvolvimento do modelo proposto. Ja´ a terceira parte, formada
pelos Cap´ıtulos 5 e 6, apresenta os resultados e a conclusa˜o do trabalho.
14
Cap´ıtulo 2
Filtragem Adaptativa
2.1 Introduc¸a˜o
As te´cnicas de filtragem adaptativa apresentam diversas aplicac¸o˜es, dentre as
quais importa destacar: engenharia biome´dica, equalizac¸a˜o de canais, cancelamento
de eco e identificac¸a˜o de sistemas [6]. Filtros adaptativos apresentam duas grandes
vantagens com relac¸a˜o a filtros com coeficientes fixos. A primeira e´ que, ao contra´rio
de filtros com coeficientes fixos, quando se trabalha com filtros adaptativos na˜o e´
necessa´rio ter conhecimento pre´vio das caracter´ısticas do sinal de entrada, tampouco
do sistema envolvido. A segunda vantagem e´ que os filtros adaptativos podem
ser usados tanto para modelagem ou equalizac¸a˜o de sistemas invariantes no tempo
quanto de sistemas variantes no tempo.
Em um algoritmo de filtragem adaptativa, os coeficientes sa˜o atualizados
recursivamente de maneira que, apo´s um nu´mero suficiente de iterac¸o˜es, o filtro
possua uma estimativa adequada do sistema de refereˆncia. Tal atualizac¸a˜o costuma
ser regida pelo ca´lculo do gradiente de uma func¸a˜o custo estoca´stica, o qual e´ capaz
de fornecer a direc¸a˜o de atualizac¸a˜o engendrada pelo algoritmo adaptativo. Isto se
deve ao fato de que uma estrate´gia muito comum para a identificac¸a˜o adaptativa
de um sistema de refereˆncia consistir na minimizac¸a˜o de uma func¸a˜o custo. Para
isso e´ calculado o gradiente dessa func¸a˜o, ja´ que o gradiente aponta para a direc¸a˜o
de maior crescimento da func¸a˜o, e a atualizac¸a˜o e´ feita no sentido contra´rio ao do
gradiente (pois, afinal, o objetivo consiste em minimizar uma func¸a˜o custo).
A Figura 2.1 mostra a estrutura de um algoritmo adaptativo (aplicado a` iden-
15
x(k)
wo
w(k)
y(k)
−
+
+
d(k)
ν(k)
e(k)
Figura 2.1: Diagrama de blocos de um algoritmo adaptativo.
tificac¸a˜o de sistemas, foco deste projeto), cujos coeficientes do filtro de comprimento
N podem ser coletados no vetor w(k) definido por:
w(k) ,
[
w0(k) w1(k) . . . wN−1(k)
]T
, (2.1)
sendo a sa´ıda do filtro no instante k definida por y(k) , wT (k)x(k), com o vetor de
entrada x(k) descrito por:
x(k) =
[
x(k) x(k − 1) . . . x(k −N + 1)
]T
, (2.2)
onde k representa a k-e´sima iterac¸a˜o. Cabe ressaltar que neste trabalho todos os
vetores envolvidos sa˜o do tipo coluna. Apo´s um nu´mero suficiente de iterac¸o˜es, e´
esperado que y(k) seja similar ao valor de refereˆncia d(k) = (wo)Tx(k)+ν(k), sendo
wo o vetor que conte´m os coeficientes a serem identificados e definido por:
w(k) ,
[
wo0(k) wo1(k) . . . woN−1(k)
]T
, (2.3)
e ν(k) um ru´ıdo somado ao sinal de refereˆncia, geralmente atribu´ıdo a erros de
medic¸a˜o e/ou de modelagem.
2.2 Algoritmo LMS
O algoritmo de mı´nimos quadrados (LMS, do ingleˆs Least-Mean Squares)
foi um dos primeiros algoritmos adaptativos e teve origem no algoritmo “Steepest
Descent”. A ideia deste algoritmo era percorrer uma superf´ıcie, descrita aproxima-
damente por uma func¸a˜o custo apropriada, ate´ o seu ponto de mı´nimo. A func¸a˜o
16
custo a partir da qual o algoritmo LMS foi derivado e´ o valor quadra´tico me´dio do
erro (MSE) entre o sinal de refereˆncia e a sa´ıda do filtro adaptativo:
F [e(k)] = E[e2(k)] = E[(d(k)−wT (k)x(k))2]. (2.4)
Como ja´ foi dito anteriormente, algoritmos adaptativosna˜o raro sa˜o atuali-
zados recursivamente na direc¸a˜o contra´ria ao do vetor gradiente da func¸a˜o custo.
Portanto, podemos escrever a equac¸a˜o de atualizac¸a˜o da seguinte forma:
w(k + 1) = w(k)− β∂F [e(k)]
∂w(k) , (2.5)
onde ∂F [e(k)]
∂w(k) e´ o vetor gradiente de uma func¸a˜o do erro instantaˆneo e β e´ uma cons-
tante de proporcionalidade (“step size”) utilizada para evitar saltos muito grandes
durante o processo de aprendizagem do filtro, fazendo com que o algoritmo convirja
sem experimentar grandes oscilac¸o˜es, as quais degradam seu desempenho, particu-
larmente em regime permanente. Para a func¸a˜o custo MSE da equac¸a˜o (2.4), o vetor
gradiente e´ dado por:
∂E [e2(k)]
∂w(k) = E
[
∂e2(k)
∂w(k)
]
= E
[
2e(k) ∂e(k)
∂w(k)
]
= E
[
2e(k)∂(d(k)−wT (k)x(k))
∂w(k)
]
= −2E [e(k)x(k)]
(2.6)
Aplicando a equac¸a˜o acima na equac¸a˜o de atualizac¸a˜o dos coeficientes do
filtro, obtemos:
w(k + 1) = w(k) + 2E[e(k)x(k)]
= w(k) + βE[x(k)(d(k)− xT (k)w(k))]
= w(k) + β(pdx(k)−Rxx(k)w(k))
(2.7)
conhecida como equac¸a˜o de atualizac¸a˜o do algoritmo “Steepest Descent”. Vale no-
tar que com esse algoritmo ainda e´ necessa´rio estimar caracter´ısticas do sinal de
entrada, como a matriz autocorrelac¸a˜o do sinal de entrada definida por Rxx(k) ,
E[x(k)xT (k)]. O sinal de entrada, como sera´ mostrado mais a frente, e´ assumido
ser estaciona´rio no sentido amplo (WSS, do ingleˆs: Wide Sense Stacionary), e a
correlac¸a˜o cruzada de d(k) com x(k), a qual tambe´m cumpre estimar, e´ definida
por pdx(k) = E[d(k)x(k)]. Por isso, no algoritmo LMS foi proposta a adoc¸a˜o do
17
gradiente de uma estimativa do MSE, de sorte a usar a func¸a˜o custo instantaˆnea
FLMS[e(k)] = e2(k). Portanto, a equac¸a˜o de atualizac¸a˜o para o caso do LMS pode
ser escrita da seguinte forma:
w(k + 1) = w(k) + 2β′e(k)x(k)
= w(k) + βx(k)e(k),
(2.8)
onde 2β′ = β.
2.3 Algoritmo NLMS
Nesta sec¸a˜o, apresentaremos o algoritmo de mı´nimos quadrados normalizado
(NLMS, do ingleˆs Normalized Least-Mean Squares). O funcionamento desse algo-
ritmo e´ muito similar ao do seu antecessor (o LMS). A principal diferenc¸a reside no
fato de que, conforme o pro´prio nome revela, o termo de atualizac¸a˜o dos coeficien-
tes do filtro e´ normalizado pela norma euclidiana (||.||2) do vetor de entrada x(k).
Essa normalizac¸a˜o com relac¸a˜o ao sinal de entrada e´ muito interessante porque faz
com que o passo de aprendizagem seja inversamente proporcional a` energia do ve-
tor x(k). Tal propriedade permite que o algoritmo convirja mais rapidamente em
momentos em que o sinal de entrada e´ mais uniforme e evite saltos quando o sinal
sofre alterac¸o˜es mais bruscas [7].
Na sec¸a˜o anterior, derivamos o algoritmo LMS a partir de uma func¸a˜o custo
apropriada. Como o algoritmo NLMS trata-se apenas de uma normalizac¸a˜o do
termo de atualizac¸a˜o do algoritmo anterior, ele possui uma equac¸a˜o de atualizac¸a˜o
dos coeficientes semelhante, como mostrado abaixo:
w(k + 1) = w(k) + β||x(k)||2 + δx(k)e(k), (2.9)
onde δ e´ uma constante comumente usada para evitar diviso˜es por zero. E´ poss´ıvel
derivar a equac¸a˜o do NLMS por meio da otimizac¸a˜o de uma func¸a˜o custo com
restric¸a˜o. A ideia e´ minimizar a norma da diferenc¸a entre os coeficientes do filtro
de refereˆncia e o filtro adaptativo. Para isso, definamos o erro a posteriori ep(k) no
instante k por:
18
ep(k) , d(k)−wT (k + 1)x(k). (2.10)
Agora, basta resolver o problema de otimizac¸a˜o com restric¸a˜o abaixo.
minw(k+1) ||w(k + 1)−w(k)||2
sujeito a ep(k) = (1− β)e(k).
(2.11)
Para resolver esse problema, recorremos aos multiplicadores de Lagrange:
F = ||w(k + 1)−w(k)||2 + λep(k)
= ||w(k + 1)||2 − 2wT (k + 1)w(k) + ||w(k)||2 + λep(k).
(2.12)
Para achar o mı´nimo dessa func¸a˜o em relac¸a˜o w(k + 1), basta calcular seu
gradiente em func¸a˜o de w(k) e iguala´-la a zero, logo:
∂F
∂w(k + 1) = 2w(k + 1)− 2w(k)− λx(k) = 0 (2.13)
w(k + 1) = w(k) + λx(k)2 . (2.14)
Igualando as duas equac¸o˜es do erro a posteriori e substituindo w(k+1) pelo
resultado obtido na equac¸a˜o (2.14), temos:
e(k)− βe(k) = d(k)−w(k)Tx(k)− λx(k)Tx(k)2
= e(k) + λ||x(k)||22
(2.15)
λ = 2βe(k)||x(k)||2 (2.16)
Da´ı podemos concluir que a equac¸a˜o de atualizac¸a˜o dos coeficientes pode ser
escrita da seguinte forma:
w(k + 1) = w(k) + βx(k)e(k)||x(k)||2 . (2.17)
O algoritmo LMS, assim como muitos outros, tambe´m pode ser derivado
utilizando multiplicadores de Lagrange [8]. No caso do LMS, o problema fica da
seguinte forma:
19
minw(k+1) ||w(k + 1)−w(k)||2
sujeito a ep(k) = (1− β||x(k)||2)e(k).
(2.18)
Assim como no caso anterior, recorremos aos multiplicadores de Lagrange:
F = ||w(k + 1)−w(k)||2 + λep(k)
= ||w(k + 1)||2 − 2wT (k + 1)w(k) + ||w(k)||2 + λep(k).
(2.19)
Para achar o mı´nimo dessa func¸a˜o em relac¸a˜o w(k + 1), basta calcular seu
gradiente em func¸a˜o de w(k) e iguala´-la a zero, logo:
∂F
∂w(k + 1) = 2w(k + 1)− 2w(k)− λx(k) = 0 (2.20)
w(k + 1) = w(k) + λx(k)2 . (2.21)
Igualando as duas equac¸o˜es do erro a posteriori e substituindo w(k+1) pelo
resultado obtido na equac¸a˜o (2.21), temos:
e(k)− β||x(k)||2e(k) = d(k)−w(k)Tx(k)− λx(k)Tx(k)2
= e(k) + λ||x(k)||22
(2.22)
λ = 2βe(k) (2.23)
Da´ı podemos concluir que a equac¸a˜o de atualizac¸a˜o dos coeficientes pode ser
escrita da seguinte forma:
w(k + 1) = w(k) + βx(k)e(k). (2.24)
2.4 Algoritmo Sign-error
Nessa sec¸a˜o, sera´ apresentada uma variac¸a˜o do algoritmo LMS, o sign-error
LMS e sua versa˜o normalizada. Essa variac¸a˜o do algoritmo LMS reduz o custo
computacional (caso escolhamos de modo apropriado o passo de aprendizagem) e
apresenta maior robustez com relac¸a˜o ao ru´ıdo [9, 10]. A func¸a˜o custo definida para
esse algoritmo e´ o mo´dulo do sinal do erro (FSIGN[e(k)] = |e(k)|). Da´ı podemos
20
desenvolver a equac¸a˜o de atualizac¸a˜o apropriada para os coeficientes do filtro, como
segue:
w(k + 1) = w(k)− β∇F [e(k)]∇w(k)
= w(k)− βsign[e(k)] ∂e(k)
∂w(k)
= w(k)− βsign[e(k)]∂(d(k)−w(k)Tx(k))
∂w(k)
= w(k) + βsign[e(k)]x(k)
(2.25)
Na sua forma normalizada, podemos escrever:
w(k + 1) = w(k) + β||x(k)||2 + δ sign[e(k)]x(k) (2.26)
2.5 Conclusa˜o
Neste cap´ıtulo foi feita uma revisa˜o sobre filtragem adaptativa, e como esta e´
usada na identificac¸a˜o de sistemas que e´ o foco deste trabalho. Tambe´m foram apre-
sentados o desenvolvimento dos algoritmos da famı´lia LMS que, como veremos mais
adiante, e´ uma famı´lia de algoritmos adaptativos amplamente utilizada, tanto na
pra´tica como no meio acadeˆmico, e muito importante como base para os algoritmos
estudados neste trabalho.
21
Cap´ıtulo 3
Identificac¸a˜o de Sistemas Esparsos
3.1 Introduc¸a˜o
Desde o in´ıcio dos anos 2000, muitos autores notaram que sistemas reais,
recorrentemente, apresentam respostas ao impulso esparsas, sendo tais respostas ao
impulso comuns em aplicac¸o˜es como canais de transmissa˜o de televisa˜o digital e
cancelamento de eco [11].
Um sistema esparso e´ um sistema cuja resposta ao impulso possui muitos
coeficientes de magnitude nula ou quase nula. Por se tratar de uma propriedade
recorrente, a capacidade de incorpora´-la no processo de aprendizagem do filtro adap-
tativo vem ganhando notoriedade por acelerar a convergeˆncia dos algoritmos e/ou
diminuir o erro em regime permanente. Como nenhum dos algoritmos tradicionais
da famı´lia LMS faziam uso dessa propriedade na identificac¸a˜o de sistemas, algorit-
mos conscientes da esparsidade foram desenvolvidos. Tais algoritmos sa˜o capazes
de aproveitar a esparsidade dos sistemas de diferentes formas, seja identificando e
na˜o atualizando regio˜es inativas (isto e´, com coeficientes muito pro´ximos de zero)
[12, 13], seja propondouma atualizac¸a˜o espec´ıfica para cada coeficiente com base em
sua magnitude (algoritmos proporcionais) [14, 15, 16], ou ainda aplicando uma pena-
lizac¸a˜o aos coeficientes dentro de uma determinada faixa, de forma a “empurra´-los”
para zero [11, 17, 18, 19], dentre outras formas propostas na literatura [20].
22
3.2 PNLMS
Apesar do foco deste trabalho ser em algoritmos que usam a regularizac¸a˜o
pela norma ℓ0, nesta sec¸a˜o e´ mostrada uma das primeiras derivac¸o˜es realizadas para
se utilizar a propriedade de coeficientes esparsos, que e´ a atualizac¸a˜o proporcional
dos coeficientes (PNLMS). A principal ideia deste paradigma consiste na atualizac¸a˜o
proporcional dos coeficientes consoante a sua magnitude, de acordo com a seguinte
equac¸a˜o de atualizac¸a˜o:
w(k + 1) = w(k) + β
xT (k)Λ(k)x(k) + δΛ(k)x(k)e(k), (3.1)
onde a matriz Λ(k) e´ responsa´vel pela ponderac¸a˜o da atualizac¸a˜o dos coeficientes
do filtro adaptativo.
Embora o algoritmo PNLMS apresente ra´pida convergeˆncia inicial quando
comparado ao NLMS, essa taxa sofre grande reduc¸a˜o durante o processo de con-
vergeˆncia. Ale´m disso, para o caso de respostas ao impulso na˜o-esparsas, a con-
vergeˆncia do PNLMS e´ mais lenta que a do NLMS [15, 21]. Para compensar esses
problemas, outros algoritmos proporcionais a partir do PNLMS foram propostos em
[22, 23].
3.3 ℓ0-LMS
O algoritmo ℓ0-LMS e´ uma versa˜o do LMS capaz de explorar a propriedade de
esparsidade na identificac¸a˜o de sistemas, atraindo muito a atenc¸a˜o da comunidade
acadeˆmica por conseguir melhorar tanto a taxa convergeˆncia como o erro de regime
permanente em sistemas esparsos [18]. A mudanc¸a consiste na adic¸a˜o de um termo
a` func¸a˜o custo do LMS que penaliza soluc¸o˜es pouco esparsas, sendo esta func¸a˜o
descrita pela seguinte equac¸a˜o:
Fℓ0−LMS(k) = e(k)2 +
κ
β
Fρ[w(k)], (3.2)
onde κ e´ um paraˆmetro empregado para controlar a penalizac¸a˜o imposta a soluc¸o˜es
pouco esparsas, e a func¸a˜o Fρ[w(k)] e´ uma func¸a˜o diferencia´vel por partes que
aproxima a norma ℓ0. Uma escolha comum na literatura para essa func¸a˜o, e que
sera´ usada tambe´m nesse trabalho, e´ [11, 17]:
23
Fρ [w(k)] =
N−1∑
n=0
(
1− e−ρ|wn(k)|
)
, (3.3)
onde ρ ∈ R+ e´ um paraˆmetro arbitra´vel, o qual controla a aproximac¸a˜o da norma
ℓ0, como mostrado na Figura 3.1.
500 1000 1500 2000 2500 3000 3500 4000 4500
0
0.1
0.2
500 1000 1500 2000 2500 3000 3500 4000 4500
0
2
4
6
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es(a)
(b)
ρ = 2
ρ = 4ρ = 6
ρ = 20
w
(k
)
F
ρ
[w
(k
)]
Figura 3.1: (a) Valores dos coeficientes do filtro adaptativo w(k) ao longo das
iterac¸o˜es. (b) Fρ[w(k)] para ρ = 2, ρ = 4, ρ = 6 e ρ = 20.
A Figura 3.1(a) mostra a evoluc¸a˜o dos coeficientes do filtro adaptativo ao
longo do tempo. Ja´ Figura 3.1(b) mostra a sa´ıda da func¸a˜o Fρ [w(k)] que, como
podemos perceber, e´ condicionada ao valor de ρ escolhido. Vale notar como ρ
atua na interpretac¸a˜o da func¸a˜o Fρ [w(k)] sobre quais coeficientes esta˜o suficiente-
mente pro´ximos de zero para serem considerados esparsos, e assim sofrerem a devida
atuac¸a˜o do algoritmo adaptativo, como sera´ mostrado adiante.
Uma vez definida a func¸a˜o custo, e´ poss´ıvel escrever a equac¸a˜o de atualizac¸a˜o
do ℓ0-LMS e do ℓ0-NLMS da seguinte forma:
w(k + 1) = w(k) + β˜(k)x(k)e(k) + κf ρ[w(k)], (3.4)
onde f ρ[w(k)] e´ uma aproximac¸a˜o do negativo do gradiente de Fρ[w(k)] e β˜(k) e´ o
passo de aprendizado tanto para o ℓ0-LMS quanto para o ℓ0-NLMS, como mostrado
abaixo:
β˜(k) =
 β, para o algoritmo ℓ0-LMS,β
xT (k)x(k)+δ , para o algoritmo ℓ0-NLMS.
(3.5)
24
Vale notar que ∂Fρ[w(k)]
∂w(k) apresenta um custo computacional elevado por ter-
se que calcular o resultado de uma exponencial a toda iterac¸a˜o. Por isso, sera´
empregada uma aproximac¸a˜o de baixo custo desse gradiente: fρ [wi(k)] ≈ −∂Fρ[w(k)]∂wi(k) .
Tal aproximac¸a˜o e´ feita utilizando a se´rie de McLaurin, um caso particular da se´rie
de Taylor, e truncando-a nos dois primeiros termos. Esse termo pode ser visto como
um termo de atrac¸a˜o para zero e pode ser descrito por [11]:
fρ[wi(k)] =

ρ2wi(k) + ρ, −1ρ ≤ wi(k) < 0
ρ2wi(k)− ρ, 0 < wi(k) ≤ 1ρ
0, no resto.
(3.6)
Vale notar que a func¸a˜o fρ(x) implementa uma func¸a˜o que atrai valores de
x, dentro de uma determinada faixa controlada por ρ, para 0 [11].
1000 2000 3000 4000
−4
−2
0
1000 2000 3000 4000
−2
0
2
4
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
f ρ
[w
i(k
)]
f ρ
[w
i(k
)]
Figura 3.2: (a) fρ[wi(k)] quando i = 7 e ρ = 6. (b) fρ[wi(k)] quando i = 3 e ρ = 6.
A Figura 3.2(a) mostra um coeficiente do filtro que na˜o e´ considerado esparso.
Note que o coeficiente so´ sofre a penalizac¸a˜o imposta por fρ[wi(k)] durante um
determinado tempo devido ao valor com o qual ele foi inicializado (no caso todos
25
os coeficientes do filtro adaptativo foram inicializados com 0). Ja´ figura 3.2(b)
mostra um coeficiente que sempre sofre penalizac¸a˜o por se tratar de um coeficiente
considerado esparso.
3.4 Conclusa˜o
Neste cap´ıtulo foi feita uma revisa˜o sobre identificac¸a˜o de sistemas esparsos,
e foi mostrado como vem crescendo o desenvolvimento de algoritmos adaptativos
cientes dessa propriedade, ta˜o comum em diversas aplicac¸o˜es. Tambe´m foram apre-
sentados os algoritmos adaptativos proporcionais e os com regularizac¸a˜o de norma
ℓ0, este u´ltimo sendo o caso de interesse deste trabalho.
26
Cap´ıtulo 4
Ana´lise de transiente
4.1 Me´todos de ana´lise
A ana´lise teo´rica de algoritmos adaptativos e´ de grande importaˆncia, pois
cabe a ela fornecer de antema˜o informac¸o˜es sobre as caracter´ısticas e o comporta-
mento do algoritmo ao projetista. Diversas te´cnicas de ana´lises foram empregadas na
literatura ao longo dos anos, dentre as quais cumpre destacar: ana´lise de esperanc¸a
estat´ıstica exata [24], balanceamento de energia [25] e ca´lculo recursivo da matriz de
autocorrelac¸a˜o dos desvios dos coeficientes [11]. A maior parte das te´cnicas tentam
estimar de maneira confia´vel a evoluc¸a˜o de duas me´tricas principais de desempenho
em algoritmos adaptativos, o MSE e o MSD.
Neste trabalho, e´ feita uma ana´lise dos algoritmos ℓ0-sign-LMS e ℓ0-sign-
NLMS, empregando a te´cnica do ca´lculo recursivo da matriz de autocorrelac¸a˜o dos
desvios. Tal te´cnica consiste em determinar equac¸o˜es a diferenc¸as que consigam
prever o comportamento de Rw˜(k) , E[w˜(k)w˜T (k)], onde w˜(k) = wo −w(k) e´ o
vetor de desvio dos coeficientes adaptativos na k-e´sima iterac¸a˜o.
Para que a ana´lise seja poss´ıvel, e´ necessa´rio que algumas hipo´teses sejam
feitas:
H1: x(k), β˜(k) e w˜(k) sa˜o mutuamente independentes.
H2: O ru´ıdo aditivo ν(k), de me´dia zero e variaˆncia finita, e´ branco e ide-
pendente de x(k). Sua variaˆncia no instante k e´ descrita por σ2ν(k).
H3: As seguintes aproximac¸o˜es sa˜o necessa´rias para que se tenha uma soluc¸a˜o
27
fechada:
E {w˜i(k)fρ [wj(k)]} ≈ E {w˜i(k)}E {fρ [wj(k)]}
E {fρ [wi(k)] fρ [wj(k)]} ≈ E {fρ [wi(k)]}E {fρ [wj(k)]}
(4.1)
H4: A distribuic¸a˜o dos coeficientes w˜i(k) e´ Gaussiana.
H5: O sinal de entrada e´ estaciona´rio, gaussiano e todos os autovalores da
sua matriz de autocorrelac¸a˜o sa˜o na˜o nulos.
Com as hipo´teses H1 e H2, podemos calcular o MSE segundo [26]:
ξ(k) , E
[
e2(k)
]
≈ σ2ν(k) + Tr
{
RxE
[
w˜(k)w˜T (k)
]}
, (4.2)
onde Rx = E[x(k)xT (k)] e´ a autocorrelac¸a˜o do sinal de entrada, Tr {X} e´ o trac¸o
da matriz X e σ2ν(k) e´ a variaˆncia do ru´ıdo no instante k.
Ja´ o MSD pode ser calculado pela seguinte equac¸a˜o:
MSD(k) , E[‖wo −w(k)‖2] = Tr
{
E[w˜(k)w˜T (k)]
}
. (4.3)
4.2 Algunscomenta´rios sobre as hipo´teses
Vale fazer algumas observac¸o˜es acerca das hipo´teses feitas na sec¸a˜o anterior
e que sera˜o utilizadas ao longo deste cap´ıtulo. Em H1 e´ suposto que x(k), β˜(k)
e w˜(k) sa˜o mutuamente idependentes. A independeˆncia entre x(k) e w˜(k) e´ uma
propriedade conhecida como “independence assumption” e amplamente encontrada
no meio acadeˆmico [27, 28, 26, 6]. Ja´ no que tange a independeˆncia de β˜(k) com
relac¸a˜o a`s outras varia´veis aleato´rias, e´ fa´cil notar que para o caso do algoritmo
LMS a hipo´tese e´ verdadeira, uma vez que β e´ uma constante que na˜o depende
do valor assumido por x(k). Pore´m, no caso do algoritmo NLMS e´ preciso aplicar
o “Averaging Principle” [29] na expressa˜o E[β˜(k)A], onde β˜(k) e A sa˜o varia´veis
aleato´rias ditas conjuntamente estaciona´rias [30, 31, 32]. Tal princ´ıpio defende que
β˜(k) varia devagar com respeito ao sinal de entrada, permitindo que E[β˜(k)A] seja
aproximado por E[β˜(k)]E[A].
Sobre a hipo´tese H2, vale notar que ela reforc¸a a linearidade entre x(k) e
d(k), o que e´ razoa´vel em diversas aplicac¸o˜es (vide [11]). Este trabalho na˜o fica
restrito a uma variaˆncia do ru´ıdo constante como e´ comum na literatura, aceitando
que ela varie ao longo do tempo.
28
Embora H3 seja uma suposic¸a˜o “forc¸ada” para facilitar os ca´lculos, mostrou-
se uma aproximac¸a˜o razoa´vel como observado em [11].
Assim como H1, H4 e´ uma hipo´tese muito encontrada na literatura e que pode
ser justificada pelo teorema central do limite [31]. Resultados acerca da distribuic¸a˜o
dos coeficientes de w(k), e que corroboram a utilizac¸a˜o desta hipo´tese, podem ser
encontrados tambe´m em [11].
A hipo´tese H5 na˜o assume que o sinal de entrada seja branco, tornando o
estudo aqui feito mais abrangente do que e´ comumente encontrado a este respeito.
Pore´m, na˜o engloba o caso de todos os sinais coloridos, uma vez que assume-se que
todos os autovalores de Rx sa˜o na˜o-nulos.
4.3 Descric¸a˜o dos momentos de primeira e se-
gunda ordens
Como dito anteriormente, o foco deste trabalho e´ fazer uma ana´lise dos al-
goritmos ℓ0-sign-LMS e ℓ0-sign-NLMS, criando um modelo que permita fazer uma
estimativa da evoluc¸a˜o das respectivas matrizes de autocorrelac¸a˜o dos desvios. Por-
tanto, comecemos desenvolvendo suas equac¸o˜es de atualizac¸a˜o, as quais sa˜o uma das
contribuic¸o˜es deste trabalho.
Como ja´ foi dito, para explorar as caracter´ısticas de um sistema esparso, e´
somado um termo de regularizac¸a˜o a` func¸a˜o custo do algoritmo com o qual se deseja
trabalhar, no caso, o sign-LMS. Logo, temos a seguinte func¸a˜o custo:
F(k) = |e(k)|+ κ
β
Fρ[w(k)] (4.4)
Como ja´ sabemos, o coeficiente do filtro adaptativo no instante k + 1 e´ cal-
culado recursivamente pelo coeficiente no instante anterior, e somando o negativo
do gradiente da func¸a˜o custo escalado por β. Logo, a equac¸a˜o de atualizac¸a˜o do
algoritmo ℓ0-sign e´ dada por:
w(k + 1) = w(k) + β˜(k)x(k)sign[e(k)] + κf ρ[w(k)]. (4.5)
Definida a equac¸a˜o de atualizac¸a˜o para ambos os algoritmos (cabendo no-
tar serem ambos contribuic¸o˜es deste trabalho), nossa ana´lise consiste em estimar
29
a evoluc¸a˜o da matriz de autocorrelac¸a˜o dos desvios. Portanto, devemos manipular
a equac¸a˜o anterior substituindo w(k) por wo − w˜(k), de modo a encontrar uma
atualizac¸a˜o recursiva dos desvios. Ou seja:
wo − w˜(k + 1) = wo − w˜(k) + β˜(k)x(k)sign[e(k)] + κf ρ[w(k)]. (4.6)
Ao subtrairmos wo e multiplicarmos por −1 ambos os lados, encontramos:
w˜(k + 1) = w˜(k)− β˜(k)x(k)sign[e(k)]− κf ρ[w(k)]. (4.7)
Para que a ana´lise teo´rica possa ser feita de maneira mais simples, doravante
trabalharemos com a equac¸a˜o de atualizac¸a˜o na sua forma escalar, ou seja, ao inve´s
de calcularmos o vetor de desvio diretamente, calcularemos seus coeficientes. Enta˜o,
devemos reescrever a equac¸a˜o (4.7) da seguinte forma:
w˜i(k + 1) = w˜i(k)− β˜(k)x(k − i)sign[e(k)]− κfρ[wi(k)]. (4.8)
Para que possamos inferir as estat´ısticas de primeira e segunda ordem, deve-
mos primeiro escrever o erro e(k) da seguinte forma:
e(k) = d(k)− y(k) = (wo)Tx(k) + ν(k)−wT (k)x(k)
= w˜T (k)x(k) + ν(k)
= ∑N−1n=0 w˜n(k)x(k − n) + ν(k)
(4.9)
Substituindo (4.9) na equac¸a˜o (4.8), temos:
w˜i(k+1) = w˜i(k)−β˜(k)x(k−i)sign
[
N−1∑
n=0
w˜n(k)x(k − n) + ν(k)
]
−κfρ[wi(k)]. (4.10)
Uma vez definida a equac¸a˜o de atualizac¸a˜o dos desvios na sua forma escalar,
devemos propor uma equac¸a˜o estat´ıstica que descreva o comportamento do algoritmo
na me´dia, uma vez que a equac¸a˜o (4.10) e´ uma equac¸a˜o determin´ıstica. Portanto,
devemos aplicar o operador do valor esperado a` equac¸a˜o (4.10), a qual passa a ser
escrita da seguinte forma:
30
E[w˜i(k + 1)] = E[w˜i(k)]
−E[β˜(k)x(k − i)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))]
−κE {fρ[wi(k)]} .
(4.11)
Para que possamos continuar a ana´lise, sera´ aplicado o teorema de Price
[33, 34] a` equac¸a˜o (4.11). Tal teorema permite que escrevamos:
E[sign(A)B] =
√
2
πσ2A
E[AB], (4.12)
onde A e B sa˜o duas varia´veis aleato´rias conjuntamente Gaussianas e de me´dia
zero, e σ2A = E[A2]. Portanto, utilizando o teorema de Price, podemos reescrever a
equac¸a˜o (4.11) da seguinte forma:
E[w˜i(k + 1)] = E[w˜i(k)]
−
√
2
πσ2e
E[β˜(k)x(k − i)∑N−1n=0 w˜n(k)x(k − n)]
+E[β˜(k)x(k − i)ν(k)]
−κE[fρ[wi(k)]]
(4.13)
Pela hipo´tese H2, podemos observar que E[β˜(k)x(k − i)ν(k)] = 0, logo:
E[w˜i(k + 1)] = E[w˜i(k)]
−
√
2
πσ2e
E[β˜(k)x(k − i)∑N−1n=0 w˜n(k)x(k − n)]
−κE[fρ[wi(k)]]
(4.14)
Por fim, a hipo´tese H1 nos diz que β˜(k), x(k) e w˜i(k) sa˜o mutuamente in-
dependentes. Portanto, utilizando H1 e a propriedade da linearidade entre os ope-
radores valor esperado e somato´rio, a equac¸a˜o (4.14) pode ser reescrita da seguinte
maneira:
E[w˜i(k + 1)] = E[w˜i(k)]−
√
2
πσ2e
E[β˜(k)]
N−1∑
n=0
E[w˜n(k)]rin − κE {fρ[wi(k)]} , (4.15)
onde σ2e e´ a variaˆncia do erro e rin , E[x(k − i)x(k − n)].
Para estimar a evoluc¸a˜o da matriz de autocorrelac¸a˜o dos desvios, devemos
estimar a evoluc¸a˜o dos coeficientes de w˜(k)w˜T (k) na me´dia. Com base na equac¸a˜o
31
(4.10), a equac¸a˜o do ca´lculo recursivo para um coeficiente gene´rico dessa matriz e´
dada por:
w˜i(k + 1)w˜j(k + 1) = w˜i(k)w˜j(k)
−β˜(k)w˜i(k)x(k − j)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))
−κw˜i(k)fρ[wj(k)]
−β˜(k)w˜j(k)x(k − i)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))
+β˜(k)2x(k − i)x(k − j)sign2(∑N−1n=0 w˜n(k)x(k − n) + ν(k))
+κβ˜(k)x(k − i)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))fρ[wj(k)]
−κw˜j(k)fρ[wi(k)]
+κβ˜(k)x(k − j)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))fρ[wi(k)]
+κ2fρ[wi(k)]fρ[wj(k)]
(4.16)
Como a matriz de autocorrelac¸a˜o dos desvios e´ calculada via E[w˜(k)w˜T (k)],
devemos aplicar o operador do valor esperado na equac¸a˜o (4.16), a qual passa a ser
escrita da seguinte forma:
E[w˜i(k+1)w˜j(k+1)] = E[w˜i(k)w˜j(k)]
−E[β˜(k)w˜i(k)x(k − j)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))]
−E[κw˜i(k)fρ[wj(k)]]
−E[β˜(k)w˜j(k)x(k − i)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))]
+E[β˜(k)2x(k − i)x(k − j)sign2(∑N−1n=0 w˜n(k)x(k − n) + ν(k))]
+E[κβ˜(k)x(k − i)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))fρ[wj(k)]]
−E[κw˜j(k)fρ[wi(k)]]
+E[κβ˜(k)x(k − j)sign(∑N−1n=0 w˜n(k)x(k − n) + ν(k))fρ[wi(k)]]
+E[κ2fρ[wi(k)]fρ[wj(k)]]
(4.17)
Utilizando o teorema de Price, podemos reescrever a equac¸a˜o (4.17) da se-
guinte maneira:
32
E[w˜i(k+1)w˜j(k+1)] = E[w˜i(k)w˜j(k)]
−
√
2
πσ2e
E[β˜(k)w˜i(k)x(k − j)(∑N−1n=0 x(k − n)w˜n(k) + ν(k))]
−κE[w˜i(k)fρ[wj(k)]]
−
√
2
πσ2e
E[β˜(k)w˜j(k)x(k − i)(∑N−1n=0 x(k − n)w˜n(k) + ν(k))]
+E[β˜(k)2x(k − i)x(k − j)]
+
√
2
πσ2e
κE[β˜(k)x(k − i)(∑N−1n=0 w˜n(k)x(k − n) + ν(k))fρ[wj(k)]]
−κE[w˜j(k)fρ[wi(k)]]
+
√
2
πσ2e
κE[β˜(k)x(k − j)(∑N−1n=0 w˜n(k)x(k − n) + ν(k))fρ[wi(k)]]
+κ2E[fρ[wi(k)]fρ[wj(k)]],(4.18)
onde tambe´m utilizamos o fato de que sign2(x) = 1.
Pela hipo´tese H2, podemos observar que E[β(k)x(k − j)ν(k)] = 0, logo:
E[w˜i(k + 1)w˜j(k + 1)] = E[w˜i(k)w˜j(k)]
−
√
2
πσ2e
E[β˜(k)w˜i(k)x(k − j)∑N−1n=0 x(k − n)w˜n(k)]
−κE[w˜i(k)fρ[wj(k)]]
−
√
2
πσ2e
E[β˜(k)w˜j(k)x(k − i)∑N−1n=0 x(k − n)w˜n(k)]
+E[β˜(k)2x(k − i)x(k − j)]
+
√
2
πσ2e
κE[β˜(k)x(k − i)∑N−1n=0 w˜n(k)x(k − n)fρ[wj(k)]]
−κE[w˜j(k)fρ[wi(k)]]
+
√
2
πσ2e
κE[β˜(k)x(k − j)∑N−1n=0 w˜n(k)x(k − n)fρ[wi(k)]]
+κ2E[fρ[wi(k)]fρ[wj(k)]]
(4.19)
A hipo´tese H1, nos diz que β˜(k), x(k) e w˜(k) sa˜o mutuamente independentes.
Portanto, utilizando H1 e a propriedade da linearidade entre os operadores valor
esperado e somato´rio, a equac¸a˜o (4.19) pode ser reescrita da seguinte maneira:
33
E[w˜i(k + 1)w˜j(k + 1)] = E[w˜i(k)w˜j(k)]
−
√
2
πσ2e
E[β˜(k)]∑N−1n=0 E[w˜i(k)w˜n(k)]rjn
−κE[w˜i(k)fρ[wj(k)]]
−
√
2
πσ2e
E[β˜(k)]∑N−1n=0 E[w˜j(k)w˜n(k)]rin
+E[β˜(k)2]rij
+
√
2
πσ2e
κE[β˜(k)]∑N−1n=0 E[w˜n(k)rinfρ[wj(k)]]
−κE[w˜j(k)fρ[wi(k)]]
+
√
2
πσ2e
κE[β˜(k)]∑N−1n=0 E[w˜n(k)rjnfρ[wi(k)]]
+κ2E[fρ[wi(k)]fρ[wj(k)]]
(4.20)
Por fim, as aproximac¸o˜es descritas na hipo´tese H3 nos permitem reescrever
a equac¸a˜o (4.20) como a seguir:
E[w˜i(k + 1)w˜j(k + 1)] = E[w˜i(k)w˜j(k)]
−
√
2
πσ2e
E[β˜(k)]∑N−1n=0 E[w˜i(k)w˜n(k)]rjn
−κE[w˜i(k)]E[fρ[wj(k)]]
−
√
2
πσ2e
E[β˜(k)]∑N−1n=0 E[w˜j(k)w˜n(k)]rin
+E[β˜(k)2]rij
+
√
2
πσ2e
κE[β˜(k)]∑N−1n=0 E[w˜n(k)]rinE[fρ[wj(k)]]
−κE[w˜j(k)]E[fρ[wi(k)]]
+
√
2
πσ2e
κE[β˜(k)]∑N−1n=0 E[w˜n(k)]rjnE[fρ[wi(k)]]
+κ2E[fρ[wi(k)]]E[fρ[wj(k)]]
(4.21)
Uma vez definidas as equac¸o˜es recursivas para os momentos de primeira e
segunda ordem, cabe agora empreender o ca´lculo dos termos: E
[
β˜(k)
]
, E
[
β˜2(k)
]
e
E[fρ[wi(k)]]. Comecemos pelo ca´lculo de E
[
β˜(k)
]
e E
[
β˜2(k)
]
. No caso de algoritmos
na˜o normalizados (LMS), esses termos sa˜o determin´ısticos e definidos por β e β2.
Pore´m, em algoritmos normalizados, o passo de aprendizagem β e´ modulado pela
norma euclidiana do vetor de entrada (xTx) que faz com que β(k) deixe de ser
determin´ıstico e seja calculado por: βE[ 1
xTx+δ ]. Para realizar o ca´lculo desse valor
esperado, utilizaremos uma aproximac¸a˜o de primeira ordem de McLaurin, como
proposto em [35, 36, 37], reescrevendo E[ 1
xTx+δ ] como:
34
E
[
1
(xT (k)x(k)+δ)n
]
≈ E
[
1
(xT (k)x(k))n
]
︸ ︷︷ ︸
,En
−nδE
[
1
(xT (k)x(k))n+1
]
.
(4.22)
Assim, podemos escrever β(k) e β2(k) como:
E
{
β˜(k)
}
= β
(
E1 − δE2
)
, (4.23)
E
{
β˜(k)2
}
= β2
(
E2 − 2δE3
)
. (4.24)
Devemos agora realizar o ca´lculo de E1, E2 e E3 e, para tanto, utilizaremos
a hipo´tese H5, que nos permite escrever En da seguinte forma:
En = 1(2π)L/2√det(Rx)
∫ ∞
−∞
. . .
∫ ∞
−∞︸ ︷︷ ︸
L×
1
(xTx)n e
−x
TR−1x x
2 dx. (4.25)
Para que possamos chegar a uma soluc¸a˜o anal´ıtica para (4.25), devemos de-
finir uma func¸a˜o auxiliar Ψn(ω):
Ψn(ω) = 1(2π)L/2√det(Rx)
∫ ∞
−∞
. . .
∫ ∞
−∞︸ ︷︷ ︸
L×
1
(xTx)n e
−ωxTxe−
xTR−1x x
2 dx, (4.26)
podemos perceber que a func¸a˜o auxiliar foi descrita de tal forma que quando ω = 0
recuperamos En. Logo:
En = Ψn(ω)|ω=0 = Ψn(0)
=
∫
. . .
∫
︸ ︷︷ ︸
N×
∂nΨn(ω)
∂nω
dω . . . dω︸ ︷︷ ︸
N×
∣∣∣∣∣∣∣∣∣
ω=0
,
(4.27)
onde ∂nΨn(ω)
∂nω
e´ descrito pela seguinte equac¸a˜o:
∂nΨn(ω)
∂nω
= (−1)n
(2π)L/2
√
det(Rx)
∫ ∞
−∞
. . .
∫ ∞
−∞︸ ︷︷ ︸
L×
e−ωx
Txe−
xTR−1x x
2 dx
= (−1)n
(2π)L/2
√
det(Rx)
∫∞
−∞ . . .
∫∞
−∞ e
−
xT (R−1x +2ωI)x
2 dx
= (−1)n
(2π)L/2
√
det(Rx)
√
det
[(
R−1x + 2ωI
)−1]
= (−1)n√
det(I+2ωRx)
.
(4.28)
35
Substituindo o resultado obtido em (4.28) na equac¸a˜o (4.27), temos que:
En =
∫
. . .
∫
︸ ︷︷ ︸
N×
(−1)n√
det (I + 2ωRx)
dω . . . dω︸ ︷︷ ︸
N×
∣∣∣∣∣∣∣∣∣
ω=0
. (4.29)
Para acharmos uma soluc¸a˜o para equac¸a˜o (4.29), ter´ıamos que fazer o ca´lculo de
integrais hiper-el´ıpticas, as quais na˜o apresentam soluc¸a˜o anal´ıtica, exceto em casos
muito simples. Para que possamos resolver a equac¸a˜o (4.29), devemos fazer algumas
aproximac¸o˜es: Sejam Q e Λ duas matrizes que conte´m, respectivamente, os autove-
tores e os autovalores de Rx. Logo, podemos escrever Rx = QΛQT , onde Λ e´ uma
matriz diagonal que conte´m os autovalores de Rx. Como Q e´ ortonormal, podemos
escrever que RxQ = QΛ, e assim temos que:
(I + 2ωRx)Q = Q+ 2ω
=QΛ︷ ︸︸ ︷
RxQ = Q (I + 2ωΛ) .
Com isso, podemos concluir que os autovetores de (I + 2ωRx) coincidem com os
autovetores de Rx e os autovalores de (I + 2ωRx) sa˜o dados por 1 + 2ωλi, onde λi
e´ o i-e´simo autovalor de Rx (e o i-e´simo elemento de Λ). Como o determinante de
uma matriz e´ o produto de seus autovalores, podemos reescrever a equac¸a˜o (4.29)
da seguinte maneira:
En =
∫
. . .
∫
︸ ︷︷ ︸
N×
(−1)n√∏N
l=1 (1 + 2ωλl)
dω . . . dω︸ ︷︷ ︸
N×
∣∣∣∣∣∣∣∣∣
ω=0
, (4.30)
onde ωl , − 12λl e´ a l-e´sima raiz de det (I + 2ωRx). Usando essa definic¸a˜o na equac¸a˜o
(4.30), podemos expressar En como:
En =
∫
. . .
∫
︸ ︷︷ ︸
N×
(−1)n√(
2N∏Nl=1λl)(ω − ω1) . . . (ω − ωN)dω . . . dω
∣∣∣∣∣∣∣∣∣
ω=0
. (4.31)
Assim como a equac¸a˜o (4.29), a equac¸a˜o (4.31) na˜o apresenta soluc¸a˜o fechada. Por
isso, e´ feita uma aproximac¸a˜o em que os pares de ra´ızes adjacentes sa˜o substitu´ıdos
por suas respectivas me´dias geome´tricas (ω′q, com multiplicidade 2), tal que [36]:
ω′q = −
√
ω2q−1ω2q, (4.32)
36
para q = 1, 2, . . . , N/2. Vale notar que ω′q deve ser negativo, uma vez que ωl e´
negativo. Usando (4.32) em (4.31), temos que:
En ≈ (−1)
n√
2L∏Nl=1 λl
∫
. . .
∫
︸ ︷︷ ︸
n×
1
(ω − ω′1)(ω − ω′2) . . . (ω − ω′N
2
) dω . . . dω︸ ︷︷ ︸
n×
∣∣∣∣∣∣∣∣∣
ω=0
. (4.33)
Expandindo ℘(ω) , 1(ω−ω′1)(ω−ω′2)...(ω−ω′N
2
) em frac¸o˜es parciais, obtemos a equac¸a˜o
a seguir:
℘(ω) = A1
ω − ω′1
+ A2
ω − ω′2
+ . . .+ AN/2
ω − ω′N/2
, (4.34)
onde
Aq =
1∏N/2
j=1,j 6=q
(
ω′q − ω′j
) , (4.35)
para q = 1, . . . , N/2. Substituindo a equac¸a˜o (4.34) em (4.33), podemos reescrever
a aproximac¸a˜o para En da seguinte forma:
En ≈ (−1)n√
2L
∏N
l=1 λl
∫
. . .
∫
︸ ︷︷ ︸
n×
(
A1
ω−ω′1 + . . .+
AN
2
ω−ω′N
2
)
dω . . . dω︸ ︷︷ ︸
n×
∣∣∣∣∣∣∣∣∣
ω=0
, (4.36)
onde A1, . . . , AN
2
sa˜o dados pela equac¸a˜o (4.35). Com o resultado obtido na equac¸a˜o
(4.36) podemos calcular En explicitamente para n = 1, 2, 3, como mostrado a seguir:
E¯1 ≈ Γ1
∫  A1
ω − ω′1
+ · · ·+
AN
2
ω − ω′N
2
 dω
∣∣∣∣∣∣
ω=0
= Γ1
N/2∑
l=1
Alln (ω − ω′l)
∣∣∣∣∣∣
ω=0
= Γ1
N/2∑
l=1
Alln (−ω′l) ,
onde
E¯2 ≈ Γ2
∫∫  A1
ω − ω′1
+ . . .+
AN
2
ω − ω′N
2
 dωdω
∣∣∣∣∣∣
ω=0
= Γ2
N/2∑
l=1
Al [ω′l − ω − ω′lln (ω − ω′l) + ωln (ω − ω′l)]
∣∣∣∣∣∣
ω=0
= Γ2
N/2∑
l=1
Al [ω′l − ω′lln (−ω′l)] ,
37
e
E¯3≈Γ3
∫∫∫ A1
ω − ω′1
+ · · ·+
AN
2
ω − ω′L
2
 dωdωdω
∣∣∣∣∣∣
ω=0
=Γ3
N/2∑
l=1
Al
[
ω′2
l
ln(ω−ω′l)
2 +
3ω′
l
ω
2 +
ω2ln(ω−ω′l)
2 −
3ω′2
l
4
−ω′lωln(ω−ω′l)
]∣∣∣
ω=0
= Γ3
N/2∑
l=1
Al
[
ω′2l ln (−ω′l)
2 −
3 (ω′l)
2
4
]
.
Cabe-nos ainda obter um resultado anal´ıtico para o termo E[fρ[wi(k)]]. Para
tanto, seja µi,k e σ2i,k a me´dia e a variaˆncia de w˜i(k), respectivamente. Como wi(k) =
woi−w˜i(k), e woi e´ determin´ıstico, podemos observar que a variaˆncia de wi(k) tambe´m
e´ dada por σ2i,k, e a me´dia de wi(k) e´ dada por µi,k = woi − µi,k.
Portanto, aplicando a hipo´tese H4, podemos escrever a equac¸a˜o para E {fρ[wi(k)]}
da seguinte forma [11]:
E [fρ (wi(k))] = 1√2πσi,k
∫∞
−∞ fρ [wi(k)] e
− (wi(k)−µi,k)
2
2σ2i,k dwi(k)
= ρ
2σi,k√
2π
e
−(µi,k+1ρ)2
2σ2
i,k − e
−(µi,k− 1ρ)2
2σ2
i,k

+ρ
2µi,k
2
[
erf
(
µi,k+ 1ρ√
2σi,k
)
− erf
(
µi,k− 1ρ√
2σi,k
)]
+ρ2
[
erf
(
µi,k+ 1ρ√
2σi,k
)
+erf
(
µi,k− 1ρ√
2σi,k
)
−2erf
(
µi,k√
2σi,k
)]
,
(4.37)
onde erf(x) , 2√
π
∫ x
0 e
−t2dt.
4.4 Conclusa˜o
Na primeira sec¸a˜o deste cap´ıtulo apresentou-se o me´todo de ana´lise a ser
utilizado, bem como as hipo´teses necessa´rias para o desenvolvimento da ana´lise. Na
segunda sec¸a˜o foram apresentadas observac¸o˜es acerca das hipo´teses a serem seguidas.
Na terceira sec¸a˜o e´ apresentado o desenvolvimento dos algoritmos estudados e, enta˜o,
desenvolvidas as equac¸o˜es necessa´rias para a criac¸a˜o do modelo proposto e posterior
comparac¸a˜o com o modelo emp´ırico.
38
Cap´ıtulo 5
Resultados
Para avaliar a adequac¸a˜o do modelo estoca´stico proposto neste trabalho ao
caso real, foram feitas diversas simulac¸o˜es, nas quais um filtro adaptativo tenta
identificar uma dentre as func¸o˜es de transfereˆncia descritas pelos primeiros N coefi-
cientes de [38]. Algumas dessas func¸o˜es de transfereˆncia possuem coeficientes muito
pequenos, enta˜o um fator de escalonamento α foi utilizado. O filtro adaptativo pos-
sui o mesmo comprimento N e o sinal de entrada e´ gerado passando um sinal branco
e gaussiano por um filtro de colorimento com func¸a˜o de transfereˆncia:
H(z) = 1− 0, 6z + 0, 2z−1 − 0, 3z−2. (5.1)
Primeiro, foram feitas simulac¸o˜es para avaliar o comportamento transiente dos al-
goritmos.
Para um primeiro exemplo, foi utilizado o modelo 1 de [38] com N = 12,
α = 1, 100 me´dias de Monte Carlo, β = 10−3, δ = 10−6, σ2ν = 10−6, κ = 10−9
e ρ = 20, tanto para o caso na˜o-normalizado quanto para o caso normalizado.
A Figura 5.1 mostra a evoluc¸a˜o do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.2
mostra a evoluc¸a˜o do algoritmo ℓ0-sign-NLMS, e e´ poss´ıvel perceber que para ambos
os casos o modelo proposto consegue rastrear o comportamento do filtro real tanto
no caso do MSE quanto no caso do MSD.
Em um segundo exemplo, foi observado o comportamento do sistema quando
β varia a cada iterac¸a˜o. Foi utilizado o modelo 6 de [38] com N = 12, α = 100,
100 me´dias de Monte Carlo, δ = 10−6, σ2ν = 10−6, κ = 10−9 e ρ = 20, tanto para
o caso na˜o-normalizado quanto para o caso normalizado. A Figura 5.3(a) mostra
39
1000 2000 3000 4000
−40
−20
1000 2000 3000 4000
−40
−30
−20
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
M
SE
(d
B)
M
SD
(d
B)
Figura 5.1: Desempenho do algoritmo ℓ0-sign-LMS. Emp´ırico (em azul) e teo´rico
(em vermelho). (a) MSE (dB); (b) MSD (dB).
a evoluc¸a˜o do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.4(a) mostra a evoluc¸a˜o
do algoritmo ℓ0-sign-NLMS, com β variando conforme a Figura 5.3(b), e podemos
observar que mesmo quando β varia ao longo do tempo o modelo teo´rico consegue
rastrear o resultado experimental.
Em um terceiro exemplo, foi observado o comportamento do sistema quando
σ2ν varia a cada iterac¸a˜o. Foi utilizado o modelo 8 de [38] com N = 12, α = 1, 100
me´dias de Monte Carlo, β = 10−3, δ = 10−6, κ = 10−9 e ρ = 20, tanto para o
caso na˜o-normalizado quanto para o caso normalizado. A Figura 5.5(a) mostra a
evoluc¸a˜o do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.6(a) mostra a evoluc¸a˜o do
algoritmo ℓ0-sign-NLMS, com σ2ν variando conforme a Figura 5.5(b). Assim como
nos exemplos anteriores, vemos que o modelo estoca´stico proposto se adequa bem ao
resultado experimental, ratificando que a ana´lise e´ va´lida mesmo quando a variaˆncia
do ru´ıdo na˜o e´ constante.
Em um quarto exemplo, foi observado o comportamento do sistema para
40
1 2 3 4
x 104
−40
−20
1 2 3 4
x 104
−60
−40
−20
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
M
SE
(d
B)
M
SD
(d
B)
Figura 5.2: Desempenho do algoritmo ℓ0-sign-NLMS. Emp´ırico (em azul) e teo´rico
(em vermelho). (a) MSE (dB); (b) MSD (dB).
κ = 10−10, κ = 10−8 e κ = 10−7. Foi utilizado o modelo 6 de [38] com N = 12, α =
100, δ = 10−6, σ2ν = 10−6, β = 10−3 e ρ = 20, tanto para o caso na˜o-normalizado
quanto para o caso normalizado. A Figura 5.7(a) mostra a evoluc¸a˜o do algoritmo ℓ0-
sign-LMS, enquanto a Figura 5.8(a) mostra a evoluc¸a˜o do algoritmo ℓ0-sign-NLMS.
As figuras 5.7(b) e 5.8(b) mostram um “zoom” em uma regia˜o de interesse das
figuras 5.7(a) e 5.8(a). Neste exemplo, vale notar que no caso do algoritmo na˜o-
normalizado a variac¸a˜o do paraˆmetro κ na˜o altera muito nem a convergeˆncia nem
o erro quadra´tico me´dio em regime permanente. Ja´ no caso normalizado, podemos
observar que aumentando o κ de 10−10 para 10−7 o sistema converge mais devagar.
Por fim, foram feitas simulac¸o˜es para avaliar o comportamento em regime
permanente dos algoritmos.
Em um quinto exemplo, foi observado o comportamento do sistema em regime
permanente para diversos valores de β. Para essa simulac¸a˜o, foi utilizado o modelo
4 de [38] com N = 12, α = 10, 10 me´dias de Monte Carlo, δ = 10−6, σ2ν = 10−6, κ =
41
1000 2000 3000 4000 5000 6000 7000
−40
−20
1000 2000 3000 4000 5000 6000 7000
5
10 x 10
−4
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
M
SE
(d
B)
β
Figura 5.3: (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-LMS com β variando.
Emp´ırico (em azul) e teo´rico (em vermelho).(b) Comportamento de β ao longo das
iterac¸o˜es.
10−9 e ρ = 20, tanto para o caso na˜o-normalizado quanto para o caso normalizado.
A Figura 5.9 mostra a evoluc¸a˜o do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.10
mostra a evoluc¸a˜o do algoritmo ℓ0-sign-NLMS, sendo poss´ıvel perceber que, para
ambos os casos, o modelo proposto consegue prever o MSE e o MSD com precisa˜o
maior quando β e´ pequeno, o que e´ coerente com o fato de que o teorema de Price
e´ mais acurado quando o valor de β e´ baixo [39, 40].
Em um sexto exemplo, foi observado o comportamento do sistema em regime
permanente para diversos valores de κ. Para essa simulac¸a˜o, foi utilizado o modelo
5 de [38] com N = 12, α = 10, 10 me´dias de Monte Carlo, δ = 10−6, σ2ν = 10−6, β =
10−3 e ρ = 20, tanto para o caso na˜o-normalizado quanto para o caso normalizado.
A Figura 5.11 mostra a evoluc¸a˜o do algoritmo ℓ0-sign-LMS, enquanto a Figura
5.12 mostra a evoluc¸a˜o do algoritmo ℓ0-sign-NLMS. Neste exemplo, e´ interessante
notar que, em regime permanente, enquanto para o caso na˜o-normalizado o modelo
42
0.5 1 1.5 2 2.5 3 3.5
x 104
−60
−40
−20
0.5 1 1.5 2 2.5 3 3.5
x 104
5
10 x 10
−4
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
M
SE
(d
B)
β
Figura 5.4: (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-NLMS com β variando.
Emp´ırico (em azul) e teo´rico (em vermelho).(b) Comportamento de β ao longo das
iterac¸o˜es.
proposto se adequa melhor para valores de κ pequenos, para o caso normalizado o
modelo se adequa melhor para valores de κ maiores.
Em um se´timo exemplo, foi observado o comportamento do sistema em regime
permanente para diversos valores de ρ. Para essa simulac¸a˜o, foi utilizado o modelo 4
de [38] com N = 12, α = 10, 10 me´dias de Monte Carlo, δ = 10−6, κ = 10−9, tanto
para o caso na˜o-normalizado quanto para o caso normalizado. A Figura 5.13 mostra
a evoluc¸a˜o do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.14 mostra a evoluc¸a˜o
do algoritmo ℓ0-sign-NLMS, sendo poss´ıvel perceber que, para ambos os casos, o
modelo proposto consegue prever o MSE e o MSD em regime permanente. Curioso
notar que o erro em regime permanente na˜o apresenta variac¸a˜o com a magnitude de
ρ para a func¸a˜o de transfereˆncia utilizada.
Pelas simulac¸o˜es apresentadas neste cap´ıtulo, podemos observarque o modelo
proposto consegue prever com razoa´vel acura´cia as me´tricas de desempenho. Vale
43
1000 2000 3000 4000
−38
−36
−34
−32
−30
−28
1000 2000 3000 4000
−50
−40
−30
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
M
SE
(d
B)
σ
2 ν
Figura 5.5: (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-LMS com σ2ν variando.
Emp´ırico (em azul) e teo´rico (em vermelho).(b) Comportamento de σ2ν ao longo das
iterac¸o˜es.
notar tambe´m que o modelo e´, em geral, mais acurado para o caso na˜o-normalizado
e apresenta melhor desempenho para valores pequenos de β e κ.
44
2000 4000 6000 8000 100001200014000
−40
−30
2000 4000 6000 8000 100001200014000
−50
−40
−30
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
M
SE
(d
B)
σ
2 ν
Figura 5.6: (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-NLMS com σ2ν variando.
Emp´ırico (em azul) e teo´rico (em vermelho).(b) Comportamento de σ2ν ao longo das
iterac¸o˜es.
45
1000 2000 3000 4000 5000 6000 7000
−30
−20
−10
960 980 1000 1020 1040
−30
−28
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
M
SE
(d
B)
M
SE
(d
B)
Figura 5.7: (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-LMS para κ = 10−10, κ =
10−7. Emp´ırico (em azul, com 10000 me´dias de Monte Carlo) e teo´rico (em verme-
lho).(b) “Zoom” na regia˜o de interesse demarcada por um retaˆngulo em (a).
46
0.5 1 1.5 2 2.5 3 3.5
x 104
−50
−40
−30
−20
−10
1.45 1.5 1.55 1.6 1.65
x 104
−50
−45
−40
Nu´mero de Iterac¸o˜es
Nu´mero de Iterac¸o˜es
(a)
(b)
κ = 10−10
κ = 10−7
M
SE
(d
B)
M
SE
(d
B)
Figura 5.8: (a) Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-NLMS para κ =
10−10, κ = 10−7. Emp´ırico (em azul, com 2500 me´dias de Monte Carlo) e teo´rico
(em vermelho).(b) “Zoom” na regia˜o de interesse demarcada por um retaˆngulo em
(a).
47
2 4 6 8 10
x 10−4
−50
−40
2 4 6 8 10
x 10−4
−55
−50
−45
β
β
(a)
(b)
M
SE
(d
B)
M
SD
(d
B)
Figura 5.9: Desempenho do algoritmo ℓ0-sign-LMS em regime permanente para
diferentes valores de β. Emp´ırico (em azul) e teo´rico (em vermelho). (a) MSE (dB);
(b) MSD (dB).
48
2 4 6 8 10
x 10−4
−58
−56
2 4 6 8 10
x 10−4
−70
−65
−60
β
β
(a)
(b)
M
SE
(d
B)
M
SD
(d
B)
Figura 5.10: Desempenho do algoritmo ℓ0-sign-NLMS em regime permanente para
diferentes valores de β. Emp´ırico (em azul) e teo´rico (em vermelho). (a) MSE (dB);
(b) MSD (dB).
49
2 4 6 8 10
x 10−6
−38
−36
−34
−32
−30
−28
2 4 6 8 10
x 10−6
−40
−30
κ
κ
(a)
(b)
M
SE
(d
B)
M
SD
(d
B)
Figura 5.11: Desempenho do algoritmo ℓ0-sign-LMS em regime permanente para
diferentes valores de κ. Emp´ırico (em azul) e teo´rico (em vermelho). (a) MSE (dB);
(b) MSD (dB).
50
2 4 6 8 10
x 10−6
−50
−40
−30
2 4 6 8 10
x 10−6
−60
−40
−20
κ
κ
(a)
(b)
M
SE
(d
B)
M
SD
(d
B)
Figura 5.12: Desempenho do algoritmo ℓ0-sign-NLMS em regime permanente para
diferentes valores de κ. Emp´ırico (em azul) e teo´rico (em vermelho). (a) MSE (dB);
(b) MSD (dB).
51
0 5 10 15 20
−40
−35
−30
−25
−20
−15
ρ
σ
ν2 = 10
−2
σ
ν2 = 10
−3
σ
ν2 = 10
−4
M
SE
(d
B)
Figura 5.13: Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-LMS em regime permanente
para diferentes valores de ρ e para σ2ν = 10−2, σ2ν = 10−3 e σ2ν = 10−4.
52
0 5 10 15 20
−40
−35
−30
−25
−20
−15
ρ
σ
ν2 = 10
−2
σ
ν2 = 10
−3
σ
ν2 = 10
−4
M
SE
(d
B)
Figura 5.14: Evoluc¸a˜o do MSE para o algoritmo ℓ0-sign-NLMS em regime perma-
nente para diferentes valores de ρ e para σ2ν = 10−2, σ2ν = 10−3 e σ2ν = 10−4.
53
Cap´ıtulo 6
Conclusa˜o
Com o objetivo de desenvolver um modelo capaz de prever o comportmento
dos algoritmos ℓ0-sign-LMS e ℓ0-sign-NLMS, no Cap´ıtulo 2 foi feita uma breve re-
visa˜o sobre filtragem adaptativa, mostrando-se uma configurac¸a˜o usada para identi-
ficac¸a˜o de sistemas e os algoritmos que precederam os algoritmos em ana´lise. Ja´ no
Cap´ıtulo 3 foi feita uma revisa˜o sobre sistemas esparsos e algoritmos que tentavam
explorar essa caracter´ıstica, dentre eles algoritmos proporcionais e os da famı´lia ℓ0.
No Cap´ıtulo 4, foi desenvolvido um modelo para prever o comportamento dos
algoritmos ℓ0-sign-LMS e ℓ0-sign-NLMS por meio do ca´lculo recursivo da matriz de
autocorrelac¸a˜o dos desvios, levando em considerac¸a˜o duas das principais me´tricas
de desempenho utilizadas em processamento de sinais, o MSE e o MSD. Uma vez
proposto o modelo, no Cap´ıtulo 5 e´ feita uma comparac¸a˜o entre os modelos teo´rico
e pra´tico por meio de simulac¸o˜es.
Com base nas simulac¸o˜es apresentadas no Cap´ıtulo 5, poˆde-se observar que
o modelo teo´rico mostrou-se capaz de prever o comportamento dos algoritmos es-
tudados ao longo deste trabalho de maneira satisfato´ria, prevendo a evoluc¸a˜o das
me´tricas de desmpenho adequadamente tanto para o caso na˜o-normalizado (ℓ0-sign-
LMS) quanto para o caso normalizado (ℓ0-sign-NLMS), sem apresentar restric¸o˜es
quanto ao sinal de entrada ser branco e a` variaˆncia do ru´ıdo ser constante. Pore´m,
observamos uma limitac¸a˜o, para o caso normalizado, quanto ao valor de β, o qual
deve ser suficientemente pequeno, mas que vai de acordo com as observac¸o˜es feitas
em [39, 40].
54
Refereˆncias Bibliogra´ficas
[1] S. Al-Sayed, A. M. Zoubir, and A. H. Sayed, “Robust adaptation in impulsive
noise,” IEEE Transactions on Signal Processing, vol. 64, pp. 2851–2865, June
2016.
[2] P. Stoica, G. Liu, J. Li, and E. G. Larsson, “Nonparametric spectral analysis of
gapped data via an adaptive filtering approach,” Circuits, Systems and Signal
Processing, vol. 20, pp. 485–496, Sept 2001.
[3] B. Dickinson, “Adaptive filters: Structures, algorithms, and applications,”
IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 33,
pp. 1345–1345, Oct 1985.
[4] N. V. Thakor and Y. S. Zhu, “Applications of adaptive filtering to ecg analysis:
noise cancellation and arrhythmia detection,” IEEE Transactions on Biomedi-
cal Engineering, vol. 38, pp. 785–794, Aug 1991.
[5] M. L. Honig and D. G. Messerschmitt, Adaptive filters: structures, algorithms
and applications, vol. 1. Springer, 1984.
[6] S. S. Haykin, Adaptive filter theory. Pearson Education India, 2008.
[7] D. T. M. Slock, “On the convergence behavior of the lms and the normalized lms
algorithms,” IEEE Transactions on Signal Processing, vol. 41, pp. 2811–2825,
Sep 1993.
[8] A. H. Sayed, Adaptive filters. John Wiley & Sons, 2011.
[9] G. Gui and L. Xu, “Regularization parameter selection method for sign lms with
reweighted ℓ1-norm constraint algorithm,” arXiv preprint arXiv:1503.03608,
Apr 2015.
55
[10] M. S. Mohammed and K. Ki-Seong, “Sign least mean squares-based decon-
volution technique for ultrasonic testing,” Russian Journal of Nondestructive
Testing, vol. 48, pp. 609–613, Oct 2012.
[11] K. da S. Olinto, D. B. Haddad, and M. R. Petraglia, “Transient analysis of
l0-lms and l0-nlms algorithms,” Signal Processing, vol. 127, pp. 217 – 226, Jan
2016.
[12] R. K. Martin, W. A. Sethares, R. C. Williamson, and C. R. Johnson, “Ex-
ploiting sparsity in adaptive filters,” IEEE Transactions on Signal Processing,
vol. 50, pp. 1883–1894, Aug 2002.
[13] J. Homer, “Detection guided nlms estimation of sparsely parametrized chan-
nels,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal
Processing, vol. 47, pp. 1437–1442, Dec 2000.
[14] D. L. Duttweiler, “Proportionate normalized least-mean-squares adaptation in
echo cancelers,” IEEETransactions on Speech and Audio Processing, vol. 8,
pp. 508–518, Sep 2000.
[15] D. B. Haddad and M. R. Petraglia, “Transient and steady-state mse analysis
of the impnlms algorithm,” Digital Signal Processing, vol. 33, pp. 50 – 59, July
2014.
[16] L. R. Vega, H. Rey, J. Benesty, and S. Tressens, “A family of robust algorithms
exploiting sparsity in adaptive filters,” IEEE Transactions on Audio, Speech,
and Language Processing, vol. 17, pp. 572–581, May 2009.
[17] Y. Gu, J. Jin, and S. Mei, “l0 norm constraint lms algorithm for sparse system
identification,” IEEE Signal Processing Letters, vol. 16, pp. 774–777, Sept 2009.
[18] Y. Yu, H. Zhao, and B. Chen, “Sparse normalized subband adaptive filter
algorithm with l0-norm constraint,” Journal of the Franklin Institute, vol. 353,
pp. 5121 – 5136, Sept 2016.
[19] G. Su, J. Jin, Y. Gu, and J. Wang, “Performance analysis of ℓ0 norm constraint
least mean square algorithm,” IEEE Transactions on Signal Processing, vol. 60,
pp. 2223–2235, May 2012.
56
[20] N. Kalouptsidis, G. Mileounis, B. Babadi, and V. Tarokh, “Adaptive algorithms
for sparse system identification,” Signal Processing, vol. 91, pp. 1910 – 1919,
Feb 2011.
[21] M. Fukumoto, S. Saiki, et al., “An improved mu-law proportionate nlms algo-
rithm,” in 2008 IEEE International Conference on Acoustics, Speech and Signal
Processing, pp. 3797–3800, IEEE, March 2008.
[22] S. L. Gay, “An efficient, fast converging adaptive filter for network echo cancel-
lation,” in Signals, Systems &amp; Computers, 1998. Conference Record of the
Thirty-Second Asilomar Conference on, vol. 1, pp. 394–398, IEEE, Nov 1998.
[23] H. Deng and M. Doroslovacki, “Proportionate adaptive algorithms for network
echo cancellation,” IEEE Transactions on Signal Processing, vol. 54, pp. 1794–
1803, Apr 2006.
[24] S. C. Douglas and W. Pan, “Exact expectation analysis of the lms adaptive
filter,” IEEE Transactions on Signal Processing, vol. 43, pp. 2863–2871, Dec
1995.
[25] T. Y. Al-Naffouri and A. H. Sayed, “Transient analysis of adaptive filters with
error nonlinearities,” IEEE Transactions on Signal Processing, vol. 51, pp. 653–
663, March 2003.
[26] P. S. R. Diniz, “Adaptive filtering: algorithms and practical implementation,”
The international series in Engineering and Computer Scienc, 2008.
[27] J. Rickard and J. Zeidler, “Second-order output statistics of the adaptive line
enhancer,” IEEE Transactions on Acoustics, Speech, and Signal Processing,
vol. 27, pp. 31–39, Feb 1979.
[28] B. Widrow and S. D. Stearns, “Adaptive signal processing,” Printice Hall, New
Jersey, 1985.
[29] C. Samson and V. Reddy, “Fixed point error analysis of the normalized ladder
algorithm,” IEEE Transactions on Acoustics, Speech, and Signal Processing,
vol. 31, pp. 1177–1191, Oct 1983.
57
[30] S. Werner, M. L. De Campos, and P. S. Diniz, “Partial-update nlms algorithms
with data-selective updating,” IEEE Transactions on Signal Processing, vol. 52,
pp. 938–949, April 2004.
[31] K. T. Wagner and M. I. Doroslovacki, “Towards analytical convergence analysis
of proportionate-type nlms algorithms,” in Acoustics, Speech and Signal Proces-
sing, 2008. ICASSP 2008. IEEE International Conference on, pp. 3825–3828,
IEEE, March 2008.
[32] N. J. Bershad, E. Eweda, and J. C. Bermudez, “Stochastic analysis of the lms
and nlms algorithms for cyclostationary white gaussian inputs,” IEEE Tran-
sactions on Signal Processing, vol. 62, pp. 2238–2249, May 2014.
[33] R. Price, “A useful theorem for nonlinear devices having gaussian inputs,” IRE
Transactions on Information Theory, vol. 4, pp. 69–72, June 1958.
[34] E. Eweda, “Analysis and design of a signed regressor lms algorithm for statio-
nary and nonstationary adaptive filtering with correlated gaussian data,” IEEE
Transactions on Circuits and Systems, vol. 37, pp. 1367–1374, Nov 1990.
[35] E. M. Lobato, O. J. Tobias, and R. Seara, “Stochastic model for the nlms algo-
rithm with correlated gaussian data,” in 2006 IEEE International Conference
on Acoustics Speech and Signal Processing Proceedings, vol. 3, pp. III–III, IEEE,
Jul 2006.
[36] J. E. Kolodziej, O. J. Tobias, and R. Seara, “Stochastic analysis of the modified
dnlms algorithm for gaussian data,” in 2006 International Telecommunications
Symposium, pp. 929–934, Sept 2006.
[37] E. M. Lobato, O. J. Tobias, and R. Seara, “Stochastic modeling of the
transform-domain ε-lms algorithm,” IEEE Transactions on Signal Processing,
vol. 56, pp. 1840–1852, May 2008.
[38] I. TSG, “15, digital network echo cancellers (recommendation),” tech. rep.,
Tech. Rep. G. 168, ITU-T, 2004.
58
[39] E. V. Papoulis and T. Stathaki, “A normalized robust mixed-norm adaptive
algorithm for system identification,” IEEE Signal Processing Letters, vol. 11,
pp. 56–59, Jan 2004.
[40] V. Mathews and S. Cho, “Improved convergence analysis of stochastic gradient
adaptive filters using the sign algorithm,” IEEE Transactions on Acoustics,
Speech, and Signal Processing, vol. 35, pp. 450–454, Apr 1987.
59