Algoritmos
-
Upload
deiner-zapata-silva -
Category
Documents
-
view
9 -
download
0
description
Transcript of Algoritmos
-
4o Ingeniera de Telecomunicacion
Tema 6: Filtrado Optimo y Filtrado Adaptativo
I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Indice
1 Introduccion
2 Filtro de Wiener
3 Algoritmo Maximo Descenso
4 LMS
5 Aplicaciones
6 Extensiones
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Introduccion
Filtrado optimo (filtro de Wiener)1 A partir de una entrada, x[n], consideramos el problema de como
disenar un filtro FIR cuya salida se aproxime a una senal deseada,d[n]
2 Hacemos un formulacion estocastica: El objetivo es minimizar elerror cuadratico medio (MSE) entre la senal deseada y la salidadel filtro
3 El filtro optimo se calcula resolviendo las ecuaciones normales(solo son necesarios los estadsticos de segundo orden): solucionbloque o batch
Filtrado adaptativo1 Algoritmos que actualizan los coeficientes del filtro con cada nueva
observacion de d[n] (operan muestra a muestra)2 El mas popular es el algoritmo Least Mean Square (LMS)3 Permiten adaptarse a cambios en la estadstica de las senales
involucradas (e.g, senales no estacionarias)
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Indice
1 Introduccion
2 Filtro de Wiener
3 Algoritmo Maximo Descenso
4 LMS
5 Aplicaciones
6 Extensiones
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Filtro de Wiener
( )W z[ ]x n
[ ]d n
Entrada
[ ]y nSalida
Referencia
+
[ ]e n
Error
Filtro de Wiener
Los coeficientes del filtro W (z) secalculan para minimizar lavarianza (potencia) del error
Minimizar E[(e[n])2
]
Norbert Wiener (1894-1964)
432 NOTICES OF THE AMS VOLUME 42, NUMBER 4
Wiener became acquainted with Volterras The-ory of integral equations, Osgoods Theory offunctions, Lebesgues book on the theory of in-tegration, and Frchets treatise on the theory offunctionals. Wiener claims that For the firsttime I began to have a really good understand-ing of modern mathematics.
In 1919, after many odd jobs as far afield asjournalism and engineering, Wieners nomadicexistence ended. Professor Osgood at Harvardobtained for Norbert an instructorship at MIT.Whether MITs decision to hire Wiener wasguided by phenomenal insider information orwas just a fortuitous product of the old boy net-work, there can be no doubt that Wieners ap-pointment was a gamble which paid off for bothparties! Wiener remained at MIT until his re-tirement in 1960, and during that period he notonly put MIT on the map mathematically, but he
also played a profound part in the creation ofthe culture to which MIT owes much of its pre-sent fame and prestige.
Mathematical Work at MITDuring his first dozen years at MIT, Wiener madehis most astounding contributions to pure math-ematics: He constructed Brownian motion, laida new foundation for potential theory, and in-vented his generalized harmonic analysis.
The history of Brownian motion has takensome interesting twists and turns. The namehonors the nineteenth century botanist RobertBrown, who reported that pollen and many typesof inorganic particles suspended in water per-form a strange St. Vitus dance. Brown refutedsome facile explanations of this motion, al-though debate still raged over whether the move-ment was of biological origin. It was Einsteinsfamous 1905 article on the subject that cata-pulted Brownian motion into twentieth centuryphysics. Einstein showed that a molecular (as op-posed to a continuum) model of water predictsthe existence of the phenomenon that Brown ob-served. Interestingly, he predicted Brownian mo-tion before learning about Browns observa-tions.1
Because it is virtually impossible to solveNewtons equations of motion for anything likethe number of particles in a drop of water, Ein-stein adopted a statistical approach and showedthat the evolution of the distribution of Brown-ian particles is governed by the heat equation.That is, the density of particles at each point fol-lows the same physical law as the temperatureat each point. Actually, from the physical pointof view, this description of Einsteins paperthrows out the baby with the wash. A physicistcannot talk about a one-size-fits-all heat equa-tion any more than a one-size-fits-all wave equa-tion; there are all-important constants whichenter any physical equation. For the wave equa-tion, the essential physical constant is the speedof light. In the case of the heat equation, thereis the diffusion constant, and it was Einsteins for-mula for the diffusion constant which won his1905 article its place in history. Namely, Einsteinexpressed the diffusion constant as the ratio of
The
MIT
Mus
eum
1 On page 17 of Dynamical theories of Brownian mo-tion (Princeton Univ. Press, 1967), Edward Nelson re-marks, It is sad to realize that despite all the hard workwhich had gone into the study of Brownian motion, Ein-stein was unaware of the existence of the phenomenon.He predicted it on theoretical grounds and formulateda correct quantitative theory of it. He quotes Einsteinas saying, My major aimwas to find facts whichwould guarantee as much as possible the existence ofatoms of definite finite size.
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Filtro optimo
( )W z[ ]x n
[ ]d n
Entrada
[ ]y nSalida
Referencia
+
[ ]e n
Error
Consideramos un filtro FIR con M coeficientesw = [w0, w1, . . . , wM1]
T
W (z) = w0 + w1z1 + w2z2 + . . .+ wM1zM+1
La salida del filtro es
y[n] =M1k=0
wkx[nk] =[w0 w1 . . . wM1
] x[n]
x[n 1]. . .
x[nM + 1]
= wTxnTema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Donde hemos definido el vector M 1xn = [x[n], x[n 1], . . . , x[nM + 1]]T
Tenga en cuenta tambien que
y[n] = wTxn = xTnw
La funcion de coste a minimizar es
J(w) = E[(e[n])2
]= E
[(d[n]wTxn
)2]=
E[(d[n])2 +
(wTxn
)2 2(wTxn)d[n]] = 2d+wTE [xnxTn ]w2wTE [xnd[n]]El termino E
[xnx
Tn
]es
E[xnx
Tn
]= E
x[n]x[n 1]. . .
x[nM + 1]
[x[n] x[n 1] . . . x[nM + 1]]
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Es decir,E[xnx
Tn
]= Rx
que es la matriz de autocorrelacion de la entrada dedimensiones M MPor otra parte, el termino E [xnd[n]] es
E [xnd[n]] = E
x[n]x[n 1]. . .
x[nM + 1]
d[n] =
rxd[0]rxd[1]. . .
rxd[M + 1]
= pque es el vector de dimensiones M 1 con la correlacioncruzada entre la entrada y la salida deseada o senal dereferencia
Funcion de coste
J(w) = 2d + wTRxw 2wTp
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
En el caso de un filtro con dos coeficientes w = [w0, w1]T la
funcion de coste queda
J(w0, w1) = 2d+[w0 w1
] [rx[0] rx[1]rx[1] rx[0]
] [w0w1
]2 [w0 w1] [ rxd[0]rxd[1]
]=
= 2d +(w20 + w
21
)rx[0] + 2w0w1rx[1] 2w0rxd[0] 2w1rxd[1]
que es un paraboloide
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Para calcular la solucion del filtro optimo tomamos derivadas enla funcion de coste e igualamos a cero
J(w) = 2Rxw 2p = 0 = Rxw = p
nuevamente hay que resolver las ecuaciones normalesrx[0] rx[1] . . . rx[M 1]rx[1] rx[0] . . . rx[M 2]
.... . . . . .
...rx[M 1] rx[M 2] . . . rx[0]
w0w1...
wM1
=
rxd[0]rxd[1]
...rxd[M + 1]
Filtro de Wiener
wopt = R1x p
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Cual es el MSE mnimo? es decir, la potencia del error para elfiltro de WienerRecordemos que la funcion de coste es
J(w) = 2d + wTRxw 2wTp
Sustituyendo wopt = R1x p en la funcion anterior tenemos
Jmin = 2d + w
ToptRxwopt 2wToptp
MSE min
Jmin = 2d wToptp
La funcion de coste podemos reescribirla como
J(w) = Jmin + (w wopt)T R (w wopt)
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Ejemplo: eliminacion de ruido
( )W z[ ] [ ]d n r n+
[ ]d n
Entrada
[ ]y nSalida
Referencia
+
[ ]e n
Error
Rx = Rd + Rn
p =[rd[0] rd[1] . . . rd[M 1]
]T= rd
w = (Rd + Rn)1
rd
Cuando M , el filtro de Wiener en el dominio de lafrecuencia en este caso queda
W () =Sd()
Sd() + Sn()
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
0[ ] sin( ) [ ]x n n r n = + + 0[ ] 2cos( )d n n = +1z
0w 1w
+
++
-[ ]y n
Cual es la autocorelacion de la entrada?
Rx =
[12 +
2 12 cos(0)
12 cos(0)
12 +
2
]
Cual es el vector de correlacion cruzada?
p =
[0
sin(0)
]
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
El filtro de Wiener eswopt = R
1x p
wopt =1
1/4 + 4 + 2 1/4 cos(0)2[
12 +
2 12 cos(0) 12 cos(0) 12 + 2] [
0sin(0)
]
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Principio de ortogonalidad
El filtro de Wiener se puede derivar, alternativamente, a travesdel principio de ortogonalidad
La solucion que minimiza el MSE es aquella en la que el error esortogonal a las observaciones (entrada del filtro)
xn = [x[n], x[n 1], . . . , x[nM + 1]]T
Principio de ortogonalidad
E [xne[n]] = 0
E[xn(d[n] xTnw)
]= 0 = Rxw = p
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
En resumen
Para derivar el filtro de Wiener necesitamos unicamente conocerestadsticos de segundo orden: autocorrelacion de la entrada ycorrelacion cruzada entre la entrada y la salida deseadaEl filtro extrae la parte de la entrada que tiene correlacion linealcon la salida deseada: si la salida esta incorrelada con laentrada el filtro de Wiener es nuloLa senal de error resultante esta incorrelada con la entrada delfiltro
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Indice
1 Introduccion
2 Filtro de Wiener
3 Algoritmo Maximo Descenso
4 LMS
5 Aplicaciones
6 Extensiones
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
El algoritmo de maximo descenso
Antes de estudiar el principal algoritmo adaptativo (LMS) vamosa plantear una forma iterativa de resolver las ecuacionesnormalesEsta tecnica se conoce como el metodo o algoritmo de maximodescenso (steepest descent)Recordemos otra vez que la funcion de coste a minimizar es
J(w) = 2d + wTRxw 2wTp
y su derivada (gradiente) con respecto a w es (eliminando elfactor de escala 2)
J(w) = Rxw pEl gradiente de una funcion particularizado en un punto w(n)indica la direccion de maximo incremento de la funcion en esepuntoUna forma de minimizar la funcion de coste es moverse en ladireccion contraria al gradiente
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Maximo descenso
w(n+ 1) = w(n) J(w) = w(n) + (pRxw(n))
(0)( ) |w wJ w =
(1)( ) |w wJ w =
(0)w
(1)w
(2)( ) |w wJ w =
(2)w
optw
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
El tamano del paso en la direccion J(w) lo controlamos conel parametro Finalmente, el algoritmo de maximo descenso se resumen enlos siguientes pasos
1 Inicializar el filtro w(0)2 For n = 0, 1, . . .
w(n+ 1) = w(n) + (pRxw(n))3 end
Fjese que el punto de convergencia satisface las ecuacionesnormales, es decir, w(n+ 1) = w(n), cuando se cumple
Rxw(n) = p
y, por lo tanto, el algoritmo se detiene cuando alcanza la solucionde WienerPara asegurar la convergencia hay que elegir un valor de suficientemente pequeno
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
ConvergenciaConvergencia del algoritmo de maximo descenso
El algoritmo de maximo descenso converge a la solucion de Wiener si elparametro del algoritmo cumple
0 2max
donde max es el maximo autovalor de la matriz Rx
Autovalores y autovectores
La matriz de autocorrelacion Rx puede decomponerse (diagonalizarse)como
Rx =Mi=1
iqiqTi = QDQ
T
donde D = diag (1, 2, . . . , M ) es una matriz diagonal que contiene losautovalores y Q es una matriz ortogonal (i.e., QTQ = I) que contiene losautovectoresEn Matlab los autovalores y autovectores se obtienen como : [Q,D]=eig(Rx);
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Consideremos un problema en el que la matriz deautocorrelacion de la entrada es
Rx =
[2 2r2r 2
]Ejemplos de convergencia
SEAL DE ENTRADABLANCA (r=0)
SEAL DE ENTRADAMUY CORRELADA (r=0.9)
1911
min
max =+
=rr
1
11
min
max =+
=rr
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Convergencia lenta y suave
BAJO ALTO
Convergencia rpida y errtica
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
0 10 20 30-0.2
0
0.2
0.4
0.6
Iterations
0w
1w
0 10 20 300.74
0.76
0.78
0.8
0.82
0.84
0.86
)(nJ
Iterations
0w
1w0 10 20
)(nJ
0 10 20 300.74
0.76
0.78
0.8
30
0
0.2
0.4
max/1 =5.0=r
max/7.1 =5.0=r
0 10 20 300
0.2
0.4
0.6
0.8
1
0 10 20 300.19
0.2
0.21
0.22
0.23
0.24
)(nJ0w
1wmax/1 =
9.0=r
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Indice
1 Introduccion
2 Filtro de Wiener
3 Algoritmo Maximo Descenso
4 LMS
5 Aplicaciones
6 Extensiones
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
El algoritmo LMS (Least Mean Square)
El algoritmo de maximo descenso es una forma iterativa deresolver las ecuaciones normales (o un sistema cualquiera deecuaciones lineales), pero NO es un algoritmo adaptativoNotese que el algoritmo de maximo descenso requiere conocero estimar Rx y p para calcular el gradiente en un punto w(n)
J(w) = Rxw(n) p
J(w) = E [xnxTn ]w(n) E [xnd[n]]Como podemos estimar Rx y p cuando solo disponemos de xny de d[n]?
J(w) = xnxTnw(n) xnd[n]que puede interpretarse como una estima instantanea delgradiente
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
El gradiente instantaneo puede reescribirse como
J(w) = xny[n] xnd[n] = xn (y[n] d[n]) = e[n]xn
es decir, J(w)=-error datoLMS
La ecuacion fundamental del LMS es, entonces
w(n+ 1) = w(n) + e[n]xn
Ventajas:Nos precisa conocer los estadsticos de la senalPermite seguir cambios en las senales involucradas (tracking)Facil implementacion y baja carga computacional (M + 1multiplicaciones y M 1 sumas por cada iteracion del algoritmo enel caso de senales reales)
Inconvenientes:La estima del gradiente es ruidosa
Tema 6: Filtrado Optimo y Filtrado Adaptativo I. Santamara
-
Introduccion Filtro de Wiener Alg. Maximo Descenso LMS Aplicaciones Extensiones
Algoritmo LMS
Inicializar w(0)For n = 0, . . .
e(n) = d(n)w(n)Txnw(n+ 1) = w(n) + e[n]xn
end
Convergencia del LMS
La convergencia del LMS ha de ser en media
lmn
E [w(n)] = wopt
y en MSE (mas restrictiva)
lmn
E [J(n)] = Cte = J()
La condicion de convergencia en media y MSE es
0