filtro de mínimos cuadrados

Los algoritmos de mínimos cuadrados ( LMS ) son una clase de filtros adaptativos que imitan un filtro deseado al encontrar los coeficientes del filtro que producen el mínimo cuadrado medio de la señal de error (diferencia entre la señal deseada y la real). Se trata de un método de descenso de gradiente estocástico, ya que el filtro se adapta únicamente 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 sobre redes neuronales de una sola capa. En concreto, utilizaron el descenso de gradiente para entrenar a ADALINE para el reconocimiento de patrones, y denominaron al algoritmo " regla delta ". Aplicaron esta regla a los filtros, dando como resultado el algoritmo LMS.

La imagen muestra las distintas partes del filtro.${\displaystyle x}$es la señal de entrada, que luego es transformada por un filtro desconocido${\displaystyle h}$que deseamos que coincida usando${\displaystyle {\hat {h}}}$. La salida del filtro desconocido es${\displaystyle y}$, que luego se ve interferida por una señal de ruido.${\displaystyle \nu }$, produciendo${\displaystyle d=y+\nu }$. Luego la señal de error${\displaystyle e=d-{\hat {y}}=y+\nu -{\hat {y}}}$se calcula y se retroalimenta al filtro adaptativo para ajustar sus parámetros con el fin de minimizar el error cuadrático medio .${\displaystyle \sum e^{2}/n}$.

La idea básica detrás del filtro LMS es aproximarse a los pesos óptimos del filtro.${\displaystyle (R^{-1}P)}$, actualizando los pesos del filtro de manera que converjan al peso óptimo del filtro. 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 del MSE es positivo, implica que el error seguiría aumentando positivamente si se utiliza el mismo peso en 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 W_{n+1}=W_{n}-\mu \nabla \varepsilon [n],}$

dónde${\displaystyle \varepsilon }$representa el error cuadrático medio y${\displaystyle \mu }$es el coeficiente de tasa de aprendizaje .

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

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 único extremo: el que minimiza el error cuadrático medio, que corresponde al peso óptimo. Por lo tanto, el método LMS se aproxima a estos pesos óptimos ascendiendo o descendiendo por la curva de error cuadrático medio frente al peso del filtro.

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

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

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

Esta función de coste (${\displaystyle C(n)}$) es el error cuadrático medio, y se minimiza mediante el LMS. De ahí proviene el nombre del LMS. Aplicar el descenso más pronunciado significa tomar las derivadas parciales con respecto a las entradas individuales del vector de coeficientes (pesos) del filtro.

${\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${\displaystyle \nabla }$es el operador gradiente

${\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,${\displaystyle \nabla C(n)}$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 a${\displaystyle \nabla C(n)}$Para expresarlo en términos matemáticos

${\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${\displaystyle {\frac {\mu}{2}}}$es 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 sepamos${\displaystyle E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$.

Por lo general, no se calcula la expectativa mencionada anteriormente. 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 dicha expectativa. Véase a continuación.

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

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

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

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

Para ese caso sencillo, 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, este es el algoritmo de actualización del filtro LMS.

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

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 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${\displaystyle \mu }$no se elige correctamente.

Si${\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 una gran cantidad debido al gradiente negativo y, por lo tanto, seguiría oscilando con una gran varianza alrededor de los pesos óptimos. Por otro lado, si${\displaystyle \mu }$Si se elige un valor demasiado pequeño, el tiempo para converger a los pesos óptimos será demasiado grande.

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

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

La velocidad máxima de convergencia se alcanza cuando

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

dónde${\displaystyle \lambda _{\min }}$es el valor propio más pequeño de${\displaystyle {\mathbf {R} }}$. Dado que${\displaystyle \mu }$es menor o igual a este óptimo, la velocidad de convergencia está determinada por${\displaystyle \lambda _{\min }}$, 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${\displaystyle \lambda _{\max }}$está cerca de${\displaystyle \lambda _{\min }}$, es decir, la velocidad máxima de convergencia alcanzable depende de la dispersión de los valores propios de${\displaystyle {\mathbf {R} }}$.

Una señal de ruido blanco tiene matriz de autocorrelación${\displaystyle {\mathbf {R} }=\sigma ^{2}{\mathbf {I} }}$dónde${\displaystyle \sigma ^{2}}$es la varianza de la señal. En este caso, todos los autovalores son iguales y la dispersión de los autovalores es 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.

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

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

dónde${\displaystyle \mathrm {tr} [{\mathbf {R} }]}$denota el rastro de${\displaystyle {\mathbf {R} }}$. Este límite garantiza que los coeficientes de${\displaystyle {\hat {h}}(n)}$no divergen (en la práctica, el valor de${\displaystyle \mu }$No debe 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.

El principal inconveniente del algoritmo LMS "puro" es que es sensible a la escala de su entrada.${\displaystyle x(n)}$Esto hace que sea muy difícil (si no imposible) elegir una tasa de aprendizaje .${\displaystyle \mu }$que garantiza la estabilidad del algoritmo (Haykin 2002). El filtro de mínimos cuadrados 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 como:

• mínimos cuadrados recursivos
• Para obtener información sobre técnicas estadísticas relevantes para el filtro LMS, consulte el método de mínimos cuadrados .
• Similitudes entre Wiener y LMS
• Ecualizador de forzado a cero
• Filtro adaptativo de núcleo
• Filtro compatible
• Filtro de Wiener

• Monson H. Hayes: Procesamiento y modelado estadístico de señales digitales, Wiley, 1996, ISBN 0-471-59431-8
• Simon Haykin: Teoría de filtros adaptativos, Prentice Hall, 2002, ISBN 0-13-048434-2
• Simon S. Haykin, Bernard Widrow (Editor): Filtros adaptativos de mínimos cuadrados, 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 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

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