Filtro de mínimos cuadrados recursivo

Algoritmo de filtro adaptativo para procesamiento de señales digitales.

Los mínimos cuadrados recursivos ( RLS ) es un algoritmo de filtro adaptativo que encuentra de forma recursiva los coeficientes que minimizan una función de costo de mínimos cuadrados lineal ponderada relacionada con las señales de entrada. Este enfoque contrasta con otros algoritmos como los mínimos cuadrados medios (LMS) que tienen como objetivo reducir el error cuadrático medio . En la derivación del RLS las señales de entrada se consideran deterministas , mientras que para el LMS y algoritmos similares se consideran estocásticas . En comparación con la mayoría de sus competidores, el RLS muestra una convergencia extremadamente rápida. Sin embargo, este beneficio tiene el costo de una alta complejidad computacional.

Motivación

RLS fue descubierto por Gauss , pero no se utilizó o se ignoró hasta 1950, cuando Plackett redescubrió el trabajo original de Gauss de 1821. En general, el RLS se puede utilizar para resolver cualquier problema que pueda resolverse mediante filtros adaptativos . Por ejemplo, supongamos que una señal se transmite a través de un canal ruidoso y con eco que hace que se reciba como ${\displaystyle d(n)}$

${\displaystyle x(n)=\sum _{k=0}^{q}b_{n}(k)d(n-k)+v(n)}$

donde representa ruido aditivo . La intención del filtro RLS es recuperar la señal deseada mediante el uso de un filtro FIR -tap : ${\displaystyle v(n)}$ ${\displaystyle d(n)}$ ${\displaystyle p+1}$ ${\displaystyle \mathbf {w} }$

${\displaystyle d(n)\approx \sum _{k=0}^{p}w(k)x(n-k)=\mathbf {w} ^{\mathit {T}}\mathbf {x} _{n}}$

¿Dónde está el vector de columna que contiene las muestras más recientes de ? La estimación de la señal deseada recuperada es ${\displaystyle \mathbf {x} _{n}=[x(n)\quad x(n-1)\quad \ldots \quad x(n-p)]^{T}}$ ${\displaystyle p+1}$ ${\displaystyle x(n)}$

${\displaystyle {\hat {d}}(n)=\sum _{k=0}^{p}w_{n}(k)x(n-k)=\mathbf {w} _{n}^{\mathit {T}}\mathbf {x} _{n}}$

El objetivo es estimar los parámetros del filtro , y en cada momento nos referimos a la estimación actual como y a la estimación de mínimos cuadrados adaptada como . también es un vector de columna, como se muestra a continuación, y la transpuesta , es un vector de fila . El producto matricial (que es el producto escalar de y ) es un escalar. La estimación es "buena" si su magnitud es pequeña en algún sentido de mínimos cuadrados . ${\displaystyle \mathbf {w} }$ ${\displaystyle n}$ ${\displaystyle \mathbf {w} _{n}}$ ${\displaystyle \mathbf {w} _{n+1}}$ ${\displaystyle \mathbf {w} _{n}}$ ${\displaystyle \mathbf {w} _{n}^{\mathit {T}}}$ ${\displaystyle \mathbf {w} _{n}^{\mathit {T}}\mathbf {x} _{n}}$ ${\displaystyle \mathbf {w} _{n}}$ ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle {\hat {d}}(n)}$ ${\displaystyle {\hat {d}}(n)-d(n)}$

A medida que pasa el tiempo, se desea evitar rehacer completamente el algoritmo de mínimos cuadrados para encontrar la nueva estimación para , en términos de . ${\displaystyle \mathbf {w} _{n+1}}$ ${\displaystyle \mathbf {w} _{n}}$

El beneficio del algoritmo RLS es que no es necesario invertir matrices, lo que ahorra costos computacionales. Otra ventaja es que proporciona intuición detrás de resultados como el filtro de Kalman .

Discusión

La idea detrás de los filtros RLS es minimizar una función de costo seleccionando adecuadamente los coeficientes del filtro y actualizando el filtro a medida que llegan nuevos datos. La señal de error y la señal deseada se definen en el siguiente diagrama de retroalimentación negativa : ${\displaystyle C}$ ${\displaystyle \mathbf {w} _{n}}$ ${\displaystyle e(n)}$ ${\displaystyle d(n)}$

