Filtro de mínimos cuadrados medios

Algoritmo estadístico

Los algoritmos de mínimos cuadrados medios ( LMS ) son una clase de filtro adaptativo que se utiliza para imitar un filtro deseado al encontrar los coeficientes de filtro que se relacionan con la producción del mínimo cuadrado medio de la señal de error (diferencia entre la señal deseada y la real). Es un método de descenso de gradiente estocástico en el que el filtro solo se adapta en función del error en el momento actual. Fue inventado en 1960 por el profesor Bernard Widrow de la Universidad de Stanford y su primer doctorado. estudiante, Ted Hoff , basándose en su investigación en redes neuronales de una sola capa ( ADALINE ). Específicamente, utilizaron el descenso de gradiente para entrenar a ADALINE para que reconociera patrones y llamaron al algoritmo " regla delta ". Luego aplicaron la regla a los filtros, lo que dio como resultado el algoritmo LMS.

Formulación del problema

La imagen muestra las distintas partes del filtro. es la señal de entrada, que luego es transformada por un filtro desconocido que deseamos hacer coincidir usando . La salida del filtro desconocido es , que luego se interfiere con una señal de ruido , lo que produce . Luego se calcula la señal de error y se devuelve al filtro adaptativo para ajustar sus parámetros y minimizar el cuadrado medio de la señal de error . ${\displaystyle x}$ ${\displaystyle h}$ ${\displaystyle {\hat {h}}}$ ${\displaystyle y}$ ${\displaystyle \nu }$ ${\displaystyle d=y+\nu }$ ${\displaystyle e=d-{\hat {y}}=y+\nu -{\hat {y}}}$ ${\displaystyle e}$

Relación con el filtro Wiener

La realización del filtro de Wiener causal se parece mucho a la solución de la estimación de mínimos cuadrados, excepto en el dominio del procesamiento de señales. La solución de mínimos cuadrados para la matriz de entrada y el vector de salida es ${\displaystyle \mathbf {X} }$ ${\displaystyle {\boldsymbol {y}}}$

${\displaystyle {\boldsymbol {\hat {\beta }}}=(\mathbf {X} ^{\mathbf {T} }\mathbf {X} )^{-1}\mathbf {X} ^{\mathbf {T} }{\boldsymbol {y}}.}$

El filtro de mínimos cuadrados medios FIR está relacionado con el filtro de Wiener, pero minimizar el criterio de error del primero no se basa en correlaciones cruzadas o autocorrelaciones. Su solución converge a la solución del filtro de Wiener. La mayoría de los problemas de filtrado adaptativo lineal se pueden formular utilizando el diagrama de bloques anterior. Es decir, se debe identificar un sistema desconocido y el filtro adaptativo intenta adaptarlo para acercarlo lo más posible a , mientras utiliza solo señales observables , y ; pero y no son directamente observables. Su solución está estrechamente relacionada con el filtro Wiener . ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle {\hat {\mathbf {h} }}(n)}$ ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle x(n)}$ ${\displaystyle d(n)}$ ${\displaystyle e(n)}$ ${\displaystyle y(n)}$ ${\displaystyle v(n)}$ ${\displaystyle h(n)}$

Definición de símbolos

${\displaystyle n}$es el número de la muestra de entrada actual

${\displaystyle p}$es el número de grifos de filtro

${\displaystyle \{\cdot \}^{H}}$( Transpuesta hermitiana o transpuesta conjugada )

${\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}}$

${\displaystyle \mathbf {h} (n)=\left[h_{0}(n),h_{1}(n),\dots ,h_{p-1}(n)\right]^{T},\quad \mathbf {h} (n)\in \mathbb {C} ^{p}}$

${\displaystyle y(n)=\mathbf {h} ^{H}(n)\cdot \mathbf {x} (n)}$

${\displaystyle d(n)=y(n)+\nu (n)}$

${\displaystyle {\hat {\mathbf {h} }}(n)}$filtro estimado; interpretar como la estimación de los coeficientes del filtro después de n muestras

