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 doctorado. estudiante, Ted Hoff .
Formulación del problema
Relación con el filtro Wiener
La realización del filtro de Wiener causal se parece mucho a la solución a la estimación de mínimos cuadrados, excepto en el dominio de procesamiento de señales. La solución de mínimos cuadrados, para la matriz de entrada y vector de salida es
El filtro de mínimos cuadrados medios de FIR está relacionado con el filtro de Wiener, pero minimizar el criterio de error del primero no depende de correlaciones cruzadas o autocorrelaciones. Su solución converge a la solución de filtrado Wiener. La mayoría de los problemas de filtrado adaptativo lineal se pueden formular utilizando el diagrama de bloques anterior. Es decir, un sistema desconocido debe ser identificado y el filtro adaptativo intenta adaptar el filtro para acercarlo lo más posible a , utilizando solo señales observables , y ; pero, y no son directamente observables. Su solución está estrechamente relacionada con el filtro Wiener .
filtro estimado; interpretar como la estimación de los coeficientes de filtro después de n muestras
Ocurrencia
La idea básica detrás del filtro LMS es acercarse a los pesos de filtro óptimos , actualizando los pesos del filtro de manera que converjan al peso óptimo del filtro. Esto se basa en el algoritmo de descenso de gradientes. 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 de MSE es positivo, implica que el error seguirá aumentando positivamente si se usa el mismo peso para más iteraciones, 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
,
dónde representa el error cuadrático medio y es un coeficiente de convergencia.
El signo negativo muestra que bajamos la pendiente del error, para encontrar los pesos de los filtros, , que minimizan el error.
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, lo 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 por la curva del error cuadrático medio frente al peso del filtro.
Derivación
La idea detrás de los filtros LMS es utilizar el descenso más pronunciado para encontrar los pesos de los filtros.que minimizan una función de costo . Comenzamos definiendo la función de costo como
dónde es el error en la muestra actual n ydenota el valor esperado .
Esta función de costo () es el error cuadrático medio y el LMS lo minimiza. Aquí es 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)
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 expresar eso en términos matemáticos
dónde 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 se puede realizar hasta que sepamos.
Generalmente, la expectativa anterior no se calcula. 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 abajo.
Simplificaciones
Para la mayoría de los sistemas, la función de expectativa debe ser aproximado. Esto se puede hacer con el siguiente estimador insesgado
dónde indica el número de muestras que usamos para esa estimación. El caso más simple es
Para ese caso simple, el algoritmo de actualización sigue como
De hecho, esto constituye el algoritmo de actualización del filtro LMS.
Resumen del algoritmo LMS
El algoritmo LMS para un El filtro de orden se puede resumir como
Parámetros:
orden de filtro
Numero de pie
Inicialización:
Cálculo:
Para
Convergencia y estabilidad en la media
Como el algoritmo LMS no usa los valores exactos de las expectativas, las ponderaciones nunca alcanzarían las ponderaciones óptimas en el sentido absoluto, pero es posible una convergencia en la media. Es decir, aunque los pesos pueden cambiar en pequeñas cantidades, cambia con respecto 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 de paso no se elige correctamente.
Si se elige 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 variación sobre los pesos óptimos. Por otro lado, si se elige demasiado pequeño, el tiempo para converger a los pesos óptimos será demasiado grande.
Por lo tanto, un límite superior en es necesario que se da como
dónde es el mayor valor propio de la matriz de autocorrelación. Si no se cumple esta condición, el algoritmo se vuelve inestable y diverge.
La velocidad máxima de convergencia se alcanza cuando
dónde es el valor propio más pequeño de . Dado que es menor o igual a 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 esta cerca de , es decir, la velocidad de convergencia máxima alcanzable depende de la dispersión del valor propio de.
Una señal de ruido blanco tiene una matriz de autocorrelación. dónde es la varianza de la señal. En este caso, todos los valores propios son iguales y la dispersión del valor propio es el mínimo entre todas las matrices posibles. La interpretación común de este resultado es, por lo tanto, 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.
Es importante tener en cuenta que el límite superior anterior en solo refuerza la estabilidad en la media, pero los coeficientes de todavía puede crecer infinitamente, es decir, todavía es posible la divergencia de los coeficientes. Un límite más práctico es
dónde denota el rastro 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).
Filtro de mínimos cuadrados medios normalizados (NLMS)
El principal inconveniente del algoritmo LMS "puro" es que es sensible al escalado de su entrada. . Esto hace que sea muy difícil (si no imposible) elegir una tasa de aprendizajeque garantiza 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 normalizándolo con la potencia de la entrada. El algoritmo NLMS se puede resumir como:
Parámetros:
orden de filtro
Numero de pie
Inicialización:
Cálculo:
Para
Tasa de aprendizaje óptima
Se puede demostrar que si no hay interferencia (), entonces la tasa de aprendizaje óptima para el algoritmo NLMS es
y es independiente de la entrada y la respuesta de impulso real (desconocida) . En el caso general con interferencia (), la tasa de aprendizaje óptima es
Los resultados anteriores suponen que las señales y no están correlacionados entre sí, lo que generalmente es el caso en la práctica.
Prueba
Deje que la desalineación del filtro se defina como , podemos derivar la desalineación esperada para la siguiente muestra como:
Dejar y
Suponiendo independencia, tenemos:
La tasa de aprendizaje óptima se encuentra en , lo que lleva a: