最小均方滤波器

最小均方滤波器（Least Mean Square Filter，或LMS Filter）是一类可通过最小化误差讯号（error signal）之均方值（mean square）而修正滤波器系数，以模拟所需理想滤波器的自适应滤波器，其中作为修正依据的误差讯号为理想参考讯号与实际输出讯号之差。该种滤波器所用之最小均方法只以当前之讯号误差值为准进行修正，是一种随机梯度下降法。最小均方法系由斯坦福大学的Bernard Widrow教授及他的首位博士班学生Marcian Hoff于1960年提出。最小均方滤波器属于常见的自适应滤波器种类之一。

## 最小均方：问题起源

<image>

### 与维纳滤波器的关系

因果维纳滤波器（Causal Wiener Filter）的实现在形式上与最小平方法的实现非常相似，但在讯号处理这一方面却有所不同。对于最小平方的实现，令输入矩阵为$\scriptstyle\mathbf{X}$，输出矩阵为$\scriptstyle\mathbf{y}$，有：

$$\boldsymbol{\hat\beta} = (\mathbf{X} ^\mathbf{T}\mathbf{X})^{-1}\mathbf{X}^{\mathbf{T}}\boldsymbol y .$$

而有限脉冲响应（Finite Impulse Response）的最小均方滤波器和Wiener滤波器有关，只是前者并不依赖计算互相关或自相关函数即可将误差基准最小化，且其解将会收敛直至与Wiener滤波器的解重叠。大部分的线性可适性滤波问题均可以上图中的架构进行模拟，即希望尽量准确地确认一未知系统$\mathbf{h}(n)$，因此通过可适性滤波，仅以可观测讯号$x(n)$、$d(n)$与$e(n)$产生对$\mathbf{h}(n)$的估计值$\hat{\mathbf{h}}(n)$并尽量使其接近$\mathbf{h}(n)$。上图中的另几个讯号$y(n)$、$v(n)$与$h(n)$却不处于能直接被观测到的范围中。

### 变量之定义

$n$：当前输入序列的样本数（长度）。

$p$：滤波器级数。

$\{\cdot\}^H$（埃尔米特转置或共轭转置）

$$\mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T$$

$$\mathbf{h}(n) = \left[h_0(n), h_1(n), \dots, h_{p-1}(n)\right]^T,\quad \mathbf{h}(n) \in \mathbb{C}^p$$

$$y(n) = \mathbf{h}^H(n) \cdot \mathbf{x}(n)$$

$$d(n) = y(n) + \nu(n)$$

$\hat{\mathbf{h}}(n)$：对$h(n)$的估计值，可理解为代表在n个观测周期后对滤波器系数的估计。

$$e(n) = d(n) - \hat{y}(n) = d(n) - \hat{\mathbf{h}}^H(n) \cdot \mathbf{x}(n)$$

## 最小均方滤波器的基本特点

最小均方滤波器所获得的广泛应用主要得益于其两个特性：易于实作（Simplicity of implementation）与性能稳健（Robust performance）——后者主要得益于最小均方滤波器基本上不受模型影响（Model-independency）。

最小均方滤波器亦与梯度下降法（Method of steepest descent）不同：后者主要对随机输入讯号进行使用确定梯度的递归运算。此外，最小均方滤波器的实现亦不需要对相关函数取值进行测量或计算负矩阵。事实上，其他的各种线性可适性滤波算法均广泛地以最小均方滤波算法为基准，以估量自身效能。

## 概览与主要思想

最小均方滤波器的主旨是逐步进行修正，以逼近最佳的滤波系数；由Wiener–Hopf方程可解得，理想中的最佳滤波系数（所构成之向量）为$w_0=(R^{-1}p)$；其中R为输入滤波器的输入矩阵u(n)的（自）相关矩阵，p为u(n)与理想参考讯号d(n)之间的互相关向量。

基本而言，最小均方滤波算法作为线性可适性滤波算法的一种，包括有以下两个基本步骤：

一、滤波步骤（filtering process）：这一步骤包括了（a）计算一线性滤波器对一输入讯号的响应输出与（b）产生上一步中相应输出和理想相应间的测量误差值。

二、自适步骤（adaptive process）：这一步骤中，以滤波步骤中得到的测量误差值为根据，滤波器本身的参数取值将被自动更新（以便在下一个周期中产生的测量误差值相对减小）。

上述两个步骤被组合起来，形成一个反馈循环（feedback loop）。

最小均方算法首先由一组很小的权重系数（常取零）开始，且在循环的每一步中找到均方误差的斜率梯度，依据斜率梯度更新滤波器的权重系数。均方误差的斜率梯度为正值即说明若保持现有的滤波器权重系数，误差将在未来的循环中持续向正向增大——因此需要减小权重系数。同样地，若均方误差的斜率梯度为负值，就需要增大权重系数。因此，基本的权重系数递归方程为：

$W_{n+1} = W_n - \mu\nabla \varepsilon [n]$。

其中$\varepsilon$代表了均方误差之值，其系数之前的负号说明需要向斜率梯度的反方向调整滤波器系数。

上述的均方误差作为以滤波器系数为自变量的函数，具有二次函数的形式；这说明仅存在一个极值能使均方误差值最小，而这正对应了最佳的滤波器系数。因此，最小均方算法可以通过调整均方误差-滤波器系数平面上的曲线位置，来逐步迫近最适的滤波器系数取值。

### 算法之实现

