本文对 LMS 算法作以介绍,如有表述不当之处欢迎批评指正。欢迎任何形式的转载,但请务必注明出处。
目录
1. 引言2. 基本概念2.1. 横向滤波器2.2. 误差性能曲面2.3. 最陡下降法3. 实数 LMS 算法4. 复数 LMS 算法5. 后记6. 参考文献1. 引言
LMS(Least Mean Square)算法,即最小均方算法。由美国斯坦福大学的 B. Widrow 和 M. E. Hoff 于 1960 年在研究自适应理论时提出,由于其容易实现而很快得到了广泛应用,成为自适应滤波的标准算法。
2. 基本概念
2.1. 横向滤波器
可参考之前的文章 自适应滤波器之横向滤波器。
2.2. 误差性能曲面
在滤波器优化设计中,采用某种最小代价函数或者某个性能指标来衡量滤波器的好坏,而最常用的指标就是均方误差,也把这种衡量滤波器好坏的方法叫做均方误差准则。用公式表示如下:
E{e2(n)}=E{[d(n)−y(n)]2}(1)E\{e^2(n)\} = E\{[d(n) - y(n)]^2\}\tag{1}E{e2(n)}=E{[d(n)−y(n)]2}(1)
其中,E{e2(n)}E\{e^2(n)\}E{e2(n)} 就是均方误差。e(n)=d(n)−y(n)e(n) = d(n) - y(n)e(n)=d(n)−y(n),d(n)d(n)d(n) 表示滤波器输入 x(n)x(n)x(n) 时所期望得到的响应或者输出,y(n)y(n)y(n) 表示输入 x(n)x(n)x(n) 经过滤波器后实际得到的滤波器的输出,e(n)e(n)e(n) 表示输入 x(n)x(n)x(n) 时,滤波器的期望响应和实际输出之间的误差。
将 y(n)y(n)y(n) 表示成抽头权值输入列向量 x⃗(n)\vec{x}(n)x(n) 和抽头权值列向量 h⃗(n)\vec{h}(n)h(n) 内积的形式:y(n)=h⃗T(n)x⃗(n)y(n) = \vec{h}^{T}(n) \vec{x}(n)y(n)=hT(n)x(n),然后代入式 (1)(1)(1) 中,可知式 (1)(1)(1) 是以 h⃗(n)\vec{h}(n)h(n) 为多维自变量的函数,由于自变量是多维的,所以该函数对应图形是一个超抛物面(可以想象成碗的样子)且是衡正的,该超抛物面就是误差性能曲面。超抛物面有一个总体的最小值,该最小值就是最小均方误差。如前面所述,均方误差是衡量滤波器好坏的一个常用指标。当均方误差达到最小值时,该滤波器性能达到最优,即误差性能曲面上取值为最小的点对应的坐标就是最优滤波器系数向量(即最期望的滤波器抽头权值向量)。
2.3. 最陡下降法
由前面所述可知,为了使在均方误差准则设计下的滤波器性能达到最优,需要找到误差性能曲面上的最小值,由此即可得到最优滤波器系数。
在误差性能曲面上寻找的一个非常自然的方法就是沿着曲面的切线方向,也即负梯度方向进行寻找,而这个寻找过程是一个迭代的过程。设第 nnn 次迭代得到的滤波器抽头权值列向量为 h⃗(n)\vec{h}(n)h(n),并设该次迭代得到的均方误差是 ε(n)\varepsilon(n)ε(n),那么第 n+1n+1n+1 次迭代得到的滤波器系数可由下式求出:
h⃗(n+1)=h⃗(n)−12g⃗(n)μ(n)(2)\vec{h}(n+1) = \vec{h}(n) - \frac{1}{2} \vec{g}(n) \mu(n) \tag{2}h(n+1)=h(n)−21g(n)μ(n)(2)
其中 g⃗(n)\vec{g}(n)g(n) 是该次迭代时的梯度向量,−g⃗(n)-\vec{g}(n)−g(n) 就是该次迭代的方向向量,μ(n)\mu(n)μ(n) 是第 nnn 次迭代时所用的步长,又称作收敛因子。且:
g⃗(n)=∂ε(n)∂h⃗(n)=∂E{e2(n)}∂h⃗(n)(3)\vec{g}(n) = \frac{\partial\varepsilon(n)}{\partial\vec{h}(n)}=\frac{\partial E\{e^2(n)\}}{\partial\vec{h}(n)} \tag{3}g(n)=∂h(n)∂ε(n)=∂h(n)∂E{e2(n)}(3)
上述选择误差性能曲面上负的梯度向量作为搜索时的方向向量的方法称为“最陡下降法”。
3. 实数 LMS 算法
在利用上述的最陡下降法计算 g⃗(n)\vec{g}(n)g(n) 时需要知道一些先验知识,而这在实际工作中是无法实现的,因此必须得到 g⃗(n)\vec{g}(n)g(n) 的估计值 g^⃗(n)\vec{\widehat{g}}(n)g(n)。
B. Widrow 和 M. E. Hoff 提出的思路是利用瞬时误差能量 e2(n)e^2(n)e2(n) 来代替均方误差能量 E{e2(n)}E\{e^2(n)\}E{e2(n)}。可知:
g^⃗(n)=∂e2(n)∂h⃗(n)=−2e(n)x⃗(n)(4)\vec{\widehat{g}}(n)=\frac{\partial e^2(n)}{\partial\vec{h}(n)}=-2e(n)\vec{x}(n) \tag{4}g(n)=∂h(n)∂e2(n)=−2e(n)x(n)(4)
进一步令 μ(n)\mu(n)μ(n) 为常数 μ\muμ,则可得到新的迭代公式:
h⃗(n+1)=h⃗(n)+μe(n)x⃗(n)(5)\vec{h}(n+1)=\vec{h}(n)+\mu e(n)\vec{x}(n) \tag{5}h(n+1)=h(n)+μe(n)x(n)(5)
上式即为 LMS 算法,又称随机梯度法。为了使 LMS 算法收敛,经过推导 μ\muμ 的取值范围应该是:
0<μ<2/MPx(6)0<\mu<2/MP_x\tag{6}0<μ<2/MPx(6)
其中 MMM 为滤波器的长度,PxP_xPx 为输入信号的功率。
4. 复数 LMS 算法
上述描述的算法均是在实数上定义的,下面给出了在复数上定义的 LMS 算法(具体推导过程可参考 论文笔记之 CLMS)。
y(n)=h⃗T(n)x⃗(n)(7){\bm y(n)} = \vec{{\bm h}}^{T}(n) \vec{{\bm x}}(n) \tag{7}y(n)=hT(n)x(n)(7)
e(n)=d(n)−y(n)(8){\bm e(n)} = {\bm d(n)} - {\bm y(n)} \tag{8}e(n)=d(n)−y(n)(8)
h⃗(n+1)=h⃗(n)+μe(n)x⃗∗(n)(9)\vec{{\bm h}}(n+1) = \vec{{\bm h}}(n) + \mu {\bm e(n)} \vec{{\bm x}}^{*}(n)\tag{9}h(n+1)=h(n)+μe(n)x∗(n)(9)
其中,黑体表示复数信号,∗*∗ 表示复数共轭。
在一些文献中,读者还能看到以下复数形式:
y(n)=h⃗H(n)x⃗(n)(10){\bm y(n)} = \vec{{\bm h}}^{H}(n) \vec{{\bm x}}(n) \tag{10}y(n)=hH(n)x(n)(10)
e(n)=d(n)−y(n)(11){\bm e(n)} = {\bm d(n)} - {\bm y(n)} \tag{11}e(n)=d(n)−y(n)(11)
h⃗(n+1)=h⃗(n)+μe∗(n)x⃗(n)(12)\vec{{\bm h}}(n+1) = \vec{{\bm h}}(n) + \mu {\bm e}^{*}(n) \vec{{\bm x}}(n)\tag{12}h(n+1)=h(n)+μe∗(n)x(n)(12)
其中,HHH 表示复数共轭转置。
5. 后记
LMS 算法提出之后,研究者们又提出了许多改进版的 LMS 算法。其中,最常用的当属归一化 LMS(NLMS) 算法,对该算法的介绍可参考 自适应滤波器之 NLMS 算法。
6. 参考文献
[1] 《数字信号处理理论,算法与实现》第三版 作者:胡广书