-
Parte 3
Filtros adaptativos
3.1. Preliminar matematico
Sea R una matriz simetrica de numeros reales, o bien una matriz
hermtica de numeros complejos.Nos planteamos el siguiente sistema
de ecuaciones:
Ru = u
donde u es un vector columna y un numero, real o complejo.Esto
es equivalente a
(R I)u = 0
siendo I la matriz identidad. Para que este sistema homogeneo
tenga solucion debe exigirse que el deter-minante sea 0:
det(R I) =
R11 R12 . . . R1p
R21 R22 ...
......
...Rp1 . . . Rpp
Si los valores Rij son conocidos, al desarrollar este
determinante obtendremos un polinomio en la variable de grado p.
Las races de dicho polinomio, 1, . . . , p se llaman valores
propios de la matriz R.
Ahora volvamos al sistema de ecuaciones inicial con cada valor
propio como valor para :
Ru = iu
Al vector ui que es solucion de esta ecuacion (y tal vector
existe, dado que cualquiera de los i haca alsistema compatible) se
le llama vector propio ui asociado al valor propio i.
El teorema de descomposicion de matrices dice que, si R es una
matriz simetrica de valores reales,o bien una matriz hermtica de
valores complejos, entonces R se puede escribir como producto de
tresmatrices, R = V V H donde
V =
u1(1) u2(1) . . . up(1)...
...u1(p) u2(p) . . . up(p)
y
=
1 0 . . . 00 2 . . . 0...
... 00 0 . . . p
Es decir, la matriz V tiene a los vectores propios como columnas
y la matriz tiene los valores propiosen la diagonal principal. El
orden de ambos debe coincidir (es decir, el valor propio que
situemos en lafila i, columna i de debe generar el vector propio
que se use como columna i-esima de V). Es costumbredisponer los
valores propios ordenados de mayor a menor, desde la esquina
superior izquierda hasta lainferior derecha de la matriz .
Ademas de esto, V es unamatriz unitaria, lo cual significa que
cumple la propiedad de que V V H = I.La matriz R, como todas las
matrices, representa una aplicacion lineal, en este caso del
espacio
vectorial Rp en s mismo; de hecho, si tomamos un vector x su
vector imagen bajo la aplicacion linealsera Rx. Con el teorema de
descomposicion lo que hacemos es un cambio de base, concretamente a
la
29
-
base formada por los vectores B = {u1, u2, . . . , up} de tal
modo que la expresion en ella de la aplicaciones la matriz diagonal
. Cuando esto ocurre, hacer actuar una aplicacion lineal sobre un
vector significasimplemente multiplicar cada una de sus componentes
por una constante (distinta), pero en cualquiercaso la componente
k-esima depende solo de la correspondiente componente del vector
inicial. Se dicepor ello que las componentes en dicha base estan
desacopladas respecto a la aplicacion lineal.
Se llama forma cuadratica F a una aplicacion de Rp Rp R, es
decir, a una aplicacion que acada par de vectores les hace
corresponder un numero real, definida como
FR(x, y) = xT R y
donde R es una matriz p p.Se dice que una forma cuadratica F es
definida positiva si x, y Rp, xT R y > 0.Se dice que una forma
cuadratica F es semidefinida positiva si x, y Rp, xT R y 0.Un
teorema importante de algebra de matrices dice que, si R es real y
simetrica, o bien compleja y
hermtica, entonces
La forma cuadratica FR es definida positiva si, y solo si, k
> 0k = 1..p.
La forma cuadratica FR es semidefinida positiva si, y solo si, k
0k = 1..p.
siendo (1, . . . , p) los valores propios de R.
3.2. Introduccion
En el tema anterior se explico la forma de disenar filtro
optimos, en el sentido de exhibir el mnimoerror cuadratico posible,
asumiendo que la senal que filtramos es estacionaria en sentido
amplio (WSS).Como excepcion, el filtro de Kalman poda tratar
senales no estacionarias cambiando cierta ganancia encada
instante.
No obstante, las senales no siempre son estacionarias; una
posible idea para tratarlas sera considerarventanas temporales y
usar un filtro de Wiener diferente para cada una; los problemas de
esta aprox-imacion son dos: el primero, que si la senal vara de
modo rapido, la ventanas deberan ser breves, yquiza no contasemos
con suficientes datos como para estimar fiablemente la varianza del
ruido, necesariapara el diseno de un filtro de Wiener, ademas de
que habra problemas de continuidad en el cambio deventana. El
segundo problema es mas basico: el modelo que se esta imponiendo
para el sistema (senalestacionaria a trozos) es en realidad
incorrecto.
La idea correcta es considerar la posibilidad de usar filtros
lineales, pero no invariantes con el tiempo, esdecir, cuyos
coeficientes w(0), w(1), . . . , w(p) sean en realidad wn(0),
wn(1), . . . , wn(p) donde el subndicen indica la dependencia con
el instante de tiempo dicreto, n.
La forma en que esto se va a realizar es incremental, es decir,
partiremos de un vector de coeficientesdel filtro en el instante n,
sea wn y a partir de el calcularemos el correspondiente vector del
instantesiguiente como wn+1 = wn +w donde w es una correccion. La
forma de calcular esta correccion es elobjetivo principal de este
tema.
A veces es incluso preferible disenar este tipo de filtros
tambien para sistemas que suponemos osabemos WSS, por ejemplo
porque un filtro de Wiener que de un error suficientemente bajo es
de logitudexcesiva, o porque la matriz del sistema lineal para el
diseno del filtro fuese casi singular (determinantemuy pequeno) lo
que provoca problemas de estabilidad numerica.
La idea general de los filtros adaptativos se refleja en el
siguiente esquema:
30
-
d(n)W (z) +x(n)
d(n)
e(n)
wn
n
de adaptacinAlgoritmo
El algoritmo adaptativo trabaja con la entrada y el error,
generando en cada instante la correccionw para el instante
siguiente.
Sea cual sea este algoritmo, esta claro que debiera tener las
siguientes propiedades:
1. Para una senal WSS la secuencia de correcciones debera hacer
que los pesos convergieran a lasolucion del filtro optimo de
Wiener, es decir,
lmn
wn = R1x rdx
2. No debera ser necesario conocer las estadsticas de la senal,
es decir, rx(k) y rdx(k) para calcularw. La estimacion de estas
estadsticas debera estar en todo caso includa dentro del
algoritmo.
3. Para senales no WSS el filtro debera ser capaz de adaptarse a
las estadsticas cambiantes paraseguir a la solucion a medida que
esta evolucionase.
Un problema puede ser que la senal d(n) no este disponible para
poder calcular e(n). No obstante,en algunos casos s lo esta; uno
muy importante es la identificacion de sistemas:
d(n)W (z) +x(n)
e(n)
wn
n
de adaptacinAlgoritmo
Plantad(n)
++
v(n)
Se trata de disenar un filtro que se comporte como la planta,
cuyas entradas y salida podemos observar,pero cuya estructura
interna es desconocida.
3.3. Filtros adaptativos FIR
Son muy usados en aplicaciones como ecualizadores adaptativos,
sistemas digitales de comunicaciono control adaptativo de ruido. La
razon es que es facil controlar que el filtro sea un sistema
estable y queexisten algoritmos para adaptar los coeficientes que
son simples y de convergencia probada.
El problema general se plantea como
d(n) =
pk=0
wn(k)x(n k) = wTnx(n) (senal resultante del filtro)
31
-
Como siempre, (n) debe ser mnima:
(n) = E{| e(n) |2
}= E
{| d(n) d(n) |2
}= E
{| d(n) wTnx(n) |
2}
Igual que en la deduccion de los filtros FIR de Wiener, haciendo
d(n)dwn(k)
= 0 obtenemos
E {e(n)x(n k)} = 0, k = 0, . . . , p (principio de
ortogonalidad)
y sustituyendo,
E
{[d(n)
pl=0
wnx(n l)
]x(n l)
}= E {d(n)x(n k)} , k = 0, . . . , p
Es, como en el caso de filtros de Wiener, un sistema de p
ecuaciones lineales con p incognitas, pero aqu lamatriz del sistema
y el vector de terminos independientes dependen de n:
Rx(n) w = rdx(n)
donde
Rx(n) =
E {x(n)x(n)} E {x(n 1)x(n)} . . . E {x(n p)x(n)}E {x(n)x(n 1)}
.
......
E {x(n)x(n p)} . . . E {x(n p)x(n p)}
y
rdx(n) =
E {d(n)x(n)}E {d(n)x(n 1)}
...E {d(n)x(n p)}
Ahora no podemos decir que E {x(n)x(n s)} = rx(s), puesto que la
senal no es WSS (el parecido entrela senal y su version desplazada
s periodos, rx(s), no depende solo del desplazamiento s sino
tambien delinstante n es que miremos la senal, puesto que esta va
cambiando).
La idea obvia (resolver el sistema de ecuaciones en cada
instante) es impracticable, primero por unacuestion de coste
computacional y luego porque tendramos que estimar cada vez las
correlaciones.
En lugar de ello se usara un algoritmo de descenso de gradiente.
La idea es que el error cuadratico depende de wn; entonces,
hallaremos la derivada con respecto a wn y cambiaremos wn
moviendolo enla direccion de maxima variacion de (el gradiente ) de
modo que el valor de la funcion decrezcahasta que no lo haga mas
(estaremos en un mnimo). El algoritmo es:
1. Inicializar w a w0 (p. ej., resolviendo las ecuaciones de
Wiener-Hopf con los valores Rx(0) y rdx(0)del instante inicial)
2. Inicializar n 1.
3. Evaluar el gradiente de (n) respecto a w:
(n) =
(n)wn(0)
...(n)wn(p)
32
-
4. Actualizar w comown+1 = wn (n)
donde es un valor positivo que da la anchura del salto.
5. Hacer n n+ 1 e ir al paso 3.
Para evaluar (n) notemos que
(n) = E{| e(n) |2
}= E
{ | e(n) |2
}= E {e(n)e(n)}
pero como e(n) = d(n) wnx(n), tenemos que e(n) = x(n) (como
vector), de donde
(n) = E {e(n)x(n)} y por tanto,
wn+1 = wn + E {e(n)x(n)}
En el caso particular de proceso estacionario tendramos que
E {e(n)x(n)} = E {d(n)x(n)} E{wTnx(n)x
(n)}= rdx Rxwn
con lo que el algoritmo de descenso de gradiente sera
wn+1 = wn + (rdx Rxwn)
pero, por la ecuacion de Wiener-Hopf, Rxwn = rdx con lo que wn+1
= wn + 0 = wn, es decir, el filtrono cambia, siendo siempre el
filtro optimo de Winener.
Sin embargo, es muy imporantante ver si el proceso de adaptacion
convergera a la solucion del filtrode Wiener aun si empezamos por
cualquier valor de w. La siguiente propiedad establece que
efectivamenteas es.
Para procesos d(n) y x(n) de tipo WSS, el algoritmo de descenso
de gradiente converge a la solucionde las ecuaciones de
Wiener-Hopf, es decir,
lmn
wn = R1x rdx
si el tamano de paso satisface la condicion de que 0 < <
2max
, siendo max es mayor valor propio dela matriz Rx. Para ver
esto, recordemos que la ecuacion de actualizacion era:
wn+1 = wn + (rdx Rxwn)
o, lo que es lo mismo,wn+1 = (I Rx)wn + rdx
Restando w (la solucion de Wiener-Hopf) de ambas partes de la
igualdad, y usando que rdx = Rxwtenemos
wn+1 w = (I Rx)wn + rdx w = [I Rx] (wn w)
Definimos ahora el vector de error en los pesos como
cn wn w
con lo que cn+1 = (I Rx) cn. Si usamos el teorema de
descomposicion de matrices podemos escribir
cn+1 =(I V V H
)cn
y como V es unitaria, I = V V H de modo que
cn+1 =(V V H V V H
)cn = V (I )V
Hcn
33
-
Multiplicando ambas partes de la ecuacion por V H queda
V Hcn+1 = (I )VHcn
Definimos ahora el vector cn cambiado a la base de vectores
propios como un VHcn y as finalmente,
un+1 = (I )un
que espresa como va cambiando el vector de error en los pesos a
cada iteracion.Esto nos servira para poder calcular el error
cuadratico cometido en una iteracion, (n), y compararlo
con el error cuadratico mnimo que nos dara el filtro de Wiener,
min. Recordemos que en el tema anteriorse probo que
min = rd(0) rHdxw
siendo w el filtro optimo de Wiener. Pero si en lugar de el
vector w ponemos el que en este momentoestamos usando, wn, el error
cuadratico sera
(n) = E{| e(n) |2
}= E
{| d(n) wTnx(n) |
2}= rd(0) r
Hdxwn
Expresando esto en terminos del error en los pesos, cn wn w,
(n) = rd(0) rHdx(w + cn) (w + cn)
Hrdx + (w + cn)Rx(w + cn)
Haciendo los productos y usando de nuevo que Rxw = rdx
queda:
(n) = rd(0) rHdxw + c
Hn Rxcn
pero los dos primeros terminos son precisamente min, luego
(n) = min + cHn Rxcn
Escribiendo Rx mediante el teorema de descomposicion de
matrices,
(n) = min + uHn xun
Esta ecuacion tiene tres importantes consecuencias:
Si Rx es definida o semidefinida positiva (todos sus valores
propios son mayores o iguales que cero),el error en caulquier
instante es siempre mayor (o como mucho, igual) que el error que
obtendramoscon un filtro de Wiener, es decir, resolviendo en cada
instante las ecuaciones de Wiener-Hopf.
El algoritmo de actualizacion que estamos aplicando hara que los
wn se acerquen cada vez mas a w,con lo que el error cuadratico se
reducira. La razon de esto es que, como se probara en un
problemaposterior, si el valor de es apropiado, un 0 cuando n , con
lo que wn w.
De un modo un poco mas complicado, que no veremos aqu, se puede
incluso comprobar que (n)se reduce exponencialmente con el valor de
n, de modo que unas pocas iteraciones deben en generalser
suficientes para la convergencia.
34
-
3.4. El algoritmo LMS
Anteriormente vimos que la formula general para el algoritmo
adaptativo que cambiaba los pesos delfiltro era
wn+1 = wn + E {e(n)x(n)}
y el problema era que, al no ser el proceso estacionario, no
podemos estimar E {e(n)x(n)} de una vezpara siempre sino que
deberamos hacerlo en cada instante de tiempo. Una idea sera dar
como estimadorla media del valor en los ultimos L instantes de
muestreo:
E {e(n)x(n)} =1
L
L1l=0
e(n l)x(n l)
En el caso extremo, podramos considerar solo el ultimo instante
(es decir, tomar L = 1) con lo queE {e(n)x(n)} = e(n)x(n) y
entonces
wn+1 = wn + e(n)x(n)
Se puede ver que la actualizacion de un vector w con p
componentes requerira 2p+ 3 multiplicaciones y2p+ 2 sumas.
En este caso, el movimiento del vector wn en el espacio de los
pesos (de los filtros) no apunta necesari-amente en la direccion de
maximo decrecimiento del error para cada iteracion, como haca el
algoritmode descenso de gradiente. No obstante, en promedio y al
cabo de un numero suficiente de iteraciones,acabara convergiendo.
Para verlo, tomemos la esperanza de la ecuacion anterior:
E {wn+1} = E {wn}+ E{(d(n) wTnx(n))x
(n)}= E {wn}+ E {d(n)x
(n)} E{x(n)xT (n)wn
}Si asumimos que los datos x(n) y el vector de pesos wn son
estadsticamente independientes (lo cual noes estrictamente cierto,
dado que wn se calcula a partir de xn anteriores) quedara:
E {wn+1} = E {wn}+ E {(d(n)x(n)} E
{x(n)xT (n)
}E {wn}
E {wn+1} = (I Rx)E {wn}+ rdx
que es la misma ecuacion que habamos visto en la seccion
anterior, pero reemplazando wn por suesperanza, y all ya se razono
la convergencia, que ocurra necesariamente si el tamano de paso
era0 < < 2
max. Esta cota resulta ser demasiado grande para la mayora de
las aplicaciones. Moverse
por el espacio de los filtros a saltos demasiado grandes lleva a
que la varianza de wn (y por tantolos valores maximos de los
propios pesos) puedan llegar en algunos instantes del algoritmo a
crecerdesmesuradamente, dando problemas de representacion en la
memoria y estabilidad numerica. Por esose prefiere usar una cota
menor, que hace la convergencia mas lenta, pero mas segura. En
concreto, esclaro que
max
p1k=0
k = tr(Rx)
donde tr(Rx) es la traza de la matriz Rx, definida como la suma
de los elementos de su diagonal principal.Si el proceso se
aproximase a un proceso WSS (y todos se aproximan, si consideramos
intervalos
temporales pequenos), tenemos que tr(Rx) = prx(0) = pE{| x(n)
|2
}con lo que la cota para resulta
ser
0