El error depende implícitamente de los coeficientes de filtro a través de la estimación : ${\displaystyle {\hat {d}}(n)}$

${\displaystyle e(n)=d(n)-{\hat {d}}(n)}$

Por lo tanto , el hecho de que la función de error de mínimos cuadrados ponderados (la función de costos que deseamos minimizar) también dependa de los coeficientes del filtro: ${\displaystyle C}$ ${\displaystyle e(n)}$

${\displaystyle C(\mathbf {w} _{n})=\sum _{i=0}^{n}\lambda ^{n-i}e^{2}(i)}$

¿Dónde está el "factor de olvido" que da exponencialmente menos peso a las muestras de errores más antiguas? ${\displaystyle 0<\lambda \leq 1}$

La función de costo se minimiza tomando las derivadas parciales de todas las entradas del vector de coeficientes y estableciendo los resultados en cero. ${\displaystyle k}$ ${\displaystyle \mathbf {w} _{n}}$

${\displaystyle {\frac {\partial C(\mathbf {w} _{n})}{\partial w_{n}(k)}}=\sum _{i=0}^{n}2\lambda ^{n-i}e(i)\cdot {\frac {\partial e(i)}{\partial w_{n}(k)}}=-\sum _{i=0}^{n}2\lambda ^{n-i}e(i)\,x(i-k)=0\qquad k=0,1,\ldots ,p}$

A continuación, reemplace con la definición de la señal de error. ${\displaystyle e(n)}$

${\displaystyle \sum _{i=0}^{n}\lambda ^{n-i}\left[d(i)-\sum _{\ell =0}^{p}w_{n}(\ell )x(i-\ell )\right]x(i-k)=0\qquad k=0,1,\ldots ,p}$

Reorganizando la ecuación se obtiene

${\displaystyle \sum _{\ell =0}^{p}w_{n}(\ell )\left[\sum _{i=0}^{n}\lambda ^{n-i}\,x(i-l)x(i-k)\right]=\sum _{i=0}^{n}\lambda ^{n-i}d(i)x(i-k)\qquad k=0,1,\ldots ,p}$

Esta forma se puede expresar en términos de matrices.

${\displaystyle \mathbf {R} _{x}(n)\,\mathbf {w} _{n}=\mathbf {r} _{dx}(n)}$

donde es la matriz de covarianza muestral ponderada para , y es la estimación equivalente para la covarianza cruzada entre y . Con base en esta expresión encontramos los coeficientes que minimizan la función de costos como ${\displaystyle \mathbf {R} _{x}(n)}$ ${\displaystyle x(n)}$ ${\displaystyle \mathbf {r} _{dx}(n)}$ ${\displaystyle d(n)}$ ${\displaystyle x(n)}$

${\displaystyle \mathbf {w} _{n}=\mathbf {R} _{x}^{-1}(n)\,\mathbf {r} _{dx}(n)}$

Este es el principal resultado de la discusión.

Eligiendo λ

Cuanto menor es, menor es la contribución de las muestras anteriores a la matriz de covarianza. Esto hace que el filtro sea más sensible a muestras recientes, lo que significa más fluctuaciones en los coeficientes del filtro. El caso se conoce como algoritmo RLS de ventana creciente . En la práctica, generalmente se elige entre 0,98 y 1. ^[1] Al utilizar la estimación de máxima verosimilitud de tipo II, se puede estimar el valor óptimo a partir de un conjunto de datos. ^[2] ${\displaystyle \lambda }$ ${\displaystyle \lambda =1}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$

Algoritmo recursivo

La discusión dio como resultado una única ecuación para determinar un vector de coeficientes que minimice la función de costos. En esta sección queremos derivar una solución recursiva de la forma

${\displaystyle \mathbf {w} _{n}=\mathbf {w} _{n-1}+\Delta \mathbf {w} _{n-1}}$

