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 de la Universidad de Stanford Bernard Widrow y su primer estudiante de doctorado, 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 reconocer 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 se transforma mediante un filtro desconocido que deseamos igualar utilizando . La salida del filtro desconocido es , que luego se ve interferida por 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 con el fin de 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 de Wiener

La realización del filtro causal de Wiener 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 la minimización del criterio de error del primero no depende de 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 adaptar el filtro para que sea lo más cercano posible a , mientras que solo utiliza señales observables , y ; pero , y no son directamente observables. Su solución está estrechamente relacionada con el filtro de 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}}$( Transposición hermítica o transposición 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, se actualizan los pesos. Es decir, si el gradiente MSE es positivo, implica que el error seguiría aumentando positivamente si se usa el mismo peso para iteraciones posteriores, lo que significa que necesitamos reducir los pesos. De la misma manera, si el gradiente es negativo, necesitamos aumentar los pesos. La ecuación de actualización de pesos 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 de los filtros es una función cuadrática, lo que significa que solo tiene un 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 o descendiendo por la curva de error cuadrático medio en función del 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 costo 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 ahí el nombre del LMS. La aplicación del descenso más pronunciado implica tomar las derivadas parciales con respecto a las entradas individuales del vector de coeficientes 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, es un vector que apunta hacia el ascenso más pronunciado de la función de costo. Para encontrar el mínimo de la función de costo, necesitamos dar un paso en la dirección opuesta de . Para expresarlo 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\}}$

donde es el tamaño del paso (constante de adaptación). Esto 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 sepamos . ${\displaystyle {\frac {\mu }{2}}}$ ${\displaystyle E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

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

Simplificaciones

Para la mayoría de los sistemas, la función de expectativa debe aproximarse. Esto se puede hacer con el siguiente estimador imparcial ${\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 es el siguiente:

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

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

Resumen del algoritmo LMS

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

Convergencia y estabilidad en la media

Como el algoritmo LMS no utiliza los valores exactos de las expectativas, los pesos nunca alcanzarían los pesos óptimos en sentido absoluto, pero es posible una convergencia en la media. Es decir, aunque los pesos puedan cambiar en pequeñas cantidades, cambian en torno a 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, y por lo tanto los pesos pueden cambiar en un valor grande, de modo que el gradiente que era negativo en el primer instante puede volverse positivo. Y en el segundo instante, el peso puede cambiar en la dirección opuesta en una gran cantidad debido al gradiente negativo y, por lo tanto, seguiría oscilando con una gran variación en torno 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 grande. ${\displaystyle \mu }$ ${\displaystyle \mu }$

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

donde es 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} }}},}$

donde es el valor propio más pequeño de . Dado que es menor o igual que este óptimo, la velocidad de convergencia está determinada por , con un valor mayor que 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 de valores propios 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 dispersión de los valores propios 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 las señales de entrada blancas y lentamente para las señales de entrada coloreadas, como los 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 solo refuerza 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 diverjan (en la práctica, el valor de no debería elegirse cerca de este límite superior, ya que es algo optimista debido a las aproximaciones y suposiciones realizadas 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 normalizados (NLMS)

El principal inconveniente del algoritmo LMS "puro" es que es sensible al escalamiento 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 normalizados (NLMS) es una variante del algoritmo LMS que resuelve este problema normalizando con la potencia de la entrada. El algoritmo NLMS se puede resumir de la siguiente manera: ${\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 generalmente es el caso en la práctica. ${\displaystyle v(n)}$ ${\displaystyle x(n)}$

Prueba

Dejemos que la desalineación del filtro se defina como , y 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]}}}$

Véase también

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

Referencias

• Monson H. Hayes: Procesamiento y modelado 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ínimos cuadrados medios, 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 de núcleo: 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