${\displaystyle e(n)=d(n)-{\hat {y}}(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\cdot \mathbf {x} (n)}$

Idea

La idea básica detrás del filtro LMS es acercarse a los pesos de filtro óptimos , actualizando los pesos de filtro de manera que converjan al peso de filtro óptimo. Esto se basa en el algoritmo de descenso de gradiente. El algoritmo comienza asumiendo pesos pequeños (cero en la mayoría de los casos) y, en cada paso, al encontrar el gradiente del error cuadrático medio, los pesos se actualizan. Es decir, si el gradiente de MSE es positivo, implica que el error seguirá aumentando positivamente si se usa el mismo peso para iteraciones posteriores, lo que significa que debemos reducir los pesos. De la misma manera, si el gradiente es negativo, necesitamos aumentar los pesos. La ecuación de actualización de peso es ${\displaystyle (R^{-1}P)}$

${\displaystyle W_{n+1}=W_{n}-\mu \nabla \varepsilon [n],}$

donde representa el error cuadrático medio y es un coeficiente de convergencia. ${\displaystyle \varepsilon }$ ${\displaystyle \mu }$

El signo negativo muestra que bajamos la pendiente del error para encontrar los pesos del filtro, que minimizan el error. ${\displaystyle \varepsilon }$ ${\displaystyle W_{i}}$

El error cuadrático medio en función de los pesos del filtro es una función cuadrática, lo que significa que tiene un solo extremo, que minimiza el error cuadrático medio, que es el peso óptimo. Por lo tanto, el LMS se acerca a estos pesos óptimos ascendiendo/descendiendo hacia abajo por la curva de error cuadrático medio versus peso del filtro.

Derivación

La idea detrás de los filtros LMS es utilizar el descenso más pronunciado para encontrar pesos de filtro que minimicen una función de costo . Comenzamos definiendo la función de costos como ${\displaystyle {\hat {\mathbf {h} }}(n)}$

${\displaystyle C(n)=E\left\{|e(n)|^{2}\right\}}$

donde es el error en la muestra actual n y denota el valor esperado . ${\displaystyle e(n)}$ ${\displaystyle E\{\cdot \}}$

Esta función de costo ( ) es el error cuadrático medio y el LMS lo minimiza. De aquí es de donde el LMS recibe su nombre. Aplicar el descenso más pronunciado significa tomar las derivadas parciales con respecto a las entradas individuales del vector de coeficiente de filtro (peso) ${\displaystyle C(n)}$

${\displaystyle \nabla _{{\hat {\mathbf {h} }}^{H}}C(n)=\nabla _{{\hat {\mathbf {h} }}^{H}}E\left\{e(n)\,e^{*}(n)\right\}=2E\left\{\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))\,e^{*}(n)\right\}}$

¿Dónde está el operador de gradiente? ${\displaystyle \nabla }$

${\displaystyle \nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))=\nabla _{{\hat {\mathbf {h} }}^{H}}\left(d(n)-{\hat {\mathbf {h} }}^{H}\cdot \mathbf {x} (n)\right)=-\mathbf {x} (n)}$

${\displaystyle \nabla C(n)=-2E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

Ahora bien, es un vector que apunta hacia el ascenso más pronunciado de la función de costes. Para encontrar el mínimo de la función de costo necesitamos dar un paso en la dirección opuesta a . Para expresar eso en términos matemáticos. ${\displaystyle \nabla C(n)}$ ${\displaystyle \nabla C(n)}$

${\displaystyle {\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)-{\frac {\mu }{2}}\nabla C(n)={\hat {\mathbf {h} }}(n)+\mu \,E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

¿Dónde está el tamaño del paso (constante de adaptación)? Eso significa que hemos encontrado un algoritmo de actualización secuencial que minimiza la función de costo. Desafortunadamente, este algoritmo no es realizable hasta que lo sepamos . ${\displaystyle {\frac {\mu }{2}}}$ ${\displaystyle E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

Generalmente, la expectativa anterior no se calcula. En cambio, para ejecutar el LMS en un entorno en línea (actualizándose después de recibir cada nueva muestra), utilizamos una estimación instantánea de esa expectativa. Vea abajo.

Simplificaciones

Para la mayoría de los sistemas, la función de expectativa debe ser aproximada. Esto se puede hacer con el siguiente estimador insesgado ${\displaystyle {E}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

${\displaystyle {\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}={\frac {1}{N}}\sum _{i=0}^{N-1}\mathbf {x} (n-i)\,e^{*}(n-i)}$

donde indica el número de muestras que utilizamos para esa estimación. El caso más simple es ${\displaystyle N}$ ${\displaystyle N=1}$

${\displaystyle {\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}=\mathbf {x} (n)\,e^{*}(n)}$

Para ese caso simple, el algoritmo de actualización sigue el siguiente

${\displaystyle {\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \mathbf {x} (n)\,e^{*}(n)}$

De hecho, este constituye el algoritmo de actualización del filtro LMS.

Resumen del algoritmo LMS

El algoritmo LMS para un filtro de orden ésimo se puede resumir como ${\displaystyle p}$

Convergencia y estabilidad en la media

Como el algoritmo LMS no utiliza los valores exactos de las expectativas, las ponderaciones nunca alcanzarían las ponderaciones óptimas en sentido absoluto, pero es posible una convergencia en media. Es decir, aunque los pesos pueden cambiar en pequeñas cantidades, cambia alrededor de los pesos óptimos. Sin embargo, si la varianza con la que cambian los pesos es grande, la convergencia en la media sería engañosa. Este problema puede ocurrir si el valor del tamaño del paso no se elige correctamente. ${\displaystyle \mu }$

Si se elige que sea grande, la cantidad con la que cambian los pesos depende en gran medida de la estimación del gradiente, por lo que los pesos pueden cambiar en un valor grande, de modo que el gradiente que era negativo en el primer instante ahora puede volverse positivo. Y en el segundo instante, el peso puede cambiar en la dirección opuesta en gran medida debido al gradiente negativo y, por lo tanto, seguiría oscilando con una gran variación con respecto a los pesos óptimos. Por otro lado, si se elige que sea demasiado pequeño, el tiempo para converger a los pesos óptimos será demasiado largo. ${\displaystyle \mu }$ ${\displaystyle \mu }$

Por lo tanto, se necesita un límite superior que viene dado como , ${\displaystyle \mu }$ ${\displaystyle 0<\mu <{\frac {2}{\lambda _{\mathrm {max} }}}}$

donde está el mayor valor propio de la matriz de autocorrelación . Si esta condición no se cumple, el algoritmo se vuelve inestable y diverge. ${\displaystyle \lambda _{\max }}$ ${\displaystyle {\mathbf {R} }=E\{{\mathbf {x} }(n){\mathbf {x} ^{H}}(n)\}}$ ${\displaystyle {\hat {h}}(n)}$

La velocidad máxima de convergencia se logra cuando

${\displaystyle \mu ={\frac {2}{\lambda _{\mathrm {max} }+\lambda _{\mathrm {min} }}},}$

¿Dónde está el valor propio más pequeño de ? Dado que es menor o igual a este óptimo, la velocidad de convergencia está determinada por , y un valor mayor produce una convergencia más rápida. Esto significa que se puede lograr una convergencia más rápida cuando está cerca de , es decir, la velocidad de convergencia máxima alcanzable depende de la dispersión del valor propio de . ${\displaystyle \lambda _{\min }}$ ${\displaystyle {\mathbf {R} }}$ ${\displaystyle \mu }$ ${\displaystyle \lambda _{\min }}$ ${\displaystyle \lambda _{\max }}$ ${\displaystyle \lambda _{\min }}$ ${\displaystyle {\mathbf {R} }}$

Una señal de ruido blanco tiene una matriz de autocorrelación donde es la varianza de la señal. En este caso, todos los valores propios son iguales y la distribución del valor propio es la mínima entre todas las matrices posibles. Por lo tanto, la interpretación común de este resultado es que el LMS converge rápidamente para señales de entrada blancas y lentamente para señales de entrada coloreadas, como procesos con características de paso bajo o paso alto. ${\displaystyle {\mathbf {R} }=\sigma ^{2}{\mathbf {I} }}$ ${\displaystyle \sigma ^{2}}$

Es importante señalar que el límite superior anterior sólo impone la estabilidad en la media, pero los coeficientes de aún pueden crecer infinitamente, es decir, la divergencia de los coeficientes aún es posible. Un límite más práctico es ${\displaystyle \mu }$ ${\displaystyle {\hat {h}}(n)}$

${\displaystyle 0<\mu <{\frac {2}{\mathrm {tr} \left[{\mathbf {R} }\right]}},}$

donde denota la traza de . Este límite garantiza que los coeficientes de no divergen (en la práctica, el valor de no debe elegirse cerca de este límite superior, ya que es algo optimista debido a las aproximaciones y suposiciones hechas en la derivación del límite). ${\displaystyle \mathrm {tr} [{\mathbf {R} }]}$ ${\displaystyle {\mathbf {R} }}$ ${\displaystyle {\hat {h}}(n)}$ ${\displaystyle \mu }$

Filtro de mínimos cuadrados medios normalizado (NLMS)

El principal inconveniente del algoritmo LMS "puro" es que es sensible a la escala de su entrada . Esto hace que sea muy difícil (si no imposible) elegir una tasa de aprendizaje que garantice la estabilidad del algoritmo (Haykin 2002). El filtro de mínimos cuadrados medios normalizado (NLMS) es una variante del algoritmo LMS que resuelve este problema normalizando con la potencia de la entrada. El algoritmo NLMS se puede resumir como: ${\displaystyle x(n)}$ ${\displaystyle \mu }$

Tasa de aprendizaje óptima

Se puede demostrar que si no hay interferencia ( ), entonces la tasa de aprendizaje óptima para el algoritmo NLMS es ${\displaystyle v(n)=0}$

${\displaystyle \mu _{opt}=1}$

y es independiente de la entrada y de la respuesta al impulso real (desconocida) . En el caso general con interferencia ( ), la tasa de aprendizaje óptima es ${\displaystyle x(n)}$ ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle v(n)\neq 0}$

${\displaystyle \mu _{opt}={\frac {E\left[\left|y(n)-{\hat {y}}(n)\right|^{2}\right]}{E\left[|e(n)|^{2}\right]}}}$

Los resultados anteriores suponen que las señales y no están correlacionadas entre sí, lo que suele ser el caso en la práctica. ${\displaystyle v(n)}$ ${\displaystyle x(n)}$

Prueba

Definamos la desalineación del filtro como , podemos derivar la desalineación esperada para la siguiente muestra como: ${\displaystyle \Lambda (n)=\left|\mathbf {h} (n)-{\hat {\mathbf {h} }}(n)\right|^{2}}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \,e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \,\left(v^{*}(n)+y^{*}(n)-{\hat {y}}^{*}(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]}$

dejar y ${\displaystyle \mathbf {\delta } ={\hat {\mathbf {h} }}(n)-\mathbf {h} (n)}$ ${\displaystyle r(n)={\hat {y}}(n)-y(n)}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right|^{2}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)\right]}$

Suponiendo independencia tenemos:

${\displaystyle E\left[\Lambda (n+1)\right]=\Lambda (n)+E\left[\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)\right]-2E\left[{\frac {\mu |r(n)|^{2}}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=\Lambda (n)+{\frac {\mu ^{2}E\left[|e(n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-{\frac {2\mu E\left[|r(n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}}$

La tasa de aprendizaje óptima se encuentra en , lo que conduce a: ${\displaystyle {\frac {dE\left[\Lambda (n+1)\right]}{d\mu }}=0}$

${\displaystyle 2\mu E\left[|e(n)|^{2}\right]-2E\left[|r(n)|^{2}\right]=0}$

${\displaystyle \mu ={\frac {E\left[|r(n)|^{2}\right]}{E\left[|e(n)|^{2}\right]}}}$

Ver también

• Mínimos cuadrados recursivos
• Para conocer técnicas estadísticas relevantes para el filtro LMS, consulte Mínimos cuadrados .
• Similitudes entre Wiener y LMS
• Filtro adaptativo de dominio de frecuencia de bloque de retardo múltiple
• Ecualizador de fuerza cero
• Filtro adaptativo del kernel
• Filtro coincidente
• Filtro de salchicha

Referencias

• Monson H. Hayes: Modelado y procesamiento estadístico de señales digitales, Wiley, 1996, ISBN  0-471-59431-8
• Simon Haykin: teoría del filtro adaptativo, Prentice Hall, 2002, ISBN 0-13-048434-2 
• Simon S. Haykin, Bernard Widrow (Editor): Filtros adaptativos de mínimo cuadrado medio, Wiley, 2003, ISBN 0-471-21570-8 
• Bernard Widrow, Samuel D. Stearns: procesamiento adaptativo de señales, Prentice Hall, 1985, ISBN 0-13-004029-0 
• Weifeng Liu, Jose Principe y Simon Haykin: Filtrado adaptativo del kernel: una introducción completa, John Wiley, 2010, ISBN 0-470-44753-2 
• Paulo SR Diniz: Filtrado adaptativo: algoritmos e implementación práctica, Kluwer Academic Publishers, 1997, ISBN 0-7923-9912-9 

enlaces externos

• Algoritmo LMS en conjuntos de antenas adaptativas www.antenna-theory.com
• Demostración de cancelación de ruido LMS www.advsolned.com