查看“︁最小均方滤波器”︁的源代码

{{NoteTA|G1=Communication}}
'''最小均方濾波器'''（Least Mean Square Filter，或LMS Filter）是一類可通過最小化誤差訊號（error signal）之[[均方值]]（mean square）而修正濾波器係數，以模拟所需理想濾波器的[[自適應濾波器]]，其中作為修正依據的誤差訊號為理想參考訊號與實際輸出訊號之差。該種濾波器所用之最小均方法只以當前之訊號誤差值為準進行修正，是一種{{le|隨機梯度下降法|Stochastic gradient descent}}。最小均方法係由[[斯坦福大學]]的[[w:Bernard Widrow|Bernard Widrow]]教授及他的首位博士班學生[[w:Marcian Hoff|Marcian Hoff]]於1960年提出。最小均方濾波器屬於常見的自適應濾波器種類之一。

== 最小均方：問題起源 ==
[[File:Lms filter.svg|444px|LMS filter]]


=== 與最小平方濾波器的異同 ===
因果[[維納濾波]]器（Causal Wiener Filter）的實現在形式上與[[最小平方法]]的實現非常相似，但在[[訊號處理]]這一方面卻有所不同。對於最小平方的實現，令輸入矩陣為<math>
\scriptstyle\mathbf{X}</math>，輸出矩陣為<math>\scriptstyle\mathbf{y} </math>，有：

<math>
\boldsymbol{\hat\beta} = (\mathbf{X} ^\mathbf{T}\mathbf{X})^{-1}\mathbf{X}^{\mathbf{T}}\boldsymbol y .
</math>

而有限脈衝響應（Finite Impulse Response）的最小均方濾波器卻類似Wiener濾波器，只是前者並不依賴計算互相關或自相關函數即可將誤差基準最小化，且其解將會收斂直至與Wiener濾波器的解重疊。大部分的線性可適性濾波問題均可以上圖中的架構進行模擬，即希望盡量準確地確認一未知系統<math>\mathbf{h}(n)</math>，因此通過可適性濾波，僅以可觀測訊號<math>x(n)</math>、<math>d(n)</math>與<math>e(n)</math>產生對<math>\mathbf{h}(n)</math>的估計值<math>\hat{\mathbf{h}}(n)</math>並盡量使其接近<math>\mathbf{h}(n)</math>。上圖中的另幾個訊號<math>y(n)</math>、<math>v(n)</math>與<math>h(n)</math>卻不處於能直接被觀測到的範圍中。

=== 變量之定義 ===
:<math>n</math>：當前輸入序列的樣本數（長度）；
:<math>p</math>：濾波器級數；
:<math> \{\cdot\}^H </math>（[[埃爾米特轉置]]或[[共軛轉置]]）
:<math>
\mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T
</math> 
:<math> 
\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
</math>
:<math> 
y(n) = \mathbf{h}^H(n) \cdot \mathbf{x}(n)
</math>
:<math>
d(n) = y(n) + \nu(n)
</math> 
:<math>\hat{\mathbf{h}}(n)</math>：對<math>h(n)</math>的估計值，可理解為代表在n個觀測週期後對濾波器係數的估計；
:<math> 
e(n) = d(n) - \hat{y}(n) = d(n) - \hat{\mathbf{h}}^H(n) \cdot \mathbf{x}(n) 
</math>


== 最小均方濾波器的基本特點 ==
最小均方濾波器所獲得的廣泛應用主要得益於其兩個特性：易於實作（Simplicity of implementation）與性能穩健（Robust performance）——後者主要得益於最小均方濾波器基本上不受模型影響（Model-independency）。
最小均方濾波器亦與[[梯度下降法]]（Method of steepest descent）不同：後者主要對隨機輸入訊號進行使用確定梯度的遞歸運算。此外，最小均方濾波器的實現亦不需要對相關函數取值進行測量或計算負矩陣。事實上，其他的各種線性可適性濾波演算法均廣泛地以最小均方濾波演算法為基準，以估量自身效能。


== 概覽與主要思想 ==
最小均方濾波器的主旨是逐步進行修正，以逼近最佳的濾波係數；由Wiener–Hopf方程可解得，理想中的最佳濾波係數（所構成之向量）為<math>w_0=(R^{-1}p)</math>；其中R為輸入濾波器的輸入矩陣u(n)的（自）[[相關矩陣]]，p為'''u'''(n)與理想參考訊號d(n)之間的[[互相關]]向量。

基本而言，最小均方濾波演算法作為線性可適性濾波演算法的一種，包括有以下兩個基本步驟：

一、濾波步驟（filtering process）：這一步驟包括了（a）計算一線性濾波器對一輸入訊號的響應輸出與（b）產生上一步中相應輸出和理想相應間的測量誤差值。
二、自適步驟（adaptive process）：這一步驟中，以濾波步驟中得到的測量誤差值為根據，濾波器本身的參數取值將被自動更新（以便在下一個週期中產生的測量誤差值相對減小）。

上述兩個步驟被組合起來，形成一個[[反饋迴圈]]（feedback loop）。
最小均方演算法首先由一組很小的權重係數（常取零）開始，且在迴圈的每一步中找到均方誤差的斜率梯度，依據斜率梯度更新濾波器的權重係數。均方誤差的斜率梯度為正值即說明若保持現有的濾波器權重係數，誤差將在未來的迴圈中持續向正向增大——因此需要減小權重係數。同樣地，若均方誤差的斜率梯度為負值，就需要增大權重係數。因此，基本的權重係數遞歸方程為：

<math> W_{n+1} = W_n - \mu\nabla \varepsilon [n] </math>，

其中<math> \varepsilon </math>代表了均方誤差之值，其係數之前的負號說明需要向斜率梯度的反方向調整濾波器係數。
上述的均方誤差作為以濾波器係數為自變量的函數，具有二次函數的形式；這說明僅存在一個極值能使均方誤差值最小，而這正對應了最佳的濾波器係數。因此，最小均方演算法可以通過調整均方誤差-濾波器係數平面上的曲線位置，來逐步迫近最適的濾波器係數取值。

=== 演算法之實現 ===
對於<math>order=p</math>的情形，可適性最小均方濾波器的演算法實現如下所示：

{| 
| 涉及參數之定義: || <math>p=</math> 濾波器的階數  
|- 
|  || <math>\mu=</math> 步長  
|-
|初始化: || <math>\hat{\mathbf{h}}(0)=\operatorname{zeros}(p)</math>
|-
|運算迴圈: || For <math>n=0,1,2,... </math>
|-
|||
<math>\mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T</math>
|-
|||<math> e(n) = d(n)-\hat{\mathbf{h}}^{H}(n)\mathbf{x}(n)</math>
|-
|||<math> \hat{\mathbf{h}}(n+1) = \hat{\mathbf{h}}(n)+\mu\,e^{*}(n)\mathbf{x}(n)</math>
|}

== 收斂效率與穩定性 ==
由於最小均方演算法並不使用準確的期望值，濾波器的權重係數也就不會絕對地達到最佳取值，但是在總體上演算法仍然可以達到收斂——即實際權重係數將與最佳權重係數相比將或大或小，但誤差大小會相當有限。然而若權重係數變動時的方差（或標準差）過大，收斂的方向就可能錯誤。若演算法中的步長未經過謹慎的選擇，上述問題就很可能會發生。

如步長<math> \mu </math>的取值較大，權重係數就會在更新迴圈中更快地向梯度估計值的方向改變，從而使得權重係數在每一次迴圈中的變動值更大——若開始時的梯度值為負，在更新權重後梯度便可能變為正值。亦即在「第二個」時刻，權重係數的值將因為負的梯度值向相反方向劇烈改變；此後，權重係數的值仍將以較大的幅度圍繞最佳取值上下波動。從另一方面來說，若<math> \mu </math>的取值過小，要達成最佳權重係數便會需要過於漫長的收斂時間。因此，演算法的實現需要在兩種極端之間有所權衡與取捨。 

因此，演算法步長<math> \mu </math>應有一上限，如下：
<math> 0<\mu<\frac{2}{\lambda_{\mathrm{max}}} </math>

其中<math>\lambda_{\max}</math>是[[自相关函数|自相關]]矩陣<math> {\mathbf{R}} = E\{{\mathbf{x}}(n){\mathbf{x}^H}(n)\}</math>中的最大特徵值。當上式所述的條件未能達到時，系統將是非穩定的， <math>\hat{h}(n)</math>也不會收斂。
最快收斂速度的達成條件如下：
<math>
\mu=\frac{2}{\lambda_{\mathrm{max}}+\lambda_{\mathrm{min}}},
</math>
其中<math>\lambda_{\min}</math>是R的最小特徵值。
考慮到<math>\mu</math>的值小於等於最佳值，收斂速度將會由<math>\lambda_{\min}</math>決定，其值越大，就會導致收斂速度越快。這就意味著最佳收斂速度可以在當<math>\lambda_{\max}</math>接近<math>\lambda_{\min}</math>時達成，即由<math>{\mathbf{R}}</math>的特徵值擴散度決定可達到的最高收斂速度。

一個[[白雜訊]]訊號的自相關矩陣為<math>{\mathbf{R}}=\sigma^2 {\mathbf{I}}</math>；其中<math>\sigma^2</math>是訊號的方差。在這種情況下所有的特徵值都是相等的，且特徵值擴散度在所有的可能矩陣中為最小。

對於這上述結果的一種常見解釋是正因為如此，最小均方演算法才會對白訊號為輸入的情形收斂更快，而對如帶有低通或高通特性的有色訊號（均值不為零）輸入收斂得更慢。

值得注意的是前面闡述的<math>\mu</math>值上限只在普遍意義上對可適性最小均方濾波器的穩定性存在影響，在單獨的實際情形中，<math>\hat{h}(n)</math>的係數仍然可能增長至至無限大，即濾波器權重係數仍可能發散而無法達到收斂。一個更為實際的上下限條件是 ：
<math>
0<\mu<\frac{2}{\mathrm{tr}\left[{\mathbf{R}}\right]},
</math>
其中<math>\mathrm{tr}[{\mathbf{R}}]</math>表示<math>{\mathbf{R}}</math>的軌跡（trace）。上述上下限條件確保了<math>\hat{h}(n)</math>的係數將不會發散（在實際情況中，由於上述公式在推導過程中所假定的條件過於寬鬆，<math>\mu</math>的值不應選取得過於接近上限）。

== 歸一化最小均方濾波器 ==

對於基本的最小均方演算法來說，其最大的缺陷就是對於輸入<math>x(n)</math>振幅過於敏感。這就使得設計者難以選取能夠確保演算法穩定性的步長<math>\mu</math>取值。因此，可運用歸一化最小均方濾波器——最小均方濾波器的一種變種，來將輸入訊號的功率歸一化，以解決這一問題。下面是對歸一化最小均方演算法的簡述：

{| 
| 參數定義 || <math>p=</math> 濾波器級數
|- 
|  || <math>\mu=</math> 濾波器步長  
|-
|初始化： || <math>\hat{\mathbf{h}}(0)=\operatorname{zeros}(p)</math>
|-
|開始運算： || For <math>n=0,1,2,... </math>
|-
|||
<math>\mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T</math>
|-
|||<math> e(n) = d(n)-\hat{\mathbf{h}}^{H}(n)\mathbf{x}(n)</math>
|-
|||<math> \hat{\mathbf{h}}(n+1) = \hat{\mathbf{h}}(n)+\frac{\mu\,e^{*}(n)\mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)}</math>
|}

=== 最佳步長取值 ===
若不存在干擾訊號<math>v(n)=0</math>，歸一化最小均方演算法可選取的最佳步長值為<math>\mu_{opt}=1</math>，該值不受輸入訊號<math>x(n)</math>與實際響應<math>\mathbf{h}(n)</math>的影響。在存在干擾(<math>v(n) \ne 0</math>)的情形中，最佳步長值則為：
<math>
\mu_{opt}=\frac{E\left[\left|y(n)-\hat{y}(n)\right|^2\right]}{E\left[|e(n)|^2\right]}
</math>

上述結果是在假定訊號<math>v(n)</math>與<math>x(n)</math>互不相關的前提下推導出的，該假設亦在大部分情形下符合現實。推導過程請參見[https://en.wikipedia.org/wiki/Least_mean_squares_filter#Convergence_and_stability_in_the_mean] {{Wayback|url=https://en.wikipedia.org/wiki/Least_mean_squares_filter#Convergence_and_stability_in_the_mean |date=20210225034141 }}。

==相關條目==
* [[遞迴最小平方濾波器]]
* 有關和最小均方滤波器相關的統計技巧，可以參考[[最小二乘法]]
<!--* {{link-en||Similarities between Wiener and LMS|Similarities between Wiener and LMS}}
* {{link-en||Multidelay block frequency domain adaptive filter|Multidelay block frequency domain adaptive filter}}-->
*{{link-en|迫零均衡器|Zero-forcing equalizer}}
*{{link-en|核自適應濾波器|Kernel adaptive filter}}
* [[匹配濾波器]]
* [[维纳滤波]]

==參考文獻==
*[http://onlinelibrary.wiley.com/doi/10.1002/0471461288.fmatter/pdf Least-Mean-Square Adaptive Filters] {{Wayback|url=http://onlinelibrary.wiley.com/doi/10.1002/0471461288.fmatter/pdf |date=20180213034800 }}
*[http://access.ee.ntu.edu.tw/course/VLSI_SP_89second/student/Final_Project/R89921153_report.PDF LMS Adaptive filters] {{Wayback|url=http://access.ee.ntu.edu.tw/course/VLSI_SP_89second/student/Final_Project/R89921153_report.PDF |date=20151123054854 }}
*[http://www.ece.umd.edu/~ravig/Courses_files/AdaptiveEqualizationLMS_ENEE634.pdf Adaptive Equalization Techniques using  Least Mean Square (LMS) algorithm] {{Wayback|url=http://www.ece.umd.edu/~ravig/Courses_files/AdaptiveEqualizationLMS_ENEE634.pdf |date=20140302161848 }}
* Monson H. Hayes: ''Statistical Digital Signal Processing and Modeling,'' Wiley, 1996, ISBN 0-471-59431-8
* Simon Haykin: ''Adaptive Filter Theory,'' Prentice Hall, 2002, ISBN 0-13-048434-2
* Simon S. Haykin, Bernard Widrow (Editor): ''Least-Mean-Square Adaptive Filters,'' Wiley, 2003, ISBN 0-471-21570-8
* Bernard Widrow, Samuel D. Stearns: ''Adaptive Signal Processing,'' Prentice Hall, 1985, ISBN 0-13-004029-0
* Weifeng Liu, Jose Principe and Simon Haykin: ''Kernel Adaptive Filtering: A Comprehensive Introduction,'' John Wiley, 2010, ISBN 0-470-44753-2
* Paulo S.R. Diniz: ''Adaptive Filtering: Algorithms and Practical Implementation,'' Kluwer Academic Publishers, 1997, ISBN 0-7923-9912-9

[[Category:数字信号处理]]
[[Category:滤波器理论]]