递归最小二乘法

线性最小二乘法(LMS)在应用时所有数据都是一次全部测量好再进行求解。但实际中有时存在测量数据时在想获得的,即时刻获得测量数据,每次获得新的测量数据后,需要进行最小二乘法以更新状态。如果每次更新都采用最小二乘法伪逆解进行更新,计算次数很多,计算量很大,且需要保存测量数据。我们可以采用递归的方式,递归最小二乘法(RLS,Recursive Least Squares),每次对新测量结果进行修正,减少计算量和存储量。

我们首先回顾下线性最小二乘法的伪逆解, n为样本数,其中矩阵求逆的计算量时很大的

Y_n=X_n*\vec{\omega} \\
\vec{\omega}=(X_n^TX_n)^{-1}X_n^TY_n

样本递归最小二乘

我们把矩阵求逆部分标记为R, 那么解可以写为:

R_n=X_n^TX_n \\
z_n=X_n^TY_n \\
=>  \vec{\omega}_n=R_n^{-1}z_n

当新样本来临时,我们的处理是在 Xn 原矩阵下方加入一个新的行向量,故我们对Xn进行分块处理,根据矩阵乘法有下式:

R_n=X_n^TX_n=[X_{n-1}^T|x_n][\frac{X_{n-1}}{x_n}]\\
=X_{n-1}^TX_{n-1}+x_nx_n^T \\
=R_{n-1}+x_nx_n^T

这样我们就有了一个基本的递归公式

时间递归最小二乘

实际应用中,我们会考虑新的样本比旧的样本更有价值,于是我们给递归中加入一个遗忘因子 \lambda ,得到如下表达

R_n=\lambda R_{n-1} + x_nx_n^T

Rn逆的递推

我们这里再插入介绍一条关于矩阵逆的引理(如果需要证明下式,直接将两式相乘即可,如果正向严格证明,需要用到舒尔补,可以参考:https://blog.sciencenet.cn/blog-465130-1086221.html

A=B^{-1}+CD^{-1}C^T \\
A^{-1}=B-BC(D+C^TBC)^{-1}C^TB

我们要求快速求Rn的逆,就需要借助上式:

A=R_n \\
B=(\lambda R_{n-1})^{-1} \\
C=x_n \\
D=1

ABCD四项直接带入,经过化简最终可以得到下式,看起来很麻烦,但是相比直接求逆还是要简化不少:

R_n^{-1}=\frac{R_{n-1}^{-1}}{\lambda}-\frac{R_{n-1}^{-1}x_nx_n^TR_{n-1}^{-1}}{\lambda ^2+\lambda x_n^tR_{n-1}^{-1}x_n}

我们进一步简化公式,我们定义式子的中间项,增益向量为kn , 式子进一步简化:

k_n=\frac{R_{n-1}^{-1}x_n}{\lambda+x_n^TR_{n-1}^{-1}x_n} \\
R_n^{-1} = \frac{1}{\lambda}R_{n-1}^{-1}-\frac{1}{\lambda}k_nx_n^TR_{n-1}^{-1}

这里有一个巧合

R_n^{-1} x_n=k_n

到这里我们已经明确了Rn的递归关系

Zn的递推

我们在回到式子另一项Zn,同样采用分块的方式进行推导递归关系:

z_n=X_n^TY_n=[X_{n-1}^T|x_n][\frac{Y_{n-1}}{y_n}]\\
=X_{n-1}^TY_{n-1}+x_ny_n \\
z_n=\lambda z_{n-1}+x_ny_n

我们回到最初的表达,把递推关系带入:

\omega_n=R_n^{-1}z_n=P_nz_n \\
\omega_n=P_nz_n=P_n[\lambda z_{n-1}+x_ny_n] \\
=\lambda[\frac{1}{\lambda}P_{n-1}-\frac{1}{\lambda}k_nx_n^TP_{n-1}]z_{n-1}+P_nx_ny_n \\
=P_{n-1}z_{n-1}-k_nx_n^{n}P_{n-1}z_{n-1}+P_nx_ny_n \\
=\omega_{n-1}-k_n(x_n^T\omega_{n-1}-y_n)

结论

好了,这样我们就得到了RLS算法推导的结论:

\omega_n=\omega_{n-1}+k_ne_n

参考资料:

https://www.bilibili.com/video/BV14S4y1T7X6/?vd_source=e9a49c3706fb720317b097c81f7e033c

发表评论