donde es un factor de corrección en el tiempo . Comenzamos la derivación del algoritmo recursivo expresando la covarianza cruzada en términos de ${\displaystyle \Delta \mathbf {w} _{n-1}}$ ${\displaystyle {n-1}}$ ${\displaystyle \mathbf {r} _{dx}(n)}$ ${\displaystyle \mathbf {r} _{dx}(n-1)}$

¿Dónde está el vector de datos dimensionales? ${\displaystyle \mathbf {x} (i)}$ ${\displaystyle {p+1}}$

${\displaystyle \mathbf {x} (i)=[x(i),x(i-1),\dots ,x(i-p)]^{T}}$

De manera similar expresamos en términos de por ${\displaystyle \mathbf {R} _{x}(n)}$ ${\displaystyle \mathbf {R} _{x}(n-1)}$

Para generar el vector de coeficientes nos interesa la inversa de la matriz determinista de autocovarianza. Para esa tarea la identidad de la matriz de Woodbury resulta útil. Con

La identidad de la matriz de Woodbury sigue

Para alinearnos con la literatura estándar, definimos

donde el vector de ganancia es ${\displaystyle g(n)}$

Antes de continuar, es necesario adoptar otra forma. ${\displaystyle \mathbf {g} (n)}$

Restando el segundo término del lado izquierdo se obtiene

Con la definición recursiva de la forma deseada sigue ${\displaystyle \mathbf {P} (n)}$

${\displaystyle \mathbf {g} (n)=\mathbf {P} (n)\mathbf {x} (n)}$

Ahora estamos listos para completar la recursividad. Como se discutio

El segundo paso se deriva de la definición recursiva de . A continuación incorporamos la definición recursiva de junto con la forma alternativa de y obtenemos ${\displaystyle \mathbf {r} _{dx}(n)}$ ${\displaystyle \mathbf {P} (n)}$ ${\displaystyle \mathbf {g} (n)}$

Con llegamos a la ecuación de actualización. ${\displaystyle \mathbf {w} _{n-1}=\mathbf {P} (n-1)\mathbf {r} _{dx}(n-1)}$

¿Dónde está el error a priori ? Compare esto con el error a posteriori ; el error calculado después de actualizar el filtro: ${\displaystyle \alpha (n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n-1}}$

${\displaystyle e(n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n}}$

Eso significa que encontramos el factor de corrección.

${\displaystyle \Delta \mathbf {w} _{n-1}=\mathbf {g} (n)\alpha (n)}$

Este resultado intuitivamente satisfactorio indica que el factor de corrección es directamente proporcional tanto al error como al vector de ganancia, que controla cuánta sensibilidad se desea, a través del factor de ponderación . ${\displaystyle \lambda }$

Resumen del algoritmo RLS

El algoritmo RLS para un filtro RLS de orden p se puede resumir como

La recursividad para sigue una ecuación algebraica de Riccati y, por lo tanto, traza paralelos con el filtro de Kalman . ^[3] ${\displaystyle P}$

Filtro de mínimos cuadrados recursivo de celosía (LRLS)

El filtro adaptativo de mínimos cuadrados recursivo de celosía está relacionado con el RLS estándar, excepto que requiere menos operaciones aritméticas (orden N ). ^[4] Ofrece ventajas adicionales sobre los algoritmos LMS convencionales, como tasas de convergencia más rápidas, estructura modular e insensibilidad a las variaciones en la dispersión de valores propios de la matriz de correlación de entrada. El algoritmo LRLS descrito se basa en errores a posteriori e incluye la forma normalizada. La derivación es similar al algoritmo RLS estándar y se basa en la definición de . En el caso de la predicción directa, tenemos la señal de entrada como la muestra más actualizada. El caso de predicción hacia atrás es , donde i es el índice de la muestra en el pasado que queremos predecir y la señal de entrada es la muestra más reciente. ^[5] ${\displaystyle d(k)\,\!}$ ${\displaystyle d(k)=x(k)\,\!}$ ${\displaystyle x(k-1)\,\!}$ ${\displaystyle d(k)=x(k-i-1)\,\!}$ ${\displaystyle x(k)\,\!}$

