Embed Size (px)
Citation preview
ANALISE DE TRANSIENTE DOS ALGORITMOS ℓ0-SIGN-LMS
E ℓ0-SIGN-NLMS
Leonardo Oliveira dos Santos
Projeto de Graduacao apresentado ao Curso
de Engenharia Eletronica e de Computacao
da Escola Politecnica, Universidade Federal
do Rio de Janeiro, como parte dos requisitos
necessarios a obtencao 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 Politecnica - Departamento de Eletronica e de Computacao
Centro de Tecnologia, bloco H, sala H-217, Cidade Universitaria
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 mencao, reproducao parcial ou integral e a transmissao entre bibli-
otecas deste trabalho, sem modificacao de seu texto, em qualquer meio que esteja
ou venha a ser fixado, para pesquisa academica, comentarios e citacoes, desde que
sem finalidade comercial e que seja feita a referencia bibliografica completa.
Os conceitos expressos neste trabalho sao de responsabilidade do(s) autor(es).
4
DEDICATORIA
Ao meu pai Delcides.
A minha mae Monica.
Aos meus amigos do Zueira.
5
AGRADECIMENTO
Eu gostaria muito escrever um texto bonito pra mostrar o quao grato eu sou as
pessoas que percorreram comigo esse caminho tortuoso ate aqui, mas essas mesmas
pessoas sabem que me expressar nao e uma das minhas qualidades. Entao, eu queria
apenas agredecer a toda minha famılia e aos meus amigos Carlos Lordelo, Diego
Freitas, Fabio Oliveira, Felipe Feitosa, Felipe Gonzalez, Felipe Petraglia, Gabriel
Torres, Gustavo Nunes, Henrique Dias, Joao Victor, Julio 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 sao comuns nas mais diversas areas de aplicacao da filtragem
adaptativa, dentre elas controle, engenharia biomedica e cancelamento de eco. Algo-
ritmos capazes de usar essa propriedade para acelerar a convergencia e/ou melhorar
o erro em regime permanente vem ganhando cada vez mais destaque na comunidade
academica.
Motivado por essas experiencias positivas, este trabalho apresenta uma analise
teorica do transiente e do regime permanente dos algoritmos ℓ0-sign-LMS e ℓ0-sign-
NLMS, a qual e efetuada atraves do calculo recursivo da matriz de autocorrelacao dos
desvios. Durante a analise sao assumidas algumas suposicoes comuns na literatura,
embora tenha sido evitada a hipotese muito frequente de que o sinal de entrada
e branco. Ao final, sao efetuadas diversas simulacoes para avaliar o desempenho
do modelo estocastico proposto perante simulacoes computacionais dos algoritmos
adaptativos sob analise.
Palavras-Chave: filtragem adaptativa, calculo recursivo da matriz de autocorrelacao
dos desvios, ℓ0-sign-LMS, ℓ0-sign-NLMS, identificacao de sistemas esparsos, analise
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
iteracoes. (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 teorico
(em vermelho). (a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . 40
5.2 Desempenho do algoritmo ℓ0-sign-NLMS. Empırico (em azul) e teorico
(em vermelho). (a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . 41
5.3 (a) Evolucao do MSE para o algoritmo ℓ0-sign-LMS com β variando.
Empırico (em azul) e teorico (em vermelho).(b) Comportamento de
β ao longo das iteracoes. . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.4 (a) Evolucao do MSE para o algoritmo ℓ0-sign-NLMS com β variando.
Empırico (em azul) e teorico (em vermelho).(b) Comportamento de
β ao longo das iteracoes. . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5 (a) Evolucao do MSE para o algoritmo ℓ0-sign-LMS com σ2ν variando.
Empırico (em azul) e teorico (em vermelho).(b) Comportamento de
σ2ν ao longo das iteracoes. . . . . . . . . . . . . . . . . . . . . . . . . 44
5.6 (a) Evolucao do MSE para o algoritmo ℓ0-sign-NLMS com σ2ν vari-
ando. Empırico (em azul) e teorico (em vermelho).(b) Comporta-
mento de σ2ν ao longo das iteracoes. . . . . . . . . . . . . . . . . . . . 45
5.7 (a) Evolucao do MSE para o algoritmo ℓ0-sign-LMS para κ = 10−10, κ =
10−7. Empırico (em azul, com 10000 medias de Monte Carlo) e teorico
(em vermelho).(b) “Zoom” na regiao de interesse demarcada por um
retangulo em (a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
9
5.8 (a) Evolucao do MSE para o algoritmo ℓ0-sign-NLMS para κ = 10−10, κ =
10−7. Empırico (em azul, com 2500 medias de Monte Carlo) e teorico
(em vermelho).(b) “Zoom” na regiao de interesse demarcada por um
retangulo em (a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.9 Desempenho do algoritmo ℓ0-sign-LMS em regime permanente para
diferentes valores de β. Empırico (em azul) e teorico (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 teorico (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 teorico (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 teorico (em vermelho).
(a) MSE (dB); (b) MSD (dB). . . . . . . . . . . . . . . . . . . . . . . 51
5.13 Evolucao 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 Evolucao 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
Sumario
1 Introducao 13
1.1 Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Conteudo do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Filtragem Adaptativa 15
2.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Algoritmo LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Algoritmo NLMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Algoritmo Sign-error . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Identificacao de Sistemas Esparsos 22
3.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 PNLMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 ℓ0-LMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Analise de transiente 27
4.1 Metodos de analise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Alguns comentarios sobre as hipoteses . . . . . . . . . . . . . . . . . 28
4.3 Descricao dos momentos de primeira e segunda ordens . . . . . . . . 29
4.4 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5 Resultados 39
11
6 Conclusao 54
12
Capıtulo 1
Introducao
1.1 Contexto
Historicamente, a abordagem parametrica tem sido a abordagem principal
da engenharia para processamento de sinais, sendo baseada em modelos derivados
de conhecimento a priori concernente ao problema em questao. Por outro lado, a
abordagem nao-parametrica e baseada no uso de modelos mais genericos, treina-
dos para replicar comportamentos desejados usando informacoes estatısticas de um
agrupamento de dados. Filtros adaptativos sao, na verdade, baseados em uma abor-
dagem situada entre esses dois extremos [1, 2]. Quando o conhecimento previo de
um processo dinamico e de suas estatısticas e limitado, o concurso de filtros adapta-
tivos pode resultar em uma melhora no desempenho, comparativamente aos filtros
parametricos convencionais. Alem disso, eles podem oferecer outras vantagens para
o processamento de sinais. Consequentemente, filtros adaptativos estao sendo usa-
dos em diversas aplicacoes, incluindo comunicacoes, controle, robotica, biomedica,
entre outros [3, 4, 5]. Motivado por isso, este trabalho propoe 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 parametros) para o problema em questao.
13
1.2 Objetivo
O objetivo deste trabalho consiste em efetuar uma analise dos algoritmos
ℓ0-sign-LMS e ℓ0-sign-NLMS e, entao, propor um modelo estocastico 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 autocorrelacao dos desvios
dos coeficientes; (2) calcular metricas de desempenho a cada iteracao, no caso, o
erro quadratico medio (MSE, do ingles: Mean Square Error) e o desvio quadratico
medio (MSD, do ingles: Mean Square Deviation).
1.3 Metodologia
Este trabalho visa estimar o comportamento medio dos algoritmos sob analise.
Para tanto, usa o metodo do calculo recursivo da matriz de autocorrelacao dos des-
vios. Tal tecnica consiste em determinar equacoes a diferencas recursivas que con-
sigam prever o comportamento de Rw(k) = E[w(k)wT (k)], onde w(k) e o vetor
de desvio dos coeficientes adaptativos na k-esima iteracao. Estimada tal matriz
de autocorrelacao para cada iteracao, podemos inferir a evolucao das metricas de
desempenho MSE e MSD.
1.4 Conteudo do Trabalho
Este trabalho foi dividido em tres partes. Na primeira parte, formada pelos
Capıtulos 1, 2 e 3, e feita uma introducao sobre o trabalho e uma revisao 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 conclusao do trabalho.
14
Capıtulo 2
Filtragem Adaptativa
2.1 Introducao
As tecnicas de filtragem adaptativa apresentam diversas aplicacoes, dentre as
quais importa destacar: engenharia biomedica, equalizacao de canais, cancelamento
de eco e identificacao de sistemas [6]. Filtros adaptativos apresentam duas grandes
vantagens com relacao a filtros com coeficientes fixos. A primeira e que, ao contrario
de filtros com coeficientes fixos, quando se trabalha com filtros adaptativos nao e
necessario ter conhecimento previo 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 equalizacao de sistemas invariantes no tempo
quanto de sistemas variantes no tempo.
Em um algoritmo de filtragem adaptativa, os coeficientes sao atualizados
recursivamente de maneira que, apos um numero suficiente de iteracoes, o filtro
possua uma estimativa adequada do sistema de referencia. Tal atualizacao costuma
ser regida pelo calculo do gradiente de uma funcao custo estocastica, o qual e capaz
de fornecer a direcao de atualizacao engendrada pelo algoritmo adaptativo. Isto se
deve ao fato de que uma estrategia muito comum para a identificacao adaptativa
de um sistema de referencia consistir na minimizacao de uma funcao custo. Para
isso e calculado o gradiente dessa funcao, ja que o gradiente aponta para a direcao
de maior crescimento da funcao, e a atualizacao e feita no sentido contrario ao do
gradiente (pois, afinal, o objetivo consiste em minimizar uma funcao 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.
tificacao 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-esima iteracao. Cabe ressaltar que neste trabalho todos os
vetores envolvidos sao do tipo coluna. Apos um numero suficiente de iteracoes, e
esperado que y(k) seja similar ao valor de referencia d(k) = (wo)T x(k)+ν(k), sendo
wo o vetor que contem os coeficientes a serem identificados e definido por:
w(k) ,[wo
0(k) wo1(k) . . . wo
N−1(k)]T
, (2.3)
e ν(k) um ruıdo somado ao sinal de referencia, geralmente atribuıdo a erros de
medicao e/ou de modelagem.
2.2 Algoritmo LMS
O algoritmo de mınimos quadrados (LMS, do ingles 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 funcao custo apropriada, ate o seu ponto de mınimo. A funcao
16
custo a partir da qual o algoritmo LMS foi derivado e o valor quadratico medio do
erro (MSE) entre o sinal de referencia 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 adaptativos nao raro sao atuali-
zados recursivamente na direcao contraria ao do vetor gradiente da funcao custo.
Portanto, podemos escrever a equacao de atualizacao 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 funcao do erro instantaneo 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 oscilacoes, as quais degradam seu desempenho, particu-
larmente em regime permanente. Para a funcao custo MSE da equacao (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 equacao acima na equacao de atualizacao 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 equacao de atualizacao do algoritmo “Steepest Descent”. Vale no-
tar que com esse algoritmo ainda e necessario estimar caracterısticas do sinal de
entrada, como a matriz autocorrelacao 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 estacionario no sentido amplo (WSS, do ingles: Wide Sense Stacionary), e a
correlacao cruzada de d(k) com x(k), a qual tambem cumpre estimar, e definida
por pdx(k) = E[d(k)x(k)]. Por isso, no algoritmo LMS foi proposta a adocao do
17
gradiente de uma estimativa do MSE, de sorte a usar a funcao custo instantanea
FLMS[e(k)] = e2(k). Portanto, a equacao de atualizacao 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 secao, apresentaremos o algoritmo de mınimos quadrados normalizado
(NLMS, do ingles Normalized Least-Mean Squares). O funcionamento desse algo-
ritmo e muito similar ao do seu antecessor (o LMS). A principal diferenca reside no
fato de que, conforme o proprio nome revela, o termo de atualizacao dos coeficien-
tes do filtro e normalizado pela norma euclidiana (||.||2) do vetor de entrada x(k).
Essa normalizacao com relacao 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 alteracoes mais bruscas [7].
Na secao anterior, derivamos o algoritmo LMS a partir de uma funcao custo
apropriada. Como o algoritmo NLMS trata-se apenas de uma normalizacao do
termo de atualizacao do algoritmo anterior, ele possui uma equacao de atualizacao
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 divisoes por zero. E possıvel
derivar a equacao do NLMS por meio da otimizacao de uma funcao custo com
restricao. A ideia e minimizar a norma da diferenca entre os coeficientes do filtro
de referencia 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 otimizacao com restricao 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 funcao em relacao w(k + 1), basta calcular seu
gradiente em funcao 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 equacoes do erro a posteriori e substituindo w(k + 1) pelo
resultado obtido na equacao (2.14), temos:
e(k) − βe(k) = d(k) − w(k)T x(k) − λx(k)T x(k)2
= e(k) + λ||x(k)||22
(2.15)
λ = 2βe(k)||x(k)||2 (2.16)
Daı podemos concluir que a equacao de atualizacao 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, tambem 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 funcao em relacao w(k + 1), basta calcular seu
gradiente em funcao 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 equacoes do erro a posteriori e substituindo w(k + 1) pelo
resultado obtido na equacao (2.21), temos:
e(k) − β||x(k)||2e(k) = d(k) − w(k)T x(k) − λx(k)T x(k)2
= e(k) + λ||x(k)||22
(2.22)
λ = 2βe(k) (2.23)
Daı podemos concluir que a equacao de atualizacao 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 secao, sera apresentada uma variacao do algoritmo LMS, o sign-error
LMS e sua versao normalizada. Essa variacao do algoritmo LMS reduz o custo
computacional (caso escolhamos de modo apropriado o passo de aprendizagem) e
apresenta maior robustez com relacao ao ruıdo [9, 10]. A funcao custo definida para
esse algoritmo e o modulo do sinal do erro (FSIGN[e(k)] = |e(k)|). Daı podemos
20
desenvolver a equacao de atualizacao 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)T x(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 Conclusao
Neste capıtulo foi feita uma revisao sobre filtragem adaptativa, e como esta e
usada na identificacao de sistemas que e o foco deste trabalho. Tambem 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
pratica como no meio academico, e muito importante como base para os algoritmos
estudados neste trabalho.
21
Capıtulo 3
Identificacao de Sistemas Esparsos
3.1 Introducao
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 aplicacoes como canais de transmissao de televisao 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 convergencia dos algoritmos e/ou
diminuir o erro em regime permanente. Como nenhum dos algoritmos tradicionais
da famılia LMS faziam uso dessa propriedade na identificacao de sistemas, algorit-
mos conscientes da esparsidade foram desenvolvidos. Tais algoritmos sao capazes
de aproveitar a esparsidade dos sistemas de diferentes formas, seja identificando e
nao atualizando regioes inativas (isto e, com coeficientes muito proximos de zero)
[12, 13], seja propondo uma atualizacao especıfica para cada coeficiente com base em
sua magnitude (algoritmos proporcionais) [14, 15, 16], ou ainda aplicando uma pena-
lizacao 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 regularizacao
pela norma ℓ0, nesta secao e mostrada uma das primeiras derivacoes realizadas para
se utilizar a propriedade de coeficientes esparsos, que e a atualizacao proporcional
dos coeficientes (PNLMS). A principal ideia deste paradigma consiste na atualizacao
proporcional dos coeficientes consoante a sua magnitude, de acordo com a seguinte
equacao de atualizacao:
w(k + 1) = w(k) + β
xT (k)Λ(k)x(k) + δΛ(k)x(k)e(k), (3.1)
onde a matriz Λ(k) e responsavel pela ponderacao da atualizacao dos coeficientes
do filtro adaptativo.
Embora o algoritmo PNLMS apresente rapida convergencia inicial quando
comparado ao NLMS, essa taxa sofre grande reducao durante o processo de con-
vergencia. Alem disso, para o caso de respostas ao impulso nao-esparsas, a con-
vergencia 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 versao do LMS capaz de explorar a propriedade de
esparsidade na identificacao de sistemas, atraindo muito a atencao da comunidade
academica por conseguir melhorar tanto a taxa convergencia como o erro de regime
permanente em sistemas esparsos [18]. A mudanca consiste na adicao de um termo
a funcao custo do LMS que penaliza solucoes pouco esparsas, sendo esta funcao
descrita pela seguinte equacao:
Fℓ0−LMS(k) = e(k)2 + κ
βFρ[w(k)], (3.2)
onde κ e um parametro empregado para controlar a penalizacao imposta a solucoes
pouco esparsas, e a funcao Fρ[w(k)] e uma funcao diferenciavel por partes que
aproxima a norma ℓ0. Uma escolha comum na literatura para essa funcao, e que
sera usada tambem nesse trabalho, e [11, 17]:
23
Fρ [w(k)] =N−1∑
n=0
(1 − e−ρ|wn(k)|
), (3.3)
onde ρ ∈ R+ e um parametro arbitravel, o qual controla a aproximacao 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 45000
2
4
6
Numero de Iteracoes
Numero de Iteracoes(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
iteracoes. (b) Fρ[w(k)] para ρ = 2, ρ = 4, ρ = 6 e ρ = 20.
A Figura 3.1(a) mostra a evolucao dos coeficientes do filtro adaptativo ao
longo do tempo. Ja Figura 3.1(b) mostra a saıda da funcao Fρ [w(k)] que, como
podemos perceber, e condicionada ao valor de ρ escolhido. Vale notar como ρ
atua na interpretacao da funcao Fρ [w(k)] sobre quais coeficientes estao suficiente-
mente proximos de zero para serem considerados esparsos, e assim sofrerem a devida
atuacao do algoritmo adaptativo, como sera mostrado adiante.
Uma vez definida a funcao custo, e possıvel escrever a equacao de atualizacao
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 aproximacao 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 iteracao. Por isso, sera
empregada uma aproximacao de baixo custo desse gradiente: fρ [wi(k)] ≈ −∂Fρ[w(k)]∂wi(k) .
Tal aproximacao e feita utilizando a serie de McLaurin, um caso particular da serie
de Taylor, e truncando-a nos dois primeiros termos. Esse termo pode ser visto como
um termo de atracao 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 funcao fρ(x) implementa uma funcao 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
024
Numero de Iteracoes
Numero de Iteracoes(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 nao e considerado esparso.
Note que o coeficiente so sofre a penalizacao 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 penalizacao por se tratar de um coeficiente
considerado esparso.
3.4 Conclusao
Neste capıtulo foi feita uma revisao sobre identificacao de sistemas esparsos,
e foi mostrado como vem crescendo o desenvolvimento de algoritmos adaptativos
cientes dessa propriedade, tao comum em diversas aplicacoes. Tambem foram apre-
sentados os algoritmos adaptativos proporcionais e os com regularizacao de norma
ℓ0, este ultimo sendo o caso de interesse deste trabalho.
26
Capıtulo 4
Analise de transiente
4.1 Metodos de analise
A analise teorica de algoritmos adaptativos e de grande importancia, pois
cabe a ela fornecer de antemao informacoes sobre as caracterısticas e o comporta-
mento do algoritmo ao projetista. Diversas tecnicas de analises foram empregadas na
literatura ao longo dos anos, dentre as quais cumpre destacar: analise de esperanca
estatıstica exata [24], balanceamento de energia [25] e calculo recursivo da matriz de
autocorrelacao dos desvios dos coeficientes [11]. A maior parte das tecnicas tentam
estimar de maneira confiavel a evolucao de duas metricas principais de desempenho
em algoritmos adaptativos, o MSE e o MSD.
Neste trabalho, e feita uma analise dos algoritmos ℓ0-sign-LMS e ℓ0-sign-
NLMS, empregando a tecnica do calculo recursivo da matriz de autocorrelacao dos
desvios. Tal tecnica consiste em determinar equacoes a diferencas que consigam
prever o comportamento de Rw(k) , E[w(k)wT (k)], onde w(k) = wo − w(k) e o
vetor de desvio dos coeficientes adaptativos na k-esima iteracao.
Para que a analise seja possıvel, e necessario que algumas hipoteses sejam
feitas:
H1: x(k), β(k) e w(k) sao mutuamente independentes.
H2: O ruıdo aditivo ν(k), de media zero e variancia finita, e branco e ide-
pendente de x(k). Sua variancia no instante k e descrita por σ2ν(k).
H3: As seguintes aproximacoes sao necessarias para que se tenha uma solucao
27
fechada:E {wi(k)fρ [wj(k)]} ≈ E {wi(k)}E {fρ [wj(k)]}E {fρ [wi(k)] fρ [wj(k)]} ≈ E {fρ [wi(k)]}E {fρ [wj(k)]}
(4.1)
H4: A distribuicao dos coeficientes wi(k) e Gaussiana.
H5: O sinal de entrada e estacionario, gaussiano e todos os autovalores da
sua matriz de autocorrelacao sao nao nulos.
Com as hipoteses H1 e H2, podemos calcular o MSE segundo [26]:
ξ(k) , E[e2(k)
]≈ σ2
ν(k) + Tr{RxE
[w(k)wT (k)
]}, (4.2)
onde Rx = E[x(k)xT (k)] e a autocorrelacao do sinal de entrada, Tr {X} e o traco
da matriz X e σ2ν(k) e a variancia do ruıdo no instante k.
Ja o MSD pode ser calculado pela seguinte equacao:
MSD(k) , E[‖wo − w(k)‖2] = Tr{E[w(k)wT (k)]
}. (4.3)
4.2 Alguns comentarios sobre as hipoteses
Vale fazer algumas observacoes acerca das hipoteses feitas na secao anterior
e que serao utilizadas ao longo deste capıtulo. Em H1 e suposto que x(k), β(k)
e w(k) sao mutuamente idependentes. A independencia entre x(k) e w(k) e uma
propriedade conhecida como “independence assumption” e amplamente encontrada
no meio academico [27, 28, 26, 6]. Ja no que tange a independencia de β(k) com
relacao as outras variaveis aleatorias, e facil notar que para o caso do algoritmo
LMS a hipotese e verdadeira, uma vez que β e uma constante que nao depende
do valor assumido por x(k). Porem, no caso do algoritmo NLMS e preciso aplicar
o “Averaging Principle” [29] na expressao E[β(k)A], onde β(k) e A sao variaveis
aleatorias ditas conjuntamente estacionarias [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 hipotese H2, vale notar que ela reforca a linearidade entre x(k) e
d(k), o que e razoavel em diversas aplicacoes (vide [11]). Este trabalho nao fica
restrito a uma variancia do ruıdo constante como e comum na literatura, aceitando
que ela varie ao longo do tempo.
28
Embora H3 seja uma suposicao “forcada” para facilitar os calculos, mostrou-
se uma aproximacao razoavel como observado em [11].
Assim como H1, H4 e uma hipotese muito encontrada na literatura e que pode
ser justificada pelo teorema central do limite [31]. Resultados acerca da distribuicao
dos coeficientes de w(k), e que corroboram a utilizacao desta hipotese, podem ser
encontrados tambem em [11].
A hipotese H5 nao assume que o sinal de entrada seja branco, tornando o
estudo aqui feito mais abrangente do que e comumente encontrado a este respeito.
Porem, nao engloba o caso de todos os sinais coloridos, uma vez que assume-se que
todos os autovalores de Rx sao nao-nulos.
4.3 Descricao dos momentos de primeira e se-
gunda ordens
Como dito anteriormente, o foco deste trabalho e fazer uma analise dos al-
goritmos ℓ0-sign-LMS e ℓ0-sign-NLMS, criando um modelo que permita fazer uma
estimativa da evolucao das respectivas matrizes de autocorrelacao dos desvios. Por-
tanto, comecemos desenvolvendo suas equacoes de atualizacao, as quais sao uma das
contribuicoes deste trabalho.
Como ja foi dito, para explorar as caracterısticas de um sistema esparso, e
somado um termo de regularizacao a funcao custo do algoritmo com o qual se deseja
trabalhar, no caso, o sign-LMS. Logo, temos a seguinte funcao 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 funcao custo escalado por β. Logo, a equacao de atualizacao 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 equacao de atualizacao para ambos os algoritmos (cabendo no-
tar serem ambos contribuicoes deste trabalho), nossa analise consiste em estimar
29
a evolucao da matriz de autocorrelacao dos desvios. Portanto, devemos manipular
a equacao anterior substituindo w(k) por wo − w(k), de modo a encontrar uma
atualizacao 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 analise teorica possa ser feita de maneira mais simples, doravante
trabalharemos com a equacao de atualizacao na sua forma escalar, ou seja, ao inves
de calcularmos o vetor de desvio diretamente, calcularemos seus coeficientes. Entao,
devemos reescrever a equacao (4.7) da seguinte forma:
wi(k + 1) = wi(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)T x(k) + ν(k) − wT (k)x(k)
= wT (k)x(k) + ν(k)
= ∑N−1n=0 wn(k)x(k − n) + ν(k)
(4.9)
Substituindo (4.9) na equacao (4.8), temos:
wi(k+1) = wi(k)−β(k)x(k−i)sign[
N−1∑
n=0wn(k)x(k − n) + ν(k)
]−κfρ[wi(k)]. (4.10)
Uma vez definida a equacao de atualizacao dos desvios na sua forma escalar,
devemos propor uma equacao estatıstica que descreva o comportamento do algoritmo
na media, uma vez que a equacao (4.10) e uma equacao determinıstica. Portanto,
devemos aplicar o operador do valor esperado a equacao (4.10), a qual passa a ser
escrita da seguinte forma:
30
E[wi(k + 1)] = E[wi(k)]
−E[β(k)x(k − i)sign(∑N−1n=0 wn(k)x(k − n) + ν(k))]
−κE {fρ[wi(k)]} .
(4.11)
Para que possamos continuar a analise, sera aplicado o teorema de Price
[33, 34] a equacao (4.11). Tal teorema permite que escrevamos:
E[sign(A)B] =√
2πσ2
A
E[AB], (4.12)
onde A e B sao duas variaveis aleatorias conjuntamente Gaussianas e de media
zero, e σ2A = E[A2]. Portanto, utilizando o teorema de Price, podemos reescrever a
equacao (4.11) da seguinte forma:
E[wi(k + 1)] = E[wi(k)]
−√
2πσ2
eE[β(k)x(k − i)∑N−1
n=0 wn(k)x(k − n)]
+E[β(k)x(k − i)ν(k)]
−κE[fρ[wi(k)]]
(4.13)
Pela hipotese H2, podemos observar que E[β(k)x(k − i)ν(k)] = 0, logo:
E[wi(k + 1)] = E[wi(k)]
−√
2πσ2
eE[β(k)x(k − i)∑N−1
n=0 wn(k)x(k − n)]
−κE[fρ[wi(k)]]
(4.14)
Por fim, a hipotese H1 nos diz que β(k), x(k) e wi(k) sao mutuamente in-
dependentes. Portanto, utilizando H1 e a propriedade da linearidade entre os ope-
radores valor esperado e somatorio, a equacao (4.14) pode ser reescrita da seguinte
maneira:
E[wi(k + 1)] = E[wi(k)] −√
2πσ2
e
E[β(k)]N−1∑
n=0E[wn(k)]rin − κE {fρ[wi(k)]} , (4.15)
onde σ2e e a variancia do erro e rin , E[x(k − i)x(k − n)].
Para estimar a evolucao da matriz de autocorrelacao dos desvios, devemos
estimar a evolucao dos coeficientes de w(k)wT (k) na media. Com base na equacao
31
(4.10), a equacao do calculo recursivo para um coeficiente generico dessa matriz e
dada por:
wi(k + 1)wj(k + 1) = wi(k)wj(k)
−β(k)wi(k)x(k − j)sign(∑N−1n=0 wn(k)x(k − n) + ν(k))
−κwi(k)fρ[wj(k)]
−β(k)wj(k)x(k − i)sign(∑N−1n=0 wn(k)x(k − n) + ν(k))
+β(k)2x(k − i)x(k − j)sign2(∑N−1n=0 wn(k)x(k − n) + ν(k))
+κβ(k)x(k − i)sign(∑N−1n=0 wn(k)x(k − n) + ν(k))fρ[wj(k)]
−κwj(k)fρ[wi(k)]
+κβ(k)x(k − j)sign(∑N−1n=0 wn(k)x(k − n) + ν(k))fρ[wi(k)]
+κ2fρ[wi(k)]fρ[wj(k)](4.16)
Como a matriz de autocorrelacao dos desvios e calculada via E[w(k)wT (k)],
devemos aplicar o operador do valor esperado na equacao (4.16), a qual passa a ser
escrita da seguinte forma:
E[wi(k+1)wj(k+1)] = E[wi(k)wj(k)]
−E[β(k)wi(k)x(k − j)sign(∑N−1n=0 wn(k)x(k − n) + ν(k))]
−E[κwi(k)fρ[wj(k)]]
−E[β(k)wj(k)x(k − i)sign(∑N−1n=0 wn(k)x(k − n) + ν(k))]
+E[β(k)2x(k − i)x(k − j)sign2(∑N−1n=0 wn(k)x(k − n) + ν(k))]
+E[κβ(k)x(k − i)sign(∑N−1n=0 wn(k)x(k − n) + ν(k))fρ[wj(k)]]
−E[κwj(k)fρ[wi(k)]]
+E[κβ(k)x(k − j)sign(∑N−1n=0 wn(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 equacao (4.17) da se-
guinte maneira:
32
E[wi(k+1)wj(k+1)] = E[wi(k)wj(k)]
−√
2πσ2
eE[β(k)wi(k)x(k − j)(∑N−1
n=0 x(k − n)wn(k) + ν(k))]
−κE[wi(k)fρ[wj(k)]]
−√
2πσ2
eE[β(k)wj(k)x(k − i)(∑N−1
n=0 x(k − n)wn(k) + ν(k))]
+E[β(k)2x(k − i)x(k − j)]
+√
2πσ2
eκE[β(k)x(k − i)(∑N−1
n=0 wn(k)x(k − n) + ν(k))fρ[wj(k)]]
−κE[wj(k)fρ[wi(k)]]
+√
2πσ2
eκE[β(k)x(k − j)(∑N−1
n=0 wn(k)x(k − n) + ν(k))fρ[wi(k)]]
+κ2E[fρ[wi(k)]fρ[wj(k)]],(4.18)
onde tambem utilizamos o fato de que sign2(x) = 1.
Pela hipotese H2, podemos observar que E[β(k)x(k − j)ν(k)] = 0, logo:
E[wi(k + 1)wj(k + 1)] = E[wi(k)wj(k)]
−√
2πσ2
eE[β(k)wi(k)x(k − j)∑N−1
n=0 x(k − n)wn(k)]
−κE[wi(k)fρ[wj(k)]]
−√
2πσ2
eE[β(k)wj(k)x(k − i)∑N−1
n=0 x(k − n)wn(k)]
+E[β(k)2x(k − i)x(k − j)]
+√
2πσ2
eκE[β(k)x(k − i)∑N−1
n=0 wn(k)x(k − n)fρ[wj(k)]]
−κE[wj(k)fρ[wi(k)]]
+√
2πσ2
eκE[β(k)x(k − j)∑N−1
n=0 wn(k)x(k − n)fρ[wi(k)]]
+κ2E[fρ[wi(k)]fρ[wj(k)]](4.19)
A hipotese H1, nos diz que β(k), x(k) e w(k) sao mutuamente independentes.
Portanto, utilizando H1 e a propriedade da linearidade entre os operadores valor
esperado e somatorio, a equacao (4.19) pode ser reescrita da seguinte maneira:
33
E[wi(k + 1)wj(k + 1)] = E[wi(k)wj(k)]
−√
2πσ2
eE[β(k)]∑N−1
n=0 E[wi(k)wn(k)]rjn
−κE[wi(k)fρ[wj(k)]]
−√
2πσ2
eE[β(k)]∑N−1
n=0 E[wj(k)wn(k)]rin
+E[β(k)2]rij
+√
2πσ2
eκE[β(k)]∑N−1
n=0 E[wn(k)rinfρ[wj(k)]]
−κE[wj(k)fρ[wi(k)]]
+√
2πσ2
eκE[β(k)]∑N−1
n=0 E[wn(k)rjnfρ[wi(k)]]
+κ2E[fρ[wi(k)]fρ[wj(k)]]
(4.20)
Por fim, as aproximacoes descritas na hipotese H3 nos permitem reescrever
a equacao (4.20) como a seguir:
E[wi(k + 1)wj(k + 1)] = E[wi(k)wj(k)]
−√
2πσ2
eE[β(k)]∑N−1
n=0 E[wi(k)wn(k)]rjn
−κE[wi(k)]E[fρ[wj(k)]]
−√
2πσ2
eE[β(k)]∑N−1
n=0 E[wj(k)wn(k)]rin
+E[β(k)2]rij
+√
2πσ2
eκE[β(k)]∑N−1
n=0 E[wn(k)]rinE[fρ[wj(k)]]
−κE[wj(k)]E[fρ[wi(k)]]
+√
2πσ2
eκE[β(k)]∑N−1
n=0 E[wn(k)]rjnE[fρ[wi(k)]]
+κ2E[fρ[wi(k)]]E[fρ[wj(k)]]
(4.21)
Uma vez definidas as equacoes recursivas para os momentos de primeira e
segunda ordem, cabe agora empreender o calculo dos termos: E[β(k)
], E
[β2(k)
]e
E[fρ[wi(k)]]. Comecemos pelo calculo de E[β(k)
]e E
[β2(k)
]. No caso de algoritmos
nao normalizados (LMS), esses termos sao determinısticos e definidos por β e β2.
Porem, em algoritmos normalizados, o passo de aprendizagem β e modulado pela
norma euclidiana do vetor de entrada (xT x) que faz com que β(k) deixe de ser
determinıstico e seja calculado por: βE[ 1xT x+δ
]. Para realizar o calculo desse valor
esperado, utilizaremos uma aproximacao de primeira ordem de McLaurin, como
proposto em [35, 36, 37], reescrevendo E[ 1xT x+δ
] 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 calculo de E1, E2 e E3 e, para tanto, utilizaremos
a hipotese H5, que nos permite escrever En da seguinte forma:
En = 1(2π)L/2
√det(Rx)
∫ ∞
−∞. . .∫ ∞
−∞︸ ︷︷ ︸L×
1(xT x)n e− xT R−1
x x
2 dx. (4.25)
Para que possamos chegar a uma solucao analıtica para (4.25), devemos de-
finir uma funcao auxiliar Ψn(ω):
Ψn(ω) = 1(2π)L/2
√det(Rx)
∫ ∞
−∞. . .∫ ∞
−∞︸ ︷︷ ︸L×
1(xT x)n e−ωxT xe− xT R−1
x x
2 dx, (4.26)
podemos perceber que a funcao 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 equacao:
∂nΨn(ω)∂nω
= (−1)n
(2π)L/2√
det(Rx)
∫ ∞
−∞. . .∫ ∞
−∞︸ ︷︷ ︸L×
e−ωxT xe− xT R−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−1
x + 2ωI)−1
]
= (−1)n√det(I+2ωRx)
.
(4.28)
35
Substituindo o resultado obtido em (4.28) na equacao (4.27), temos que:
En =∫
. . .∫
︸ ︷︷ ︸N×
(−1)n
√det (I + 2ωRx)
dω . . . dω︸ ︷︷ ︸N×
∣∣∣∣∣∣∣∣∣ω=0
. (4.29)
Para acharmos uma solucao para equacao (4.29), terıamos que fazer o calculo de
integrais hiper-elıpticas, as quais nao apresentam solucao analıtica, exceto em casos
muito simples. Para que possamos resolver a equacao (4.29), devemos fazer algumas
aproximacoes: Sejam Q e Λ duas matrizes que contem, respectivamente, os autove-
tores e os autovalores de Rx. Logo, podemos escrever Rx = QΛQT , onde Λ e uma
matriz diagonal que contem 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) sao dados por 1 + 2ωλi, onde λi
e o i-esimo autovalor de Rx (e o i-esimo elemento de Λ). Como o determinante de
uma matriz e o produto de seus autovalores, podemos reescrever a equacao (4.29)
da seguinte maneira:
En =∫
. . .∫
︸ ︷︷ ︸N×
(−1)n
√∏Nl=1 (1 + 2ωλl)
dω . . . dω︸ ︷︷ ︸N×
∣∣∣∣∣∣∣∣∣ω=0
, (4.30)
onde ωl , − 12λl
e a l-esima raiz de det (I + 2ωRx). Usando essa definicao na equacao
(4.30), podemos expressar En como:
En =∫
. . .∫
︸ ︷︷ ︸N×
(−1)n
√(2N∏N
l=1λl
)(ω − ω1) . . . (ω − ωN)
dω . . . dω
∣∣∣∣∣∣∣∣∣ω=0
. (4.31)
Assim como a equacao (4.29), a equacao (4.31) nao apresenta solucao fechada. Por
isso, e feita uma aproximacao em que os pares de raızes adjacentes sao substituıdos
por suas respectivas medias geometricas (ω′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∏N
l=1 λl
∫. . .∫
︸ ︷︷ ︸n×
1(ω − ω′
1)(ω − ω′2) . . . (ω − ω′
N2
) dω . . . dω︸ ︷︷ ︸n×
∣∣∣∣∣∣∣∣∣ω=0
. (4.33)
Expandindo ℘(ω) , 1(ω−ω′
1)(ω−ω′2)...(ω−ω′
N2
) em fracoes parciais, obtemos a equacao
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 equacao (4.34) em (4.33), podemos reescrever
a aproximacao para En da seguinte forma:
En ≈ (−1)n√2L∏N
l=1 λl
∫. . .∫
︸ ︷︷ ︸n×
(A1
ω−ω′1
+ . . . +A N
2ω−ω′
N2
)dω . . . dω︸ ︷︷ ︸
n×
∣∣∣∣∣∣∣∣∣ω=0
, (4.36)
onde A1, . . . , AN2
sao dados pela equacao (4.35). Com o resultado obtido na equacao
(4.36) podemos calcular En explicitamente para n = 1, 2, 3, como mostrado a seguir:
E1 ≈ Γ1
∫ A1
ω − ω′1
+ · · · +AN
2
ω − ω′N2
dω
∣∣∣∣∣∣ω=0
= Γ1
N/2∑
l=1Alln (ω − ω′
l)∣∣∣∣∣∣ω=0
= Γ1
N/2∑
l=1Alln (−ω′
l) ,
onde
E2 ≈ Γ2
∫∫ A1
ω − ω′1
+ . . . +AN
2
ω − ω′N2
dωdω
∣∣∣∣∣∣ω=0
= Γ2
N/2∑
l=1Al [ω′
l − ω − ω′lln (ω − ω′
l) + ωln (ω − ω′l)]∣∣∣∣∣∣ω=0
= Γ2
N/2∑
l=1Al [ω′
l − ω′lln (−ω′
l)] ,
37
e
E3 ≈Γ3
∫∫∫ A1
ω − ω′1
+ · · · +AN
2
ω − ω′L2
dωdωdω
∣∣∣∣∣∣ω=0
=Γ3
N/2∑
l=1Al
[ω′2
lln(ω−ω′
l)2 +
3ω′lω
2 +ω2ln(ω−ω′
l)2 − 3ω′2
l4
−ω′lωln(ω−ω′
l)]∣∣∣
ω=0
= Γ3
N/2∑
l=1Al
[ω′2
l 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 media e a variancia de wi(k), respectivamente. Como wi(k) =
woi −wi(k), e wo
i e determinıstico, podemos observar que a variancia de wi(k) tambem
e dada por σ2i,k, e a media de wi(k) e dada por µi,k = wo
i − µi,k.
Portanto, aplicando a hipotese H4, podemos escrever a equacao 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σ2i,k − e
−(µi,k− 1ρ)2
2σ2i,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√π
∫ x0 e−t2
dt.
4.4 Conclusao
Na primeira secao deste capıtulo apresentou-se o metodo de analise a ser
utilizado, bem como as hipoteses necessarias para o desenvolvimento da analise. Na
segunda secao foram apresentadas observacoes acerca das hipoteses a serem seguidas.
Na terceira secao e apresentado o desenvolvimento dos algoritmos estudados e, entao,
desenvolvidas as equacoes necessarias para a criacao do modelo proposto e posterior
comparacao com o modelo empırico.
38
Capıtulo 5
Resultados
Para avaliar a adequacao do modelo estocastico proposto neste trabalho ao
caso real, foram feitas diversas simulacoes, nas quais um filtro adaptativo tenta
identificar uma dentre as funcoes de transferencia descritas pelos primeiros N coefi-
cientes de [38]. Algumas dessas funcoes de transferencia possuem coeficientes muito
pequenos, entao 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 funcao de transferencia:
H(z) = 1 − 0, 6z + 0, 2z−1 − 0, 3z−2. (5.1)
Primeiro, foram feitas simulacoes para avaliar o comportamento transiente dos al-
goritmos.
Para um primeiro exemplo, foi utilizado o modelo 1 de [38] com N = 12,
α = 1, 100 medias de Monte Carlo, β = 10−3, δ = 10−6, σ2ν = 10−6, κ = 10−9
e ρ = 20, tanto para o caso nao-normalizado quanto para o caso normalizado.
A Figura 5.1 mostra a evolucao do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.2
mostra a evolucao 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 iteracao. Foi utilizado o modelo 6 de [38] com N = 12, α = 100,
100 medias de Monte Carlo, δ = 10−6, σ2ν = 10−6, κ = 10−9 e ρ = 20, tanto para
o caso nao-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
Numero de Iteracoes
Numero de Iteracoes(a)
(b)
MSE
(dB)
MSD
(dB)
Figura 5.1: Desempenho do algoritmo ℓ0-sign-LMS. Empırico (em azul) e teorico
(em vermelho). (a) MSE (dB); (b) MSD (dB).
a evolucao do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.4(a) mostra a evolucao
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 teorico consegue
rastrear o resultado experimental.
Em um terceiro exemplo, foi observado o comportamento do sistema quando
σ2ν varia a cada iteracao. Foi utilizado o modelo 8 de [38] com N = 12, α = 1, 100
medias de Monte Carlo, β = 10−3, δ = 10−6, κ = 10−9 e ρ = 20, tanto para o
caso nao-normalizado quanto para o caso normalizado. A Figura 5.5(a) mostra a
evolucao do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.6(a) mostra a evolucao do
algoritmo ℓ0-sign-NLMS, com σ2ν variando conforme a Figura 5.5(b). Assim como
nos exemplos anteriores, vemos que o modelo estocastico proposto se adequa bem ao
resultado experimental, ratificando que a analise e valida mesmo quando a variancia
do ruıdo nao 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
Numero de Iteracoes
Numero de Iteracoes(a)
(b)
MSE
(dB)
MSD
(dB)
Figura 5.2: Desempenho do algoritmo ℓ0-sign-NLMS. Empırico (em azul) e teorico
(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 nao-normalizado
quanto para o caso normalizado. A Figura 5.7(a) mostra a evolucao do algoritmo ℓ0-
sign-LMS, enquanto a Figura 5.8(a) mostra a evolucao do algoritmo ℓ0-sign-NLMS.
As figuras 5.7(b) e 5.8(b) mostram um “zoom” em uma regiao de interesse das
figuras 5.7(a) e 5.8(a). Neste exemplo, vale notar que no caso do algoritmo nao-
normalizado a variacao do parametro κ nao altera muito nem a convergencia nem
o erro quadratico medio 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 simulacoes 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 simulacao, foi utilizado o modelo
4 de [38] com N = 12, α = 10, 10 medias 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
10x 10
−4
Numero de Iteracoes
Numero de Iteracoes(a)
(b)
MSE
(dB)
β
Figura 5.3: (a) Evolucao do MSE para o algoritmo ℓ0-sign-LMS com β variando.
Empırico (em azul) e teorico (em vermelho).(b) Comportamento de β ao longo das
iteracoes.
10−9 e ρ = 20, tanto para o caso nao-normalizado quanto para o caso normalizado.
A Figura 5.9 mostra a evolucao do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.10
mostra a evolucao 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 precisao
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 simulacao, foi utilizado o modelo
5 de [38] com N = 12, α = 10, 10 medias de Monte Carlo, δ = 10−6, σ2ν = 10−6, β =
10−3 e ρ = 20, tanto para o caso nao-normalizado quanto para o caso normalizado.
A Figura 5.11 mostra a evolucao do algoritmo ℓ0-sign-LMS, enquanto a Figura
5.12 mostra a evolucao do algoritmo ℓ0-sign-NLMS. Neste exemplo, e interessante
notar que, em regime permanente, enquanto para o caso nao-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
10x 10
−4
Numero de Iteracoes
Numero de Iteracoes(a)
(b)
MSE
(dB)
β
Figura 5.4: (a) Evolucao do MSE para o algoritmo ℓ0-sign-NLMS com β variando.
Empırico (em azul) e teorico (em vermelho).(b) Comportamento de β ao longo das
iteracoes.
proposto se adequa melhor para valores de κ pequenos, para o caso normalizado o
modelo se adequa melhor para valores de κ maiores.
Em um setimo exemplo, foi observado o comportamento do sistema em regime
permanente para diversos valores de ρ. Para essa simulacao, foi utilizado o modelo 4
de [38] com N = 12, α = 10, 10 medias de Monte Carlo, δ = 10−6, κ = 10−9, tanto
para o caso nao-normalizado quanto para o caso normalizado. A Figura 5.13 mostra
a evolucao do algoritmo ℓ0-sign-LMS, enquanto a Figura 5.14 mostra a evolucao
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 nao apresenta variacao com a magnitude de
ρ para a funcao de transferencia utilizada.
Pelas simulacoes apresentadas neste capıtulo, podemos observar que o modelo
proposto consegue prever com razoavel acuracia as metricas de desempenho. Vale
43
1000 2000 3000 4000−38−36−34−32−30−28
1000 2000 3000 4000−50
−40
−30
Numero de Iteracoes
Numero de Iteracoes(a)
(b)
MSE
(dB)
σ2 ν
Figura 5.5: (a) Evolucao do MSE para o algoritmo ℓ0-sign-LMS com σ2ν variando.
Empırico (em azul) e teorico (em vermelho).(b) Comportamento de σ2ν ao longo das
iteracoes.
notar tambem que o modelo e, em geral, mais acurado para o caso nao-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
Numero de Iteracoes
Numero de Iteracoes(a)
(b)
MSE
(dB)
σ2 ν
Figura 5.6: (a) Evolucao do MSE para o algoritmo ℓ0-sign-NLMS com σ2ν variando.
Empırico (em azul) e teorico (em vermelho).(b) Comportamento de σ2ν ao longo das
iteracoes.
45
1000 2000 3000 4000 5000 6000 7000
−30
−20
−10
960 980 1000 1020 1040
−30
−28
Numero de Iteracoes
Numero de Iteracoes(a)
(b)
MSE
(dB)
MSE
(dB)
Figura 5.7: (a) Evolucao do MSE para o algoritmo ℓ0-sign-LMS para κ = 10−10, κ =
10−7. Empırico (em azul, com 10000 medias de Monte Carlo) e teorico (em verme-
lho).(b) “Zoom” na regiao de interesse demarcada por um retangulo 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
Numero de Iteracoes
Numero de Iteracoes(a)
(b)
κ = 10−10
κ = 10−7
MSE
(dB)
MSE
(dB)
Figura 5.8: (a) Evolucao do MSE para o algoritmo ℓ0-sign-NLMS para κ =
10−10, κ = 10−7. Empırico (em azul, com 2500 medias de Monte Carlo) e teorico
(em vermelho).(b) “Zoom” na regiao de interesse demarcada por um retangulo 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)
MSE
(dB)
MSD
(dB)
Figura 5.9: Desempenho do algoritmo ℓ0-sign-LMS em regime permanente para
diferentes valores de β. Empırico (em azul) e teorico (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)
MSE
(dB)
MSD
(dB)
Figura 5.10: Desempenho do algoritmo ℓ0-sign-NLMS em regime permanente para
diferentes valores de β. Empırico (em azul) e teorico (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)
MSE
(dB)
MSD
(dB)
Figura 5.11: Desempenho do algoritmo ℓ0-sign-LMS em regime permanente para
diferentes valores de κ. Empırico (em azul) e teorico (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)
MSE
(dB)
MSD
(dB)
Figura 5.12: Desempenho do algoritmo ℓ0-sign-NLMS em regime permanente para
diferentes valores de κ. Empırico (em azul) e teorico (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
MSE
(dB)
Figura 5.13: Evolucao 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
MSE
(dB)
Figura 5.14: Evolucao 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
Conclusao
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-
visao sobre filtragem adaptativa, mostrando-se uma configuracao usada para identi-
ficacao de sistemas e os algoritmos que precederam os algoritmos em analise. Ja no
Capıtulo 3 foi feita uma revisao 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 calculo recursivo da matriz de
autocorrelacao dos desvios, levando em consideracao duas das principais metricas
de desempenho utilizadas em processamento de sinais, o MSE e o MSD. Uma vez
proposto o modelo, no Capıtulo 5 e feita uma comparacao entre os modelos teorico
e pratico por meio de simulacoes.
Com base nas simulacoes apresentadas no Capıtulo 5, pode-se observar que
o modelo teorico mostrou-se capaz de prever o comportamento dos algoritmos es-
tudados ao longo deste trabalho de maneira satisfatoria, prevendo a evolucao das
metricas de desmpenho adequadamente tanto para o caso nao-normalizado (ℓ0-sign-
LMS) quanto para o caso normalizado (ℓ0-sign-NLMS), sem apresentar restricoes
quanto ao sinal de entrada ser branco e a variancia do ruıdo ser constante. Porem,
observamos uma limitacao, para o caso normalizado, quanto ao valor de β, o qual
deve ser suficientemente pequeno, mas que vai de acordo com as observacoes feitas
em [39, 40].
54
Referencias Bibliograficas
[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,” IEEE Transactions 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 & 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
