最小二乘法及其應(yīng)用

最小二乘法及其應(yīng)用第一頁，共七十六頁，編輯于2023年，星期三最小二乘法是求解最優(yōu)化問題的一種有效而方便的方法。信號處理中有許多問題可歸結(jié)為最優(yōu)化問題，因此最小二乘法是信號處理的重要工具之一。希爾伯特空間中線性逼近問題的求解方法稱為最小二乘法。通常它有三種不同的表現(xiàn)形式：投影法、求導(dǎo)法和配方法。下面來分別說明。3-1最小二乘法的三種形式第二頁，共七十六頁，編輯于2023年，星期三設(shè)X為希爾伯特空間，為X中一組歸一化正交元素，x為X中的某一元素。在子空間中求一元素m。使得（3-1-1）由于M中元素可表為的線性組合，問題轉(zhuǎn)化成為求，使得（3-1-2）第三頁，共七十六頁，編輯于2023年，星期三第二章中的投影定理指出了最優(yōu)系數(shù)應(yīng)滿足（3-1-3）由此即得。也就是說，當(dāng)且僅當(dāng)取為x關(guān)于歸一化正交系的傅立葉系數(shù)時，式(3-1-2)成立。（3-1-4）第四頁，共七十六頁，編輯于2023年，星期三這種求解方法稱為投影法，它是最小二乘法的第一種表現(xiàn)形式。第二種方法是求導(dǎo)法，仍以上面的問題為例來說明。記泛函為了能用求導(dǎo)法求此泛函的極小值，將它表為第五頁，共七十六頁，編輯于2023年，星期三其中。于是最優(yōu)的應(yīng)滿足即下面再用第三種方法即配方法來求解：（3-1-5）第六頁，共七十六頁，編輯于2023年，星期三以上三種方法都稱為最小二乘法。在實際應(yīng)用中，他們各有各的優(yōu)勢和缺陷，我們并不能通過簡單的比較來說明他們誰優(yōu)誰劣，因為衡量一種方法好壞的標(biāo)準(zhǔn)是多方面的。因此，在不同的場合根據(jù)不同的需要和可能，靈活選擇和使用合適的方法，是掌握最小二乘法的關(guān)鍵。第七頁，共七十六頁，編輯于2023年，星期三利用令導(dǎo)數(shù)等于零來求函數(shù)的極值是一種方便的方法。但是對于多元函數(shù)，有時由于變元太多而使表達式相當(dāng)繁復(fù)，為此，本節(jié)介紹用向量-矩陣的形式來簡化求導(dǎo)過程。下面舉例個例子來具體說明。例3-2-1

求矛盾方程組Ax=b的最小二乘解（可參閱第二章的相關(guān)例題）3-2向量-矩陣求導(dǎo)及配方法第八頁，共七十六頁，編輯于2023年，星期三解：求Ax=b的最小二乘解就是求的極小點。由于下面先給出兩個需要用到的向量求導(dǎo)公式：（3-2-1）（3-2-2）當(dāng)A不時對稱陣時，式（3-2-10）應(yīng)該為（3-2-3）第九頁，共七十六頁，編輯于2023年，星期三利用式（3-2-1）和（3-2-2）可以立即得到（3-2-4）這就是書中例2-4-1中所得到的法方程若使用配方法，則有：第十頁，共七十六頁，編輯于2023年，星期三可以看出，本例中介紹的兩個向量求導(dǎo)公式中，提到了對于向量x求導(dǎo)的梯度算符,我們還可以引入對矩陣求導(dǎo)的梯度算符

：（3-2-5）第十一頁，共七十六頁，編輯于2023年，星期三需要說明的是，算符只有作用在關(guān)于的標(biāo)量函數(shù)上才有意義。例如對于二次型由于，故（3-2-6）（3-2-7）在課本中，給出了一些常用的向量-矩陣求導(dǎo)公式，在實際應(yīng)用中可供大家查閱。第十二頁，共七十六頁，編輯于2023年，星期三設(shè)有如圖3-3-1所示的系統(tǒng)T。當(dāng)輸入n個數(shù)據(jù)時，輸出為y，且有下列線性關(guān)系：3-3應(yīng)用舉例3-3-1系統(tǒng)辨識（3-3-1）其中為未知，需要通過對輸入輸出的觀測值來確定這組參數(shù)。第十三頁，共七十六頁，編輯于2023年，星期三現(xiàn)設(shè)進行了m次觀測，觀測值為和圖3-3-1多輸入單輸出系統(tǒng)則問題成為求使之滿足（3-3-2）第十四頁，共七十六頁，編輯于2023年，星期三若記及則方程（3-3-2）成為（3-3-3）當(dāng)方程（3-3-3）無解時，問題就轉(zhuǎn)化為求矛盾方程組的最小二乘解?？梢缘玫剑?-3-4）第十五頁，共七十六頁，編輯于2023年，星期三進而考察多輸入多輸出的情形。關(guān)系式為其中（3-3-6）（3-3-5）現(xiàn)設(shè)輸入和輸出的第k次觀測值分別是

