Filtro recursivo de mínimos cuadrados

El método de mínimos cuadrados recursivos ( RLS ) es un algoritmo de filtro adaptativo que encuentra recursivamente los coeficientes que minimizan una función de coste de mínimos cuadrados lineales ponderados relacionada con las señales de entrada. Este enfoque contrasta con otros algoritmos, como el de mínimos cuadrados medios (LMS), que buscan 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 presenta una convergencia extremadamente rápida. Sin embargo, esta ventaja conlleva una elevada complejidad computacional.

El RLS fue descubierto por Gauss , pero permaneció sin usar o ignorado 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(nk)+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 de -taps , : ${\displaystyle v(n)}$${\displaystyle d(n)}$${\displaystyle p+1}$${\displaystyle \mathbf {w} }$

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

donde es el vector 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(np)]^{T}}$${\displaystyle p+1}$${\displaystyle x(n)}$

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

El objetivo es estimar los parámetros del filtro , y en cada instante nos referimos a la estimación actual como y a la estimación de mínimos cuadrados adaptada por . también es un vector columna, como se muestra a continuación, y la transpuesta , , es un vector fila . El producto matricial (que es el producto escalar de y ) es , un escalar. La estimación es "buena" si es pequeña en magnitud 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 {\sombrero {d}}(n)-d(n)}$

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

La ventaja del algoritmo RLS es que no requiere la inversión de matrices, lo que ahorra costes computacionales. Otra ventaja es que proporciona una comprensión intuitiva de resultados como los del filtro de Kalman .

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

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

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

La función de error de mínimos cuadrados ponderados —la función de coste que deseamos minimizar—, al ser una función de , también depende de los coeficientes del filtro: ${\displaystyle C}$${\displaystyle e(n)}$

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

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

La función de coste se minimiza tomando las derivadas parciales de todas las entradas del vector de coeficientes e igualando los resultados a cero. ${\displaystyle k}$${\displaystyle \mathbf {w} _ {n}}$

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

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

${\displaystyle \sum _{i=0}^{n}\lambda ^{ni}\left[d(i)-\sum _{\ell =0}^{p}w_{n}(\ell )x(i-\ell )\right]x(ik)=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 ^{ni}\,x(i-\ell )x(ik)\right]=\sum _{i=0}^{n}\lambda ^{ni}d(i)x(ik)\qquad k=0,1,\ldots ,p}$

Esta forma puede expresarse 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 costo 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 resultado principal de la discusión.

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

La discusión dio como resultado una única ecuación para determinar un vector de coeficientes que minimiza la función de costo. 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)}$

donde es el vector de datos dimensional ${\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 de autocovarianza determinista. Para ello, la identidad matricial de Woodbury resulta muy útil.

La identidad de la matriz de Woodbury es la siguiente:

Para estar en consonancia con la literatura estándar, definimos

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

Antes de continuar, es necesario ponerlo en 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 se sigue ${\displaystyle \mathbf {P} (n)}$

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

Ahora estamos listos para completar la recursión. Como ya se ha comentado,

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 esto 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 ? Compárelo con el error a posteriori ; el error calculado después de que se actualiza 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 hemos encontrado 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 }$

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

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

El filtro adaptativo de mínimos cuadrados recursivos reticulares 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 los 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 predicción hacia adelante, tenemos con 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)\,\!}$

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

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

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

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

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

${\displaystyle \xi _{f_{\min }}^{d}(k,i)\,\!}$es el error mínimo de predicción hacia adelante 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 del multiplicador de alimentación directa.

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

El algoritmo para un filtro LRLS se puede resumir como

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

El algoritmo para un filtro NLRLS se puede resumir como

• Filtro adaptativo
• Filtro adaptativo de núcleo
• filtro de mínimos cuadrados
• Ecualizador de forzado a cero

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