对于$order=p$的情形，可适性最小均方滤波器的算法实现如下所示：

涉及参数之定义:｜$p=$ 滤波器的阶数

$\mu=$ 步长

初始化:｜$\hat{\mathbf{h}}(0)=\operatorname{zeros}(p)$

运算循环:｜For $n=0,1,2,...$

$$\mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T$$ $$e(n) = d(n)-\hat{\mathbf{h}}^{H}(n)\mathbf{x}(n)$$ $$\hat{\mathbf{h}}(n+1) = \hat{\mathbf{h}}(n)+\mu\,e^{*}(n)\mathbf{x}(n)$$

## 收敛效率与稳定性

由于最小均方算法并不使用准确的期望值，滤波器的权重系数也就不会绝对地达到最佳取值，但是在总体上算法仍然可以达到收敛——即实际权重系数将与最佳权重系数相比将或大或小，但误差大小会相当有限。然而若权重系数变动时的方差（或标准差）过大，收敛的方向就可能错误。若算法中的步长未经过谨慎的选择，上述问题就很可能会发生。

如步长$\mu$的取值较大，权重系数就会在更新循环中更快地向梯度估计值的方向改变，从而使得权重系数在每一次循环中的变动值更大——若开始时的梯度值为负，在更新权重后梯度便可能变为正值。亦即在“第二个”时刻，权重系数的值将因为负的梯度值向相反方向剧烈改变；此后，权重系数的值仍将以较大的幅度围绕最佳取值上下波动。从另一方面来说，若$\mu$的取值过小，要达成最佳权重系数便会需要过于漫长的收敛时间。因此，算法的实现需要在两种极端之间有所权衡与取舍。

因此，算法步长$\mu$应有一上限，如下：

$$0<\mu<\frac{2}{\lambda_{\mathrm{max}}}$$

其中$\lambda_{\max}$是自相关矩阵${\mathbf{R}} = E\{{\mathbf{x}}(n){\mathbf{x}^H}(n)\}$中的最大特征值。当上式所述的条件未能达到时，系统将是非稳定的， $\hat{h}(n)$也不会收敛。

最快收敛速度的达成条件如下：

$$\mu=\frac{2}{\lambda_{\mathrm{max}}+\lambda_{\mathrm{min}}},$$ 其中$\lambda_{\min}$是R的最小特征值。

考虑到$\mu$的值小于等于最佳值，收敛速度将会由$\lambda_{\min}$决定，其值越大，就会导致收敛速度越快。这就意味着最佳收敛速度可以在当$\lambda_{\max}$接近$\lambda_{\min}$时达成，即由${\mathbf{R}}$的特征值扩散度决定可达到的最高收敛速度。

一个白噪声讯号的自相关矩阵为${\mathbf{R}}=\sigma^2 {\mathbf{I}}$；其中$\sigma^2$是讯号的方差。在这种情况下所有的特征值都是相等的，且特征值扩散度在所有的可能矩阵中为最小。

对于这上述结果的一种常见解释是正因为如此，最小均方算法才会对白讯号为输入的情形收敛更快，而对如带有低通或高通特性的有色讯号（均值不为零）输入收敛得更慢。

值得注意的是前面阐述的$\mu$值上限只在普遍意义上对可适性最小均方滤波器的稳定性存在影响，在单独的实际情形中，$\hat{h}(n)$的系数仍然可能增长至至无限大，即滤波器权重系数仍可能发散而无法达到收敛。一个更为实际的上下限条件是：

$$0<\mu<\frac{2}{\mathrm{tr}\left[{\mathbf{R}}\right]},$$ 其中$\mathrm{tr}[{\mathbf{R}}]$表示${\mathbf{R}}$的轨迹（trace）。上述上下限条件确保了$\hat{h}(n)$的系数将不会发散（在实际情况中，由于上述公式在推导过程中所假定的条件过于宽松，$\mu$的值不应选取得过于接近上限）。

## 归一化最小均方滤波器

对于基本的最小均方算法来说，其最大的缺陷就是对于输入$x(n)$振幅过于敏感。这就使得设计者难以选取能够确保算法稳定性的步长$\mu$取值。因此，可运用归一化最小均方滤波器——最小均方滤波器的一种变种，来将输入讯号的功率归一化，以解决这一问题。下面是对归一化最小均方算法的简述：

参数定义｜$p=$ 滤波器级数

$\mu=$ 滤波器步长

初始化：｜$\hat{\mathbf{h}}(0)=\operatorname{zeros}(p)$

开始运算：｜For $n=0,1,2,...$

$$\mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T$$ $$e(n) = d(n)-\hat{\mathbf{h}}^{H}(n)\mathbf{x}(n)$$ $$\hat{\mathbf{h}}(n+1) = \hat{\mathbf{h}}(n)+\frac{\mu\,e^{*}(n)\mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)}$$

### 最佳步长取值

若不存在干扰讯号$v(n)=0$，归一化最小均方算法可选取的最佳步长值为$\mu_{opt}=1$，该值不受输入讯号$x(n)$与实际响应$\mathbf{h}(n)$的影响。在存在干扰($v(n) \ne 0$)的情形中，最佳步长值则为：

$$\mu_{opt}=\frac{E\left[\left|y(n)-\hat{y}(n)\right|^2\right]}{E\left[|e(n)|^2\right]}$$

上述结果是在假定讯号$v(n)$与$x(n)$互不相关的前提下推导出的，该假设亦在大部分情形下符合现实。