第十六頁，共七十六頁，編輯于2023年，星期三則系統(tǒng)的辨識問題就是求A使之滿足（3-3-8）（3-3-7）其中Y為矩陣，X為矩陣。當(dāng)上述方程無解時，問題就轉(zhuǎn)化成為求A使下列非負定矩陣達到極小：（3-3-9）第十七頁，共七十六頁，編輯于2023年，星期三問題（3-3-9）可以用配方法來求解：（3-3-10）其中假定可逆。這個問題不能用求導(dǎo)法來求解，因為目標(biāo)函數(shù)J（A）不是標(biāo)量而是矩陣。要用求導(dǎo)法來求解該問題，需要引入矩陣范數(shù)的概念。第十八頁，共七十六頁，編輯于2023年，星期三矩陣的范數(shù)定義為（3-3-11）事實上，可以把式（3-3-11）理解成向量

的范數(shù)。這樣，我們可以把多輸入多輸出線性系統(tǒng)的辨識問題敘述為求矩陣A，使得（3-3-12）第十九頁，共七十六頁，編輯于2023年，星期三式（3-3-12）的形式與（3-3-9）類似，但應(yīng)注意在此處是標(biāo)量函數(shù)。她可以完全類似于式（3-3-10）那樣來配方而求解，也可體用求導(dǎo)法來求解。由于（3-3-13）利用課本中表3-2-2中的公式5和7，得到（3-3-14）第二十頁，共七十六頁，編輯于2023年，星期三數(shù)據(jù)壓縮是指在傳輸或存儲信號時對信號數(shù)據(jù)量進行壓縮。實際中的信號往往都是維數(shù)很高的隨機數(shù)據(jù)向量。各種數(shù)據(jù)間的相關(guān)性也很大，簡單的隨意壓縮會導(dǎo)致數(shù)據(jù)嚴重失真。按照最優(yōu)化原則設(shè)計的數(shù)據(jù)壓縮技術(shù)可以解決通訊和數(shù)據(jù)傳輸系統(tǒng)的信道容量不足和計算機存儲容量不足的問題，因而是一種從容量方面提高系統(tǒng)使用效率的重要技術(shù)。3-3-2數(shù)據(jù)壓縮第二十一頁，共七十六頁，編輯于2023年，星期三下面向大家介紹一種有效的數(shù)據(jù)壓縮方法。其思想是對信號作正交變換，根據(jù)失真最小的原則在變幻域進行壓縮。其框圖如下所示。設(shè)為n維隨機變量，n的值很大。經(jīng)過正交T變換后，得到變幻域的n維向量（3-3-15）第二十二頁，共七十六頁，編輯于2023年，星期三其中變幻矩陣T的列向量為滿足（3-3-16）（3-3-17）現(xiàn)在對數(shù)據(jù)進行壓縮，即保留y的m個分量其余的n-m個分量用預(yù)先選定的常數(shù)代，替，得到一個新的向量，再由通過逆變換得到x的估計第二十三頁，共七十六頁，編輯于2023年，星期三我們的問題是：如何選取變幻矩陣T和常數(shù)，y的那些分量被壓縮掉，才能使最接近x，即均方誤差最小：（3-3-18）下面來注意解決這些問題。由式（3-3-15）和式（3-3-16）可知第二十四頁，共七十六頁，編輯于2023年，星期三由此式可知，要使達到最小，應(yīng)有（3-3-19）（3-3-20）即這就使常數(shù)應(yīng)選取的數(shù)值。由此式得（3-3-21）第二十五頁，共七十六頁，編輯于2023年，星期三其中是隨機向量x的協(xié)方差陣。由式（3-3-22）可考慮如何選擇T的行向量使達到極小。注意到是歸一化正交的。為求在條件下的極值，令代入式（3-3-19），得到（3-3-22）第二十六頁，共七十六頁，編輯于2023年，星期三這表明是協(xié)方差陣的特征值，而是相應(yīng)的特征向量，很顯然,T取成x的卡享南-洛厄維變換是最合理的，此時的最小均方誤差為則由式（3-3-22），有于是（3-3-23）第二十七頁，共七十六頁，編輯于2023年，星期三根據(jù)此式，我們可先把非負定矩陣的特征值按大小次序排列，然后根據(jù)實際問題對均方誤差的要求選擇m，使得小于指定的誤差（即選擇滿足此條件的最小的m），把n-m個較小的特征值所對應(yīng)的換成。（3-3-24）第二十八頁，共七十六頁，編輯于2023年，星期三特別地，如果取E{x}=0(通常的信號經(jīng)過預(yù)處理后可滿足此條件），則取，至此，前面提出的問題便全部解決。在上述解法中，卡享南-洛厄維變換被選用并不是偶然的，因為這種變換消除了原始信號x的諸分量間的相關(guān)性，從而使數(shù)據(jù)壓縮能遵循均方誤差最小的準(zhǔn)則實施。上述數(shù)據(jù)壓縮方法告訴我們應(yīng)該壓縮掉y中那些方差大的分量，這稱為數(shù)據(jù)壓縮的方差準(zhǔn)則。第二十九頁，共七十六頁，編輯于2023年，星期三由于卡享南-洛厄維變換需要知道矩陣的特征值和特征向量，其計算量非常大，因此在實際應(yīng)用中通常都使用固定程式的有限正交變換。盡管這些變換不是最佳的，但實踐和理論表明它們也都能在較大程度上消除隨機向量諸分量間的相關(guān)性，而且由于它們具有快速算法，因而是實用的?？ㄏ砟?洛厄維變換是理論上的最佳變換，它可作為理論研究的工具，也可用來衡量其他變換優(yōu)劣的標(biāo)準(zhǔn)。第三十頁，共七十六頁，編輯于2023年，星期三設(shè)有隨機向量，它含有真實信號及噪聲，如下述模型所示：3-3-3維納濾波（3-3-25）其中H為已知矩陣，它也表示一種干擾?，F(xiàn)在將x輸入到一個如下圖所示的系統(tǒng)第三十一頁，共七十六頁，編輯于2023年，星期三要使相應(yīng)的輸出成為真實信號s的最佳估計，即均方差最小：求濾波器矩陣A，其中T是正交變換。（3-3-26）這個問題稱為維納(Wiener)濾波器設(shè)計問題。正交變換T的作用是把濾波問題轉(zhuǎn)化到變換域處理。由系統(tǒng)框圖知于是（3-3-27）第三十二頁，共七十六頁，編輯于2023年，星期三利用表3-2-2中的公式2和3，得到因此最佳濾波器矩陣A應(yīng)滿足（3-3-28）當(dāng)可逆時（3-3-29）第三十三頁，共七十六頁，編輯于2023年，星期三設(shè)信號與噪聲的均值為零：E{x}=0；E{v}=0；真實信號與噪聲不相關(guān)：；并記真實信號s與噪聲v的自相關(guān)矩陣為則第三十四頁，共七十六頁，編輯于2023年，星期三于是式（3-3-29）便成為這就是維納濾波器矩陣。（3-3-30）下面再用配方法來解決此問題。為此，用矩陣的跡來表示是有效的。第三十五頁，共七十六頁，編輯于2023年，星期三又一次得到了式（3-3-29），而且得到了最小誤差：（3-3-31）第三十六頁，共七十六頁，編輯于2023年，星期三注意到的表達式中不出現(xiàn)正交變換T，由此可知維納濾波與正交變換的選取無關(guān)。于是由式（3-3-30）聯(lián)想到若取T使得矩陣A呈對角型，則將使矩陣乘向量的計算量由降低到n。這種想法是有實際意義的。如在圖象處理中，（3-3-25）是一個典型的失真模型。若選T為傅立葉變換，則A便成為對角型矩陣。這樣的維納濾波器稱為對角線維納濾波器。第三十七頁，共七十六頁，編輯于2023年，星期三模式識別問題是設(shè)計一種分類器，使之能自動地將類別未知的對象進行歸類。需要歸類的對象稱為模式。本節(jié)來介紹模式分類器的一種設(shè)計方法。一個需要識別的對象可以用向量來表示。下面的分類器的設(shè)計是對壓縮后的模式向量進行的。

3-3-4模式識別第三十八頁，共七十六頁，編輯于2023年，星期三分類器的設(shè)計是通過下列方式（稱為訓(xùn)練或?qū)W習(xí)）來完成的。被識別的對象共有k類：。首先選取一些類別已知的模式向量（稱為訓(xùn)練模式）求屬于同一類的模式向量的平均模式：那么，對于任一類別未知的模式向量x，判決準(zhǔn)則是第三十九頁，共七十六頁，編輯于2023年，星期三稱為判決函數(shù)。根據(jù)判決準(zhǔn)則(3-3-33)實現(xiàn)分類的分類器稱為最小距離分類器。由于實際問題中屬同一類的模式往往分布的很分散和凌亂，直接采用這種線性函數(shù)作為判決界容易造成誤判。（3-3-32）由于若記則判決準(zhǔn)則等價于若（3-3-33）第四十頁，共七十六頁，編輯于2023年，星期三為了克服上述缺點，可采用如下所述的最小二乘映射技術(shù)。取定k個向量。希望存在一個線性變換A（矩陣）把屬于同一類的訓(xùn)練模式，都變?yōu)椋河谑菃栴}轉(zhuǎn)化為求矩陣A，它能夠把都變到的附近，越近越好。記第四十一頁，共七十六頁，編輯于2023年，星期三則矩陣A關(guān)于第i類訓(xùn)練模式的平均偏差為總偏差為于是A的選取應(yīng)使，故A應(yīng)滿足（3-3-34）第四十二頁，共七十六頁，編輯于2023年，星期三因此（3-3-35）求出A以后，對于任一類別未知的模式x，可如下述進行判決歸類：（3-3-36）第四十三頁，共七十六頁，編輯于2023年，星期三這種分類判決的實現(xiàn)稱為最小二乘最小距離分類器。它的主要思想是利用最小二乘映射把屬于同一類的訓(xùn)練模式盡可能地聚集在一起。從而克服了最小距離分類器的缺點。在這里所有都是可以任意選擇的，可以通過選擇特殊的，簡化判決函數(shù)的獲得過程。在課本中就給出了一種簡化方法。其中取為K維單位向量第四十四頁，共七十六頁，編輯于2023年，星期三可以看出，最小二乘最小距離分類器的判決函數(shù)僅依賴于最優(yōu)矩陣A。一旦求出A，立即就可實現(xiàn)這種分類器。在實際應(yīng)用中此方法的設(shè)計技巧是選取合適的判決向量。第四十五頁，共七十六頁，編輯于2023年，星期三設(shè)X為希爾伯特空間，是X中的一組線性無關(guān)元（不一定正交）。對某一，求，使得3-4法方程（3-4-1）換言之，求系數(shù)，使得（3-4-2）第四十六頁，共七十六頁，編輯于2023年，星期三這就是最優(yōu)系數(shù)應(yīng)滿足的方程，它是一個線性代數(shù)方程組。具體寫出來是利用投影定理，應(yīng)滿足即（3-4-3）（3-4-4）第四十七頁，共七十六頁，編輯于2023年，星期三矩陣Y就是元素組的格拉姆矩陣。它是非負定的，且當(dāng)線性無關(guān)時Y可逆。方程（3-4-4）稱為Wiener-Hopf方程。一般地，一個最優(yōu)化解應(yīng)滿足的方程稱為該最優(yōu)化問題的法方程。因此Wiener-Hopf方程是最優(yōu)化問題（3-4-2）的法方程。或?qū)懗删仃?向量形簡潔形式：（3-4-5）第四十八頁，共七十六頁，編輯于2023年，星期三現(xiàn)設(shè)是最優(yōu)系數(shù)，即滿足（3-4-3），這時的最小誤差為：（3-4-6）把這個方程合并到方程組（3-4-4）中去，成為第四十九頁，共七十六頁，編輯于2023年，星期三其中detG表示矩陣G的行列式。用克萊姆法則即可求得最小誤差為（3-4-7）第五十頁，共七十六頁，編輯于2023年，星期三特別地，如果為歸一化正交系，則為單位矩陣，式（3-4-4）成為，式（3-4-7）成為上述問題利用求導(dǎo)法也可以解。由式（3-4-2），有第五十一頁，共七十六頁，編輯于2023年，星期三利用求導(dǎo)公式，應(yīng)滿足此即式（3-4-5）若用配方法，則有易知它與式（3-4-6）是等價的。第五十二頁，共七十六頁，編輯于2023年，星期三下面，我們再來討論一個隨機序列的預(yù)測問題，來進一步說明法方程的意義考慮二階矩有限的希爾伯特空間中的序列。記子空間（3-4-8）現(xiàn)在的問題是：用中的元素來估計，使得均方誤差最小。也就是求系數(shù)使第五十三頁，共七十六頁，編輯于2023年，星期三這個問題稱為隨機序列的預(yù)測問題。（3-4-9）根據(jù)投影定理，應(yīng)是在子空間中的投影，即滿足（3-4-10）根據(jù)空間中的正交性定義，上式即為這就是最佳預(yù)測的法方程。第五十四頁，共七十六頁，編輯于2023年，星期三其中是該平穩(wěn)序列的自相關(guān)。它滿足。（3-4-11）又稱為關(guān)于平穩(wěn)序列預(yù)測問題的Yule-Walker方程。其分量形式為如果隨機序列是平穩(wěn)的，則式（3-4-10）成為（3-4-11）第五十五頁，共七十六頁，編輯于2023年，星期三（3-4-12）相應(yīng)的預(yù)測誤差為第五十六頁，共七十六頁，編輯于2023年，星期三把這個方程合并到方程（3-4-12）中去，可以寫成記其系數(shù)矩陣為。利用克萊姆法則可得（3-4-13）（3-4-14）第五十七頁，共七十六頁，編輯于2023年，星期三對于給定的序列x和y，求一個離散時不變系統(tǒng)h，使得當(dāng)輸入為x時相應(yīng)的輸出恰為y。這個問題的數(shù)學(xué)描述是：給定x和y，求h使得3-4最小二乘濾波（3-5-1）一般來說，這個問題不一定是有解的，因此將問題改成：已知x，y，求h使得（3-5-2）第五十八頁，共七十六頁，編輯于2023年，星期三我們假定x，y，h都是因果的，能量有限的于是x，y，h，式（3-5-2）中的范數(shù)是意義下的范數(shù)。這個問題稱為最小二乘濾波問題。我們先用求導(dǎo)法來解。由知目標(biāo)函數(shù)為第五十九頁，共七十六頁，編輯于2023年，星期三于是最優(yōu)解應(yīng)滿足即若記它們分別稱為x的自相關(guān)序列和x與y的互相關(guān)序列。則式（3-5-3）成為（3-5-3）第六十頁，共七十六頁，編輯于2023年，星期三這就是最小二乘濾波的法方程。下面再利用投影法來求解最小二乘濾波問題。在空間中討論。對于引入移位算子T：（3-5-4）則第六十一頁，共七十六頁，編輯于2023年，星期三這樣，就把卷積表示成中一組元素的線性組合，這是應(yīng)用投影法的關(guān)鍵。記子空間。問題便轉(zhuǎn)化為求，使，也就是求y在M中的投影。根據(jù)投影定理，應(yīng)滿足即（3-5-5）第六十二頁，共七十六頁，編輯于2023年，星期三因此式（3-5-5）就是法方程（3-5-4）。接下來我們介紹兩個實際應(yīng)用的例子。其中同理第六十三頁，共七十六頁，編輯于2023年，星期三仍然考慮因果序列。設(shè)是原始聲音信號序列。由于回聲的影響，在n時刻接收到的信號除了以外還疊加有時刻之前的回音：例3-5-1回聲干擾與最小二乘逆濾波（3-5-6）其中r是衰減因子，?，F(xiàn)在要求設(shè)計一個系統(tǒng)能夠消除這種回聲干擾，即（3-5-7）第六十四頁，共七十六頁，編輯于2023年，星期三我們把式（3-5-6）寫成卷積形式：其中為（3-5-8）將式（3-5-8）代入式（3-5-7）得這等價于（3-5-9）其中是單位脈沖序列。第六十五頁，共七十六頁，編輯于2023年，星期三于是問題轉(zhuǎn)化成給定x，要求設(shè)計一個系統(tǒng)h，使之滿足式（3-5-9）。這是一個特殊的最小二乘濾波問題，稱為最小二乘逆濾波。利用法方程（3-5-4），取，即得（3-5-10）而根據(jù)序列x的因果性，有第六十六頁，共七十六頁，編輯于2023年，星期三如果把方程（3-5-10）中的m截斷到N為止，則成為（3-5-11）這就是最小二乘逆濾波的“N截斷”法方程，它適合于實際計算。第六十七頁，共七十六頁，編輯于2023年，星期三所謂預(yù)測就是由的值預(yù)測的值，其中s為某個自然數(shù)。預(yù)測濾波問題就是要求設(shè)計一個系統(tǒng)h，使得當(dāng)輸入為時相應(yīng)的輸出為。這也是一種特殊的最小二乘濾波。根據(jù)法方程（3-5-4），只需計算：例3-5-2最小二乘預(yù)測