Resumen de parámetros

${\displaystyle \kappa _{f}(k,i)\,\!}$es el coeficiente de reflexión directa

${\displaystyle \kappa _{b}(k,i)\,\!}$es el coeficiente de reflexión hacia atrás

${\displaystyle e_{f}(k,i)\,\!}$representa el error instantáneo de predicción directa a posteriori

${\displaystyle e_{b}(k,i)\,\!}$representa el error instantáneo de predicción hacia atrás a posteriori

${\displaystyle \xi _{b_{\min }}^{d}(k,i)\,\!}$es el error mínimo de predicción hacia atrás por mínimos cuadrados

${\displaystyle \xi _{f_{\min }}^{d}(k,i)\,\!}$es el error mínimo de predicción directa de mínimos cuadrados

${\displaystyle \gamma (k,i)\,\!}$es un factor de conversión entre errores a priori y a posteriori

${\displaystyle v_{i}(k)\,\!}$son los coeficientes multiplicadores feedforward.

${\displaystyle \varepsilon \,\!}$es una pequeña constante positiva que puede ser 0,01

Resumen del algoritmo LRLS

El algoritmo para un filtro LRLS se puede resumir como

Filtro de mínimos cuadrados recursivo de celosía normalizada (NLRLS)

La forma normalizada de LRLS tiene menos recursiones y variables. Se puede calcular aplicando una normalización a las variables internas del algoritmo que mantendrá su magnitud limitada por uno. Generalmente, esto no se usa en aplicaciones en tiempo real debido a la cantidad de operaciones de división y raíz cuadrada que conllevan una alta carga computacional.

Resumen del algoritmo NLRLS

El algoritmo para un filtro NLRLS se puede resumir como

Ver también

• Filtro adaptativo
• Filtro adaptativo del kernel
• Filtro de mínimos cuadrados medios
• Ecualizador de fuerza cero

Referencias

• Hayes, Monson H. (1996). "9.4: Mínimos cuadrados recursivos". Procesamiento y modelado estadístico de señales digitales . Wiley. pag. 541.ISBN​ 0-471-59431-8.
• Simon Haykin, Teoría del filtro adaptativo , Prentice Hall, 2002, ISBN 0-13-048434-2 
• MHA Davis, RB Vinter, Control y modelado estocástico , Springer, 1985, ISBN 0-412-16200-8 
• Weifeng Liu, Jose Principe y Simon Haykin, Filtrado adaptativo del kernel: una introducción completa , John Wiley, 2010, ISBN 0-470-44753-2 
• RLPlackett, Algunos teoremas en mínimos cuadrados , Biometrika, 1950, 37, 149-157, ISSN  0006-3444
• CFGauss, Theoria combineis observeum erroribus minimis obnoxiae , 1821, Werke, 4. Göttinge

Notas

1. Emannual C. Ifeacor, Barrie W. Jervis. Procesamiento de señales digitales: un enfoque práctico, segunda edición. Indianápolis: Pearson Education Limited, 2002, pág. 718
2. Steven Van Vaerenbergh, Ignacio Santamaría, Miguel Lázaro-Gredilla "Estimación del factor de olvido en mínimos cuadrados recursivos del kernel", Taller internacional IEEE 2012 sobre aprendizaje automático para procesamiento de señales, 2012, consultado el 23 de junio de 2016.
3. Welch, Greg y Bishop, Gary "Una introducción al filtro de Kalman", Departamento de Ciencias de la Computación, Universidad de Carolina del Norte en Chapel Hill, 17 de septiembre de 1997, consultado el 19 de julio de 2011.
4. Diniz, Paulo SR, "Filtrado adaptativo: algoritmos e implementación práctica", Springer Nature Suiza AG 2020, Capítulo 7: Algoritmos RLS basados ​​en celosía adaptativa. https://doi.org/10.1007/978-3-030-29057-3_7
5. Albu, Kadlec, Softley, Matousek, Hermanek, Coleman, Fagan "Implementación de celosía RLS (normalizada) en Virtex", Procesamiento de señales digitales, 2001, consultado el 24 de diciembre de 2011.