一般的LMS算法应用参见该篇。
一般的LMS实际应用
本文设计LMS背后的数学理论知识。
1. The Least Mean Squares algorithm (LMS)
SD研究的最陡下降方法是一种递归计算信号统计量已知时维纳滤波器的递归算法 (knowledge about R och p)。
问题是，这个信息通常是未知的！
LMS是一种基于与最陡下降法相同的原理的方法，但其统计量是连续估计的。
由于统计量是连续估计的，因此LMS算法可以适应信号统计量的变化；因此，LMS算法是一种自适应滤波器。
我们想创建一个算法，以最小化\(E\{|e(n)|^2\}\)，就像SD一样，但基于未知的统计数据。
其中一个策略是使用自相关矩阵R和交叉相关向量p的估计。如果选择了瞬时估计值:
所得方法是最小均方乘算法。
对于SD，滤波器权值的更新由：
\[\pmb w(n+1)=\pmb w(n)+\frac{1}{2}\mu[-\nabla J(n)] \]where \(\nabla J(n)=-2\pmb p+2\pmb R \pmb w(n)\)
在LMS中，我们使用估计的\(\hat{\pmb R},\hat{\pmb p}\)来计算\(\hat{∇}J(n)\)，因此，更新的滤波器向量也成为一个估计。因此，记为\(\hat{w}(n)\)：
\[\hat{\pmb \nabla}J(n)=-2 \hat{\pmb p}+2 \hat{\pmb R} \hat{\pmb w}(n) \]对于LMS算法，滤波器权值的更新方程变为:
\[\hat{\pmb w}(n+1)=\hat{\pmb w}(n)+\mu \pmb u(n)e^{*}(n) \]where \(e^{*}(n)=d^{*}(n)-\pmb u^{H}(n)\hat{\pmb w(n)}\)
与SD对应式比较：
\[\pmb w(n+1)=\pmb w(n)+\mu E\{ \pmb u(n)e^{*}(n)\} \]where \(e^{*}(n)=d^{*}(n)-\pmb u^{H}(n)\pmb w(n)\)
因此，差异在于将\(E\{\pmb u(n)e^{∗}(n)\}\)估计为\(\pmb u(n)e^{∗}(n)\)。这将导致梯度噪声。
2. Convergence analysis of the LMS
考虑更新方程:
\[\hat{\pmb w}(n+1)=\hat{\pmb w}(n)+\mu \pmb u(n)e^{*}(n) \]我们想知道在\(J(n)\)和\(\hat{\pmb w(n)}\)方面，算法的收敛速度和收敛速度。
Strategy:
- 介绍滤波器权重误差向量\(\epsilon(n)=\hat{\pmb w}(n)−\pmb w_o\)。
- 用\(\epsilon (n)\)表示更新方程。
- 同\(\epsilon (n)\)表示\(J(n)\)。其中涉及到\(\pmb K(n)=E\{\pmb \epsilon (n)\pmb \epsilon^{H}(n)\}\)。
- 计算\(\pmb K(n)\)中的差分方程，它控制了收敛性。
- 从\(\pmb K(n)\)到\(\pmb X(n)\)进行变量变化，其收敛速度同样快。
2.1 The filter weight error vector
LMS包含反馈，就像SD一样，如果没有适当地选择步长µ，算法也存在发散的风险。为了研究其稳定性，引入了滤波器权重误差向量\(\epsilon (n)\)：
\[\pmb \epsilon (n)=\hat{\pmb w}(n)-\pmb w_o \]其中\(\pmb w_o=\pmb R^{-1}\pmb p，Wiener-Hopf\)。
注意，\(\epsilon (n)\)对应于SD中的\(c(n)=\pmb w(n)w−\pmb w_o\)，但由于\(\hat{\pmb w}(n)\)，\(\epsilon (n)\)是随机的。
2.2 Update equation in \(\epsilon (n)\)
n+1时刻\(\epsilon (n)\)的更新方程可以递归地表示为:
\[\epsilon (n)=\hat{\pmb w}(n)-\pmb w_o \] \[\begin{aligned} \epsilon (n+1)&=\hat{\pmb w}(n+1)-\pmb w_o \\ &=\hat{\pmb w}(n)+\mu \pmb u(n)e^{*}(n)-\pmb w_o \\ &=\pmb \epsilon (n)+\mu \pmb u(n)[d^{*}(n)-\pmb u^{H}(n)\hat{\pmb w(n)}] \\ &=\pmb \epsilon (n)+\mu \pmb u(n)[d^{*}(n)-\pmb u^{H}(n)\pmb w_o-\pmb u^{H}(n)\pmb \epsilon (n)] \\ &=[\pmb I-\mu \pmb u(n)\pmb u^{H}(n)]\pmb \epsilon(n)+\mu \pmb u(n)e^{*}_{o}(n) \end{aligned} \]where \(\pmb u(n)e^{*}_{o}(n)=d^{*}(n)-\pmb u^{H}(n)\pmb w_o\)
与SD值相比：
\[\pmb c(n)=\pmb w(n)-\pmb w_o \] \[\begin{aligned} \pmb c(n+1)&=\pmb w(n)+\mu[\pmb p-\pmb R\pmb w(n)]-\pmb w_o \\ &=\pmb c(n)+\mu[\pmb p-\pmb R\pmb w(n)] \\ &=\pmb c(n)+\mu [\pmb R\pmb w_o-\pmb R\pmb w(n)] \\ &=\pmb c(n)+\mu \pmb R[\pmb w_o-\pmb w(n)] \\ &=c(n)-\mu \pmb R c(n) \\ &=(\pmb I-\mu \pmb R)\pmb c(n) \end{aligned} \] \[\pmb c(n+1)=(\pmb I-\mu \pmb R)\pmb c(n) \]2.3 Express J(n) in \(\epsilon(n)\)
LMS的收敛性分析要比SD的收敛性分析复杂得多。因此，需要两种假设（近似值）。
- Independence theory
- Direct-averaging method
2.3.1 Independence theory
- 不同时间的输入向量实例n，u（1），u（2），…，u(n)，是相互独立的（因此不相关）。
- n时刻的输入信号向量与所有早期时刻的期望信号无关，u(n)独立于d（1），d（2），……，d(n−1)。
- 时间n、d(n)的期望信号独立于所有早期的期望信号，d（1）、d（2），…，d(n−1)，但依赖于时间n、u(n)的输入信号向量。
- 同时出现瞬间n的信号d(n)和u(n)相互正态分布。
2.3.2 Direct-averaging
Direct-averaging意味着在更新方程中的\(\epsilon\)，
\[\epsilon (n+1)=[\pmb I-\mu \pmb u(n)\pmb u^{H}(n)]\pmb \epsilon(n)+\mu \pmb u(n)e^{*}_{o}(n) \]瞬时估计\(\hat{\pmb R}(n)=\pmb u(n)\pmb u^{H}(n)\)被期望集合\(\pmb R=E\{\pmb u(n)\pmb u^{H}(n)\}\)取代：
\[\epsilon (n+1)=[\pmb I-\mu \pmb R]\pmb \epsilon(n)+\mu \pmb u(n)e^{*}_{o}(n) \]在SD中，我们有：
\[J(n)=J_{min}+(\pmb w-\pmb w_o)^{H}\pmb R(\pmb w-\pmb w_o) \]而R的特征值控制了收敛速度。
对于LMS来说，\(\pmb \epsilon (n)=\hat{\pmb w}(n)-\pmb w_o\)
\[\begin{aligned} J(n)&=E\{|e(n)|^{2}\}=E\{|d(n)-\hat{\pmb w}^{H}u(n)|^2\} \\ &=E\{|e_o(n)-\pmb \epsilon^{H}u(n)|^2\} \\ &=^{i}E\{|e_o(n)|^{2}\}+E\{\pmb \epsilon^{H} (n)\pmb u(n)\pmb u^{H}(n)\pmb \epsilon (n)\} \end{aligned} \]这里，(i)表示使用了独立性假设。由于\(\pmb \epsilon\)和\(\hat{\pmb R}\)是估计值，而且不是独立的，所以期望算子不能平移到里面。
\(J_{ex}(n)=J(n)−J_{min}=E{\pmb \epsilon^{H}(n)\hat{\pmb R}(n)\pmb \epsilon(n)}\)的行为决定了收敛性。
下面简述一下需要用的性质：
- \(tr(scalar)=scalar\)
- \(tr(\pmb A\pmb B)=tr(\pmb B\pmb A)\)
- \(E\{tr(\pmb A)\}=tr(E\{\pmb A\})\)
\(J_{ex}(n)\)可以被重写为：
\[\begin{aligned} J_{ex}(n)&=E\{tr[\hat{\pmb R}(n)\pmb \epsilon(n)\pmb \epsilon^{H}(n)]\} \\ &=tr[E\{\hat{\pmb R}(n)\pmb \epsilon(n)\pmb \epsilon^{H}(n)\}] \\ &=tr[E\{\hat{\pmb R}(n)\}E\{\pmb \epsilon(n)\pmb \epsilon^{H}(n)\}] \\ &=tr[\pmb R\pmb K(n)] \end{aligned} \]收敛性取决于：\(\pmb K(n)=E\{\pmb \epsilon(n)\pmb \epsilon^{H}(n)\}\)
2.4 Difference equation of \(\pmb K(n)\)
滤波器权重误差的更新方程为，如前所示:
\[\epsilon (n+1)=[\pmb I-\mu \pmb u(n)\pmb u^{H}(n)]\pmb \epsilon(n)+\mu \pmb u(n)e^{*}_{o}(n) \]这个随机差分方程的解是对于小的\(µ\)接近于对的解(由Direct-averaging):
\[\epsilon (n+1)=[\pmb I-\mu \pmb R]\pmb \epsilon(n)+\mu \pmb u(n)e^{*}_{o}(n) \]这个方程仍然很难求解，但是现在K(n)的行为可以用下面的差分方程来描述：
\[\pmb K(n+1)=(\pmb I-\mu \pmb R)\pmb K(n)(\pmb I-\mu \pmb R)+\mu^2J_{min}\pmb R \]2.5 Changing of variables from \(\pmb K(n)\) to \(\pmb X(n)\)
我们运用正交分解：
\[\pmb Q^{H}\pmb R \pmb Q=\pmb \Lambda \]同时我们假设：
\[\pmb Q^{H}\pmb K(n) \pmb Q=\pmb X(n) \]其中\(\pmb Λ\)是\(\pmb R\)的对角特征值矩阵，其中\(\pmb X(n)\)通常不是对角的，得到:
\[J_{ex}(n)=tr(\pmb R\pmb K(n))=tr(\pmb \Lambda \pmb X(n)) \]由\(\pmb K(n)\)表示\(\pmb X(n)\)：
\[\pmb X(n+1)=(\pmb I-\mu \pmb \Lambda)\pmb X(n)(\pmb I-\mu \pmb \Lambda)+\mu^2J_{min}\pmb \Lambda \]\(J_{ex}(n)\)仅依赖于\(X(n)\)的对角线元素（因为跟踪\(tr(ΛX(n)]\)）。因此，我们可以编写\(J_{ex}(n)=\sum \limits_{i=1}^{M}λ_ix_{ii}(n)\)。
对角线元素的更新是由:
这是一个非均匀差分方程。这意味着将包含一个瞬态部分，以及一个依赖于Jmin和µ的静止部分。因此，可以编写成本函数:
\[J(n)=J_{min}+J_{ex}(\infty)+J_{trans}(n) \]其中\(J_{min}+J_{ex}(\infty) och J_{trans}(n)\)分别是是平稳的和瞬态的。
最好的情况是，LMS达到\(J_{min}+J_{ex}(\infty)\)。
2.5 LMS的一些性质
- 关于learning rate的限制同SD：
- \[J_{ex}(\infty)=J_{min}\sum \limits_{i=1}^{M}\frac{\mu \lambda_i}{2-\mu \lambda_i} \]
Proof:
\[\begin{aligned} J_{ex}(n)&=\sum \limits_{i=1}^{M}λ_ix_{ii}(n) \\ J_{ex}(n+1)&=\sum \limits_{i=1}^{M}λ_ix_{ii}(n+1) \\ &=\sum \limits_{i=1}^{M}λ_i[(1-\mu \lambda_i)^2x_i(n)+\mu^2J_{min} \lambda_i] \\ &=\sum \limits_{i=1}^{M}λ_i[(1-\mu \lambda_i)^{n}x_i(1)+\mu^2J_{min} \lambda_i(1+(1-\mu \lambda_i)^2+(1-\mu \lambda_i)^4+...+(1-\mu \lambda_i)^{2(n-1)})] \end{aligned} \]所以：
\[\begin{aligned} J_{ex}(\infty)&=\lim \limits_{n->\infty}\sum \limits_{i=1}^{M}λ_i[(1-\mu \lambda_i)^{n}x_i(1)+\mu^2J_{min} \lambda_i(1+(1-\mu \lambda_i)^2+(1-\mu \lambda_i)^4+...+(1-\mu \lambda_i)^{2(n-1)})] \\ &=J_{min}\sum \limits_{i=1}^{M}\frac{\mu \lambda_i}{2-\mu \lambda_i} \end{aligned} \]- \(M=J\frac{J_{ex}(\infty)}{J_{min}}\)是衡量最优解与LMS（均方意义上）的距离.
3. Rules of thumb LMS
\(\pmb R\)的各个特征值很少被知道，但是特征值的和却可以用平均功率描述。因此，通常使用一套拇指规则，即基于输入功率：
\[\sum \limits_{k=0}^{M-1}E\{|u(n-k)|^2\}=Mr(0)=tr(\pmb R) \]- Stepsize \(0<\mu<\frac{2}{\sum \limits_{k=0}^{M-1}E\{|u(n-k)|^2\}}\)
- \(\pmb M \approx \frac{\mu}{2}\sum \limits_{k=0}^{M-1}E\{|u(n-k)|^2\}\) (\(\mu \labda_i 忽略不计\))
- 平均时间常数：\(\tau_{mse,av}\approx \frac{1}{2\mu \lambda_{av}}\)
- \(\pmb M\)与\(\tau_{mse,av}\)的关系：
这里，\(\tau_{mse,av}\)表示J(n)衰减e−1因子所需的时间。
4. Summary
- 设置过滤器系数的起始值，\(\hat{\pmb w}(0)\)
- 计算误差\(\pmb e^{*}(n)=d(n)-\pmb u^{H}(n)\hat{\pmb w_o}\)
- 更新滤波器系数\(\hat{\pmb w}(n+1)=\hat{\pmb w}(n)+\mu \pmb u(n)[d(n)-\pmb u^{H}(n)\hat{\pmb w_o}]\)
- 重复步骤2和步骤3